C程序设计第2章

第2章程序的灵魂——算法2.1算法的概念2.2简单算法举例2.3算法的特性2.4怎样表示一个算法2.5结构化程序设计方法一个程序应包括以下两方面内容:（1）对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(datastructure)。（2）对操作的描述。即操作步骤，也就是算法(algorithm)。数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。著名计算机科学家沃思(NikiklausWirth)提出一个公式：数据结构+算法=程序实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：

在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。程序

=算法

+数据结构

+程序设计方法

+语言工具和环境2.1

算法的概念从事各种工作和活动，都必须事先想好进行的步骤，然后按部就班地进行，才能避免产生错乱。不要认为只有“计算”的问题才有算法。广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。对于同一个问题，可以有不同的解决方法和步骤例如求1+2+3+……+100的问题有人是：1+2，再+3，再+4，……+100

有人是：100+（1+99）+（2+98）

+…+(49+51)+50=100+49*100+50=5050

还有其他方法方法有优劣之分，希望采用的方法简单、运算步骤少的方法，我们所关心的只是计算机算法。计算机算法可分为两大类别：数值算法和非数值算法。数值运算的目的是求数值解，此种算法比较成熟（库函数）。非数值运算包括的面十分广泛，最常见的是用于事务管理领域，此种算法种类繁多。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怎么办？可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设p为被乘数，i为乘数。用循环算法来求结果。可以将算法改写如下：

S1：使p=1S2：使i=2S3：使p×i，乘积仍放在变量p中，可表示为p×i=>pS4：使i的值加1，即i+1=>iS5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。如果题目改为求1×3×5×7×9×11。算法只需作很少的改动即可：

S1：1=>pS2：3=>iS3：p×i=>pS4：i+2=>iS5：若i≤11，返回S3；否则，结束。可以看出，用这种方法表示的算法具有通用性、灵活性。【例2.2】有50个学生，要求将他们之中成绩在80分以上的学号和成绩输出。用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下。

S1：1=>iS2：如果gi≥80，则输出ni和gi，否则不输出

S3：i+1=>iS4：如果i≤50，返回S2，继续执行；否则，算法结束。本例中，变量i作为下标，用它来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。【例2.3】判定2000—2500年中的每一年是否闰年，将结果输出。闰年的条件是：①能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年；②能被100整除，又能被400整除的年份是闰年。如1600年、2000年是闰年。不符合这两个条件的年份不是闰年。算法可表示如下：设y为被检测的年份。可采取以下步骤：

S1：2000=>yS2：y不能被4整除，则输出y“不是闰年”。然后转到S6

S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转到S6S4：若y能被100整除，又能被400整除，输出y“是闰年”；否则输出“不是闰年”。然后转到S6S5：输出y“不是闰年”

S6：y+1=>yS7：当y≤2500时，转S2继续执行，如y＞2500，算法停止。在例2.3的算法中，采取了多次判断，每做一步，都分别分离出一些范围(已能判定为闰年或非闰年)，逐步缩小范围，使被判断的范围愈来愈小，直至执行S5时，只可能是非闰年。见图2.1示意。图2.1【例2.4】求1-1/2+1/3-1/4+…+1/99-1/100。算法可以表示如下：

S1：1=>signS2：1=>sumS3：2=>denoS4：(-1)×sign=>signS5：sign×(1/deno)=>termS6：sum+term=>sumS7：deno+1=>denoS8：若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的正整数，判断它是不是一个素数。判断一个数n(n≥3)是否素数的方法是很简单的：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法可以表示如下：

S1：输入n的值

S2：2=>i（i作为除数）

S3：n被i除，得余数rS4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1=>iS6：如果i≤n-1，返回S3；否则打印n“是素数”，然后结束。可只除到n/22.3算法的特性一个算法应该具有以下特点：有穷性一个算法应包含有限的操作步骤，而不能是无限的。确定性算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。有一个或多个输出算法的目的是为了求解，“解”就是输出。没有输出的算法是没有意义的。有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果。不能b=0时，求a/b等2.4怎样表示一个算法常用方法：自然语言、传统流程图、结构化流程图、伪代码、PAD图等2.4.1

用自然语言表示算法在2.2节中介绍的算法是用自然语言表示的。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。此外，用自然语言描述包含分支和循环的算法，不很方便(如例2.5的算法)。因此，除了很简单的问题以外，一般不用自然语言描述算法。2.4.2用流程图表示算法流程图是用一些图框表示各种操作，已通用。用图形表示算法，直观形象，易于理解。美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号(见图2.3)。图2.3图2.3中菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。见图2.4。连接点(小圆圈)是用于将画在不同地方的流程线连接起来。如图2.5中有两个以○为标志的连接点(在连接点圈中写上“1”)，它表示这两个点是互相连接在一起的。实际上它们是同一个点，只是画不下才分开来画。用连接点，可以避免流程线的交叉或过长，使流程图清晰。图2.4图2.5【例2.6】将例2.1求5!的算法用流程图表示，流程图见图2.6。菱形框两侧的“Y”和“N”代表“是”(yes)和“否”(no)。如果需要将最后结果打印出来，可以在菱形框的下面再加一个输出框，见图2.7。图2.6图2.7【例2.7】将例2.2的算法用流程图表示。将50名学生中成绩在80分以上者的学号和成绩打印出来。在此算法中没有包括输入50个学生数据的部分，如果包括这个输入数据的部分，流程图如图2.9所示。图2.9【例2.8】将例2.4的算法用流程图表示。见图2.11。【例2.9】将例2.5判断素数的算法用流程图表示，见图2.12。图2.11图2.12一个流程图包括以下几部分：

①表示相应操作的框；

②带箭头的流程线；

③框内外必要的文字说明。需要提醒的是流程线不要忘记画箭头，因为它是反映流程的执行先后次序的。用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。但是这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。在结构化程序设计方法推广之后，许多书刊已用N-S结构化流程图代替这种传统的流程图。2.4.3三种基本结构和改进的流程图1.传统流程图的弊端只规定了几种基本结构这些结构是方便面式的2.三种基本结构（1）顺序结构，如图2.14所示，虚线框内是一个顺序结构。（2）选择结构，或称选取结构，或称分支结构，如图2.15所示。图2.14图2.15（3）循环结构，它又称重复结构。有两类循环结构：

①当型(While型)循环结构，见图2.17(a)。②直到型(Until型)循环，见图2.17(b)。图2.17以上三种基本结构，有以下共同特点：（1）只有一个入口。（2）只有一个出口。（3）结构内的每一部分都有机会被执行到。（4）结构内不存在“死循环”(无终止的循环)。基本结构不一定只限于上面三种，只要具有上述4个特点的都可以作为基本结构。人们可以自己定义基本结构，并由这些基本结构组成结构化程序。一个好的算法只能由3种基本结构相互嵌套而成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.24图2.25（3）循环结构：当型循环结构用图2.26形式表示。图2.26表示当p1条件成立时反复执行A操作，直到p1条件不成立为止。直到型循环结构用图2.27形式表示。图2.26图2.27同样，三种基本结构可以相互嵌套例如：YP>=100Nr=0.08r=0.06n<=10P*(1+r)=>p【例2.11】将例2.1的求5!算法用N-S图表示。见图2.29。【例2.12】将例2.2的算法用N-S图表示。将50名学生中成绩高于80分的学号和成绩打印出来。见图2.31。图2.29图2.31【例2.13】将例2.3判定闰年的算法用N-S图表示。见图2.32。【例2.14】将例2.4的算法用N-S图表示。见图2.33。图2.32图2.33【例2.15】将例2.5判别素数的算法用N-S流程图表示。流程图表示见图2.34，N-S图表示见图2.35。图2.35图2.34通过以上例子，可以看出用N-S图表示算法的优点。它比文字描述直观、形象、易于理解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的。N-S流程图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。用N-S图表示的算法都是结构化的算法(它不可能出现流程无规律的跳转，而只能自上而下地顺序执行)。N-S图如同一个多层的盒子，又称盒图(boxdiagram)。2.4.5用伪代码表示算法伪代码(pseudocode)是用介于自然语言和计算机语言之间的文字和符号来描述算法。【例2.16】求5!。用伪代码表示的算法如下：开始置t的初值为1

置i的初值为2

当i<=5，执行下面操作：使t=t×i

使i=i+1(循环体到此结束)

打印t的值结束begin/*算法开始*/1=>t2=>iwhilei<=5{t×i=>ti+1=>i}printtend/*算法结束*/【例2.17】输出50个学生中成绩高于80分者的学号和成绩。用伪代码表示算法如下：

begin/*算法开始*/ 1=>i whilei<=50 {inputniandgi i+1=>i} 1=>i whilei<=50 {ifgi≥80printniandgi i+1=>i}end/*算法结束*/【例2.18】输出2000—2500年中的每一年是否闰年。begin/*算法开始*/2000=>ywhiley<=2500{ify能被4整除

ify不能被100整除

printy;“是闰年”

elseify被400整除

printy；“闰年”

elseprinty；“非闰年”

endifendifelseprinty;“非闰年”

endify+1=>y}end/*算法结束*/【例2.19】求1-1/2+1/3-1/4+…+1/99-1/100。用伪代码表示的算法如下：

begin/*算法开始*/ 1=>sum2=>deno 1=>sign whiledeno<=100 {(-1)×sign=>sign sign×1/deno=>term sum