《高级程序设计语言》 第二章 程序的灵魂——算法

高级程序设计语言 吴凡 TEL:89202682 E-mail:cdwf@tom.com

高级程序设计语言 吴 凡 TEL: 83202682 E-mail: cdwf@tom.com

第二章程序的灵魂——算法 20049-15

2004-9-15 第二章 程序的灵魂——算法

程序 ■程序包括两个方面: 对数据的描述,即数据结构( data structure) 对操作的描述(操作步骤),即算法( algorithm) 操作的对象是数据, 操作的目的是对数据进行加工处理,以获取结果 ■算法:解决”做什么”和”怎么做”的问题 语句( statements)只是算法的具体体现 ■沃思公式:数据结构+算法=程序 20049-15

2004-9-15 程序 ◼ 程序包括两个方面： ◼ 对数据的描述，即数据结构(data structure) ◼ 对操作的描述(操作步骤)，即算法(algorithm) ◼ 操作的对象是数据， ◼ 操作的目的是对数据进行加工处理，以获取结果 ◼ 算法：解决”做什么”和”怎么做”的问题 ◼ 语句(statements)只是算法的具体体现 ◼ 沃思公式: 数据结构 + 算法 = 程序

算法的概念 ■算法(广义):为解决一个问题而采用的方法 和步骤 算法多样性 不同的算法具有简单和复杂的分别,但首要保 证算法正确性,再考虑算法的质量 ■计算机算法:是计算机为解决一个问题而采用 的方法和步骤 ■计算机算法的两大类: ■数值运算算法:目的求数值解 非数值运算算法:应用广泛 20049-15

2004-9-15 算法的概念 ◼ 算法（广义）：为解决一个问题而采用的方法 和步骤。 ◼ 算法多样性 ◼ 不同的算法具有简单和复杂的分别，但首要保 证算法正确性，再考虑算法的质量。 ◼ 计算机算法：是计算机为解决一个问题而采用 的方法和步骤。 ◼ 计算机算法的两大类： ◼ 数值运算算法：目的求数值解 ◼ 非数值运算算法：应用广泛

简单算法举例 ■例21求5! 思考:给定正整数n,求n→应具有通用性、 灵活性 累加,累乘等运算问题的基本算法 累计结果tota):需要设定初值 变化量(〕:正确确定每次参与运算的变化量 累次计算,直到到达预期范围 tota= total OPERATORi运算符)i; 改变i值,重复计算 应用:例24 20049-15

2004-9-15 简单算法举例 ◼ 例2.1 求5！ ◼ 思考：给定正整数n，求n → 应具有通用性、 灵活性 ◼ 累加，累乘等运算问题的基本算法 ◼ 累计结果(total)：需要设定初值； ◼ 变化量(i)：正确确定每次参与运算的变化量 ◼ 累次计算，直到i到达预期范围 ▪ total ＝ total OPERATOR(运算符) i； ▪ 改变i值，重复计算 ◼ 应用：例2.4

简单算法举例 ■例23判断2000-2500年中的每一年是否闰年, 将结果输出 仔细确定判断条件,逐步缩小判断范围 对范围的确定要保证无遗漏 20049-15

2004-9-15 简单算法举例 ◼ 例2.3判断2000－2500年中的每一年是否闰年， 将结果输出。 ◼ 仔细确定判断条件，逐步缩小判断范围 ◼ 对范围的确定要保证无遗漏

算法的特性 ■有穷性:要确定合理的限定范围 ■确定性 有零个或多个输入 ■有一个或多个输出 ■有效性 20049-15

2004-9-15 算法的特性 ◼ 有穷性：要确定合理的限定范围 ◼ 确定性 ◼ 有零个或多个输入 ◼ 有一个或多个输出 ◼ 有效性

怎样表示一个算法 ■算法表示的方法: ■自然语言:通俗易懂,但文字冗长,不严格,易出现歧 义性 传统流程图:直观形象,易于理解 用图框表示各种操作。 用流程线表示各图框的执行顺序 要注意避免无规律的流程转向 结构化流程图(N-S流程图) 算法全部的矩形框内 无流程线 伪代码 PAD图 20049-15

2004-9-15 怎样表示一个算法 ◼ 算法表示的方法： ◼ 自然语言：通俗易懂，但文字冗长，不严格，易出现歧 义性 ➢ 传统流程图：直观形象，易于理解 ➢ 用图框表示各种操作。 ➢ 用流程线表示各图框的执行顺序 ➢ 要注意避免无规律的流程转向 ➢ 结构化流程图（N-S流程图) ➢ 算法全部的矩形框内 ➢ 无流程线 ◼ 伪代码 ◼ PAD图

程序设计的三种基本结构 ■顺序结构:自顶向下,无分支,无转移 ■选择结构:有分支,需条件判断 循环结构:有转移,某些语句需要重复执行 当型( While型)循环 直到型(Unt型)循环 ■这三种基本结构可以组成任意复杂的算法 20049-15

2004-9-15 程序设计的三种基本结构 ◼ 顺序结构: 自顶向下,无分支,无转移 ◼ 选择结构: 有分支,需条件判断 ◼ 循环结构: 有转移,某些语句需要重复执行 ◼ 当型（While型）循环 ◼ 直到型（Until型）循环 ◼ 这三种基本结构可以组成任意复杂的算法

顺序结构 ■顺序结构:自顶向下顺序执行,无分支,无转 移 a A AB B b 流程图表示法 NS图表示法 20049-15

2004-9-15 顺序结构 ◼ 顺序结构: 自顶向下顺序执行，无分支，无转 移 A B 流程图表示法 A B N-S图表示法 a b