大学计算机基础大学计算机基础北京航空航天大学北京航空航天大学教学课件教学课件1第第5 5章章 程序设计基础程序设计基础5.3 5.3 程序设计步骤与程序设计方法程序设计步骤与程序设计方法 5.1 5.1 程序和程序设计语言程序和程序设计语言 5.2 5.2 算法算法 5.4 5.4 常用程序设计语言常用程序设计语言 5.5 5.5 程序设计范型程序设计范型 2本章重点n程序的概念n程序设计语言的结构n算法的概念与描述方法n程序设计步骤n程序设计方法35.1 程序和程序设计语言u5.1.1 程序的一般概念 u5.1.2 程序设计语言的概述 u5.1.3 程序设计语言的结构 45.1.1 程序的一般概念 n生活中程序的概念何事？何事？策划策划导演导演例1：年终总结会的程序：会议主持宣布会议开始领导讲话个人或团队代表发言领导总结会议主持宣布会议结束55.1.1 程序的一般概念（续1） n生活中程序的概念甲地乙地丙地A线8公里B线5公里C线4公里步行骑车开车时间红绿灯铁道依据实际案例并精心计算依据实际案例并精心计算 解决该计算问题的方法、步骤就包含了程序的概念。 例2：某人从甲地到丙地去。65.1.1 程序的一般概念（续2） n计算机程序的概念：为实现某一算法而编写的指令序列。宏观地描述该指令序列，可用计算机的l机器语言l汇编语言l高级语言用经典的公式可表示为：程序 = 算法 + 数据结构75.1.2 程序设计语言的概述 n程序设计编写程序的全过程。有学者认为：程序设计 = 算法 + 数据结构 + 程序设 计语言 n程序设计语言人和计算机之间对话和交流的一种 工具，用于描述计算机所执行的操作。n计算机程序设计语言有几百种，但是最常用的不过10 多种，了解一些程序设计语言的不同特性，有助于为 特定任务而选择适当的程序设计语言。 81. 机器语言（Machine Language） n指令指挥计算机完成某个基本操作的命令。机器语言程 序注解10110000 00001000 00101100 00001010 11110100把8存放到累加器A中。 将10与累加器A中的8相加，结 果存在A中。 程序结束。 指令系统所有的指令集合。 （第一代程序设计语 言 ） 机器语言用二进制代码表示指令系统的语言。 机器语言程序由二进制代码按一定规则组 成的、能 被机器理解和运行的指令序列。（也称可执行程序 ）例如：计算累加器A=8+10的机器语言程序如下：92. 汇编语言（Assembly Language ） n汇编语言实质就是以容易记忆的代码或英文单词来 代替约定的机器指令。（第二代程序设计语言）汇编语言源 程序注解MOV A, 8 ADD A, 10 HLT把8存放到累加器A中。 将10与累加器A中的8相加，结果 存在A中。 程序结束。例如：用ADD表示加、SUB表示减、JMP表示跳转 、MOV表示数据的传送指令等 。 汇编源程序使用汇编语 言编写的程序。例如：上述计算累加器A=8+10的汇编语 言程序如下：103. 高级语言（High Level Language） n高级语言类似数学语言或人的自然语言，同时又不依赖 于某种计算机硬件，使得设计编制的程序能够在所有机器上通用。 （第三代程序设计语言）n程序设计语言在不同的系统平台使用比较普遍的有： FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、 SIMULA 67、Pascal、C、Smalltalk 80、Ada、C+、 VC、VB、Delphi、Java、JavaScript、C#、Visual BASIC.NET。n可视化语言构成了命令式语言中的另一个子类。最流行 的可视化语言Visual BASIC（1999年），已被Visual BASIC.NET（2002年）取代。提供拖拉式生成代码段的功 能。一度被认作第四代语言，此说法已不再使用了。 11程序设计语言的特点 n机器语言的特点：编程难效率高 需要指 令系统难读难维护n高级语言的特点 ：编程容易效率低 需要编译系统易读易维护n汇编语言的特点 ：编程不容易效率较高 需要汇编程序不易读不易维护125.1.3 程序设计语言的结构 n程序结构的多样性：结构化程序 模块化程序 面向对象的程序结构n一个良好结构的程序具有以下等特点： 结构清晰容易阅读容易理解容易验证容易维护n1996年，计算机科学家Boehm和Jacopini提出并从数学上证明任何一个算法，都能以三种基本控制结构表示，即顺序结构 、选择结构和循环结构。13结构化程序设计中顺序结构 n按照程序语句行的自然顺序，一条语句一条语句 地执行程序。 语句A入口语句B出口14结构化程序设计中选择结构 n根据条件的判断确定应该执行哪一条分支的语句 序列。（又称为分支结构 ） 入口出口语句序列A语句序列B条件真假单分支、多分支结构？单分支、多分支结构？ 15入口假真语句序列出口直到型循环结构 条件结构化程序设计中循环结构 n主要用于重复执行相同的语句序列（被称为循环体）， 直到判定条件为假（或为真）时才可终止执行循环体。 出口入口语句序列假条件 真当型循环结构 16结构化程序设计的特点 n每种结构，只有一个入口和一个出口，这是结构化设计 的一个原则。n遵循结构化程序设计的原则，按照结构化程序设计方法 设计出的程序具有明显的优点：其一，程序易读、理解和维护。程序员用结构 化编程方法，将复杂程序分解成若干子结构，便于 控制、降低程序的复杂性，因此容易编写程序，同 时便于验证程序。其二，提高编程工作效率，降低软件开发成本 。由于结构化编程方法能够把错误控制到最低限度 ，因此能够减少调试和查错的时间。 175.2 算法u5.2.1 算法的概念与特征 u5.2.2 算法的描述方法 u5.2.3 程序设计典型算法 185.2.1 算法的概念与特征 1976年Niklaus Wirth（也是Pascal语言发明 者，1984年获得图灵奖）的专著：Algorithms Data Structures Programs（算法 十 数据结构 = 程序）在计算机软件开发行业中产生了极为深远的影响，从 而推动了软件开发技术和方法步入正轨，使人们开始深入 研究数据结构和算法设计与分析的技术和方法。 191. 算法的概念 n算法解决某个具体问题而采取的方法与步骤的完整和 准确的描述。是指令的有限序列，其中每一条指令表示一个或 多个操作。是问题的程序化解决方案，这些解决方案本身并 不是答案，而是获得答案的精确指令。 算法的分类 顺序算法：是由冯诺依曼型计算机体系结构所决定的 ，其主要思想是指令逐条运行，每次执行一步操作。 并行算法：要求在一些更新式的计算机中可以在同一时 间执行多条指令。 202. 算法的特征 n一个算法必须具备五项基本特征：有穷性、确定性、 数据输入、数据输出和可行性。（1）有穷性算法是有序指令的集合，并在 执行有穷步骤后能够终止。（2）确定性每条指令必须有确切的含义， 且无二义性。在任何条件下，算法只有唯一 的一条执行路径，即对于相同的输入数据只 能得到相同的输出数据。（3）输入数据可有零个或多个输入数据。 这些输入数据取自于某个特定对象的集合。（4）输出数据必须有一个或多个输出数据 。（5）可行性描述的操作都可以通过已经实 现的基本运算执行有限次来实现，也可以证 明整个算法实施后可以得到预期的解。 21例5.1 一个非算法的计数过程 令n为0； 置n为n+1； 返回。结论：不能称为算法。 原因：违背了算法特征中（1）、（4）、（5）。 22例5.2 计数器算法 用自然语言编写一个不超过1万次的计数器算法： 令n为0； 置n为n+1 若n小于10000，则返回；否则，输出n之值， 且算法到此结束。结论：是算法。 原因：符合算法特征。 在算法设计过程中，其实还有有关正确性、可读性 、健壮性、效率与低存储量需求，以及算法效率的度量 等问题。235.2.2 算法的描述方法 流程图（FlowChart）PAD图（Problem Analysis Diafram，问题分析图）N-S图自然语言伪代码 UML图 （Unified Modeling Language，统一建模语言）241. 流程图 n流程图（框图）用不同形状的几何图形表示不同性质的 操作，用流程线指明算法的执行方向。ANSI(美国国家 标准化协会)、ISO（国际标准化组织）和我国国家标准 中均有类似的规定。常见的流程图符号如下： 向下或向右的流程线可以不画出箭头。当流程线有交叉 时，则画一半圆通过交叉点。 25用流程图描述的计数器算法 262. PAD图 n由日立公司推出的PAD图是一种二维图。即从上向下顺 序执行，从左到右表示层次关系。表示三种基本结构的 PAD图如下： 273. N-S图 n1973年美国两位学者提出无流程线的N-S图（盒图）。 结构化程序设计由三种基本结构而组成，则算法也应采 用结构化描述方法，N-S图的基本单元是矩形框，框内可 以有三种基本结构，形如堆积木，也只有一个入口和一个 出口。三种基本结构的N-S图如下： 28用N-S图描述的计数器算法 294. 自然语言 n自然语言是人们日常生活、工作和学习中使用的通用语言 ，使用自然语言的文字描述算法通俗易懂，但也有它的缺 陷： （1）容易产生歧义性，因为自然语言经常要根据上下文才 能判别其含义，不太严格。（2）自然语言很难清楚地表达算法的逻辑流程，对于算法 中的条件判断、循环，尤其是在这些处理中还有多层嵌 套，就很难用清晰而直观的语言来表达算法的流程。因 此仅适于描述简单问题 。 305. 伪代码 n伪代码是介于自然语言和计算机语言之间的文字和符号 ，它不能被计算机所理解，但使用伪代码描述的算法很 容易转变成某种编程语言。/用伪代码描述的计数器算法如下：n 0don n+1while n void main(void) int a, b, c, max; /* 定义 4 个整型变量 */int max3(int a, int b, int c); /* max3 函数原形声明 */printf(“Input 3 integer numbers:”);/* 输出双引号中的提示信息 */scanf(“%d%d%d”, /* 输入 3 个整数 */max = max3(a,b,c); /* 调用 max3 函数求最大值 */printf(“The max is: %d n”, max); /* 输出 max 中的最大值 */ /* End of main function */* 求 3 个整数的最大值的子函数 max3 */ int max3(int a,int b,int c) /* max3 函数将返回整型值 */ int m; /* 定义 m 整型变量 */ if( a b ) m = a; /* 从 a 与 b 中取大数送 m 中 */else m = b;if( m c ) ; /* 从 m 与 c 中取大数送 m 中，“；”即m=m */elsem = c;return(m); /* 返回 m 给主函数 */ /* End of max3 function */352. 欧几里得算法 n求解两个不全为