《计算机导论精品PPT-第五章算法与程序设计.ppt》由会员分享，可在线阅读，更多相关《计算机导论精品PPT-第五章算法与程序设计.ppt（52页珍藏版）》请在三一办公上搜索。
1、5 算法与程序设计,为什么要用计算机解题？,计算机为什么能解题？,计算机能解什么题？,计算机如何解题？,人类是如何解题的？,George Polya:How to Solve It?Understanding the problem:“What you are given and what you are supposed to figure out”Devising a plan:“How will you attack the problem?”Carrying out the plan:Solve the problem.Looking back:check the result,and
2、,波利亚（George Polya，1887-1985），美籍匈牙利数学家。生于布达佩斯，卒于美国。青年时期曾在布达佩斯、维也纳、巴黎等地攻读数学、物理和哲学，获博士学位。1914年在瑞士苏黎世工业大学任教，1938年任数理学院院长。1940年移居美国，历任布朗大学、斯坦福大学教授。1963年获美国数学会功勋奖。他是法国科学院、美国全国科院和匈牙利科学院的院士。曾著有怎样解题、数学的发现、数学与猜想等，它们被译成多种文字，广为流传。,5.1 计算机问题求解 计算机求解问题的步骤（1）问题分析（2）数学模型的建立（3）算法设计与选择（4）算法表示,（5）算法分析（6）算法实现（7）程序调试（8）
3、结果整理文档编制,计算机求解问题的核心是什么？,为什么？,一般计算机面对现实问题是无能为力的，需要人类对问题抽象化、形式化后才能机械地执行，学习算法设计和程序设计的重点就是把人类找到的求解问题的方法、步骤以过程化、形式化、机械化的形式表示出来，以便让计算机执行。,人们要想让计算机完成某项工作，从简单的统计学生成绩到复杂的宇宙飞船自动控制系统，首先要明确给出工作步骤，然后用某种计算机能理解的方式告诉计算机。这就是计算机领域两项非常重要的工作：算法设计和程序设计，算法设计就是给出完成任务的工作步骤，程序设计就是用计算机能理解的某种语言把算法改写成程序。,要想充分发挥计算机的作用，就必须针对要完成的
4、工作，设计出高质量的算法和相应的程序，所以算法设计和程序设计能力是计算机专业学生必备的基本能力之一。,算法设计是程序设计的高级阶段。,算法是计算机学科中最具有方法论性质的核心概念，被誉为计算机学科的灵魂。,什么 是 算 法？,5.2 算法分析与设计5.2.1 算法的概念 算法（algorithm）是指在解决问题时，按照某种机械步骤一定可以得到问题结果（有解时给出问题的解，无解时给出无解的结论）的处理过程。算法（algorithm）就是为了解决一个问题而采取的方法和步骤。,5.2.2 算法的基本性质 目的性 算法有明确的目的，算法能完成赋予它的功能。分步性 算法为完成其复杂的功能，由一系列计算机
5、可执行的步骤组成。有序性 算法的步骤是有序的，不可以随意改变算法步骤的执行顺序。有限性 算法是有限的指令序列，算法所包含的步骤是有限的。操作性 有意义的算法总是对某些对象进行操作，使其改变状态，完成其功能。,5.2.3 算法的基本特征 并不是所有问题都有解决它们的方法，也不是所有人类解决问题的方法都能设计出相应的算法。有穷性 确定性 有效性 算法有零个或多个输入 算法有一个或多个输出,5.2.4 算法的评价标准 算法的正确性 算法的时间复杂度 算法的空间复杂度 算法的可理解性,5.2.5 算法描述 自然语言 流程图 盒图 PAD图 伪代码 程序设计语言,（1）自然语言 自然语言是人们日常所用的
6、语言，使用这些语言不用专门训练，所描述的算法通俗易懂。（2）流程图 流程图是描述算法的常用工具，采用ANSI规定的一组图形符号来表示算法的图形，可方便的表示顺序、选择和循环结构。,流程图的基本组件,顺序结构,选择结构,循环结构,（3）盒图（N_S图）美国学者I.Nassi 和 B.Shneiderman提出的一种在流程图中完全去掉流程线，全部算法写在一个矩形阵内，在框内还可以包含其他框的流程图形式。,（4）PAD图（5）伪代码 介于自然语言和计算机语言之间的文字和符号来描述算法。（6）程序设计语言,5.2.6 算法举例（1）求 5！,数学模型：5！=12345,步骤1:先求1*2,得到2步骤2
7、:将结果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；否则算法结束。,算法分析与设计：,流程图：,程序：,5.2.6 算法举例（2）小明数了数圈在一起的鸡和兔共有30个头，他又数了数脚有90个，那么究竟在这个圈里鸡和兔各有多少只？,算法分析与设计：设X为鸡数，Y为兔数，则Y=30-X，2*X+4*Y=90，令X为循环变量，初值为1，步长为1，共循环30次，在循环体内
8、判断2*X+4*Y=90是否成立，成立则输出X和Y 的值，即为满足条件的鸡和兔的数量。,N_S图：,程序：,#include int main()int x,y;x=1;while(i=30)y=30-x;if(x*2+4*y=90)printf(鸡:%d，兔:%dn,x,y);x=x+1;return 0;,X=1,5.3 程序设计5.3.1 程序设计原则与过程（1）原则 自顶向下 逐步细化 模块化设计 限制使用GOTO语句,（2）步骤 分析问题 设计算法 编写程序 对源程序进行编辑、编译和连接 运行程序，分析结果 编写程序文档,5.3.2 程序的基本结构 顺序结构 选择结构 循环结构,5.
9、3.3 程序的执行方式 解释方式 每执行一句就翻译一句，即边执行边解释。编译方式 在程序第一次执行前先将其翻译成二进制程序，然后每次执行的时候就可以直接执行这个翻译好的二进制程序了。,5.3.4 程序设计语言 机器语言 汇编语言 高级语言 结构化程序设计语言 面向对象程序设计语言 可视化程序设计语言 人工智能程序设计语言,学习语言是设计程序的基础,（1）机器语言由二进制编码指令构成的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。,（2）汇编语言由助记符指令构成的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。,（3）高级语言由自然语言和数学公式表示的语言。是
10、一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。,常用高级语言 FORTRAN语言FORTRAN是FORmula TRANslator（公式翻译器）的缩写。主要用于复杂的科学计算领域。ALGOL语言ALGOL是ALGOrithm Language（算法语言）的缩写。主要用于数学与科学计算。,COBOL语言 COBOL是COmmon Business-Oriented Language（面向商业的通用语言）的缩写。主要用于企业管理和事务处理。BASIC语言 BASIC是Beginners All-purpose Symbolic Instruction Code（初学者通用符号指令码）
11、的缩写。主要用于初学者和较小规模的程序开发。,（4）结构化程序设计语言早期程序设计方法的不足注重功能的实现/注重内存的节省/注重执行效率的提高。不注重程序结构的清晰性。不注重程序的可理解性和可修改性。结构化程序设计语言的特点 注重程序结构的清晰性。注重程序的可理解性和可修改性。采用模块化程序设计方法。,常用结构化程序设计语言 PASCAL语言 是在ALGOL语言的基础上发展起来的。以法国著名科学家帕斯卡的名字命名。严格的语法格式与结构化形式。C语言 是在ALGOL60语言的基础上发展起来的。兼具低级语言和高级语言的特点。是最为流行的程序设计语言之一。,（5）面向对象程序设计语言 结构化程序设计
12、方法的不足 面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起，当程序复杂度较高时，容易出错，而且错误难以查找和修改。,面向对象程序设计语言的特点 将问题分解为对象。对象将自己的属性和方法封装成一个整体，供程序设计者使用。对象之间的相互作用则通过消息传递来实现。使人们对复杂系统的认识过程与程序设计过程尽可能一致。,常用面向对象程序设计语言 Simula 67 发布于19
13、67年，是面向对象语言的鼻祖。C+发布于1983年，是在C语言的基础上发展起来的。C+是得到广泛应用的一种面向对象语言。目前常用的版本有Visual C+,C#,Visual C+.Net等。Java发布于1995年，适合于网络程序设计。目前得到广泛应用的一种面向对象程序设计语言。,（6）可视化程序设计语言以图形化的编程方式将面向对象技术的特性体现出来。使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。,常用可视化程序设计语言Visual C+功能强大，比较适合专业人员使用。Visual Basic易于学习和掌握，比较适合非专业人员和初学者使用。,（7）人工智能程序设计语言适合于知识表示和逻辑推理。常用人工智能程序设计语言 LISP LISP是LISt Processing（表处理）的缩写。可以解决人工智能中的符号处理问题。PROLOG 是PROgramming in LOGic（逻辑程序设计）的缩写。自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。,小 结：1.计算机问题求解 2.算法设计 3.程序设计,
