计算机导论精品PPT-第五章-算法与程序设计

电子与信息工程学院计算机导论5算法与程序设计电子与信息工程学院算法与程序设计计算机导论电子与信息工程学院算法与程序设计计算机导论5.1计算机问题求解5.2算法分析与设计5.3程序设计电子与信息工程学院算法与程序设计计算机导论电子与信息工程学院算法与程序设计计算机导论GeorgePolya:《HowtoSolveIt?》Understandingtheproblem:“Whatyouaregivenandwhatyouaresupposedtofigureout”Devisingaplan:“Howwillyouattacktheproblem?”Carryingouttheplan:Solvetheproblem.Lookingback:checktheresult,and…电子与信息工程学院算法与程序设计计算机导论波利亚（GeorgePolya，1887-1985），美籍匈牙利数学家。生于布达佩斯，卒于美国。青年时期曾在布达佩斯、维也纳、巴黎等地攻读数学、物理和哲学，获博士学位。1914年在瑞士苏黎世工业大学任教，1938年任数理学院院长。1940年移居美国，历任布朗大学、斯坦福大学教授。1963年获美国数学会功勋奖。他是法国科学院、美国全国科院和匈牙利科学院的院士。曾著有《怎样解题》、《数学的发现》、《数学与猜想》等，它们被译成多种文字，广为流传。电子与信息工程学院算法与程序设计计算机导论5.1计算机问题求解计算机求解问题的步骤（1）问题分析（2）数学模型的建立（3）算法设计与选择（4）算法表示电子与信息工程学院算法与程序设计计算机导论（5）算法分析（6）算法实现（7）程序调试（8）结果整理文档编制电子与信息工程学院算法与程序设计计算机导论一般计算机面对现实问题是无能为力的，需要人类对问题抽象化、形式化后才能机械地执行，学习算法设计和程序设计的重点就是把人类找到的求解问题的方法、步骤以过程化、形式化、机械化的形式表示出来，以便让计算机执行。电子与信息工程学院算法与程序设计计算机导论人们要想让计算机完成某项工作，从简单的统计学生成绩到复杂的宇宙飞船自动控制系统，首先要明确给出工作步骤，然后用某种计算机能理解的方式告诉计算机。这就是计算机领域两项非常重要的工作：算法设计和程序设计，算法设计就是给出完成任务的工作步骤，程序设计就是用计算机能理解的某种语言把算法改写成程序。电子与信息工程学院算法与程序设计计算机导论要想充分发挥计算机的作用，就必须针对要完成的工作，设计出高质量的算法和相应的程序，所以算法设计和程序设计能力是计算机专业学生必备的基本能力之一。电子与信息工程学院算法与程序设计计算机导论电子与信息工程学院算法与程序设计计算机导论电子与信息工程学院算法与程序设计计算机导论5.2算法分析与设计5.2.1算法的概念算法（algorithm）是指在解决问题时，按照某种机械步骤一定可以得到问题结果（有解时给出问题的解，无解时给出无解的结论）的处理过程。算法（algorithm）就是为了解决一个问题而采取的方法和步骤。电子与信息工程学院算法与程序设计计算机导论5.2.2算法的基本性质目的性—算法有明确的目的，算法能完成赋予它的功能。分步性—算法为完成其复杂的功能，由一系列计算机可执行的步骤组成。有序性—算法的步骤是有序的，不可以随意改变算法步骤的执行顺序。有限性—算法是有限的指令序列，算法所包含的步骤是有限的。操作性—有意义的算法总是对某些对象进行操作，使其改变状态，完成其功能。电子与信息工程学院算法与程序设计计算机导论5.2.3算法的基本特征并不是所有问题都有解决它们的方法，也不是所有人类解决问题的方法都能设计出相应的算法。有穷性确定性有效性算法有零个或多个输入算法有一个或多个输出电子与信息工程学院算法与程序设计计算机导论5.2.4算法的评价标准算法的正确性算法的时间复杂度算法的空间复杂度算法的可理解性电子与信息工程学院算法与程序设计计算机导论5.2.5算法描述自然语言流程图盒图PAD图伪代码程序设计语言电子与信息工程学院算法与程序设计计算机导论（1）自然语言自然语言是人们日常所用的语言，使用这些语言不用专门训练，所描述的算法通俗易懂。（2）流程图流程图是描述算法的常用工具，采用ANSI规定的一组图形符号来表示算法的图形，可方便的表示顺序、选择和循环结构。电子与信息工程学院算法与程序设计计算机导论流程图的基本组件起止框输入输出框判断框处理框流程线电子与信息工程学院算法与程序设计计算机导论顺序结构AB电子与信息工程学院算法与程序设计计算机导论ABPTFAPFT选择结构电子与信息工程学院算法与程序设计计算机导论循环结构APTAPFT电子与信息工程学院算法与程序设计计算机导论（3）盒图（N_S图）美国学者I.Nassi和B.Shneiderman提出的一种在流程图中完全去掉流程线，全部算法写在一个矩形阵内，在框内还可以包含其他框的流程图形式。电子与信息工程学院算法与程序设计计算机导论AB顺序结构YPNAB选择结构电子与信息工程学院算法与程序设计计算机导论当P成立AAP成立循环结构电子与信息工程学院算法与程序设计计算机导论（4）PAD图（5）伪代码介于自然语言和计算机语言之间的文字和符号来描述算法。（6）程序设计语言电子与信息工程学院算法与程序设计计算机导论5.2.6算法举例（1）求5！数学模型：5！=1×2×3×4×5电子与信息工程学院算法与程序设计计算机导论步骤1:先求1*2,得到2步骤2:将结果2再乘以3,得到结果6步骤3:将6再乘以4,得24步骤4:将24再乘以5,得120。这就是最后的结果。S1:使p=1S2:使i=1S3:使p*i,乘积放在变量p中，（p*i=p)S4:使i的值加1,（i+1=i)S5:如果i不大于5，返回重新执行步骤S3以及其后的S4和S5；否则算法结束。算法分析与设计：电子与信息工程学院算法与程序设计计算机导论流程图：#includestdio.hintmain(){inti,p;i=1;p=1;while(i=5){p=p*i;i=i+1;}printf(“%d\n”,p);return0;}程序：开始i=5P=P*ii=i+1输出P结束TF电子与信息工程学院算法与程序设计计算机导论5.2.6算法举例（2）小明数了数圈在一起的鸡和兔共有30个头，他又数了数脚有90个，那么究竟在这个圈里鸡和兔各有多少只？数学模型：设鸡和兔的总头数为T，总脚数为J，x为鸡数，y为兔数列出方程式：电子与信息工程学院算法与程序设计计算机导论算法分析与设计：设X为鸡数，Y为兔数，则Y=30-X，2*X+4*Y=90，令X为循环变量，初值为1，步长为1，共循环30次，在循环体内判断2*X+4*Y=90是否成立，成立则输出X和Y的值，即为满足条件的鸡和兔的数量。电子与信息工程学院算法与程序设计计算机导论N_S图：程序：#includestdio.hintmain(){intx,y;x=1;while(i=30){y=30-x;if(x*2+4*y==90)printf(鸡:%d，兔:%d\n,x,y);x=x+1;}return0;}X=1电子与信息工程学院算法与程序设计计算机导论5.3程序设计5.3.1程序设计原则与过程（1）原则自顶向下逐步细化模块化设计限制使用GOTO语句电子与信息工程学院算法与程序设计计算机导论（2）步骤分析问题设计算法编写程序对源程序进行编辑、编译和连接运行程序，分析结果编写程序文档电子与信息工程学院算法与程序设计计算机导论5.3.2程序的基本结构顺序结构选择结构循环结构电子与信息工程学院算法与程序设计计算机导论5.3.3程序的执行方式解释方式每执行一句就翻译一句，即边执行边解释。编译方式在程序第一次执行前先将其翻译成二进制程序，然后每次执行的时候就可以直接执行这个翻译好的二进制程序了。电子与信息工程学院算法与程序设计计算机导论5.3.4程序设计语言机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言学习语言是设计程序的基础电子与信息工程学院算法与程序设计计算机导论（1）机器语言由二进制编码指令构成的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。0001010101101100//把地址为01101100的内存单元中的数装入0101号寄存器0001011001101101//把地址为01101101的内存单元中的数装入0110号寄存器0101000001010110//把01101100和01101101中的数相加,结果存入0000号寄存器0011000001101110//把0000号寄存器中的数存入地址为01101110的内存单元中电子与信息工程学院算法与程序设计计算机导论（2）汇编语言由助记符指令构成的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。MOVR5,X//把内存单元X中的数装入R5寄存器。ADDR5,Y//把R5中的数与Y单元中的数相加，结果存入R5。MOVZ,R5//把R5中的数存入Z单元中。电子与信息工程学院算法与程序设计计算机导论（3）高级语言由自然语言和数学公式表示的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。Z=X+Y//把内存单元X中的数与Y中的数相加，结果存入Z单元电子与信息工程学院算法与程序设计计算机导论常用高级语言FORTRAN语言•FORTRAN是FORmulaTRANslator（公式翻译器）的缩写。•主要用于复杂的科学计算领域。ALGOL语言•ALGOL是ALGOrithmLanguage（算法语言）的缩写。•主要用于数学与科学计算。电子与信息工程学院算法与程序设计计算机导论COBOL语言•COBOL是COmmonBusiness-OrientedLanguage（面向商业的通用语言）的缩写。•主要用于企业管理和事务处理。BASIC语言•BASIC是Beginner’sAll-purposeSymbolicInstructionCode（初学者通用符号指令码）的缩写。•主要用于初学者和较小规模的程序开发。电子与信息工程学院算法与程序设计计算机导论（4）结构化程序设计语言早期程序设计方法的不足•注重功能的实现/注重内存的节省/注重执行效率的提高。•不注重程序结构的清晰性。•不注重程序的可理解性和可修改性。结构化程序设计语言的特点•注重程序结构的清晰性。•注重程序的可理解性和可修改性。•采用模块化程序设计方法。电子与信息工程学院算法与程序设计计算机导论常用结构化程序设计语言PASCAL语言•是在ALGOL语言的基础上发展起来的。•以法国著名科学家帕斯卡的名字命名。•严格的语法格式与结构化形式。C语言•是在ALGOL60语言的基础上发展起来的。•兼具低级语言和高级语言的特点。•是最为流行的程序设计语言之一。电子与信息工程学院算法与程序设计计算机导论（5）面向对象程序设计语言结构化程序设计方法的不足•面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。•强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起，当程序复杂度较高时，容易出错，而且错误难以查找和修改。电子与信息工程学院算法与程序设计计算机导论面向对象程序设计语言的特点•将问题分解为对象。•对象将自己的属性和方法封装成一个整体，供程序设计者使用。•对象之间的相互作用则通过消息传递来实现。•使人们对复杂系统的认识过程与程序设计过程尽可能一致。电子与信息工程学院算法与程序设计计算机导论常用面向对象程序设计语言Simula67•发布于1967年，是面向对象语言