高级程序设计语言吴 凡
TEL,83202682
E-mail,cdwf@tom.com
2004-9-15
第二章 程序的灵魂 —— 算法
2004-9-15
程序
程序包括两个方面：
对数据的描述，即数据结构 (data structure)
对操作的描述 (操作步骤 )，即算法 (algorithm)
操作的对象是数据，
操作的目的是对数据进行加工处理，以获取结果
算法：解决”做什么”和”怎么做”的问题
语句 (statements)只是算法的具体体现
沃思公式,数据结构 + 算法 = 程序
2004-9-15
算法的概念
算法（广义）：为解决一个问题而采用的方法和步骤。
算法多样性
不同的算法具有简单和复杂的分别，但首要保证算法正确性，再考虑算法的质量。
计算机算法：是计算机为解决一个问题而采用的方法和步骤。
计算机算法的两大类：
数值运算算法：目的求数值解
非数值运算算法：应用广泛
2004-9-15
简单算法举例
例 2.1 求 5！
思考：给定正整数 n，求 n? 应具有通用性、
灵活性
累加，累乘等运算问题的基本算法
累计结果 (total)：需要设定初值；
变化量 (i)：正确确定每次参与运算的变化量
累次计算，直到 i到达预期范围
total ＝ total OPERATOR(运算符 ) i；
改变 i值，重复计算
应用：例 2.4
2004-9-15
简单算法举例
例 2.3判断 2000－ 2500年中的每一年是否闰年，
将结果输出。
仔细确定判断条件，逐步缩小判断范围
对范围的确定要保证无遗漏
2004-9-15
算法的特性
有穷性：要确定合理的限定范围
确定性
有零个或多个输入
有一个或多个输出
有效性
2004-9-15
怎样表示一个算法
算法表示的方法：
自然语言：通俗易懂，但文字冗长，不严格，易出现歧义性
传统流程图：直观形象，易于理解
用图框表示各种操作。
用流程线表示各图框的执行顺序
要注意避免无规律的流程转向
结构化流程图（ N-S流程图 )
算法全部的矩形框内
无流程线
伪代码
PAD图
2004-9-15
程序设计的三种基本结构
顺序结构,自顶向下,无分支,无转移
选择结构,有分支,需条件判断
循环结构,有转移,某些语句需要重复执行
当型（ While型）循环
直到型（ Until型）循环
这三种基本结构可以组成任意复杂的算法。
2004-9-15
顺序结构
顺序结构,自顶向下顺序执行，无分支，无转移
A
B
流程图表示法
A
B
N-S图表示法
a
b
2004-9-15
选择结构 (选取结构、分支结构 )
选择结构：有分支,需条件判断
无论条件 p是否成立，只能执行 A,B两个分支中的一支
A,B分支中，可以有一支是“空语句”（图 2.16）
A B
流程图表示法 N-S图表示法
pYes/成立 NO/不成立
A B
p
成立 不成立
a
b
2004-9-15
循环结构 （重复结构）
当型（ While型）循环
流程顺序：“判断?执行?再判断?再执行?...”
由判断条件 P决定重复执行的次数，循环次数可控
当 P不成立时，停止循环
循环体内应该有使循环停止的操作
A
流程图表示法 N-S图表示法
p 成立不成立
A
当 p成立
a
b
2004-9-15
循环结构 （重复结构）
直到（ Until型）型循环
先执行，再判断（即 操作 A至少 要执行 一次 ）
重复执行，直到条件满足（即条件 不 成立时，重复 执行 ）
流程图表示法 N-S图表示法
p 不成立成立
A
直到 p成立
A
a
b
2004-9-15
基本结构的特点
基本结构的特点：
只有一个入口
只有一个出口
结构内部每一部分都能被执行到
结构内不存在“死循环”
由基本结构所构成的算法属于”结构化”的算法
不存在无规律的转向，只在结构内部才存在分支和跳转
2004-9-15
伪代码（ pseudo code）
伪代码：用文字和符号描述算法
格式自由，书写方便，修改容易
一般在设计算法时使用
2004-9-15
结构化程序设计方法
基本原则
自顶向下，逐步细化
模块化设计
根据功能划分模块
C语言中用函数实现模块
结构化编码
采用基本结构描述算法
用高级语言实现算法
举例 2.22
TEL,83202682
E-mail,cdwf@tom.com
2004-9-15
第二章 程序的灵魂 —— 算法
2004-9-15
程序
程序包括两个方面：
对数据的描述，即数据结构 (data structure)
对操作的描述 (操作步骤 )，即算法 (algorithm)
操作的对象是数据，
操作的目的是对数据进行加工处理，以获取结果
算法：解决”做什么”和”怎么做”的问题
语句 (statements)只是算法的具体体现
沃思公式,数据结构 + 算法 = 程序
2004-9-15
算法的概念
算法（广义）：为解决一个问题而采用的方法和步骤。
算法多样性
不同的算法具有简单和复杂的分别，但首要保证算法正确性，再考虑算法的质量。
计算机算法：是计算机为解决一个问题而采用的方法和步骤。
计算机算法的两大类：
数值运算算法：目的求数值解
非数值运算算法：应用广泛
2004-9-15
简单算法举例
例 2.1 求 5！
思考：给定正整数 n，求 n? 应具有通用性、
灵活性
累加，累乘等运算问题的基本算法
累计结果 (total)：需要设定初值；
变化量 (i)：正确确定每次参与运算的变化量
累次计算，直到 i到达预期范围
total ＝ total OPERATOR(运算符 ) i；
改变 i值，重复计算
应用：例 2.4
2004-9-15
简单算法举例
例 2.3判断 2000－ 2500年中的每一年是否闰年，
将结果输出。
仔细确定判断条件，逐步缩小判断范围
对范围的确定要保证无遗漏
2004-9-15
算法的特性
有穷性：要确定合理的限定范围
确定性
有零个或多个输入
有一个或多个输出
有效性
2004-9-15
怎样表示一个算法
算法表示的方法：
自然语言：通俗易懂，但文字冗长，不严格，易出现歧义性
传统流程图：直观形象，易于理解
用图框表示各种操作。
用流程线表示各图框的执行顺序
要注意避免无规律的流程转向
结构化流程图（ N-S流程图 )
算法全部的矩形框内
无流程线
伪代码
PAD图
2004-9-15
程序设计的三种基本结构
顺序结构,自顶向下,无分支,无转移
选择结构,有分支,需条件判断
循环结构,有转移,某些语句需要重复执行
当型（ While型）循环
直到型（ Until型）循环
这三种基本结构可以组成任意复杂的算法。
2004-9-15
顺序结构
顺序结构,自顶向下顺序执行，无分支，无转移
A
B
流程图表示法
A
B
N-S图表示法
a
b
2004-9-15
选择结构 (选取结构、分支结构 )
选择结构：有分支,需条件判断
无论条件 p是否成立，只能执行 A,B两个分支中的一支
A,B分支中，可以有一支是“空语句”（图 2.16）
A B
流程图表示法 N-S图表示法
pYes/成立 NO/不成立
A B
p
成立 不成立
a
b
2004-9-15
循环结构 （重复结构）
当型（ While型）循环
流程顺序：“判断?执行?再判断?再执行?...”
由判断条件 P决定重复执行的次数，循环次数可控
当 P不成立时，停止循环
循环体内应该有使循环停止的操作
A
流程图表示法 N-S图表示法
p 成立不成立
A
当 p成立
a
b
2004-9-15
循环结构 （重复结构）
直到（ Until型）型循环
先执行，再判断（即 操作 A至少 要执行 一次 ）
重复执行，直到条件满足（即条件 不 成立时，重复 执行 ）
流程图表示法 N-S图表示法
p 不成立成立
A
直到 p成立
A
a
b
2004-9-15
基本结构的特点
基本结构的特点：
只有一个入口
只有一个出口
结构内部每一部分都能被执行到
结构内不存在“死循环”
由基本结构所构成的算法属于”结构化”的算法
不存在无规律的转向，只在结构内部才存在分支和跳转
2004-9-15
伪代码（ pseudo code）
伪代码：用文字和符号描述算法
格式自由，书写方便，修改容易
一般在设计算法时使用
2004-9-15
结构化程序设计方法
基本原则
自顶向下，逐步细化
模块化设计
根据功能划分模块
C语言中用函数实现模块
结构化编码
采用基本结构描述算法
用高级语言实现算法
举例 2.22
