第2章 算法—程序的灵魂

主要内容 一、 算法的概念 二、 算法的特性 三、 算法的表示方法 四、 结构化程序设计方法

著名计算机科学家沃思提出一个公式:  数据结构 + 算法 = 程序 一、算法的概念 一个程序应包括两个方面的内容: 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm) 著名计算机科学家沃思提出一个公式:  数据结构 + 算法 = 程序

一、算法的概念 例： 求 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 方法1：1+2，+3，+4，一直加到100 加99次 例： 求 方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+…+(49 +51)+50 = 100 + 49×100 +50 加51次

一、算法的概念 计算机算法可分为两大类别： 数值运算算法：求数值解，例如求方程的根、求函数的定积分等。 非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。

二、算法的特性 有穷性：包含有限的操作步骤 确定性：算法中的每一个步骤都应当是确定的 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息 有一个或多个输出：算法的目的是为了求解，“解” 就是输出 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果 。

三、算法的表示方法 常用的表示算法的方法有： 自然语言 传统流程图 结构化流程图 N-S图 伪代码 计算机语言

1、自然语言 Part 3 算法的表示 优点：通俗易懂 缺点：文字冗长，容易出现“歧义性”，有时候需要通过上下文来判断正确含义。

2、传统流程图 Part 3 算法的表示 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号： 起止框 判断框 处理框 输入/输出框 注释框 流向线 连接点

2、传统流程图 Part 3 算法的表示 例 将求5!的算法用流程图表示

2、传统流程图 缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。 Part 3 算法的表示 传统流程图的流程可以是： 缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。 解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。 这种如同乱麻一样的算法称为BS型算法，意为一碗面条(A Bowl of Spaghetti)，乱无头绪。

3、结构化流程图 Part 3 算法的表示 Bohra和Jacopini提出了以下三种基本结构： 顺序结构、选择结构、循环结构

3、结构化流程图 Part 3 算法的表示 顺序结构

3、结构化流程图 Part 3 算法的表示 选择结构

3、结构化流程图 Part 3 算法的表示 当型(While型)循环结构 直到型(Until型)循环

3、结构化流程图 三种基本结构的共同特点： (1)只有一个入口； Part 3 算法的表示 三种基本结构的共同特点： (1)只有一个入口； (2)只有一个出口；（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。） (3)结构内的每一部分都有机会被执行到； (4)结构内不存在“死循环”(无终止的循环)。

3、结构化流程图 Part 3 算法的表示 不正确的流程表示： 图中没有一条从入口到出口的路径通过A框。 流程内的死循环

3、结构化流程图 Part 3 算法的表示 多分支选择结构： 由三种基本结构所派 生出来的，根据表达式的 值决定执行路线。 虚线框内的结构是一 个入口一个出口。

4、N-S图 Part 3 算法的表示 N--S流程图用以下的流程图符号： (1)顺序结构 (2)选择结构 (3)循环结构

4、N-S图 Part 3 算法的表示 例 求5!算法用N--S图表示

5、伪代码 Part 3 算法的表示 伪代码是用介于自然语言和计算机语言之间的文字和 符号来描述算法。

5、伪代码 置t 的初值为1 例 用伪代码表示算法：求5!。 Part 3 算法的表示 也可以写成以下形式： 开始 置i 的初值为2 例 用伪代码表示算法：求5!。 开始 置t 的初值为1 置i 的初值为2 当i<=5，执行下面操作： 使t=t×i 使i=i+1 ｛循环体到此结束｝ 输出t的值 结束 也可以写成以下形式： BEGIN｛算法开始｝ 1t 2  i while i≤5 {t×i t  i+1  i} print t END｛算法结束｝

6、计算机语言 #include <stdio.h> 例 求5! ，用C语言编写。 void main( ) {int i,t; Part 3 算法的表示 #include <stdio.h> void main( ) {int i,t; t=1; i=2; while(i<=5) {t=t*i; i=i+1; } printf(“%d\n”,t); 例 求5! ，用C语言编写。

四、结构化程序设计方法 一个结构化程序 就是用高级语言表示的结构化算法。(用三种基本结构组成的程序) 结构化程序设计方法的基本思路是： 把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。

四、结构化程序设计方法 采取以下方法来保证得到结构化的程序： 自顶向下； 逐步细化； 模块化设计； 结构化编码。

四、结构化程序设计方法 用这种方法逐步分解，直到可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。

四、结构化程序设计方法 模块设计的方法： 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。 划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。