计算机导论精品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规定的一组图形符号来表示算法的图形，可方便的表示顺序、选择和循环结构。流程图的基本组件起止框输入输出框判断框处理框流程线顺序结构ABABPTFAPFT选择结构循环结构APTAPFT（3）盒图（N_S图）

美国学者I.Nassi和B.Shneiderman提出的一种在流程图中完全去掉流程线，全部算法写在一个矩形阵内，在框内还可以包含其他框的流程图形式。AB顺序结构

Y

PNAB选择结构

当P成立

A

AP成立循环结构

（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；否则算法结束。算法分析与设计：流程图：#include<stdio.h>intmain(){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结

束i=1,P=1TF5.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图：程序：#include<stdio.h>intmain(){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=15.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年，是面向对象语言的鼻祖。C++发布于1983年，是在C语言的基础上发展起来的。C++是得到广泛应用的一种面向对象语言。目前常用的版本有VisualC++,C#,VisualC++.Net等。Java发布于1995年，适合于网络程序设计。目前得到广泛应用的一种面向对象程序设计语言。（6）可视化程序设计语言以图形化的编程方式将面向对象技术的特性体现出来。使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。常用可视化程序设计语言VisualC++功能强大