第 2章 程序的灵魂 —算法任课老师：彭金莲返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作本章要求
算法的概念，
算法的特性，
算法的表示方法：流程图,伪代码,计算机语言,程序设计方法。
程序设计方法。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作第 2章 程序的灵魂 —算法
2.1 算法的概念
2.2 算法的举例
2.3 算法的特性
2.4 怎样表示一个算法
2,5 结构化程序设计方法返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 1）对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构（ data structure）。
（ 2） 对操作的描述。即操作步骤，
也就是算法（ algorithnl）。
数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。
一个程序应包括以下两方面内容：
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作程序
数据结构十算法一程序
程序 =算法十数据结构十程序设计方法个语言工具和环境
也就是说，以上 4个方面是一个程序设计人员所应具备的知识。
在这 4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决,做什么” 和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。
我们的目的是使读者通过学习本书，能够知道怎样编写一个 C程序，并且能够编写出不太复杂的 C程序。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.1 算法的概念
做任何事情都有一定的步骤。这些步骤都是按一定的顺序进行的，缺一不可，次序错了也不行。
对同一个问题，可以有不同的解题方法和步骤。
例如，求 1＋ 2＋ 3＋ … ＋ 100
计算机算法可分为两大类别：
数值运算算法：数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，都属于数值运算范围。
非数值运算算法。最常见的是用于事务管理领域，
例如图书检索、人事管理、行车调度管理等。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.2 算法的举例
例 2.1 求 1*2*3*4*5
可以用最原始的方法进行。
步骤 1：先求 1*2，得到结果 2
步骤 2：将步骤 1得到的乘积 2再乘以 3，得到结果 6。
步骤 3：将 6再乘以 4，得 24。
步骤 4：将以再乘以 5，得 120。这就是最后的结果。
这样的算法虽然是正确的，但大繁琐。如果要求
l* 2*… * 1000,则要写 999个步骤，显然是不可取的。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作一种通用的表示方法
可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。
设 p为被乘数,i为乘数。用循环算法来求结果。可以将算法改写如下：
S1,使 p=1
S2,使 i=2
S3,使 p * i,乘积仍放在变量 P中，表示为
p * i＝ >p
S4,使 i的值加 l,即 i+l>i
S5,如果 i不大于 5，返回重新执行步骤 S3以及其后的步骤 S4和 S5； 否则，算法结束。最后得到 P的值就是 5！的值。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作求 1*3*5*7*9*11
算法只需作很少的改动即可：
S1,p=1
S2,i=3
S3,p=p * i
S4,i=i ＋ 2
S5,若 i＜ 11,返回 S3；
否则，结束。
算法具有通用性、灵活性。 S3到 S5组成一个循环，在实现算法时，要反复多次执行 S3,S4,S5等步骤，直到某一时刻，执行 S5步骤时经过判断，乘数 i已超过规定的数值而不返回 S3步骤为止。此时算法结束，变量 P的值就是所求结果。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.2
有 50个学生，要求将他们之中成绩在 80分以上者打印出来。用 n表示学生学号,n1代表第一个学生学号,ni代表第 i个学生学号。用 g代表学生成绩，
gi代表第 i个学生成绩，算法可表示如下。
S1,i=1
S2,如果 gi>=80,则打印 ni和 gi,否则不打印
S3,i=i＋ l
S4,如果 i<=50,返回 S2,继续执行；
否则,算法结束。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.3 判定 2000-2500年中的每一年是否闰年
闰年的条件是 (1)能被 4整除，但不能被 100整除的年份都是闰年 (2)是闰年必能被 100整除，又能被 400整除的年份是闰年。
设 y为被检测的年份。可采取以下步骤：
S1,y=2000 /*输入一个数给 Y y */
S2,若 y不能被 4整除，则输出 y―不是闰年”。然后转到 S6
S3,若 y能被 4整除，不能被 100整除，则输出 y―是闰年”。然后转到 S6
S4,若 y能被 100整除，又能被 400整除，输出 y―是闰年”；否则输出“不是闰年”。然后转到 S6
S5,输出 y―不是闰年”
S6,y=y十 l
S7,当 y<= 2500时，转 S2继续执行，如 y ＞ 2500,算法停止。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
闰年的判定闰年的条件返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
sum 表示累加和
deno 是英文中分母
(denominator)的缩写
sign 代表数值的符号
term 代表某一项。
例 2.4
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.3算法的特性
有穷性
一个算法应包含有限的操作步骤，而不是无限的。
确定性
算法中的每一个步骤都应当是确定的，而不应当是含糊的、
模棱两可的。也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。
所谓“歧义性”是指可以被理解为两种（或多种）的可能含义。
有零个或多个输入
所谓输入是指在执行算法时需要从外界取得必要的信息。
有一个或多个输出
算法的目的是为了求解，“解”就是输出。如 5．有效性
算法中的每一个步骤都应当能有效地执行，并得到确定的结果。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4怎样表示一个算法
常用的有自然语言、传统流程图、结构化流程图、伪代码,PAD图等。
2.4.1 用自然语言表示算法
自然语言就是人们日常使用的语言，可以是汉语、
英语或其他语言。用自然语言表示通俗易懂，
文字冗长，容易出现“歧义性”。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。
用自然语言描述包含分支和循环的算法，不很方便。
因此，除了很简单的问题以外，一般不用自然语言描述算法。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.2用流程图表示算法
流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。
美国国家标准化协会 ANSI（ American
Nanonal Standard Institute） 规定了～些常用的流程图符号（见图 2.3,图 2.4 2.5）。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作流程图符号
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作菱形框的作用
菱形框的作用是对一个给定的条件进行判断，
根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口两个出口。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
连接点（小圆圈）是用于将画在不同地方的流程线连接起来。如图 2.5中有两个以○为标志的连接点（在连接点圈中写上,l‖），
它表示这两个点是互相连接在一起的。实际上它们是同一个点，
只是画不下才分开来画。用连接点，可以避免流程线的交叉或过长，使流程图清晰。
流程图返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.6
将例 2.l求 5！的算法用流程图表示，
流程图见图 2,6。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作求 5！
。菱形框两侧的,Y‖
和,N‖代表
,是,(yes） 和,否,
（ no）。 如果需要将最后结果打印出 来，
可以在菱形框的下面再加一个输出框，见图 2,7。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.7
将例 2.2的算法用流程图表示。将
50名学生中成绩在 80分以上者的学号和成绩打印出来，见图 2.8。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作图 2.9
包括输入 50个学生数据的部分，流程图如图 2.9所示。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
将例 2.3判定闰年的算法用流程图表示。
见图 2.10。
例 2.8
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.9
求 1-1/2+1/3-
1/4…… 1/99-1/100
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.3三种基本结构和改进的流程图
1,传统流程图的弊端
传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。这种情况如图 2,13所示。
这种如同乱麻一样的算法称为 BS型算法，意为一碗面条（ a
bowl of spagehetti）,乱无头绪。
这种算法并不好，难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。
为了提高算法的质量，使算法的设计和阅读方便，必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。但是，算法上难免会包含一些分支和循环，而不可能全部由一个一个框顺序组成。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
1966年,Bohra和 Jacopini提出了以下三种基本结构，用这三种基本结构作为表示一个良好算法的基本单元。
2．三种基本结构
（ 1）顺序结构，如图 2.14所示，虚线框内是一个顺序结构。其中 A和 B
两个框是顺序执行的。即在执行完 A
框所指定的操作后，必然接着执行 B
框所指定的操作。顺序结构是最简单的一种基本结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 2）选择结构
如图 2.15所示。虚线框内是一个选择结构。此结构中必包含一个判断框。根据给定的条件 P
是否成立而选择执行 A框或 B框。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作选择结构
请注意，无论 P条件是否成立，只能执行 A框或 B框之一，不可能既执行 A框又执行 B框。无论走哪一条路径，
在执行完 A或 B之后，都经过 b点，然后脱离本选择结构。
A或 B两个框中可以有一个是空的，即不执行任何操作，
如图 2.16所示。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 3）循环结构
它又称重复结构，即反复执行某一部分的操作。有两类循环结构：
①当型（ While型）循环结构
见图 2.17（ a）。 它的功能是当给定的条件已成立时，执行 A框操作，执行完 A后，再判断条件 P1是否成立，
如果仍然成立，再执行
A框，如此反复执行 A框，
直到某一次 P1条件不成立为止，此时不执行 A
框，而从 b点脱离循环结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
②直到型（ Until型）循环
见图 2.17（ b）。 它的功能是先执行 A框，然后判断给定的 P2条件是否成立，如果 P2条件不成立，
则再执行 A,然后再对 P2
条件作判断，如果 P2条件仍然不成立，又执行
A… 如此反复执行 A,直到给定的 P2条件成立为止，此时不再执行 A,从
b点脱离本循环结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作直到型循应用例子：
图 2.18是当型循环的应用例子，
图 2.19是直到型循环的应用例子。
图 2.18和图 2.19的作用都是打印 5个数,1,2,3,4,5。可以看
到，对同一个问题既可以用当型循环来处理，也可以用直到型循环来处理。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作以上三种基本结构，有以下共同特点：
（ l） 只有一个人口。图 2.14～图 2.17中的 a点为入四点。
（ 2）只有一个出口。图 2.14～图已 17中的 b点为出口点。请注意，一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。
（ 3）结构内的每～部分都有机会被执行到。也就是说，
对每一个框来说，都应当有一条从人口到出口的路径通过它。图 2.20中没有一条从人口到出口的路径通过 A
框。
（ 4）结构内不存在“死循环”（无终止的循环）。图
2.21用就是一个死循环。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.4 用 N－ S流程图表示算法
既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流程线就属多余的了。
1973年美国学者 1,Nassi和 B,Shneiderrnan提出了一种新的流程图形式。在这种流图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称 N－ S结构化流程图（ N和 S是两位美国学者的英文姓名的第一个字母）。这种流程图适于结构化程序设计，因而很受欢迎。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
N－ S流程图用以下的流程图符号：
（ 1）则顺序结构：
用图 2.24形式表示。
A和 B两个框组成一个顺序结构。
A,B可以是一个简单的操作（如读人数据或打印输出等），也可以是 3个基本结构之一。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 2）选择结构：
用图 2.25表示。它与图 2.15相应。当 P条件成立时执行 A操作，
P不成立则执行 B操作。
请注意图 2.25是一个整体，代表一个基本结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 3）循环结构：
当型循环结构用图 2.26形式表示。
2.26表示当 P1条件成立时反复执行 A操作，
直到房条件不成立为止。
直到型循环结构用图 2.27形式表示。
当 P1成立
A 直到 P1成立
A
图 2.27图 2.26
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作说明：
用以上 3种 N－ S流程图中的基本框，可以组成复杂的 N－ S流程图，以表示算法。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作求 5！
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.12
将例 2.2的算法用 N－ S图表示。将 50名学生中成绩高于 80分的学号和成绩打印出来返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作结构化算法、非结构化算法,N－ S图
归纳起来可知：
一个结构化的算法是由一些基本结构顺序组成的；
在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内（如循环中流程的跳转）；
一个非结构化的算法（如图 2,12）可以用一个等价的结构化算法（如图 2,35）代替，其功能不变。
如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。
N－ S图如同一个多层的盒子，又称盒图（ box
diagram）。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.5用伪代码表示算法
用传统的流程图和 N－ S图表示算法，直观易懂，但画起来比较费事，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的。因此，流程图适宜表示一个算法，但在设计算法过程中使用不是很理想（尤其是当算法比较复杂、需要反复修改时）。为了设计算法时方便，常用～种称为伪代码（ Pseudo code） 的 工具。
伪代码是用介于自然语言和计算机语言之间 的文字和符号来描述算法。它如同一篇文章，自上而下地写下来。
每一行（或几行）表示一个基本操作。它不用图形符号，
因此书写方便、格式紧凑，也比较好懂，便于向计算机语言算法 (即程序）过渡。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例如，“打印 x的绝对值”的算法可以用伪代码表示如下：
If x is positive THEN
print x
ELSE
print –x
它像一个英语句子一样好懂，在国外用得比较普遍，也可以用汉字伪代码，如：
若 x 为正打印 x
否则打印 -x
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2,16求 5！用伪代码表示的算法如下：
形式一开始置 t的初值为 1
置 i的初值为 2
当 i＜ =5,执行下面操作：
使 t＝＝ t*i
使 i＝＝ i+1
（ 循环体到此结束）
打印 t的值结束形式二
BEGIN（ 算法开始）
t=1
i=2
While i<=5
｛ t=t*i
i=i+1}
print t
END（ 算法结束）
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2,17打印出 50个学生中成绩高于 80分者的学号和成绩。
用伪代码表示算法如下：
BEGIN （ 算法开始）
1=>i
while i＜＝ 50
｛ input ni and gi
i+1=>i}
1＝ i
while i<＝ 50
{ if gi>=80 Print ni and gi
i+1=>i}
END （ 算法结束）
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.6用计算机语言表示算法
求 5!,用 C语言表示：
main()
{ int i,t;
t=1;
i=2;
while (i<=5)
{ t=t*i;
i=i+1;
}
printf(―%d‖,t);
}
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.21将例 2.19表示的算法（求级数的值）用 C语言表示。
main（）
{ int sign=1;
float deno=2.0,sum=1.0,term;
while (deno<=100)
{ sign=-sign;
term=sign/deno;
sum=sum+term;
deno=deno+1;
}
printf(―%f‖,sum);
}
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.5结构化程序设计方法
前面介绍了结构化的算法和三种基本结构。一个结构化程序就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、阅读、修改和维护。这就减少了程序出错的机会，提高了程序的可靠性，保证了程序的质量。
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。怎样才能得到一个结构化的程序呢时 n果我们面临一个复杂的问题，是难以一下子写出～个层次分明、结构清晰、算法正确的程序的。
结构化程序设计方法的基本思路是，把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作结构化程序设计方法
具体说，采取以下方法保证得到结构化的程序
（ 1）自顶向下；
（ 2）逐步细化；
（ 3）模块化设计；
（ 4）结构化编码。
在接受一个任务后应怎样着手进行呢？有两种不同的方法：
一种是自顶向下，逐步细化；
一种是自下而上，逐步积累。
用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫做“自顶向下，逐步细化”。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作自顶向下、逐步细化
算法的概念，
算法的特性，
算法的表示方法：流程图,伪代码,计算机语言,程序设计方法。
程序设计方法。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作第 2章 程序的灵魂 —算法
2.1 算法的概念
2.2 算法的举例
2.3 算法的特性
2.4 怎样表示一个算法
2,5 结构化程序设计方法返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 1）对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构（ data structure）。
（ 2） 对操作的描述。即操作步骤，
也就是算法（ algorithnl）。
数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。
一个程序应包括以下两方面内容：
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作程序
数据结构十算法一程序
程序 =算法十数据结构十程序设计方法个语言工具和环境
也就是说，以上 4个方面是一个程序设计人员所应具备的知识。
在这 4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决,做什么” 和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。
我们的目的是使读者通过学习本书，能够知道怎样编写一个 C程序，并且能够编写出不太复杂的 C程序。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.1 算法的概念
做任何事情都有一定的步骤。这些步骤都是按一定的顺序进行的，缺一不可，次序错了也不行。
对同一个问题，可以有不同的解题方法和步骤。
例如，求 1＋ 2＋ 3＋ … ＋ 100
计算机算法可分为两大类别：
数值运算算法：数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，都属于数值运算范围。
非数值运算算法。最常见的是用于事务管理领域，
例如图书检索、人事管理、行车调度管理等。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.2 算法的举例
例 2.1 求 1*2*3*4*5
可以用最原始的方法进行。
步骤 1：先求 1*2，得到结果 2
步骤 2：将步骤 1得到的乘积 2再乘以 3，得到结果 6。
步骤 3：将 6再乘以 4，得 24。
步骤 4：将以再乘以 5，得 120。这就是最后的结果。
这样的算法虽然是正确的，但大繁琐。如果要求
l* 2*… * 1000,则要写 999个步骤，显然是不可取的。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作一种通用的表示方法
可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。
设 p为被乘数,i为乘数。用循环算法来求结果。可以将算法改写如下：
S1,使 p=1
S2,使 i=2
S3,使 p * i,乘积仍放在变量 P中，表示为
p * i＝ >p
S4,使 i的值加 l,即 i+l>i
S5,如果 i不大于 5，返回重新执行步骤 S3以及其后的步骤 S4和 S5； 否则，算法结束。最后得到 P的值就是 5！的值。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作求 1*3*5*7*9*11
算法只需作很少的改动即可：
S1,p=1
S2,i=3
S3,p=p * i
S4,i=i ＋ 2
S5,若 i＜ 11,返回 S3；
否则，结束。
算法具有通用性、灵活性。 S3到 S5组成一个循环，在实现算法时，要反复多次执行 S3,S4,S5等步骤，直到某一时刻，执行 S5步骤时经过判断，乘数 i已超过规定的数值而不返回 S3步骤为止。此时算法结束，变量 P的值就是所求结果。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.2
有 50个学生，要求将他们之中成绩在 80分以上者打印出来。用 n表示学生学号,n1代表第一个学生学号,ni代表第 i个学生学号。用 g代表学生成绩，
gi代表第 i个学生成绩，算法可表示如下。
S1,i=1
S2,如果 gi>=80,则打印 ni和 gi,否则不打印
S3,i=i＋ l
S4,如果 i<=50,返回 S2,继续执行；
否则,算法结束。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.3 判定 2000-2500年中的每一年是否闰年
闰年的条件是 (1)能被 4整除，但不能被 100整除的年份都是闰年 (2)是闰年必能被 100整除，又能被 400整除的年份是闰年。
设 y为被检测的年份。可采取以下步骤：
S1,y=2000 /*输入一个数给 Y y */
S2,若 y不能被 4整除，则输出 y―不是闰年”。然后转到 S6
S3,若 y能被 4整除，不能被 100整除，则输出 y―是闰年”。然后转到 S6
S4,若 y能被 100整除，又能被 400整除，输出 y―是闰年”；否则输出“不是闰年”。然后转到 S6
S5,输出 y―不是闰年”
S6,y=y十 l
S7,当 y<= 2500时，转 S2继续执行，如 y ＞ 2500,算法停止。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
闰年的判定闰年的条件返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
sum 表示累加和
deno 是英文中分母
(denominator)的缩写
sign 代表数值的符号
term 代表某一项。
例 2.4
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.3算法的特性
有穷性
一个算法应包含有限的操作步骤，而不是无限的。
确定性
算法中的每一个步骤都应当是确定的，而不应当是含糊的、
模棱两可的。也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。
所谓“歧义性”是指可以被理解为两种（或多种）的可能含义。
有零个或多个输入
所谓输入是指在执行算法时需要从外界取得必要的信息。
有一个或多个输出
算法的目的是为了求解，“解”就是输出。如 5．有效性
算法中的每一个步骤都应当能有效地执行，并得到确定的结果。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4怎样表示一个算法
常用的有自然语言、传统流程图、结构化流程图、伪代码,PAD图等。
2.4.1 用自然语言表示算法
自然语言就是人们日常使用的语言，可以是汉语、
英语或其他语言。用自然语言表示通俗易懂，
文字冗长，容易出现“歧义性”。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。
用自然语言描述包含分支和循环的算法，不很方便。
因此，除了很简单的问题以外，一般不用自然语言描述算法。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.2用流程图表示算法
流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。
美国国家标准化协会 ANSI（ American
Nanonal Standard Institute） 规定了～些常用的流程图符号（见图 2.3,图 2.4 2.5）。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作流程图符号
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作菱形框的作用
菱形框的作用是对一个给定的条件进行判断，
根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口两个出口。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
连接点（小圆圈）是用于将画在不同地方的流程线连接起来。如图 2.5中有两个以○为标志的连接点（在连接点圈中写上,l‖），
它表示这两个点是互相连接在一起的。实际上它们是同一个点，
只是画不下才分开来画。用连接点，可以避免流程线的交叉或过长，使流程图清晰。
流程图返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.6
将例 2.l求 5！的算法用流程图表示，
流程图见图 2,6。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作求 5！
。菱形框两侧的,Y‖
和,N‖代表
,是,(yes） 和,否,
（ no）。 如果需要将最后结果打印出 来，
可以在菱形框的下面再加一个输出框，见图 2,7。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.7
将例 2.2的算法用流程图表示。将
50名学生中成绩在 80分以上者的学号和成绩打印出来，见图 2.8。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作图 2.9
包括输入 50个学生数据的部分，流程图如图 2.9所示。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
将例 2.3判定闰年的算法用流程图表示。
见图 2.10。
例 2.8
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.9
求 1-1/2+1/3-
1/4…… 1/99-1/100
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.3三种基本结构和改进的流程图
1,传统流程图的弊端
传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。这种情况如图 2,13所示。
这种如同乱麻一样的算法称为 BS型算法，意为一碗面条（ a
bowl of spagehetti）,乱无头绪。
这种算法并不好，难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。
为了提高算法的质量，使算法的设计和阅读方便，必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。但是，算法上难免会包含一些分支和循环，而不可能全部由一个一个框顺序组成。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
1966年,Bohra和 Jacopini提出了以下三种基本结构，用这三种基本结构作为表示一个良好算法的基本单元。
2．三种基本结构
（ 1）顺序结构，如图 2.14所示，虚线框内是一个顺序结构。其中 A和 B
两个框是顺序执行的。即在执行完 A
框所指定的操作后，必然接着执行 B
框所指定的操作。顺序结构是最简单的一种基本结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 2）选择结构
如图 2.15所示。虚线框内是一个选择结构。此结构中必包含一个判断框。根据给定的条件 P
是否成立而选择执行 A框或 B框。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作选择结构
请注意，无论 P条件是否成立，只能执行 A框或 B框之一，不可能既执行 A框又执行 B框。无论走哪一条路径，
在执行完 A或 B之后，都经过 b点，然后脱离本选择结构。
A或 B两个框中可以有一个是空的，即不执行任何操作，
如图 2.16所示。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 3）循环结构
它又称重复结构，即反复执行某一部分的操作。有两类循环结构：
①当型（ While型）循环结构
见图 2.17（ a）。 它的功能是当给定的条件已成立时，执行 A框操作，执行完 A后，再判断条件 P1是否成立，
如果仍然成立，再执行
A框，如此反复执行 A框，
直到某一次 P1条件不成立为止，此时不执行 A
框，而从 b点脱离循环结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
②直到型（ Until型）循环
见图 2.17（ b）。 它的功能是先执行 A框，然后判断给定的 P2条件是否成立，如果 P2条件不成立，
则再执行 A,然后再对 P2
条件作判断，如果 P2条件仍然不成立，又执行
A… 如此反复执行 A,直到给定的 P2条件成立为止，此时不再执行 A,从
b点脱离本循环结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作直到型循应用例子：
图 2.18是当型循环的应用例子，
图 2.19是直到型循环的应用例子。
图 2.18和图 2.19的作用都是打印 5个数,1,2,3,4,5。可以看
到，对同一个问题既可以用当型循环来处理，也可以用直到型循环来处理。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作以上三种基本结构，有以下共同特点：
（ l） 只有一个人口。图 2.14～图 2.17中的 a点为入四点。
（ 2）只有一个出口。图 2.14～图已 17中的 b点为出口点。请注意，一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。
（ 3）结构内的每～部分都有机会被执行到。也就是说，
对每一个框来说，都应当有一条从人口到出口的路径通过它。图 2.20中没有一条从人口到出口的路径通过 A
框。
（ 4）结构内不存在“死循环”（无终止的循环）。图
2.21用就是一个死循环。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.4 用 N－ S流程图表示算法
既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流程线就属多余的了。
1973年美国学者 1,Nassi和 B,Shneiderrnan提出了一种新的流程图形式。在这种流图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称 N－ S结构化流程图（ N和 S是两位美国学者的英文姓名的第一个字母）。这种流程图适于结构化程序设计，因而很受欢迎。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
N－ S流程图用以下的流程图符号：
（ 1）则顺序结构：
用图 2.24形式表示。
A和 B两个框组成一个顺序结构。
A,B可以是一个简单的操作（如读人数据或打印输出等），也可以是 3个基本结构之一。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 2）选择结构：
用图 2.25表示。它与图 2.15相应。当 P条件成立时执行 A操作，
P不成立则执行 B操作。
请注意图 2.25是一个整体，代表一个基本结构。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
（ 3）循环结构：
当型循环结构用图 2.26形式表示。
2.26表示当 P1条件成立时反复执行 A操作，
直到房条件不成立为止。
直到型循环结构用图 2.27形式表示。
当 P1成立
A 直到 P1成立
A
图 2.27图 2.26
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作说明：
用以上 3种 N－ S流程图中的基本框，可以组成复杂的 N－ S流程图，以表示算法。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作求 5！
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.12
将例 2.2的算法用 N－ S图表示。将 50名学生中成绩高于 80分的学号和成绩打印出来返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作结构化算法、非结构化算法,N－ S图
归纳起来可知：
一个结构化的算法是由一些基本结构顺序组成的；
在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内（如循环中流程的跳转）；
一个非结构化的算法（如图 2,12）可以用一个等价的结构化算法（如图 2,35）代替，其功能不变。
如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。
N－ S图如同一个多层的盒子，又称盒图（ box
diagram）。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.5用伪代码表示算法
用传统的流程图和 N－ S图表示算法，直观易懂，但画起来比较费事，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的。因此，流程图适宜表示一个算法，但在设计算法过程中使用不是很理想（尤其是当算法比较复杂、需要反复修改时）。为了设计算法时方便，常用～种称为伪代码（ Pseudo code） 的 工具。
伪代码是用介于自然语言和计算机语言之间 的文字和符号来描述算法。它如同一篇文章，自上而下地写下来。
每一行（或几行）表示一个基本操作。它不用图形符号，
因此书写方便、格式紧凑，也比较好懂，便于向计算机语言算法 (即程序）过渡。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例如，“打印 x的绝对值”的算法可以用伪代码表示如下：
If x is positive THEN
print x
ELSE
print –x
它像一个英语句子一样好懂，在国外用得比较普遍，也可以用汉字伪代码，如：
若 x 为正打印 x
否则打印 -x
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2,16求 5！用伪代码表示的算法如下：
形式一开始置 t的初值为 1
置 i的初值为 2
当 i＜ =5,执行下面操作：
使 t＝＝ t*i
使 i＝＝ i+1
（ 循环体到此结束）
打印 t的值结束形式二
BEGIN（ 算法开始）
t=1
i=2
While i<=5
｛ t=t*i
i=i+1}
print t
END（ 算法结束）
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2,17打印出 50个学生中成绩高于 80分者的学号和成绩。
用伪代码表示算法如下：
BEGIN （ 算法开始）
1=>i
while i＜＝ 50
｛ input ni and gi
i+1=>i}
1＝ i
while i<＝ 50
{ if gi>=80 Print ni and gi
i+1=>i}
END （ 算法结束）
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.4.6用计算机语言表示算法
求 5!,用 C语言表示：
main()
{ int i,t;
t=1;
i=2;
while (i<=5)
{ t=t*i;
i=i+1;
}
printf(―%d‖,t);
}
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作例 2.21将例 2.19表示的算法（求级数的值）用 C语言表示。
main（）
{ int sign=1;
float deno=2.0,sum=1.0,term;
while (deno<=100)
{ sign=-sign;
term=sign/deno;
sum=sum+term;
deno=deno+1;
}
printf(―%f‖,sum);
}
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作
2.5结构化程序设计方法
前面介绍了结构化的算法和三种基本结构。一个结构化程序就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、阅读、修改和维护。这就减少了程序出错的机会，提高了程序的可靠性，保证了程序的质量。
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。怎样才能得到一个结构化的程序呢时 n果我们面临一个复杂的问题，是难以一下子写出～个层次分明、结构清晰、算法正确的程序的。
结构化程序设计方法的基本思路是，把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作结构化程序设计方法
具体说，采取以下方法保证得到结构化的程序
（ 1）自顶向下；
（ 2）逐步细化；
（ 3）模块化设计；
（ 4）结构化编码。
在接受一个任务后应怎样着手进行呢？有两种不同的方法：
一种是自顶向下，逐步细化；
一种是自下而上，逐步积累。
用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫做“自顶向下，逐步细化”。
返回下一页上一页第 2章 程序的灵魂 —算法 计算机系 彭金莲 制作自顶向下、逐步细化
