2.1 算法的概念
2.2 简单算法举例
2.3 算法的特性
2.4 怎样表示一个算法
2.5 结构化程序设计方法习题第 2章 程序的灵魂 ——算法一个程序应包括以下两方面内容,
(1) 对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构 (data structure)。
(2) 对操作的描述。即操作步骤,也就是算法
(algorithm)。
数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，
必须认真考虑和设计数据结构和操作步骤 (即算法 )。
因此，著名计算机科学家沃思 (Nikiklaus Wirth)提出一个公式数据结构 + 算法 = 程序实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：
程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境也就是说，以上 4个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的知识。在这 4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。
我们的目的是使读者通过学习本书，能够知道怎样编写一个 C程序，并且能够编写出不太复杂的 C程序。书中将通过一些实例把以上 4个方面的知识结合起来，介绍如何编写一个 C程序。
由于算法的重要性，在本章中先介绍有关算法的初步知识，以便为后面各章的学习建立一定的基础。
2.1 算 法 的 概 念从事各种工作和活动，都必须事先想好进行的步骤，
然后按部就班地进行，才能避免产生错乱。
不要认为只有“计算”的问题才有算法。广义地说，
为解决一个问题而采取的方法和步骤，就称为
“算法”。
对同一个问题，可以有不同的解题方法和步骤。方法有优劣之分。有的方法只需进行很少的步骤，
而有些方法则需要较多的步骤。一般说，希望采用简单的和运算步骤少的方法。因此,为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。
本书所关心的当然只限于计算机算法，即计算机能执行的算法。
计算机算法可分为两大类别：数值算法和非数值算法。数值运算的目的是求数值解 。非数值运算包括的面十分广泛，最常见的是用于事务管理领域。
目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模型，可以运用数值分析方法，因此对数值运算的算法研究比较深入，算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册 (写成程序形式 )，或者将这些程序存放在磁盘或磁带上，供用户调用。
而非数值运算的种类繁多，要求各异，难以规范化，
因此只对一些典型的非数值运算算法 (例如排序算法 )作比较深入的研究。其他的非数值运算问题，
往往需要使用者参考已有的类似算法重新设计解决特定问题的专门算法。
本书不可能罗列所有算法，只是想通过一些典型算法的介绍，帮助读者了解如何设计一个算法，推动读者举一反三。希望读者通过本章介绍的例子了解怎样提出问题，怎样思考问题，怎样表示一个算法。
2.2 简单算法举例例 2.1 求 1× 2× 3× 4× 5。
可以用最原始的方法进行。
步骤 1,先求 1× 2，得到结果 2。
步骤 2,将步骤 1得到的乘积 2再乘以 3，得到结果 6。
步骤 3,将 6再乘以 4，得 24。
步骤 4,将 24再乘以 5，得 120。这就是最后的结果。
这样的算法虽然是正确的，但太繁琐。如果要求
1× 2× … × 1000，则要写 999个步骤，显然是不可取的。而且每次都直接使用上一步骤的数值结果
(如 2,6,24等 )，也不方便。应当找到一种通用的表示方法。
可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设 p为被乘数,i为乘数。用循环算法来求结果。可以将算法改写如下：
S1,使 p=1
S2,使 i=2
S3,使 p× i，乘积仍放在变量 p中，可表示为
p× i=>p
S4,使 i的值加 1，即 i+1 => i
S5,如果 i不大于 5，返回重新执行步骤 S3以及其后的步骤 S4和 S5；否则，算法结束。最后得到 p的值就是 5!的值。
上面的 S1,S2… 代表步骤 1，步骤 2……S 是 step(步 )
的缩写。这是写算法的习惯用法。
请读者仔细分析这个算法，能否得到预期的结果。
显然这个算法比前面列出的算法简练。
如果题目改为求 1× 3× 5× 7× 9× 11。
算法只需作很少的改动即可：
S1,1=>p
S2,3=>i
S3,p× i=>p
S4,i+2=>i
S5,若 i≤11，返回 S3； 否则，结束。
可以看出，用这种方法表示的算法具有通用性、灵活性。 S3到 S5组成一个循环，在实现算法时，要反复多次执行 S3,S4,S5等步骤，直到某一时刻，
执行 S5步骤时经过判断，乘数 i已超过规定的数值而不返回 S3步骤为止。此时算法结束，变量 p的值就是所求结果。
由于计算机是高速进行运算的自动机器，实现循环是轻而易举的，所有计算机高级语言中都有实现循环的语句。因此，上述算法不仅是正确的，而且是计算机能实现的较好的算法。
请读者仔细分析循环结束的条件，即 S5步骤。如果在求 1× 2× … × 11时，将 S5步骤写成
S5,若 i＜ 11，返回 S3。
这样会有什么问题?会得到什么结果?
例 2.2 有 50个学生，要求将他们之中成绩在 80分以上者打印出来。用 n表示学生学号,n1代表第一个学生学号,ni代表第 i个学生学号。用 g代表学生成绩，
gi代表第 i个学生成绩，算法可表示如下。
S1,1=>i
S2：如果 gi≥80，则打印 ni和 gi，否则不打印
S3,i+1=>i
S4：如果 i≤50，返回 S2，继续执行；否则，算法结束。
本例中，变量 i作为下标，用它来控制序号 (第几个学生，第几个成绩 )。当 i超过 50时，表示已对 50个学生的成绩处理完毕，算法结束。
例 2.3 判定 2000—2500年中的每一年是否闰年，将结果输出。
闰年的条件是,①能被 4整除，但不能被 100整除的年份都是闰年，如 1996年,2004年是闰年；②能被 100整除，又能被 400整除的年份是闰年。如
1600年,2000年是闰年。不符合这两个条件的年份不是闰年。
算法可表示如下：
设 y 为被检测的年份。可采取以下步骤：
S1,2000=>y
S2,y不能被 4整除，则输出 y ―不是闰年”。然后转到 S6
S3：若 y能被 4整除，不能被 100整除，则输出 y ―是闰年”。然后转到 S6
S4：若 y能被 100整除，又能被 400整除，输出 y―是闰年”；否则输出“不是闰年”。 然后转到 S6
S5：输出 y ―不是闰年”
S6,y+1=>y
S7：当 y≤2500时，转 S2继续执行，如 y＞ 2500，算法停止。
在这个算法中，采取了多次判断。先判断 y能否被 4
整除，如不能，则 y必然不是闰年。如 y 能被 4整除，
并不能马上决定它是否闰年，还要看它能否被 100
整除。如不能被 100整除，则肯定是闰年 (例如 1996
年 )。如能被 100整除，还不能判断它是否闰年，还要被 400整除，如果能被 400整除，则它是闰年，
否则不是闰年。
在这个算法中，每做一步，都分别分离出一些范围
(巳能判定为闰年或非闰年 )，逐步缩小范围，使被判断的范围愈来愈小，直至执行 S5时，只可能是非闰年。见图 2.1示意。
图 2.1
从图 2.1可以看出：“其他”这一部分，包括能被 4
整除，又能被 100整除，而不能被 400整除的那些年份 (如 1900年 ),是非闰年。
在考虑算法时，应当仔细分析所需判断的条件，如何一步一步缩小被判断的范围。有的问题，判断的先后次序是无所谓的，而有的问题，判断条件的先后次序是不能任意颠倒的，读者可根据具体问题决定其逻辑。
例 2.4 求 1-1/2+1/3-1/4+…+1/99 -1/100。
算法可以表示如下：
S1,1=>sign
S2,1=>sum
S3,2=>deno
S4,(-1)× sign=>sign
S5,sign× (1/deno)=>term
S6,sum+term=>sum
S7,deno+1=>deno
S8：若 deno≤100返回 S4；否则算法结束。
在步骤 S1中先预设 sign（代表级数中各项的符号，
它的值为 1或 -1）。在步骤 S2中使 sum等于 1,相当于已将级数中的第一项放到了 sum中。在步骤 S3中使分母的值为 2。在步骤 S4中使 sign的值变为 -1。
在步骤 S5中求出级数中第 2项的值 -1/2。在步骤 S6
中将刚才求出的第二项的值 -1/2累加到 sum中。至此,sum的值是 1-1/2。在步骤 S7中使分母 deno的值加 1（变成 3）。执行 S8步骤，由于 deno≤100，
故返回 S4步骤,sign的值改为 1，在 S5中求出 term
的值为 1/3，在 S6中将 1/3累加到 sum中。然后 S7再使分母变为 4。按此规律反复执行 S4到 S8步骤，直到分母大于 100为止。一共执行了 99次循环，向
sum累加入了 99个分数。 sum最后的值就是级数的值。
例 2.5 对一个大于或等于 3的正整数，判断它是不是一个素数。
所谓素数，是指除了 1和该数本身之外，不能被其他任何整数整除的数。例如,13是素数，因为它不能被 2,3,4,…,12整除。
判断一个数 n(n≥3)是否素数的方法是很简单的：将 n
作为被除数，将 2到 (n-1)各个整数轮流作为除数，
如果都不能被整除，则 n为素数。
算法可以表示如下：
S1：输入 n的值
S2,2=>i （ i作为除数）
S3,n被 i除，得余数 r
S4：如果 r=0，表示 n能被 i整除，则打印 n―不是素数”，算法结束；否则执行 S5
S5,i+1=>i
S6：如果 i≤n-1，返回 S3；否则打印 n ―是素数”，
然后结束。
实际上 n不必被 2到 (n-1)的整数除，只需被 2到 n的开方间整数除即可，甚至只需被 2到 n之间的整数除即可。例如，判断 13是否素数，只需将 13被 2,3
除即可，如都除不尽,n 必为素数。 S6步骤可改为：
S6：如果 i≤n，返回 S2；否则算法结束。
通过以上几个例子，可以初步了解怎样设计一个算法。
2.3 算法的特性一个算法应该具有以下特点：
1.有穷性一个算法应包含有限的操作步骤，而不能是无限的。
事实上，“有穷性”往往指“在合理的范围之内”。
究竟什么算“合理限度”，并无严格标准，由人们的常识和需要而定。
2.确定性算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。
3.有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。
4,有一个或多个输出算法的目的是为了求解，“解” 就是输出。没有输出的算法是没有意义的。
5,有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果。
对于不熟悉计算机程序设计的人来说，他们可以只使用别人已设计好的现成算法，只需根据算法的要求给以必要的输入，就能得到输出的结果。对他们来说，算法如同一个“黑箱子”一样,他们可以不了解“黑箱子”中的结构，只是从外部特性上了解算法的作用，即可方便地使用算法。例如，对一个“输入 3个数，求其中最大值”的算法，
可以用图 2.2表示，只要输入 a,b,c3个数，执行算法后就能得到其中最大的数。但对于程序设计人员来说，必须会设计算法，并且根据算法编写程序。
图 2.2
2.4 怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的有自然语言、传统流程图、结构化流程图、伪代码、
PAD图等。
2.4.1 用自然语言表示算法在 2.2节中介绍的算法是用自然语言表示的。用自然语言表示通俗易懂，但文字冗长,容易出现“歧义性”。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。此外，用自然语言描述包含分支和循环的算法，不很方便 (如例
2.5的算法 )。因此，除了很简单的问题以外，一般不用自然语言描述算法。
2.4.2 用流程图表示算法流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会
ANSI(American National Standard Institute)规定了一些常用的流程图符号 (见图 2.3)。
图 2.3中菱形框的作用是对一个给定的条件进行判断，
根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。见图 2.4。
连接点 (小圆圈 )是用于将画在不同地方的流程线连接起来。如图 2.5中有两个以○为标志的连接点 (在连接点圈中写上,1‖)，它表示这两个点是互相连接在一起的。实际上它们是同一个点，只是画不下才分开来画。用连接点，可以避免流程线的交叉或过长，使流程图清晰。
图 2.3
图 2.4 图 2.5
下面对 2.2节中所举的几个算法例子，改用流程图表示。
例 2.6 将例 2.1求 5!的算法用流程图表示，流程图见图
2.6。
菱形框两侧的,Y‖和,N‖代表“是” (yes)和
“否” (no)。如果需要将最后结果打印出来，可以在菱形框的下面再加一个输出框，见图 2.7。
例 2.7 将例 2.2的算法用流程图表示。将 50名学生中成绩在 80分以上者的学号和成绩打印出来，见图 2.8。
在此算法中没有包括输入 50个学生数据的部分，
如果包括这个输入数据的部分，流程图如图 2.9所示。
图 2.6 图 2.7 图 2.8
例 2.8 将例 2.3判定闰年的算法用流程图表示。
见图 2.10。显然，用图 2.10表示算法要比用文字描述算法逻辑清晰、易于理解。
请读者考虑，如果例 2.3所表示的算法中,S2步骤内没有最后“转到 S6‖这一句话，而只是
S2：若 y不能被 4整除，则打印 y ―不是闰年”
这样就意味着执行完 S2步骤后，不论 S2的执行情况如何都应执行 S3步骤。请读者画出相应的流程图。
请思考这样的算法在逻辑上有什么错误，从流程图上是很容易发现其错误的。
图 2.9 图 2.10
例 2.9 将例 2.4的算法用流程图表示。见图 2.11。
例 2.10 将例 2.5判断素数的算法用流程图表示，见图
2.12。
一个流程图包括以下几部分：①表示相应操作的框；
②带箭头的流程线；③框内外必要的文字说明。
需要提醒的是流程线不要忘记画箭头，因为它是反映流程的执行先后次序的。
用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。但是这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。在结构化程序设计方法推广之后，许多书刊已用 N-S结构化流程图代替这种传统的流程图。但是每一个程序编制人员都应当熟练掌握传统流程图。
图 2.11 图 2.12
2.4.3 三种基本结构和改进的流程图
1,传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。这种情况如图 2.13所示。
这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。如果我们写出的算法能限制流程的无规律任意转向，阅读起来就很方便。
图 2.13
但是，算法上难免会包含一些分支和循环，而不可能全部由一个一个框顺序组成。例如图 2.6到图
2.12都不是由各框顺序进行的，都包含一些流程的向前或向后的非顺序转向。为了解决这个问题，
人们设想，规定出几种基本结构，然后由这些基本结构按一定规律组成一个算法结构 (如同用一些基本预制构件来搭成房屋一样 )，整个算法的结构是由上而下地将各个基本结构顺序排列起来的。
如果能做到这一点,算法的质量就能得到保证和提高。
2,三种基本结构
1966年,Bohra和 Jacopini提出了以下三种基本结构，
作为表示一个良好算法的基本单元。
(1) 顺序结构，如图 2.14所示，虚线框内是一个顺序结构。
(2) 选择结构，或称选取结构，或称分支结构，如图
2.15所示。
请注意，无论 p 条件是否成立，只能执行 A框或 B框之一，不可能既执行 A框又执行 B框。无论走哪一条路径，在执行完 A或 B之后，都经过 b点，然后脱离本选择结构。 A或 B两个框中可以有一个是空的,即不执行任何操作，如图 2.16所示。
图 2.14 图 2.15 图 2.16
(3) 循环结构，它又称重复结构。有两类循环结构：
① 当型 (While型 )循环结构见图 2.17(a)。它的功能是当给定的条件 p1成立时，
执行 A框操作，执行完 A后，再判断条件 p1是否成立，如果仍然成立，再执行 A框，如此反复执行 A
框，直到某一次 p1条件不成立为止，此时不执行 A
框，而从 b点脱离循环结构。
② 直到型 (Until型 )循环见图 2.17(b)。它的功能是先执行 A框，然后判断给定的 p2条件是否成立，如果 p2条件不成立，则再执行 A，然后再对 p2条件作判断，如果 p2条件仍然不成立，又执行 A…… 如此反复执行 A，直到给定的
p2条件成立为止，此时不再执行 A，从 b点脱离本循环结构。
图 2.18是当型循环的应用例子，图 2.19是直到型循环的应用例子。
图 2.17 图 2.18 图 2.19
图 2.18和图 2.19的作用都是打印 5个数,1,2,3,4，
5。可以看到,对同一个问题既可以用当型循环来处理，也可以用直到型循环来处理。
以上三种基本结构，有以下共同特点：
(1) 只有一个入口。
(2) 只有一个出口。请注意，一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。
(3) 结构内的每一部分都有机会被执行到。对每一个框来说，都应有一条从入口到出口的路径通过它。
图 2.20中没有一条从入口到出口的路径通过 A框。
(4) 结构内不存在“死循环” (无终止的循环 )。图
2.21就是一个死循环。
图 2.20 图 2.21
已经证明，由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。
其实，基本结构不一定只限于上面三种，只要具有上述 4个特点的都可以作为基本结构。人们可以自己定义基本结构，并由这些基本结构组成结构化程序。例如，可以将图 2.22和图 2.23这样的结构定义为基本结构。图 2.23所示的是一个多分支选择结构，根据给定的表达式的值决定执行哪一个框。
图 2.22和图 2.23虚线框内的结构也是一个入口和一个出口，并且有上述全部的 4个特点。由它们构成的算法结构也是结构化的算法。但是，可以认为像图 2.22和图 2.23那样的结构是由三种基本结构派生出来的。因此，人们都普遍认为最基本的是本节介绍的三种基本结构。
图 2.22 图 2.23
2.4.4 用 N-S流程图表示算法既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么基本结构之间的流程线就属多余的了。
1973年美国学者 I.Nassi和 B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，
在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称 N-S结构化流程图。这种流程图适于结构化程序设计，因而很受欢迎。
N-S流程图用以下的流程图符号：
(1) 顺序结构,用图 2.24形式表示。 A和 B两个框组成一个顺序结构。
(2) 选择结构：用图 2.25表示。它与图 2.15相应。当 p
条件成立时执行 A操作,p不成立则执行 B操作。
请注意图 2.25是一个整体，代表一个基本结构。
图 2.24 图 2.25
(3) 循环结构,当型循环结构用图 2.26形式表示。
图 2.26表示当 p1条件成立时反复执行 A操作，直到 p1
条件不成立为止。
直到型循环结构用图 2.27形式表示。
用以上 3种 N-S流程图中的基本框，可以组成复杂的
N-S流程图，以表示算法。
应当说明，在图 2.24、图 2.25、图 2.26、图 2.27中的 A
框或 B框，可以是一个简单的操作 (如读入数据或打印输出等 )，也可以是 3个基本结构之一。例如，
图 2.24所示的顺序结构，其中的 A框可以又是一个选择结构,B框可以又是一个循环结构。如图 2.28
所示那样，由 A和 B这两个基本结构组成一个顺序结构。
图 2.26 图 2.27 图 2.28
通过下面的几个例子，读者可以了解如何用 N-S流程图表示算法。
例 2.11 将例 2.1的求 5!算法用 N-S图表示。见图 2.29，
它和图 2.7对应。
例 2.12 将例 2.2的算法用 N-S图表示。将 50名 学生中成绩高于 80分的学号和成绩打印出来。见图 2.30和图 2.31，它们与图 2.8和图 2.9对应。
例 2.13 将例 2.3判定闰年的算法用 N-S图表示。见图
2.32，它和图 2.10对应。
例 2.14 将例 2.4的算法用 N-S图表示。见图 2.33，它和图 2.11对应，只是最后加了一个“打印 sum‖框。
例 2.15 将例 2.5判别素数的算法用 N-S流程图表示。
图 2.29 图 2.30 图 2.31
图 2.32 图 2.33
由图 2.12可以看出，这个流程图不是由三种基本结构组成的。图中间那个循环部分，有两个出口 (一个从第二个菱形框下面出口，另一个在第一个菱形框右边出口 )，不符合基本结构的特点。由于不能分解为三种基本结构，就无法直接用 N-S流程图的三种基本结构的符号来表示。因此，应当先对图 2.12做必要的变换。要将第一个菱形框 (―r=0‖)的两个出口汇合在一点，以解决两个出口问题。当
r=0时不直接输出 n―不是素数”，而只设一个标志值（变量 w），它的初始状态为 w=0。当 r=0时 (表示 n为非素数 )使 w变成 1。如果 r ≠0则保持 w=0。 w
的作用如同一个开关，有两个工作状况,w=0和
w=1。 w=1表示 n为非素数。
如果最终 w=0，则表示 n为素数。然后将,1=>w‖框的出口线改为指向第二个菱形框，同时将第二个菱形框中的条件改为,i≤n和 w=0‖，即只有当
,i≤n‖和,w=0‖两个条件都满足时才继续执行循环。如果出现 i＞ n或 w≠0之一，都不会继续执行循环 (见图 2.34)。如果在某一次 r=0，则应执行 1=>w，
然后，由第二个菱形框判断为“条件不成立”，
接着执行图下部的选择结构。此时,w≠0，表示 n
不是素数，应打印出 n不是素数的信息。如果 w=0，
则表示在上面的每次循环中,n都不能被每一个 i整除，所以 n是素数，故输出 n是素数的信息。
图 2.34已由三种基本结构组成，可以用 N-S图表示此算法，见图 2.35。注意图 2.34直到型循环的判断条件为：,直到 i＞ n或 w≠0‖，即只要,i＞ n或 w≠0‖
之一成立，就不再继续执行循环。对此务请读者弄清楚。
通过以上例子，可以看出用 N-S图表示算法的优点。
它比文字描述直观、形象,易于理解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的。 N-S流程图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进行就可以了，十分方便。
用 N-S图表示的算法都是结构化的算法 (它不可能出现流程无规律的跳转，而只能自上而下地顺序执行 )。
图 2.34 图 2.35
归纳起来可知，一个结构化的算法是由一些基本结构顺序组成的；每个基本结构又可以包含其他的基本结构；在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内 (如循环中流程的跳转 )；一 个非结构化的算法
(如图 2.12)可以用一个等价的结构化算法 (如图 2.35)
代替，其功能不变。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。
N-S图如同一个多层的盒子，又称盒图 (box diagram)。
2.4.5 用伪代码表示算法用传统的流程图和 N-S图表示算法，直观易懂，但画起来比较费事。因此，流程图适宜表示一 个算法，
但在设计算法过程中使用不是很理想。为了设计算法时方便，常用一种称为伪代码 (pseudo code)的工具。
伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章，自上而下地写下来。每一行 (或几行 )表示一个基本操作。它不用图形符号，因此书写方便,格式紧凑，也比较好懂，便于向计算机语言算法 (即程序 )过渡。
例如,“打印 x的绝对值”的算法可以用伪代码表示如下：
IF x is positive THEN
print x
ELSE
print –x
它像一个英语句子一样好懂，在国外用得比较普遍。
也可以用汉字伪代码，如：
若 x为正打印 x
否则打印 –x
也可以中英文混用，如：
IF x 为正
print x
ELSE
print –x
即计算机语言中具有的语句关键字用英文表示，其他的可用汉字表示。总之，以便于书写和阅读为原则。用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。
将例 2.1到例 2.5的算法用伪代码表示如下。
例 2.16 求 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(算法结束 )
在本算法中采用当型循环（第 3行到笫 5行是一个当型循环）。 while意思为“当”,它表示当 i<=5时执行循环体（大括弧中的两行）的操作。
例 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.18 打印 2000—2500年中的每一年是否闰年。
用伪代码表示算法如下：
BEGIN(算法开始 )
2000=>y
while y<=2500
{if y 被 4整除
if y 不被 100整除
print y; ―是闰年”
else
if y 被 400整除
print y；“闰年”
else
print y；“非闰年”
end if
end if
else
print y; ―非闰年”
end if
y+1=>y
}
END(算法结束 )
例 2.19求 1-1/2+1/3-1/4+…+1/99 -1/100。
用伪代码表示的算法如下：
BEGIN (算法开始 )
1=> sum
2=> deno
1=> sign
while deno <= 100
{(-1)× sign=>sign
sign× 1/deno=>term
sum+term=>sum
deno+1=>deno
}
print sum
END (算法结束 )
从以上例子可以看到：伪代码书写格式比较自由，
容易表达出设计者的思想。同时，用伪代码写的算法很容易修改。用伪代码很容易写出结构化的算法。例如上面几个例子都是结构化的算法。但是用伪代码写算法不如流程图直观，可能会出现逻辑上的错误 (例如循环或选择结构的范围搞错等 )。
以上介绍了常用的表示算法的几种方法，在程序设计中读者可以根据需要和习惯任意选用。软件专业人员一般习惯使用伪代码，考虑到国内广大初学人员的情况，为便于理解，本书在以后各章中主要采用形象化的 N-S图表示算法。但是，读者对其他方法也应有所了解，以便在阅读其他书刊时不致发生困难。
2.4.6 用计算机语言表示算法要完成一件工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。因此，不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。
至今为止，我们只是描述算法，即用不同的形式表示操作的步骤。而要得到运算结果，就必须实现算法。在例 2.1,例 2.6、例 2.11和例 2.16中用不同的形式表示了求 5!的算法，但是并没有真正求出 5!
的值。实现算法的方式可能不止一种。例如对例
2.1表示的算法可以用人工心算的方式实现而得到结果，也可以用笔算或算盘、计算器求出结果，
这就是实现算法。
我们的任务是用计算机解题，也就是要用计算机实现算法。计算机是无法识别流程图和伪代码的。
只有用计算机语言编写的程序才能被计算机执行
（当然还要经过编译成目标程序才能被计算机识别和执行）。因此，在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序。
用计算机语言表示算法必须严格遵循所用语言的语法规则，这是和伪代码不同的。我们将前面介绍过的算法用 C语言表示。
例 2.20 将例 2.16表示的算法（求 5!）用 C语言表示。
main( )
{int i,t;
t=1;
i=2;
while(i<=5)
{t=t*i;
i=i+1;
}
printf("%d",t);
}
例 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);
}
在这里，不打算仔细介绍以上程序的细节，读者只需大体看懂它即可。在以后各章中会详细介绍 C语言有关的使用规则。
应当强调说明的是，写出了 C程序，仍然只是描述了算法，并未实现算法，只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。
2.5 结构化程序设计方法前面介绍了结构化的算法和三种基本结构。一个结构化程序就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，
这种程序便于编写、阅读、修改和维护。这就减少了程序出错的机会，提高了程序的可靠性。
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。如果面临一个复杂的问题，是难以一下子写出一个层次分明、结构清晰、
算法正确的程序的。结构化程序设计方法的基本思路是，把一个复杂问题的求解过程分阶段进行，
每个阶段处理的问题都控制在人们容易理解和处理的范围内。
具体说，采取以下方法保证得到结构化的程序。
(1) 自顶向下； (2) 逐步细化； (3) 模块化设计； (4) 结构化编码。
在接受一个任务后应怎样着手进行呢?有两种不同的方法：一种是自顶向下，逐步细化；一种是自下而上，逐步积累。以写文章为例来说明这个问题。
有的人胸有全局，先设想好整个文章分成哪几个部分，然后再进一步考虑每一部分分成哪几节，
每一节分成哪几段，每一段应包含什么内容，如图 2.36示意。
用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。
图 2.36
另有些人写文章时不拟提纲，如同写信一样提起笔就写，想到哪里就写到哪里，直到他认为把想写的内容都写出来了为止。这种方法叫做“自下而上，逐步积累”。
显然，用第一种方法考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分，修改有关段落即可，与其他部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。
我们应当掌握自顶向下、逐步细化的设计方法。这种设计方法的过程是将问题求解由抽象逐步具体化的过程。例如图 2.36所示。
用这种方法便于验证算法的正确性，在向下一层展开之前应仔细检查本层设计是否正确，只有上一层是正确的才能向下细化。如果每一层设计都没有问题，则整个算法就是正确的。由于每一层向下细化时都不太复杂，因此容易保证整个算法的正确性。检查时也是由上而下逐层检查，这样做，
思路清楚，有条不紊地一步一步进行，既严谨又方便。
举一个例子来说明这种方法的应用。
例 2.22 将 1到 1000之间的素数打印出来。
我们已在本章中讨论过判别素数的方法，现在采用
“筛法”来求素数表。所谓“筛法”指的是“埃拉托色尼 (Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是,在一张纸上写上 1到
1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数，见图 2.37。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49 50……
图 2.37
具体做法如下：
(1) 先将 1挖掉 (因为 1不是素数 )。
(2) 用 2去除它后面的各个数，把能被 2整除的数挖掉，
即把 2的倍数挖掉。
(3) 用 3去除它后面各数，把 3的倍数挖掉。
(4) 分别用 4,5… 各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如在图 2.37中找 1～ 50的素数，要一直进行到除数为 47为止。 (事实上，可以简化，如果需要找 1～ n范围内素数表，只需进行到除数为 n
开方 (取其整数 ) 即可。例如对 1～ 50，只需进行到将 7(50开方 )作为除数即可。 )
上面的算法可表示为：
(1) 挖去 1；
(2) 用下一个未被挖去的数 p去除 p后面各数，把 p的倍数挖掉；
(3) 检查 p是否小于 n的整数部分 (如果 n=1000，则检查 p＜ 31?),如果是，则返回 (2) 继续执行，否则就结束；
(4) 纸上剩下的数就是素数。
解题的基本思路有了，但要变成计算机的操作，还要做进一步的分析，如怎样判断一个数是否已被
“挖掉”，怎样找出某一个数 p的倍数，怎样打印出未被挖掉的数。
用自顶向下逐步细化的方法来处理这个问题，先进行“顶层设计”，见图 2.38。也可以用流程图进行逐步细化。流程图 2.39表示流程的粗略情况，把要做的三部分工作分别用 A,B,C表示。
图 2.38 图 2.39
这三部分还不够具体，要进一步细化。 A部分可以细化为图 2.40。先输入 n，然后将 1输入给 x1,2输入给 x2,1000输入给 x1000。
B部分可以细化为图 2.41。
图 2.40 图 2.41
图 2.41中的 B1与 B2不能再分了。 B1处理的方法是：使
x1=0，即哪个数不是素数,就使它等于 0，以后把不等于零的数打印出来就是所求的素数表。 B3中的循环体内以 D标志的部分还要进一步细化，对 D
细化为图 2.42。
图 2.42中的 E部分还不够具体，再进一步细化为图
2.43。图 2.43中的 F部分又细化为图 2.44。因为首先要判断某一个 xj是否已被挖掉，如已被挖掉则不必考虑被 xi除。至此，已不能也不需要再分解了。
再对图 2.39中的 C部分进行细化，见图 2.45。
对图 2.45中的 G部分进行细化，得图 2.46。
图 2.42 图 2.43 图 2.44
图 2.45 图 2.46
至此，已将图 2.39分解成为能用三种基本结构表示的基本操作了。将以上这些图合起来得到总的流程图，见图 2.47。
根据这个细化了的流程图已经可以用任何高级语言编写出源程序了。
以上是用流程图表示逐步细化的过程，如果题目复杂，则画许多分流程图也是比较费事的。 本例为了说明问题把细化过程分解得比较细，如果技巧熟悉些，可以精简一些步骤。例如从图 2.39的 C部分可以直接画出图 2.47的 C部分，而不必经过图
2.45和图 2.46。
图 2.47
也可以用伪代码来描述逐步细化过程，由于不需要画流程图，因此便于修改。例如，想对,打印全部素数”这一句话细化，只需将这句擦掉，在原处填入细化了的伪代码语句即可，或者将它向右展开，逐级细化。例如：
输入 1～ n各数 ……
把所有非素数去掉 ……
打印全部素数
i=1
while i≤n
{把未挖的 xi打印出来（ if xi不等于 0 then print xi ）
i=i+1}
对熟悉伪代码的人来说，可能这样更方便些。
在程序设计中常采用模块设计的方法，尤其是当程序比较复杂时，更有必要。在拿到一个程序模块
(实际上是程序模块的任务书 ) 以后，根据程序模块的功能将它划分为若干个子模块，如果嫌这些子模块的规模大，还可以划分为更小的模块。这个过程采用自顶向下的方法来实现。
程序中的子模块在 C语言中通常用函数来实现。例如在上例中，可以将图 2.39的 A,B,C三部分分别作为三个子模块，用三个函数来实现。
程序中的子模块一般不超过 50行，即打印时不超过一页，这样的规模便于组织，也便于阅读。划分子模块时应注意模块的独立性，即使一个模块完成一项功能,耦合性愈少愈好。
模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。
可以看到，结构化程序设计方法用来解决人脑思维能力的局限性和所处理问题的复杂性之间的矛盾。
在设计好一个结构化的算法之后，还要善于进行结构化编码。即用高级语言语句正确地实现三种基本结构。如果所用的语言是结构化的语言 (如
PASCAL,C,QBASIC,Ada等 ),则直接有与三种基本结构对应的语句，进行结构化编程序是不困难的。
本章内容十分重要,是学习后面各章的基础。学习程序设计的目的不只是学习一种特定的语言，而是学习进行程序设计的一般方法。掌握了算法就是掌握了程序设计的灵魂，再学习有关的计算机语言知识，就能够顺利地编写出任何一种语言的程序。脱离具体的语言去学习程序设计是困难的。
但是，学习语言只是为了设计程序，它本身决不是目的。千万不能拘泥于一种具体的语言，而应能举一反三。如前所述，关键是设计算法。有了正确的算法，用任何语言进行编码都不应当有什么困难。在本章中只是初步介绍了有关算法的知识，并没有深入介绍如何设计各种类型的算法。
我们将在以后各章中结合程序实例陆续介绍有关算法。
习题
2.1 什么是算法?试从日常生活中找 3个例子，描述它们的算法。
2.2 什么叫结构化的算法?为什么要提倡结构化的算法?
2.3 试述三种基本结构的特点，你能否自己另外设计两种基本结构 (要符合基本结构的特点 )。
2.4 用传统流程图表示求解以下问题的算法。
(1) 有两个瓶子 A和 B，分别盛放醋和酱油，要求将它们互换 (即 A瓶原来盛醋，现改盛酱油,B瓶则相反 )。
(2) 依次将 10个数输入，要求将其中最大的数打印出来。
(3) 有 3个数 a,b,c，要求按大小顺序把它们打印出来。
(4) 求 1+2+3+…+100 。
(5) 判断一个数 n能否同时被 3和 5整除。
(6) 将 100～ 200之间的素数打印出来。
(7) 求两个数 m和 n的最大公约数。
(8) 求方程式 ax2+bx+c=0的根。分别考虑：①有两个不等的实根；②有两个相等的实根。
2.5 用 N-S图表示 2.4题中各题的算法。
2.6 用伪代码表示 2.4题中各题的算法。
2.7 什么叫结构化程序设计?它的主要内容是什么?
2.8 用自顶向下、逐步细化的方法进行以下算法的设计：
(1) 打印出 1900—2000年中是闰年的年份，闰年的条件是：①能被 4整除但不能被 100整除；或②能被
100整除且能被 400整除。
(2) 求 ax2+bx+c=0的根。分别考虑 d=b2-4ac大于 0、等于 0和小于 0三种情况。
(3) 输入 10个数，找出最大的一个数，并打印出来。
2.2 简单算法举例
2.3 算法的特性
2.4 怎样表示一个算法
2.5 结构化程序设计方法习题第 2章 程序的灵魂 ——算法一个程序应包括以下两方面内容,
(1) 对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构 (data structure)。
(2) 对操作的描述。即操作步骤,也就是算法
(algorithm)。
数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，
必须认真考虑和设计数据结构和操作步骤 (即算法 )。
因此，著名计算机科学家沃思 (Nikiklaus Wirth)提出一个公式数据结构 + 算法 = 程序实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：
程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境也就是说，以上 4个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的知识。在这 4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。
我们的目的是使读者通过学习本书，能够知道怎样编写一个 C程序，并且能够编写出不太复杂的 C程序。书中将通过一些实例把以上 4个方面的知识结合起来，介绍如何编写一个 C程序。
由于算法的重要性，在本章中先介绍有关算法的初步知识，以便为后面各章的学习建立一定的基础。
2.1 算 法 的 概 念从事各种工作和活动，都必须事先想好进行的步骤，
然后按部就班地进行，才能避免产生错乱。
不要认为只有“计算”的问题才有算法。广义地说，
为解决一个问题而采取的方法和步骤，就称为
“算法”。
对同一个问题，可以有不同的解题方法和步骤。方法有优劣之分。有的方法只需进行很少的步骤，
而有些方法则需要较多的步骤。一般说，希望采用简单的和运算步骤少的方法。因此,为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。
本书所关心的当然只限于计算机算法，即计算机能执行的算法。
计算机算法可分为两大类别：数值算法和非数值算法。数值运算的目的是求数值解 。非数值运算包括的面十分广泛，最常见的是用于事务管理领域。
目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模型，可以运用数值分析方法，因此对数值运算的算法研究比较深入，算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册 (写成程序形式 )，或者将这些程序存放在磁盘或磁带上，供用户调用。
而非数值运算的种类繁多，要求各异，难以规范化，
因此只对一些典型的非数值运算算法 (例如排序算法 )作比较深入的研究。其他的非数值运算问题，
往往需要使用者参考已有的类似算法重新设计解决特定问题的专门算法。
本书不可能罗列所有算法，只是想通过一些典型算法的介绍，帮助读者了解如何设计一个算法，推动读者举一反三。希望读者通过本章介绍的例子了解怎样提出问题，怎样思考问题，怎样表示一个算法。
2.2 简单算法举例例 2.1 求 1× 2× 3× 4× 5。
可以用最原始的方法进行。
步骤 1,先求 1× 2，得到结果 2。
步骤 2,将步骤 1得到的乘积 2再乘以 3，得到结果 6。
步骤 3,将 6再乘以 4，得 24。
步骤 4,将 24再乘以 5，得 120。这就是最后的结果。
这样的算法虽然是正确的，但太繁琐。如果要求
1× 2× … × 1000，则要写 999个步骤，显然是不可取的。而且每次都直接使用上一步骤的数值结果
(如 2,6,24等 )，也不方便。应当找到一种通用的表示方法。
可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设 p为被乘数,i为乘数。用循环算法来求结果。可以将算法改写如下：
S1,使 p=1
S2,使 i=2
S3,使 p× i，乘积仍放在变量 p中，可表示为
p× i=>p
S4,使 i的值加 1，即 i+1 => i
S5,如果 i不大于 5，返回重新执行步骤 S3以及其后的步骤 S4和 S5；否则，算法结束。最后得到 p的值就是 5!的值。
上面的 S1,S2… 代表步骤 1，步骤 2……S 是 step(步 )
的缩写。这是写算法的习惯用法。
请读者仔细分析这个算法，能否得到预期的结果。
显然这个算法比前面列出的算法简练。
如果题目改为求 1× 3× 5× 7× 9× 11。
算法只需作很少的改动即可：
S1,1=>p
S2,3=>i
S3,p× i=>p
S4,i+2=>i
S5,若 i≤11，返回 S3； 否则，结束。
可以看出，用这种方法表示的算法具有通用性、灵活性。 S3到 S5组成一个循环，在实现算法时，要反复多次执行 S3,S4,S5等步骤，直到某一时刻，
执行 S5步骤时经过判断，乘数 i已超过规定的数值而不返回 S3步骤为止。此时算法结束，变量 p的值就是所求结果。
由于计算机是高速进行运算的自动机器，实现循环是轻而易举的，所有计算机高级语言中都有实现循环的语句。因此，上述算法不仅是正确的，而且是计算机能实现的较好的算法。
请读者仔细分析循环结束的条件，即 S5步骤。如果在求 1× 2× … × 11时，将 S5步骤写成
S5,若 i＜ 11，返回 S3。
这样会有什么问题?会得到什么结果?
例 2.2 有 50个学生，要求将他们之中成绩在 80分以上者打印出来。用 n表示学生学号,n1代表第一个学生学号,ni代表第 i个学生学号。用 g代表学生成绩，
gi代表第 i个学生成绩，算法可表示如下。
S1,1=>i
S2：如果 gi≥80，则打印 ni和 gi，否则不打印
S3,i+1=>i
S4：如果 i≤50，返回 S2，继续执行；否则，算法结束。
本例中，变量 i作为下标，用它来控制序号 (第几个学生，第几个成绩 )。当 i超过 50时，表示已对 50个学生的成绩处理完毕，算法结束。
例 2.3 判定 2000—2500年中的每一年是否闰年，将结果输出。
闰年的条件是,①能被 4整除，但不能被 100整除的年份都是闰年，如 1996年,2004年是闰年；②能被 100整除，又能被 400整除的年份是闰年。如
1600年,2000年是闰年。不符合这两个条件的年份不是闰年。
算法可表示如下：
设 y 为被检测的年份。可采取以下步骤：
S1,2000=>y
S2,y不能被 4整除，则输出 y ―不是闰年”。然后转到 S6
S3：若 y能被 4整除，不能被 100整除，则输出 y ―是闰年”。然后转到 S6
S4：若 y能被 100整除，又能被 400整除，输出 y―是闰年”；否则输出“不是闰年”。 然后转到 S6
S5：输出 y ―不是闰年”
S6,y+1=>y
S7：当 y≤2500时，转 S2继续执行，如 y＞ 2500，算法停止。
在这个算法中，采取了多次判断。先判断 y能否被 4
整除，如不能，则 y必然不是闰年。如 y 能被 4整除，
并不能马上决定它是否闰年，还要看它能否被 100
整除。如不能被 100整除，则肯定是闰年 (例如 1996
年 )。如能被 100整除，还不能判断它是否闰年，还要被 400整除，如果能被 400整除，则它是闰年，
否则不是闰年。
在这个算法中，每做一步，都分别分离出一些范围
(巳能判定为闰年或非闰年 )，逐步缩小范围，使被判断的范围愈来愈小，直至执行 S5时，只可能是非闰年。见图 2.1示意。
图 2.1
从图 2.1可以看出：“其他”这一部分，包括能被 4
整除，又能被 100整除，而不能被 400整除的那些年份 (如 1900年 ),是非闰年。
在考虑算法时，应当仔细分析所需判断的条件，如何一步一步缩小被判断的范围。有的问题，判断的先后次序是无所谓的，而有的问题，判断条件的先后次序是不能任意颠倒的，读者可根据具体问题决定其逻辑。
例 2.4 求 1-1/2+1/3-1/4+…+1/99 -1/100。
算法可以表示如下：
S1,1=>sign
S2,1=>sum
S3,2=>deno
S4,(-1)× sign=>sign
S5,sign× (1/deno)=>term
S6,sum+term=>sum
S7,deno+1=>deno
S8：若 deno≤100返回 S4；否则算法结束。
在步骤 S1中先预设 sign（代表级数中各项的符号，
它的值为 1或 -1）。在步骤 S2中使 sum等于 1,相当于已将级数中的第一项放到了 sum中。在步骤 S3中使分母的值为 2。在步骤 S4中使 sign的值变为 -1。
在步骤 S5中求出级数中第 2项的值 -1/2。在步骤 S6
中将刚才求出的第二项的值 -1/2累加到 sum中。至此,sum的值是 1-1/2。在步骤 S7中使分母 deno的值加 1（变成 3）。执行 S8步骤，由于 deno≤100，
故返回 S4步骤,sign的值改为 1，在 S5中求出 term
的值为 1/3，在 S6中将 1/3累加到 sum中。然后 S7再使分母变为 4。按此规律反复执行 S4到 S8步骤，直到分母大于 100为止。一共执行了 99次循环，向
sum累加入了 99个分数。 sum最后的值就是级数的值。
例 2.5 对一个大于或等于 3的正整数，判断它是不是一个素数。
所谓素数，是指除了 1和该数本身之外，不能被其他任何整数整除的数。例如,13是素数，因为它不能被 2,3,4,…,12整除。
判断一个数 n(n≥3)是否素数的方法是很简单的：将 n
作为被除数，将 2到 (n-1)各个整数轮流作为除数，
如果都不能被整除，则 n为素数。
算法可以表示如下：
S1：输入 n的值
S2,2=>i （ i作为除数）
S3,n被 i除，得余数 r
S4：如果 r=0，表示 n能被 i整除，则打印 n―不是素数”，算法结束；否则执行 S5
S5,i+1=>i
S6：如果 i≤n-1，返回 S3；否则打印 n ―是素数”，
然后结束。
实际上 n不必被 2到 (n-1)的整数除，只需被 2到 n的开方间整数除即可，甚至只需被 2到 n之间的整数除即可。例如，判断 13是否素数，只需将 13被 2,3
除即可，如都除不尽,n 必为素数。 S6步骤可改为：
S6：如果 i≤n，返回 S2；否则算法结束。
通过以上几个例子，可以初步了解怎样设计一个算法。
2.3 算法的特性一个算法应该具有以下特点：
1.有穷性一个算法应包含有限的操作步骤，而不能是无限的。
事实上，“有穷性”往往指“在合理的范围之内”。
究竟什么算“合理限度”，并无严格标准，由人们的常识和需要而定。
2.确定性算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。
3.有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。
4,有一个或多个输出算法的目的是为了求解，“解” 就是输出。没有输出的算法是没有意义的。
5,有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果。
对于不熟悉计算机程序设计的人来说，他们可以只使用别人已设计好的现成算法，只需根据算法的要求给以必要的输入，就能得到输出的结果。对他们来说，算法如同一个“黑箱子”一样,他们可以不了解“黑箱子”中的结构，只是从外部特性上了解算法的作用，即可方便地使用算法。例如，对一个“输入 3个数，求其中最大值”的算法，
可以用图 2.2表示，只要输入 a,b,c3个数，执行算法后就能得到其中最大的数。但对于程序设计人员来说，必须会设计算法，并且根据算法编写程序。
图 2.2
2.4 怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的有自然语言、传统流程图、结构化流程图、伪代码、
PAD图等。
2.4.1 用自然语言表示算法在 2.2节中介绍的算法是用自然语言表示的。用自然语言表示通俗易懂，但文字冗长,容易出现“歧义性”。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。此外，用自然语言描述包含分支和循环的算法，不很方便 (如例
2.5的算法 )。因此，除了很简单的问题以外，一般不用自然语言描述算法。
2.4.2 用流程图表示算法流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会
ANSI(American National Standard Institute)规定了一些常用的流程图符号 (见图 2.3)。
图 2.3中菱形框的作用是对一个给定的条件进行判断，
根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。见图 2.4。
连接点 (小圆圈 )是用于将画在不同地方的流程线连接起来。如图 2.5中有两个以○为标志的连接点 (在连接点圈中写上,1‖)，它表示这两个点是互相连接在一起的。实际上它们是同一个点，只是画不下才分开来画。用连接点，可以避免流程线的交叉或过长，使流程图清晰。
图 2.3
图 2.4 图 2.5
下面对 2.2节中所举的几个算法例子，改用流程图表示。
例 2.6 将例 2.1求 5!的算法用流程图表示，流程图见图
2.6。
菱形框两侧的,Y‖和,N‖代表“是” (yes)和
“否” (no)。如果需要将最后结果打印出来，可以在菱形框的下面再加一个输出框，见图 2.7。
例 2.7 将例 2.2的算法用流程图表示。将 50名学生中成绩在 80分以上者的学号和成绩打印出来，见图 2.8。
在此算法中没有包括输入 50个学生数据的部分，
如果包括这个输入数据的部分，流程图如图 2.9所示。
图 2.6 图 2.7 图 2.8
例 2.8 将例 2.3判定闰年的算法用流程图表示。
见图 2.10。显然，用图 2.10表示算法要比用文字描述算法逻辑清晰、易于理解。
请读者考虑，如果例 2.3所表示的算法中,S2步骤内没有最后“转到 S6‖这一句话，而只是
S2：若 y不能被 4整除，则打印 y ―不是闰年”
这样就意味着执行完 S2步骤后，不论 S2的执行情况如何都应执行 S3步骤。请读者画出相应的流程图。
请思考这样的算法在逻辑上有什么错误，从流程图上是很容易发现其错误的。
图 2.9 图 2.10
例 2.9 将例 2.4的算法用流程图表示。见图 2.11。
例 2.10 将例 2.5判断素数的算法用流程图表示，见图
2.12。
一个流程图包括以下几部分：①表示相应操作的框；
②带箭头的流程线；③框内外必要的文字说明。
需要提醒的是流程线不要忘记画箭头，因为它是反映流程的执行先后次序的。
用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。但是这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。在结构化程序设计方法推广之后，许多书刊已用 N-S结构化流程图代替这种传统的流程图。但是每一个程序编制人员都应当熟练掌握传统流程图。
图 2.11 图 2.12
2.4.3 三种基本结构和改进的流程图
1,传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。这种情况如图 2.13所示。
这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。如果我们写出的算法能限制流程的无规律任意转向，阅读起来就很方便。
图 2.13
但是，算法上难免会包含一些分支和循环，而不可能全部由一个一个框顺序组成。例如图 2.6到图
2.12都不是由各框顺序进行的，都包含一些流程的向前或向后的非顺序转向。为了解决这个问题，
人们设想，规定出几种基本结构，然后由这些基本结构按一定规律组成一个算法结构 (如同用一些基本预制构件来搭成房屋一样 )，整个算法的结构是由上而下地将各个基本结构顺序排列起来的。
如果能做到这一点,算法的质量就能得到保证和提高。
2,三种基本结构
1966年,Bohra和 Jacopini提出了以下三种基本结构，
作为表示一个良好算法的基本单元。
(1) 顺序结构，如图 2.14所示，虚线框内是一个顺序结构。
(2) 选择结构，或称选取结构，或称分支结构，如图
2.15所示。
请注意，无论 p 条件是否成立，只能执行 A框或 B框之一，不可能既执行 A框又执行 B框。无论走哪一条路径，在执行完 A或 B之后，都经过 b点，然后脱离本选择结构。 A或 B两个框中可以有一个是空的,即不执行任何操作，如图 2.16所示。
图 2.14 图 2.15 图 2.16
(3) 循环结构，它又称重复结构。有两类循环结构：
① 当型 (While型 )循环结构见图 2.17(a)。它的功能是当给定的条件 p1成立时，
执行 A框操作，执行完 A后，再判断条件 p1是否成立，如果仍然成立，再执行 A框，如此反复执行 A
框，直到某一次 p1条件不成立为止，此时不执行 A
框，而从 b点脱离循环结构。
② 直到型 (Until型 )循环见图 2.17(b)。它的功能是先执行 A框，然后判断给定的 p2条件是否成立，如果 p2条件不成立，则再执行 A，然后再对 p2条件作判断，如果 p2条件仍然不成立，又执行 A…… 如此反复执行 A，直到给定的
p2条件成立为止，此时不再执行 A，从 b点脱离本循环结构。
图 2.18是当型循环的应用例子，图 2.19是直到型循环的应用例子。
图 2.17 图 2.18 图 2.19
图 2.18和图 2.19的作用都是打印 5个数,1,2,3,4，
5。可以看到,对同一个问题既可以用当型循环来处理，也可以用直到型循环来处理。
以上三种基本结构，有以下共同特点：
(1) 只有一个入口。
(2) 只有一个出口。请注意，一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。
(3) 结构内的每一部分都有机会被执行到。对每一个框来说，都应有一条从入口到出口的路径通过它。
图 2.20中没有一条从入口到出口的路径通过 A框。
(4) 结构内不存在“死循环” (无终止的循环 )。图
2.21就是一个死循环。
图 2.20 图 2.21
已经证明，由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。
其实，基本结构不一定只限于上面三种，只要具有上述 4个特点的都可以作为基本结构。人们可以自己定义基本结构，并由这些基本结构组成结构化程序。例如，可以将图 2.22和图 2.23这样的结构定义为基本结构。图 2.23所示的是一个多分支选择结构，根据给定的表达式的值决定执行哪一个框。
图 2.22和图 2.23虚线框内的结构也是一个入口和一个出口，并且有上述全部的 4个特点。由它们构成的算法结构也是结构化的算法。但是，可以认为像图 2.22和图 2.23那样的结构是由三种基本结构派生出来的。因此，人们都普遍认为最基本的是本节介绍的三种基本结构。
图 2.22 图 2.23
2.4.4 用 N-S流程图表示算法既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么基本结构之间的流程线就属多余的了。
1973年美国学者 I.Nassi和 B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，
在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称 N-S结构化流程图。这种流程图适于结构化程序设计，因而很受欢迎。
N-S流程图用以下的流程图符号：
(1) 顺序结构,用图 2.24形式表示。 A和 B两个框组成一个顺序结构。
(2) 选择结构：用图 2.25表示。它与图 2.15相应。当 p
条件成立时执行 A操作,p不成立则执行 B操作。
请注意图 2.25是一个整体，代表一个基本结构。
图 2.24 图 2.25
(3) 循环结构,当型循环结构用图 2.26形式表示。
图 2.26表示当 p1条件成立时反复执行 A操作，直到 p1
条件不成立为止。
直到型循环结构用图 2.27形式表示。
用以上 3种 N-S流程图中的基本框，可以组成复杂的
N-S流程图，以表示算法。
应当说明，在图 2.24、图 2.25、图 2.26、图 2.27中的 A
框或 B框，可以是一个简单的操作 (如读入数据或打印输出等 )，也可以是 3个基本结构之一。例如，
图 2.24所示的顺序结构，其中的 A框可以又是一个选择结构,B框可以又是一个循环结构。如图 2.28
所示那样，由 A和 B这两个基本结构组成一个顺序结构。
图 2.26 图 2.27 图 2.28
通过下面的几个例子，读者可以了解如何用 N-S流程图表示算法。
例 2.11 将例 2.1的求 5!算法用 N-S图表示。见图 2.29，
它和图 2.7对应。
例 2.12 将例 2.2的算法用 N-S图表示。将 50名 学生中成绩高于 80分的学号和成绩打印出来。见图 2.30和图 2.31，它们与图 2.8和图 2.9对应。
例 2.13 将例 2.3判定闰年的算法用 N-S图表示。见图
2.32，它和图 2.10对应。
例 2.14 将例 2.4的算法用 N-S图表示。见图 2.33，它和图 2.11对应，只是最后加了一个“打印 sum‖框。
例 2.15 将例 2.5判别素数的算法用 N-S流程图表示。
图 2.29 图 2.30 图 2.31
图 2.32 图 2.33
由图 2.12可以看出，这个流程图不是由三种基本结构组成的。图中间那个循环部分，有两个出口 (一个从第二个菱形框下面出口，另一个在第一个菱形框右边出口 )，不符合基本结构的特点。由于不能分解为三种基本结构，就无法直接用 N-S流程图的三种基本结构的符号来表示。因此，应当先对图 2.12做必要的变换。要将第一个菱形框 (―r=0‖)的两个出口汇合在一点，以解决两个出口问题。当
r=0时不直接输出 n―不是素数”，而只设一个标志值（变量 w），它的初始状态为 w=0。当 r=0时 (表示 n为非素数 )使 w变成 1。如果 r ≠0则保持 w=0。 w
的作用如同一个开关，有两个工作状况,w=0和
w=1。 w=1表示 n为非素数。
如果最终 w=0，则表示 n为素数。然后将,1=>w‖框的出口线改为指向第二个菱形框，同时将第二个菱形框中的条件改为,i≤n和 w=0‖，即只有当
,i≤n‖和,w=0‖两个条件都满足时才继续执行循环。如果出现 i＞ n或 w≠0之一，都不会继续执行循环 (见图 2.34)。如果在某一次 r=0，则应执行 1=>w，
然后，由第二个菱形框判断为“条件不成立”，
接着执行图下部的选择结构。此时,w≠0，表示 n
不是素数，应打印出 n不是素数的信息。如果 w=0，
则表示在上面的每次循环中,n都不能被每一个 i整除，所以 n是素数，故输出 n是素数的信息。
图 2.34已由三种基本结构组成，可以用 N-S图表示此算法，见图 2.35。注意图 2.34直到型循环的判断条件为：,直到 i＞ n或 w≠0‖，即只要,i＞ n或 w≠0‖
之一成立，就不再继续执行循环。对此务请读者弄清楚。
通过以上例子，可以看出用 N-S图表示算法的优点。
它比文字描述直观、形象,易于理解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的。 N-S流程图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进行就可以了，十分方便。
用 N-S图表示的算法都是结构化的算法 (它不可能出现流程无规律的跳转，而只能自上而下地顺序执行 )。
图 2.34 图 2.35
归纳起来可知，一个结构化的算法是由一些基本结构顺序组成的；每个基本结构又可以包含其他的基本结构；在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内 (如循环中流程的跳转 )；一 个非结构化的算法
(如图 2.12)可以用一个等价的结构化算法 (如图 2.35)
代替，其功能不变。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。
N-S图如同一个多层的盒子，又称盒图 (box diagram)。
2.4.5 用伪代码表示算法用传统的流程图和 N-S图表示算法，直观易懂，但画起来比较费事。因此，流程图适宜表示一 个算法，
但在设计算法过程中使用不是很理想。为了设计算法时方便，常用一种称为伪代码 (pseudo code)的工具。
伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章，自上而下地写下来。每一行 (或几行 )表示一个基本操作。它不用图形符号，因此书写方便,格式紧凑，也比较好懂，便于向计算机语言算法 (即程序 )过渡。
例如,“打印 x的绝对值”的算法可以用伪代码表示如下：
IF x is positive THEN
print x
ELSE
print –x
它像一个英语句子一样好懂，在国外用得比较普遍。
也可以用汉字伪代码，如：
若 x为正打印 x
否则打印 –x
也可以中英文混用，如：
IF x 为正
print x
ELSE
print –x
即计算机语言中具有的语句关键字用英文表示，其他的可用汉字表示。总之，以便于书写和阅读为原则。用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。
将例 2.1到例 2.5的算法用伪代码表示如下。
例 2.16 求 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(算法结束 )
在本算法中采用当型循环（第 3行到笫 5行是一个当型循环）。 while意思为“当”,它表示当 i<=5时执行循环体（大括弧中的两行）的操作。
例 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.18 打印 2000—2500年中的每一年是否闰年。
用伪代码表示算法如下：
BEGIN(算法开始 )
2000=>y
while y<=2500
{if y 被 4整除
if y 不被 100整除
print y; ―是闰年”
else
if y 被 400整除
print y；“闰年”
else
print y；“非闰年”
end if
end if
else
print y; ―非闰年”
end if
y+1=>y
}
END(算法结束 )
例 2.19求 1-1/2+1/3-1/4+…+1/99 -1/100。
用伪代码表示的算法如下：
BEGIN (算法开始 )
1=> sum
2=> deno
1=> sign
while deno <= 100
{(-1)× sign=>sign
sign× 1/deno=>term
sum+term=>sum
deno+1=>deno
}
print sum
END (算法结束 )
从以上例子可以看到：伪代码书写格式比较自由，
容易表达出设计者的思想。同时，用伪代码写的算法很容易修改。用伪代码很容易写出结构化的算法。例如上面几个例子都是结构化的算法。但是用伪代码写算法不如流程图直观，可能会出现逻辑上的错误 (例如循环或选择结构的范围搞错等 )。
以上介绍了常用的表示算法的几种方法，在程序设计中读者可以根据需要和习惯任意选用。软件专业人员一般习惯使用伪代码，考虑到国内广大初学人员的情况，为便于理解，本书在以后各章中主要采用形象化的 N-S图表示算法。但是，读者对其他方法也应有所了解，以便在阅读其他书刊时不致发生困难。
2.4.6 用计算机语言表示算法要完成一件工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。因此，不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。
至今为止，我们只是描述算法，即用不同的形式表示操作的步骤。而要得到运算结果，就必须实现算法。在例 2.1,例 2.6、例 2.11和例 2.16中用不同的形式表示了求 5!的算法，但是并没有真正求出 5!
的值。实现算法的方式可能不止一种。例如对例
2.1表示的算法可以用人工心算的方式实现而得到结果，也可以用笔算或算盘、计算器求出结果，
这就是实现算法。
我们的任务是用计算机解题，也就是要用计算机实现算法。计算机是无法识别流程图和伪代码的。
只有用计算机语言编写的程序才能被计算机执行
（当然还要经过编译成目标程序才能被计算机识别和执行）。因此，在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序。
用计算机语言表示算法必须严格遵循所用语言的语法规则，这是和伪代码不同的。我们将前面介绍过的算法用 C语言表示。
例 2.20 将例 2.16表示的算法（求 5!）用 C语言表示。
main( )
{int i,t;
t=1;
i=2;
while(i<=5)
{t=t*i;
i=i+1;
}
printf("%d",t);
}
例 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);
}
在这里，不打算仔细介绍以上程序的细节，读者只需大体看懂它即可。在以后各章中会详细介绍 C语言有关的使用规则。
应当强调说明的是，写出了 C程序，仍然只是描述了算法，并未实现算法，只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。
2.5 结构化程序设计方法前面介绍了结构化的算法和三种基本结构。一个结构化程序就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，
这种程序便于编写、阅读、修改和维护。这就减少了程序出错的机会，提高了程序的可靠性。
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。如果面临一个复杂的问题，是难以一下子写出一个层次分明、结构清晰、
算法正确的程序的。结构化程序设计方法的基本思路是，把一个复杂问题的求解过程分阶段进行，
每个阶段处理的问题都控制在人们容易理解和处理的范围内。
具体说，采取以下方法保证得到结构化的程序。
(1) 自顶向下； (2) 逐步细化； (3) 模块化设计； (4) 结构化编码。
在接受一个任务后应怎样着手进行呢?有两种不同的方法：一种是自顶向下，逐步细化；一种是自下而上，逐步积累。以写文章为例来说明这个问题。
有的人胸有全局，先设想好整个文章分成哪几个部分，然后再进一步考虑每一部分分成哪几节，
每一节分成哪几段，每一段应包含什么内容，如图 2.36示意。
用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。
图 2.36
另有些人写文章时不拟提纲，如同写信一样提起笔就写，想到哪里就写到哪里，直到他认为把想写的内容都写出来了为止。这种方法叫做“自下而上，逐步积累”。
显然，用第一种方法考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分，修改有关段落即可，与其他部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。
我们应当掌握自顶向下、逐步细化的设计方法。这种设计方法的过程是将问题求解由抽象逐步具体化的过程。例如图 2.36所示。
用这种方法便于验证算法的正确性，在向下一层展开之前应仔细检查本层设计是否正确，只有上一层是正确的才能向下细化。如果每一层设计都没有问题，则整个算法就是正确的。由于每一层向下细化时都不太复杂，因此容易保证整个算法的正确性。检查时也是由上而下逐层检查，这样做，
思路清楚，有条不紊地一步一步进行，既严谨又方便。
举一个例子来说明这种方法的应用。
例 2.22 将 1到 1000之间的素数打印出来。
我们已在本章中讨论过判别素数的方法，现在采用
“筛法”来求素数表。所谓“筛法”指的是“埃拉托色尼 (Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是,在一张纸上写上 1到
1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数，见图 2.37。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49 50……
图 2.37
具体做法如下：
(1) 先将 1挖掉 (因为 1不是素数 )。
(2) 用 2去除它后面的各个数，把能被 2整除的数挖掉，
即把 2的倍数挖掉。
(3) 用 3去除它后面各数，把 3的倍数挖掉。
(4) 分别用 4,5… 各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如在图 2.37中找 1～ 50的素数，要一直进行到除数为 47为止。 (事实上，可以简化，如果需要找 1～ n范围内素数表，只需进行到除数为 n
开方 (取其整数 ) 即可。例如对 1～ 50，只需进行到将 7(50开方 )作为除数即可。 )
上面的算法可表示为：
(1) 挖去 1；
(2) 用下一个未被挖去的数 p去除 p后面各数，把 p的倍数挖掉；
(3) 检查 p是否小于 n的整数部分 (如果 n=1000，则检查 p＜ 31?),如果是，则返回 (2) 继续执行，否则就结束；
(4) 纸上剩下的数就是素数。
解题的基本思路有了，但要变成计算机的操作，还要做进一步的分析，如怎样判断一个数是否已被
“挖掉”，怎样找出某一个数 p的倍数，怎样打印出未被挖掉的数。
用自顶向下逐步细化的方法来处理这个问题，先进行“顶层设计”，见图 2.38。也可以用流程图进行逐步细化。流程图 2.39表示流程的粗略情况，把要做的三部分工作分别用 A,B,C表示。
图 2.38 图 2.39
这三部分还不够具体，要进一步细化。 A部分可以细化为图 2.40。先输入 n，然后将 1输入给 x1,2输入给 x2,1000输入给 x1000。
B部分可以细化为图 2.41。
图 2.40 图 2.41
图 2.41中的 B1与 B2不能再分了。 B1处理的方法是：使
x1=0，即哪个数不是素数,就使它等于 0，以后把不等于零的数打印出来就是所求的素数表。 B3中的循环体内以 D标志的部分还要进一步细化，对 D
细化为图 2.42。
图 2.42中的 E部分还不够具体，再进一步细化为图
2.43。图 2.43中的 F部分又细化为图 2.44。因为首先要判断某一个 xj是否已被挖掉，如已被挖掉则不必考虑被 xi除。至此，已不能也不需要再分解了。
再对图 2.39中的 C部分进行细化，见图 2.45。
对图 2.45中的 G部分进行细化，得图 2.46。
图 2.42 图 2.43 图 2.44
图 2.45 图 2.46
至此，已将图 2.39分解成为能用三种基本结构表示的基本操作了。将以上这些图合起来得到总的流程图，见图 2.47。
根据这个细化了的流程图已经可以用任何高级语言编写出源程序了。
以上是用流程图表示逐步细化的过程，如果题目复杂，则画许多分流程图也是比较费事的。 本例为了说明问题把细化过程分解得比较细，如果技巧熟悉些，可以精简一些步骤。例如从图 2.39的 C部分可以直接画出图 2.47的 C部分，而不必经过图
2.45和图 2.46。
图 2.47
也可以用伪代码来描述逐步细化过程，由于不需要画流程图，因此便于修改。例如，想对,打印全部素数”这一句话细化，只需将这句擦掉，在原处填入细化了的伪代码语句即可，或者将它向右展开，逐级细化。例如：
输入 1～ n各数 ……
把所有非素数去掉 ……
打印全部素数
i=1
while i≤n
{把未挖的 xi打印出来（ if xi不等于 0 then print xi ）
i=i+1}
对熟悉伪代码的人来说，可能这样更方便些。
在程序设计中常采用模块设计的方法，尤其是当程序比较复杂时，更有必要。在拿到一个程序模块
(实际上是程序模块的任务书 ) 以后，根据程序模块的功能将它划分为若干个子模块，如果嫌这些子模块的规模大，还可以划分为更小的模块。这个过程采用自顶向下的方法来实现。
程序中的子模块在 C语言中通常用函数来实现。例如在上例中，可以将图 2.39的 A,B,C三部分分别作为三个子模块，用三个函数来实现。
程序中的子模块一般不超过 50行，即打印时不超过一页，这样的规模便于组织，也便于阅读。划分子模块时应注意模块的独立性，即使一个模块完成一项功能,耦合性愈少愈好。
模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。
可以看到，结构化程序设计方法用来解决人脑思维能力的局限性和所处理问题的复杂性之间的矛盾。
在设计好一个结构化的算法之后，还要善于进行结构化编码。即用高级语言语句正确地实现三种基本结构。如果所用的语言是结构化的语言 (如
PASCAL,C,QBASIC,Ada等 ),则直接有与三种基本结构对应的语句，进行结构化编程序是不困难的。
本章内容十分重要,是学习后面各章的基础。学习程序设计的目的不只是学习一种特定的语言，而是学习进行程序设计的一般方法。掌握了算法就是掌握了程序设计的灵魂，再学习有关的计算机语言知识，就能够顺利地编写出任何一种语言的程序。脱离具体的语言去学习程序设计是困难的。
但是，学习语言只是为了设计程序，它本身决不是目的。千万不能拘泥于一种具体的语言，而应能举一反三。如前所述，关键是设计算法。有了正确的算法，用任何语言进行编码都不应当有什么困难。在本章中只是初步介绍了有关算法的知识，并没有深入介绍如何设计各种类型的算法。
我们将在以后各章中结合程序实例陆续介绍有关算法。
习题
2.1 什么是算法?试从日常生活中找 3个例子，描述它们的算法。
2.2 什么叫结构化的算法?为什么要提倡结构化的算法?
2.3 试述三种基本结构的特点，你能否自己另外设计两种基本结构 (要符合基本结构的特点 )。
2.4 用传统流程图表示求解以下问题的算法。
(1) 有两个瓶子 A和 B，分别盛放醋和酱油，要求将它们互换 (即 A瓶原来盛醋，现改盛酱油,B瓶则相反 )。
(2) 依次将 10个数输入，要求将其中最大的数打印出来。
(3) 有 3个数 a,b,c，要求按大小顺序把它们打印出来。
(4) 求 1+2+3+…+100 。
(5) 判断一个数 n能否同时被 3和 5整除。
(6) 将 100～ 200之间的素数打印出来。
(7) 求两个数 m和 n的最大公约数。
(8) 求方程式 ax2+bx+c=0的根。分别考虑：①有两个不等的实根；②有两个相等的实根。
2.5 用 N-S图表示 2.4题中各题的算法。
2.6 用伪代码表示 2.4题中各题的算法。
2.7 什么叫结构化程序设计?它的主要内容是什么?
2.8 用自顶向下、逐步细化的方法进行以下算法的设计：
(1) 打印出 1900—2000年中是闰年的年份，闰年的条件是：①能被 4整除但不能被 100整除；或②能被
100整除且能被 400整除。
(2) 求 ax2+bx+c=0的根。分别考虑 d=b2-4ac大于 0、等于 0和小于 0三种情况。
(3) 输入 10个数，找出最大的一个数，并打印出来。
