《大学计算机基础》第5章-程序设计基础.ppt

大学计算机基础 北京航空航天大学 第5章 程序设计基础 本章重点 程序的概念 程序设计语言的结构 算法的概念与描述方法 程序设计步骤 程序设计方法 5.1 程序和程序设计语言 5.1.1 程序的一般概念 5.1.2 程序设计语言的概述 5.1.3 程序设计语言的结构 5.1.1　程序的一般概念 生活中程序的概念 5.1.1　程序的一般概念（续1） 生活中程序的概念 5.1.1　程序的一般概念（续2） 计算机程序的概念： 5.1.2　程序设计语言的概述 程序设计——编写程序的全过程。 有学者认为： 程序设计 = 算法 + 数据结构 + 程序设计语言 1.　机器语言（Machine Language） 指令——指挥计算机完成某个基本操作的命令。 2.　汇编语言（Assembly Language ） 汇编语言——实质就是以容易记忆的代码或英文单词来代替约定的机器指令。（第二代程序设计语言） 3.　高级语言（High Level Language） 高级语言——类似数学语言或人的自然语言，同时又不依赖于某种计算机硬件，使得设计编制的程序能够在所有机器上通用。 （第三代程序设计语言） 程序设计语言的特点 机器语言的特点： 编程难 效率高 需要指令系统 难读 难维护 5.1.3　程序设计语言的结构 程序结构的多样性： 结构化程序 模块化程序 面向对象的程序结构 结构化程序设计中——顺序结构 按照程序语句行的自然顺序，一条语句一条语句地执行程序。 结构化程序设计中——选择结构 根据条件的判断确定应该执行哪一条分支的语句序列。（又称为分支结构 ） 结构化程序设计中——循环结构 主要用于重复执行相同的语句序列（被称为循环体），直到判定条件为假（或为真）时才可终止执行循环体。 结构化程序设计的特点 每种结构，只有一个入口和一个出口，这是结构化设计的一个原则。 5.2 算法 5.2.1 算法的概念与特征 5.2.2 算法的描述方法 5.2.3 程序设计典型算法 5.2.1　算法的概念与特征 1976年Niklaus Wirth（也是Pascal语言发明者，1984年获得图灵奖）的专著： 1. 算法的概念 算法——解决某个具体问题而采取的方法与步骤的完整和准确的描述。 是指令的有限序列，其中每一条指令表示一个或多个操作。 是问题的程序化解决方案，这些解决方案本身并不是答案，而是获得答案的精确指令。 2. 算法的特征 一个算法必须具备五项基本特征：有穷性、确定性、数据输入、数据输出和可行性。 例5.1 一个非算法的计数过程 ① 令n为0； ② 置n为n+1； ③ 返回②。 例5.2 计数器算法 用自然语言编写一个不超过1万次的计数器算法： ① 令n为0； ② 置n为n+1 ③ 若n小于10000，则返回②；否则，输出n之值，且算法到此结束。 5.2.2　算法的描述方法 流程图（FlowChart） PAD图（Problem Analysis Diafram，问题分析图） N-S图 自然语言 伪代码 UML图 （Unified Modeling Language，统一建模语言） 1. 流程图 流程图（框图）用不同形状的几何图形表示不同性质的操作，用流程线指明算法的执行方向。ANSI(美国国家标准化协会)、ISO（国际标准化组织）和我国国家标准中均有类似的规定。常见的流程图符号如下： 用流程图描述的计数器算法 2. PAD图 由日立公司推出的PAD图是一种二维图。即从上向下顺序执行，从左到右表示层次关系。表示三种基本结构的PAD图如下： 3. N-S图 1973年美国两位学者提出无流程线的N-S图（盒图）。 用N-S图描述的计数器算法 4. 自然语言 自然语言是人们日常生活、工作和学习中使用的通用语言，使用自然语言的文字描述算法通俗易懂，但也有它的缺陷： 5. 伪代码 伪代码是介于自然语言和计算机语言之间的文字和符号，它不能被计算机所理解，但使用伪代码描述的算法很容易转变成某种编程语言。 流程图形的绘制工具 当使用图形描述算法时，流程图形的绘制工具有很多。 5.2.3　程序设计典型算法 算法——数值算法或非数值算法： 1. 求3个整数的最大值算法 为了编写求3个整数最大值的通用实现过程，采用主函数调用子函数的形式描述算法。 求3个整数的最大值的C程序 2. 欧几里得算法 求解两个不全为0的非负整数m和n的最大公约数，可以采用以下欧几里得算法。 3. 两个变量值的交换算法 计算机实现的两个变量值的交换算法如下： 4. 排序算法 给定一个有n个元素可排序的序列，例如数字数据或字符串数据等，要求按照升序或降序方式