C语言程序设计(第四版)谭浩强——第2章 算法——程序的灵魂

C语言程序设计(第四版)谭浩强——第2章 算法——程序的灵魂

        通过第1章的学习，了解了C语言的特点,看到了简单的C语言程序。现在从程序的内容方面进行讨论,也就是一个程序中应该包含什么信息。或者说,为了实现解题的要求，程序应当向计算机发送什么信息。
        一个程序主要包括以下两方面的信息：
        （1）对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。这就是数据结构( data structure)。
        （2）对 *** 作的描述。即要求计算机进行 *** 作的步骤,也就是算法(algorithm)。
        数据是 *** 作的对象, *** 作的目的是对数据进行加工处理,以得到期望的结果。打个比方,厨师制作菜肴,需要有菜谱,菜谱上一般应说明：①所用配料,指出为了做出顾客所指定的菜肴,应该使用哪些材料；② *** 作步骤,指出有了这些原料,应按什么样的步骤进行加工,才能做出所需的菜肴。
        没有原料是无法加工成所需菜肴的,而对同一些原料可以加工出不同风味的菜肴。作为程序设计人员,必须认真考虑和设计数据结构和 *** 作步骤(即算法)。著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式：

算法＋数据结构=程序

        直到今天,这个公式对于过程化程序来说依然是适用的。
        实际上，一个过程化的程序除了以上两个主要要素之外,还应当采用结构化程序设计方法进行程序设计,并且用某一种计算机语言表示。因此,算法、数据结构、程序设计方法和语言工具4个方面是一个程序设计人员所应具备的知识,在设计一个程序时要综合运用这几方面的知识。在本书中不可能全面介绍这些内容,它们都属于有关的专门课程范畴。在这4个方面中,算法是灵魂,数据结构是加工对象,语言是工具,编程需要采用合适的方法。
        算法是解决“做什么”和“怎么做”的问题。程序中的 *** 作语句,实际上就是算法的体现。显然,不了解算法就谈不上程序设计。本书不是一本专门介绍算法的教材，也不是一本只介绍C语言语法规则的使用说明。本书将通过一些实例把以上4个方面的知识结合起来,使读者学会考虑解题的思路,并且能正确地编写出C语言程序。
        由于算法的重要性,本章先介绍有关算法的初步知识,以便为后面各章的学习建立一定的基础。

2.1 什么是算法

        做任何事情都有一定的步骤。例如,你想从北京去天津开会,首先要去买火车票,然后按时乘坐地铁到北京站,登上火车,到天津站后坐汽车到会场,参加会议;你要买电视机,先要选好货物,然后开票,付款,拿发票,取货,打车回家;要考大学,首先要填志愿表,交报名费,拿到准考证,按时参加考试,得到录取通知书,到指定学校报到注册等。这些步骤都是按一定的顺序进行的,缺一不可,次序错了也不行。从事各种工作和活动,都必须事先想好进行的步骤,然后按部就班地进行,才能避免产生错乱。实际上,在日常生活中,由于已养成习惯,所以人们并没意识到每件事都需要事先设计出“行动步骤”。例如吃饭、上学、打球和做作业等,事实上都是按照一定的规律进行的,只是人们不必每次都重复考虑它而已。

        不要认为只有“计算”的问题才有算法。广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。例如,描述太极拳动作的图解,就是“太极拳的算法”。一首歌曲的乐谱，也可以称为该歌曲的算法,因为它指定了演奏该歌曲的每一个步骤,按照它的规定就能演奏出预定的曲子。

        对同一个问题,可以有不同的解题方法和步骤。例如,求1＋2＋3十…＋100,有人可能先进行1＋2,再加3,再加4,一直加到100,而有的人采取这样的方法：100＋(1＋99)＋(2＋98)＋…＋(49＋51)＋50= 100＋49×100＋50 =5050。还可以有其他方法。当然,方法有优劣之分。有的方法只须进行很少的步骤,而有些方法则需要较多的步骤。一般来说,希望采用方法简单、运算步骤少的方法。因此,为了有效地进行解题,不仅需要保证算法正确,还要考虑算法的质量,选择合适的算法。
        本书所关心的当然只限于计算机算法,即计算机能执行的算法。例如,让计算机算1×2×3×4×5,或将100个学生的成绩按高低分数的次序排列,是可以做到的,而让计算机去执行“替我理发”或“煎份牛排”,是做不到的(至少目前如此)。
        计算机算法可分为两大类别:数值运算算法和非数值运算算法。数值运算的目的是求数值解，例如求方程的根、求一个函数的定积分等,都属于数值运算范围。非数值运算包括的面十分广泛,最常见的是用于事务管理领域,例如对一批职工按姓名排序、图书检索、人事管理和行车调度管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。
        由于数值运算往往有现成的模型,可以运用数值分析方法,因此对数值运算的算法的研究比较深入,算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册(写成程序形式),或者将这些程序存放在磁盘或光盘上供用户调用。例如有的计算机系统提供“数学程序库”,使用起来十分方便。
        非数值运算的种类繁多,要求各异,难以做到全部都有现成的答案,因此只有一些典型的非数值运算算法(例如排序算法、查找搜索算法等)有现成的﹑成熟的算法可供使用。许多问题往往需要使用者参考已有的类似算法的思路,重新设计解决特定问题的专门算法。本书不可能罗列所有算法,只是想通过一些典型算法的介绍,帮助读者了解什么是算法,怎样设计一个算法,帮助读者举一反三。希望读者通过本章介绍的例子了解怎样提出问题,怎样思考问题,怎样表示一个算法。

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×2X…×1000,则要写999个步骤，显然是不可取的。而且每次都要直接使用上一步骤的具体运算结果(如2,6,24等),也不方便。应当能找到一种通用的表示方法。
        不妨这样考虑：设置两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果,而是直接将每一步骤的乘积放在被乘数变量中。今设变量p为被乘数,变量i为乘数。用循环算法来求结果。可以将算法改写如下:
        S1:使p=1,或写成1→p
        S2:使i=2,或写成2→i
        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;否则,结束。其中S5也可以表示为:
        S5:若i>11,结束;否则返回 S3。上面两种写法,作用是相同的。
        可以看出用这种方法表示的算法具有一般性、通用性和灵活性。S3～S5组成一个循环,在满足某个条件(i≤11)时,反复多次执行 S3,S4和S5步骤,直到某一次执行S5步骤时,发现乘数i已超过事先指定的数值(11)而不返回S3为止。此时算法结束,变量p的值就是所求结果。
        由于计算机是高速运算的自动机器,实现循环是轻而易举的,所有计算机高级语言中都有实现循环的语句,因此，上述算法不仅是正确的,而且是计算机能方便实现的较好的算法。
        请读者仔细分析循环结束的条件,即S5。如果在求1×2×…×11时,将S5写成

        S5:若i<11,返回S3。

这样会有什么问题?得到什么结果?

        例2.2 有50个学生,要求输出成绩在80分以上的学生的学号和成绩。
        为描述方便,可以统一用n表示学生学号,用下标i代表第几个学生,n代表第一个学生学号,n代表第i个学生学号;统一用g表示学生的成绩，g1代表第1个学生的成绩,gi代表第i个学生的成绩。
        本来问题是很简单的：先检查第1个学生的成绩g1,如果它的值大于或等于80,就将此成绩输出,否则不输出。然后再检查第个学生的成绩g2……直到检查完第50个学生的成绩g50为止。但是这样表示步骤太多,表示太烦琐,最好能找到简明的表示方法。
        分析此过程的规律,每次检查的内容和处理方法都是相似的,只是检查的对象不同,而检查的对象都是学生的成绩g,只是下标不同(从g1变化到 g50)。只要有规律地改变下标i的值(从1～50),就可以把检查的对象统一表示为g,这样就可以用循环的方法来处理了。算法可表示如下:
        S1 :1→i
        S2:如果gi≥80,则输出ni;和 gi,否则不输出

        S3: i十1→i
        S4:如果i≤50,返回到步骤S2,继续执行,否则,算法结束。
        变量i代表下标,先使它的值为1,检查g1(g1到g50都是已知的)。然后使i增值1,再检查gi。通过控制i的变化,在循环过程中实现了对50个学生的成绩处理。
        可以看到,这样表示的算法比最初的表示方法抽象简明,抓住了解题的规律,易于用计算机实现。请读者通过这个简单的例子学会怎样归纳解题的规律,把具体的问题抽象化,设计出简明的算法。

        例2.3 判定2000--2500年中的每一年是否为闰年,并将结果输出。

        先分析闰年的条件:
        （1）能被4整除,但不能被100整除的年份都是闰年，如1996 年、2008年、2012年、2048年是闰年;
        （2）能被400整除的年份是闰年,如1600年、2000年是闰年。
        不符合这两个条件的年份不是闰年。例如2009年、2100年不是闰年。设year为被检测的年份。算法可表示如下:
        S1:2000→year
        S2:若year不能被4整除,则输出year 的值和“不是闰年”。然后转到S6,检查下一个年份
        S3:若year能被4整除,不能被100整除,则输出year的值和“是闰年”。然后转到S6

        S4:若year能被400整除,输出year的值和“是闰年”,然后转到S6
        S5:输出year的值和“不是闰年”
        S6: year＋1→year
        S7:当year≤2500时,转S2继续执行,否则算法停止。
        在这个算法中,采取了多次判断。先判断year能否被4整除,如不能,则year必然不是闰年。如year能被4整除,并不能马上决定它是否闰年,还要检查它能否被100整除。如不能被100整除,则肯定是闰年(例如2008年)。如能被100整除,还不能判断它是否闰年，还要检查它能否被400整除,如果能被400整除,则是闰年;否则不是闰年。

        在这个算法中,每做一步,都分别分离出一些范围(已能判定为闰年或非闰年),逐步缩小范围,使被判断的范围愈来愈小,直至执行S5时,只可能是非闰年,见图2.1。
        从图2.1可以看出:“其他”这一部分,包括不能被4整除的年份,以及能被4整除，又能被100整除,但不能被400整除的那些年份(如1900年),它们都是非闰年。
        考虑算法时,应当仔细分析所需判断的条件,如何一步一步缩小检查判断的范围。对有的问题,判断的先后次序是无所谓的;而有的问题,判断条件的先后次序是不能任意颠倒的,读者可根据具体问题决定其逻辑。

        例2.4 求1-1/2+1/3-1/4+...+1/99-1/100。
        解题思路：表面看,每一项都不一样,但稍加分析,就可以看到：

        ① 第1项的分子分母都是1 ;
        ② 第2项的分母是2,以后每一项的分母都是前一项的分母加1；

        ③ 第2项前的运算符为“-”,后一项前面的运算符都与前一项前的运算符相反。

        这就找到了多项式的规律,能把多项式表示为一般形式,即把问题抽象化了。.
        有此基础就可以写出下面的算法,用sign代表当前处理的项前面的数值符号, term代表当前项的值。sum表示当前各项的累加和,deno是当前项的分母(英文denominator 的缩写)。本例中用有含义的单词作变量名,以使算法更易于理解。
        S1:sign=1
        S2:sum=1

        S3: deno=2
        S4: sign=( -1) * sign

        S5:term=sign * ( 1/deno)

        S6:sum=sum+term

        S7 : deno=deno＋1
        S8:若deno≤100返回S4 ;否则算法结束。

        在S1中先预设sign 的值为1(sign 代表多项式中当前项的符号,它的值为1或-1)。在S2中使sum等于1,相当于已将多项式中的第一项加到了sum中了,后面应该从第⒉项开始累加。在S3中使分母的值为⒉,它是第2项的分母。在S4中使sign 的值变为-1,此时它代表第2项的符号。在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的正整数，判断它是不是一个素数。
        解题思路：所谓素数(prime),是指除了1和该数本身之外,不能被其他任何整数整除的数。例如,13是素数,因为它不能被2,3,4,…,12整除。
        判断一个数n(n≥3)是否为素数的方法是很简单的：将n作为被除数，将2~n-1各个整数先后作为除数,如果都不能被整除,则n为素数。
        算法可以表示如下:
        S1:输入n的值
        S2: i=2(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间整数除即可,甚至只须被2~n^(1/2)之间的整数除即可。例如,判断13是否为素数,只须将13被⒉,3除即可,如都除不尽, n必为素数。S6步骤可改为:
        S6:如果i≤n^(1/2),返回S3;否则算法结束。
        通过以上几个例子,可以初步了解怎样设计一个简单的算法。

2.3 算法的特性

        在2.2节了解了几种简单的算法,这些算法是可以在计算机上实现的。为了能编写程序,必须学会设计算法。不要以为任意写出的一些执行步骤就构成一个算法。一个有效算法应该具有以下特点。
        （1）有穷性。一个算法应包含有限的 *** 作步骤,而不能是无限的。例如例2.4的算法，如果将S8步骤改为:“若deno≥0,返回S4”,则循环永远不会停止,这不是有穷的步骤。事实上，“有穷性"往往指“在合理的范围之内”。如果让计算机执行一个历时1000年才结束的算法,这虽然是有穷的,但超过了合理的限度，人们也不把它视为有效算法。究竟什么算“合理限度”,由人们的常识和需要判定。
        （2）确定性。算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的。例如,有一个健身 *** 的动作要领,其中有一个动作:“手举过头顶”这个步骤就是不确定的，含糊的。是双手都举过头?还是左手或右手？举过头顶多少厘米?不同的人可以有不同的理解。算法中的每一个步骤应当不致被解释成不同的含义,而应是明确无误的。如例2.5中的S3步骤如果写成“n被一个整数除,得余数r”,这也是“不确定”的,它没有说明n被哪个整数除,因此无法执行。也就是说,算法的含义应当是唯一的,而不应当产生“歧义性”。所谓“歧义性”,是指可以被理解为两种(或多种)的可能含义。
        （3）有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。例如,在执行例⒉5算法时,需要输人n的值,然后判断n是否素数。也可以有两个或多个输入,例如,求两个整数m和n的最大公约数,则需要输人m和n的值。一个算法也可以没有输入,例如,例2.1在执行算法时不需要输人任何信息，就能求出5!。

        （4）有一个或多个输出。算法的目的是为了求解，“解”就是输出。如例2.5求素数的算法,最后输出的n“是素数”或“不是素数”就是输出的信息。但算法的输出并不一定就是计算机的打印输出或屏幕输出,一个算法得到的结果就是算法的输出。没有输出的算法是没有意义的。
        （5）有效性。算法中的每一个步骤都应当能有效地执行,并得到确定的结果。例如,若b=0,则执行a/b是不能有效执行的。
        对于一般最终用户来说,他们并不需要在处理每一个问题时都要自己设计算法和编写程序,可以使用别人已设计好的现成算法和程序,只须根据已知算法的要求给予必要的输入,就能得到输出的结果。对使用者来说,算法如同一个“黑箱子”一样,他们可以不了解“黑箱子”中的结构,只是从外部特性上了解算法的作用,即可方便地使用算法。例如,对一个“输入3个数,求其中最大值”的算法,可以用图2.2表示,只要输入a,b,c这3个数,执行算法后就能得到其中最大的数。

        对于程序设计人员来说,必须学会设计常用的算法﹐并且根据算法编写程序。

2.4 怎样表示一个算法

        为了表示一个算法,可以用不同的方法。常用的方法有:自然语言,传统流程图、结构化流程图和伪代码等。

2.4.1 用自然语言表示算法

        第.22节介绍的算法是用自然语言来表示的,自然语言就是人们日常使用的语言,可以是汉语、英语或其他语言。用自然语言表示通俗易懂,但文字冗长，容易出现歧义。自然语言表示的含义往往不大严格,要根据上下文才能判断其正确含义。例如有这样一句话:“张先生对李先生说他的孩子考上了大学”，请问是张先生的孩子考上大学还是李先生的孩子考上大学呢?光从这句话本身难以判断。此外,用自然语言来描述包含分支和循环的算法不大方便(如例2.5的算法)。因此,除了那些很简单的问题以外,一般不用自然语言表示算法。

2.4.2 用流程图表示算法

         流程图是用一些图框来表示各种 *** 作。用图形表示算法,直观形象,易于理解。美国国家标准化协会ANSI( American NationalStandard Institute)规定了一些常用的流程图符号(见图2.3),已为世界各国程序工作者普遍采用。

        图2.3中菱形框的作用是对一个给定的条件进行判断,根据给定的条件是否成立决定如何执行其后的 *** 作。它有一个入口,两个出口,见图2.4。

        连接点(小圆圈)是用于将画在不同地方的流程线连接起来。如图2.5中有两个以①为标志的连接点,它表示这两个点是互相连接在一起的,实际上它们是同一个点,只是画不下才分开来画。用连接点可以避免流程线交叉或过长,使流程图清晰。注释框不是流程图中必要的部分,不反映流程和 *** 作,只是为了对流程图中某些框的 *** 作作必要的补充说明,以帮助阅读流程图的人更好地理解流程图的作用。
        下面将2.2节中所举的几个算法例子,改用流程图表示。

        例2.6 将例2.1的算法用流程图表示。求1X2×3×4×5。
        按照流程图的规定,把算法用图2.6所示的流程图表示。菱形框两侧的Y和N代表“是”(Yes)和“否”(No)。
        如果需要将最后结果输出,可以在菱形框的下面再加一个输出框,见图2.7。

        例2.7 例2.2的算法用流程图表示。有50个学生,要求输出成绩在80分以上的学生的学号和成绩。
流程图见图2.8,在此算法中没有包括输入50个学生数据的部分。如果包括这个输入数据的部分,流程图如图2.9所示。
        例2.8 例2.3判定闰年的算法用流程图表示。判定2000—2500年中的每一年是否为闰年,将结果输出。

         流程图见图2.10。显然,用图2.10表示算法要比用文字描述算法逻辑清晰、易于理解。

        请读者考虑,如果例2.3所表示的算法中,S2步骤内没有最后“转到S6”这一句话,而只是:
        S2:若year不能被4整除,则输出y“不是闰年”
        这样就意味着执行完S2步骤后,不论S2的执行情况如何都应执行S3步骤。请读者画出相应的流程图。请思考这样的算法在逻辑上有什么错误?从流程图上是很容易发现逻辑上的错误的。

        例2.9 将例2.4的算法用流程图表示。求1-1/2+1/3-1/4+…1/99-1/100流程图见图2.11。
        例2.10 例2.5判断素数的算法用流程图表示。对一个大于或等于3的正整数，判断它是不是一个素数。
        流程图见图2.12。

通过以上几个例子可以看出流程图是表示算法的较好的工具。一个流程图包括以下几部分。

        （1）表示相应 *** 作的框;

        （2）带箭头的流程线;

        （3）框内外必要的文字说明。
        
        需要提醒的是:流程线不要忘记画箭头,因为它是反映流程的先后的,如不画出箭头就难以判定各框的执行次序了。

        用流程图表示算法直观形象,比较清楚地显示出各个框之间的逻辑关系。有一段时期国内外计算机书刊都广泛使用这种流程图表示算法。但是,这种流程图占用篇幅较多,尤其当算法比较复杂时,画流程图既费时又不方便。在结构化程序设计方法推广之后,许多书刊已用N-S结构化流程图代替这种传统的流程图(见2.4.4节),但是每一个程序编制人员都应当熟练掌握传统流程图,会看会画。

2.4.3 三种基本结构和改进的流程图

 1.传统流程图的弊端

        传统的流程图用流程线指出各框的执行顺序,对流程线的使用没有严格限制。因此,使用者可以不受限制地使流程随意地转来转去,使流程图变得毫无规律,阅读时要花很大精力去追踪流程,使人难以理解算法的逻辑。这种情况如图2.13所示,这种如同乱麻一样的算法称为BS型算法,意为一碗面条( a bowl of spaghetti),毫无头绪。
        像图2.13这样的算法是不好的,难以阅读，也难以修改,从而使算法的可靠性和可维护性难以保证。如果写出的算法能限制流程的无规律任意转向,像一本书那样由各章各节顺序组成,那么阅读起来就很方便,不会有任何困难,只须从头到尾顺序地看下去即可。而如果一本书不是由各章节顺序组成,而是毫无规律地乱排,例如第1章从36页开始到47页,第2章从98页到107页,第3章从19页到35页……各章内各节也是毫无规律地乱排,阅读这种书是不会感到愉快的。
        为了提高算法的质量,使算法的设计和阅读方便,必须限制箭头的滥用,即不允许无规律地使流程随意转向,只能顺序地进行下去。但是,算法上难免会包含一些分支和循环,而不可能全部由一个个顺序框组成。例如图2.6到图2.12都不是由各框顺序进行的,都包含一些流程的向前或向后的非顺序转向。为了解决这个问题,人们规定出几种基本结构,然后由这些基本结构按一定规律组成一个算法结构(如同用一些基本预制构件来搭成房屋一样),如果能做到这一点,算法的质量就能得到保证和提高。

2. 三种基本结构 

        （1）顺序结构。如图2.14所示﹐虚线框内是一个顺序结构。其中A和B两个框是顺序执行的。即:在执行完A框所指定的 *** 作后,必然接着执行B框所指定的 *** 作。顺序结构是最简单的一种基本结构。
        （2）选择结构。选择结构又称选取结构或分支结构,如图2.15所示。虚线框内是一个选择结构。此结构中必包含一个判断框。根据给定的条件p是否成立而选择执行A框或B框。例如p条件可以是x≥0或x>y，a十b

        注意:无论p条件是否成立,只能执行A框或B框之一,不可能既执行A框又执行B框。无论走哪一条路径,在执行完A或B之后,都经过b点,然后脱离本选择结构。A或B两个框中可以有一个是空的,即不执行任何 *** 作,如图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.18和图2.19的作用都是输出5个数:1,2,3,4,5。可以看到:对同一个问题既可以用当型循环来处理,也可以用直到型循环来处理。
        以上3种基本结构,有以下共同特点:
        （1）只有一个入口。图2.14～图2.17中的a点为入口点。
        （2）只有一个出口。图2.14～图2.17中的b点为出口点。请注意，一个判断框有两个出口,而一个选择结构只有一个出口。不要将判断框的出口和选择结构的出口混淆。
        （3）结构内的每一部分都有机会被执行到。也就是说,对每一个框来说,都应当有一条从入口到出口的路径通过它。图2.20中没有一条从人口到出口的路径通过A框。
        （4）结构内不存在“死循环”(无终止的循环)。图2.21就是一个死循环。

        由以上3种基本结构顺序组成的算法结构,可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法,它不存在无规律的转向,只在本基本结构内才允许存在分支和向前或向后的跳转。
        其实,基本结构并不一定只限于上面3种,只要具有上述4个特点的都可以作为基本结构。人们可以自己定义基本结构,并由这些基本结构组成结构化程序。例如,也可以将图2.22和图2.23这样的结构定义为基本结构。图2.23所示的是一个多分支选择结构,根据给定的表达式的值决定执行哪一个框。图2.22和图2.23虚线框内的结构也只有一个入口和一个出口,并且具有上述全部的4个特点。由它们构成的算法结构也是结构化的算法。但是,可以认为像图2.22和图2.23那样的结构是由3种基本结构派生出来的。因此,人们普遍认为最基本的是本节介绍的3种基本结构。

 2.4.4 用N—S流程图表示算法

        既然用基本结构的顺序组合可以表示任何复杂的算法结构,那么,基本结构之间的流程线就属多余的了。
        1973年,美国学者L.Nassi和 B. Shneiderman提出了一种新的流程图形式。在这种流程图中,完全去掉了带箭头的流程线。全部算法写在一个矩形框内,在该框内还可以包含其他从属于它的框,或者说,由一些基本的框组成一个大的框。这种流程图又称N-S结构化流程图(N和S是两位美国学者的英文姓氏的首字母)。这种流程图适于结构化程序设计,因而很受欢迎。
        N-S流程图用以下的流程图符号。
        (1)  顺序结构。顺序结构用图2.24形式表示。A和B两个框组成一个顺序结构。

        (2）选择结构。选择结构用图2.25表示。它与图2.15所表示的意思是相同的。当p条件成立时执行A *** 作,p不成立则执行B *** 作。注意:图2.25是一个整体,代表一个基本结构。
        (3）循环结构。当型循环结构用图2.26形式表示，当p1条件成立时反复执行A *** 作，直到p1条件不成立为止。
        直到型循环结构用图2.27形式表示。

        在初学时,为清楚起见,可如图2.26和图2.27那样,写明“当p1"或“直到p2”,待熟练之后,可以不写“当"和“直到”字样,只写“p1"和“p2”。从图的形状即可知道是当型还是直到型。
        用以上3种N-S流程图中的基本框可以组成复杂的N-S流程图,以表示算法。

        应当说明,在图2.24～图2.27中的A框或B框,可以是一个简单的 *** 作(如读入数据或打印输出等),也可以是3种基本结构之一。例如,图2.24所示的顺序结构,其中的A框可以又是一个选择结构,B框可以又是一个循环结构。如图2.28所示那样,由A和B这两个基本结构组成一个顺序结构。
        通过下面的几个例子,读者可以了解如何用N-S流程图表示算法。

        例2.11 将例2.1的求5!算法用N-S图表示。

        N-S图见图2.29,它和图2.7对应。

        例2.12 将例2.2的算法用N-S图表示。输出50名学生中成绩高于80分者的学号和成绩。
        N-S图见图2.30和图2.31,它和图2.8和图2.9对应。 

        例2.13 将例2.3判定闰年的算法用N-S图表示。N-S图见图2.32,它和图2.10对应。

        例2.14 将例2.4的算法用N-S图表示。求1-1/2+1/3-1/4+...+1/99-1/100。

        N-S图见图2.33，它和图2.11对应,只是最后加了一个“输出sum”框。
        例2.15 将例2.5判别素数的算法用N-S流程图表示。
        在例2.10中用传统流程图(图2.12)。可以看出,图2.12不是由3种基本结构组成的。图中间的循环部分有两个出口(一个从第1个判断框右面出口,另一个在第⒉个判断框下边出口),不符合基本结构的特点。由于不能分解为3种基本结构,就无法直接用N-S流程图的3种基本结构的符号来表示。因此,应当先对图2.12作必要的变换。要将第1个判断框(“r=0?”)的两个出口汇合在一点,以解决两个出口问题。当r=0时意味着n为非素数,但此时不马上输出n“不是素数”的信息,而只使标志变量w的值由0改为1(w的值为w=0)。如果r≠0,则保持w=0,见图2.34。 

        w的作用如同一个开关一样,有两种工作状况:w=0和w=1,可以从一种状态转换到另一状态。当w=1时表示被检查的数n为非素数。如果最终w=0,则表示n为素数。将“1→w”框的出口线改为指向第2个判断框,同时将第⒉个判断框中的条件改为 i≤n^(1/2)和w=0,即只有当i≤n^(1/2)和w=0两个条件都满足时才继续执行循环。如果出现i>n^(1/2)或w≠0之一,都不会继续执行循环(见图2.34)。
        如果在某一次r=0,则应执行1→w,然后,由第⒉个判断框判断为“条件不成立”,接着执行图下部的选择结构。此时,由于w≠0(表示n不是素数),故应输出n不是素数的信息。

        如果w=0,则表示在上面的每次循环中,n都不能被每一个i整除,所以n是素数,故输出n是素数的信息。
        图2.34已变成由3种基本结构组成的流程图。可以改用N-S图表示此算法,见图2.35。注意,图2.35直到型循环的判断条件为直到i>n或w≠0,即只要 i>n或w≠0之一成立,就不再继续执行循环。这和图2.34菱形框中的表示形式(i≤n^(1/2)和w=0)正好相反,请读者考虑为什么。

        通过以上几个例子,可以看出用N-S图表示算法的优点。它比文字描述直观、形象、易于理解﹔比传统流程图紧凑易画,尤其是它废除了流程线,整个算法结构是由各个基本结构按顺序组成的,N-S流程图中的上下顺序就是执行时的顺序,也就是图中位置在上面的先执行,位置在下面的后执行。写算法和看算法只须从上到下进行就可以了,十分方便。用N-S图表示的算法都是结构化的算法(它不可能出现流程无规律的跳转,而只能自上而下地顺序执行)。
        归纳起来可知:一个结构化的算法是由一些基本结构顺序组成的;在基本结构之间不存在向前或向后的跳转,流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转);一个非结构化的算法(如图2.12)可以用一个等价的结构化算法(如图2.35)代替,其功能不变。如果一个算法不能分解为若干个基本结构,则它必然不是一个结构化的算法。
        N-S图如同一个多层的盒子,又称盒图(box diagram)。

2.4.5 用伪代码表示算法

        用传统的流程图和N-S图表示算法直观易懂,但画起来比较费事,在设计一个算法时，可能要反复修改,而修改流程图是比较麻烦的。因此,流程图适于表示一个算法,但在设计算法过程中使用不是很理想(尤其是当算法比较复杂、需要反复修改时)。为了设计算法时方便,常用一种称为伪代码(pseudo code)的工具。
        伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章一样,自上而下地写下来。每一行(或几行)表示一个基本 *** 作。它不用图形符号,因此书写方便,格式紧凑,修改方便,容易看懂,也便于向计算机语言算法(即程序)过渡。
用伪代码写算法并无固定的、严格的语法规则,可以用英文,也可以中英文混用。只要把意思表达清楚,便于书写和阅读即可，书写的格式要写成清晰易读的形式。
        例2.16 求5!,用伪代码表示的算法如下:

begin                             (算法开始)

1→t

2→i
while i≤5

{t * i→t

 i十1→i

}
print t

end                                 (算法结束)

        在本算法中采用当型循环(第3行到第6行是一个当型循环)。while意思为“当”,它表示当i≤5时执行循环体(花括号中两行)的 *** 作。

        例2.17 求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(求5!)表示的算法,可以用人工心算的方式实现而得到结果。也可以用笔算或算盘,计算器来求出结果,这都是实现算法。
        我们考虑的是用计算机解题,也就是要用计算机实现算法,而计算机是无法识别流程图和伪代码的,只有用计算机语言编写的程序才能被计算机执行,因此在用流程图或伪代码描述一个算法后,还要将它转换成计算机语言程序。用计算机语言表示的算法是计算机能够执行的算法。
        用计算机语言表示算法必须严格遵循所用的语言的语法规则,这是和伪代码不同的。下面将前面介绍过的算法用C语言表示。
例2.18 将例2.16表示的算法(求5!)用C语言表示。 

#include 
int main()
{
int i,t;
t=1;
i=2;
while(i<=5)
{
t=t*i;
i=i+1;
}
printf("%dn",t);
return 0;
}

        例2.19 将例2.17表示的算法(求多项式1-1/2+1/3-1/4+…+1/99-1/100的值)用C语言表示。

#include 
int main()
{
int sign=1;
double deno=2.0,sum=1.0,term;  //定义deno，sum，term为双精度型变量
   whlie(demo<=100);
    {
    sign=-sign;
    term=sign/deno;
    sum=sum+term;
    deno=deno+1;
    }
printf("%fn",sum);
return 0;
}

        读者只须大体看懂它即可。在以后各章中会详细介绍C语言有关的使用规则。
        应当强调说明的是,写出了C程序,仍然只是描述了算法,并未实现算法。只有运行程序才是实现算法。

2.5 结构化程序设计方法 

        前面介绍了结构化的算法和3种基本结构。一个结构化程序就是用计算机语言表示的结构化算法，用3种基本结构组成的程序必然是结构化的程序。这种程序便于编写、阅读、修改和维护,这就减少了程序出错的机会,提高了程序的可靠性,保证了程序的质量。
        结构化程序设计强调程序设计风格和程序结构的规范化,提倡清晰的结构。怎样才能得到一个结构化的程序呢?如果面临一个复杂的问题,是难以一下子写出一个层次分明、结构清晰，算法正确的程序的。结构化程序设计方法的基本思路是:把一个复杂问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内。
        具体说,采取以下方法来保证得到结构化的程序:
        （1）自顶向下;
        （2）逐步细化;

        （3）模块化设计;

        （4）结构化编码。
        在接受一个任务后应怎样着手进行呢?有两种不同的方法:一种是自顶向下,逐步细化;一种是自下而上,逐步积累。以写文章为例来说明这个问题。有的人胸有全局,先设想好整个文章分成哪几个部分,然后再进一步考虑每一部分分成哪几节,每一节分成哪几段，每一段应包含什么内容,如图2.36示意。

        用这种方法逐步分解,直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫做“自顶向下,逐步细化”。
        另有些人写文章时不拟提纲,如同写信一样提笔就写,想到哪里就写到哪里,直到他认为把想写的内容都写出来了为止。这种方法叫做自下而上,逐步积累。
        显然,用第一种方法考虑周全,结构清晰,层次分明,作者容易写,读者容易看。如果发现某一部分中有一段内容不妥,需要修改,只须找出该部分,修改有关段落即可,与其他部分无关。提倡用这种方法设计程序,这就是用工程的方法设计程序。
        设计房屋就是用自顶向下、逐步细化的方法。先进行整体规划,然后确定建筑物方案，再进行各部分的设计,最后进行细节的设计(如门窗、楼道等),而绝不会在没有整体方案之前先设计楼道和厕所。而在完成设计,有了图纸之后,在施工阶段则是自下而上实施的,用一砖一瓦先实现一个局部,然后由各部分组成一个建筑物。
        应当掌握自顶向下、逐步细化的设计方法。这种设计方法的过程是将问题求解由抽象逐步具体化的过程。如图2.36所示,最开始拿到的题目是作“工作报告”,这是一个很笼统而抽象的任务,经过初步考虑之后把它分成4个大的部分。这就比刚才具体一些了,但还不够具体。这一步只是粗略地划分,称为“顶层设计”。然后一步一步细化,依次称为第2层、第3层设计,直到不需要细分为止。
        用这种方法便于验证算法的正确性,在向下一层展开之前应仔细检查本层设计是否正确,只有上一层是正确的才能向下细化。如果每一层设计都没有问题,则整个算法就是正确的。由于每一层向下细化时都不太复杂,因此容易保证整个算法的正确性。检查时也是由上而下逐层检查,这样做,思路清楚,有条不紊地一步一步地进行,既严谨又方便。
        在程序设计中常采用模块设计的方法,尤其当程序比较复杂时,更有必要。在拿到一个程序模块(实际上是程序模块的任务书)以后,根据程序模块的功能将它划分为若干个子模块,如果这些子模块的规模还嫌大,可以再划分为更小的模块。这个过程采用自顶向下的方法来实现。
        程序中的子模块在C语言中通常用函数来实现(有关函数的概念将在第7章中介绍)。

        程序中的子模块一般不超过50行,即把它打印输出时不超过一页,这样的规模便于组织,也便于阅读。划分子模块时应注意模块的独立性,即使用一个模块完成一项功能,耦合性愈少愈好。模块化设计的思想实际上是一种“分而治之”的思想,把一个大任务分为若干个子任务,每一个子任务就相对简单了。

         结构化程序设计方法用来解决人脑思维能力的局限性和被处理问题的复杂性之间的矛盾。
在设计好一个结构化的算法之后,还要善于进行结构化编码(coding)。所谓编码就是将已设计好的算法用计算机语言来表示,即根据已经细化的算法正确地写出计算机程序。结构化的语言(如Pascal,C,Visual Basic等)都有与3种基本结构对应的语句,进行结构化编程序是不困难的。
        本章的内容是十分重要的,是学习后面各章的基础。学习程序设计的目的不只是学习某一种特定的语言,而应当学习进行程序设计的一般方法。掌握了算法就是掌握了程序设计的灵魂,再学习有关的计算机语言的知识,就能够顺利地编写出任何一种语言的程序。脱离具体的语言去学习程序设计是困难的。但是,学习语言只是为了设计程序,它本身绝不是目的。高级语言有许多种,每种语言也都在不断发展,因而千万不能拘泥于一种具体的语言,而应当能举一反三。关键是设计算法,有了正确的算法,用任何语言进行编码都不是什么困难的事。

        本章只是初步介绍了有关算法的基本知识,并没有深入介绍如何设计各种类型的算法。在以后各章中将结合程序实例陆续介绍有关的算法。