第二章 算法(3)

1、第2章 程序的灵魂算法,2.1算法的概念 2.2简单算法举例 2.3算法的特性 2.4怎样表示一个算法 2.5结构化程序设计方法 总结,程序（指令的有序集合，即一系列的数据加工步骤）： 数据结构（对数据的描述，指定数据的类型和数据的组织形式） 算法（操作步骤）,数据结构 + 算法 = 程序,程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境,2.1 算法的概念,算法是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列 算法可以分为两大类：数值运算和非数值运算,2.2 简单算法举例,例2.1 求12 3 4 5。,最简单的方法： 步骤1： 先求12，得到结果2

2、。 步骤2： 将步骤1得到的乘积2再乘以3，得到结果6。 步骤3： 将6再乘以4，得24。 步骤4： 将24再乘以5，得120。这就是最后的结果。,算法： S1： 使p=1 S2： 使i=2 S3： 使pi，乘积仍放在变量p中，可表示为pi=p S4： 使i的值加1，即i+1 = i S5： 如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。,如果： 12 3 4 5 1000?,繁琐？,如果： 12 3 4 5 1000?,如果： 13 579 11?,通用灵活,例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示

3、学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩,S1：1=i S2：如果gi80，则打印ni和gi，否则不打印 S3：i+1=i S4：如果i50，返回S2，继续执行；否则，算法结束。,结束,所有年份,例2.3 判定20002500年中的每一年是否闰年，将结果输出。,闰年的条件是： 能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年； 能被100整除，又能被400整除的年份是闰年。如1600年、2000年是闰年。 不符合这两个条件的年份不是闰年。,能被4整除,不能被4整除,能被100整除,能被400整除,例2.3 判

4、定20002500年中的每一年是否闰年，将结果输出。,设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：当y2500时，转S2继续执行，如y2500，算法停止。,y=2000年,例2.3 判定20002500年中的每一年是否闰年，将结果输出。,设y 为被检测的年份。可采取以下步骤： S1：2000

5、=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：当y2500时，转S2继续执行，如y2500，算法停止。,y=2100年,例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

6、+term=sum S7：deno+1=deno S8：若deno100返回S4；否则算法结束。,例2.5 对一个大于或等于3的正整数，判断它是不是一个素数。,S1：输入n的值 S2：2=i （i作为除数） S3：n被i除，得余数r S4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5 S5：i+1=i S6：如果in-1，返回S3；否则打印 n “是素数”，然后结束。,所谓素数，是指除了1和该数本身之外，不能被其他任何整数整除的数。例如，13是素数，因为它不能被2，3，4，12整除。,n不必被2到(n-1)的整数除，只需被2到n的开方间整数除即可,2.3 算法的特

7、性,1.有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 2.确定性 算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的 3.有零个或多个输入 4. 有一个或多个输出 5. 有效性 算法中的每一个步骤都应当能有效地执行，并得到确定的结果,2.4 算法的表示方法,自然语言表示 流程图表示 N-S流程图表示 伪代码表示 计算机语言表示,2.4.1自然语言表示,在2.2节中介绍的算法是用自然语言表示的 自然语言表示通俗易懂，但文字冗长， 容易出现“歧义性”。,2.4.2流程图表示,流程图表示的特点： 直观形象 易于理解 美国国家标准化协会（ANSI）规定的流程符号：,图 2.4 图

8、 2.5,三种基本结构,1966年，Bohra和Jacopini提出了以下三种基本结构，作为表示一个良好算法的基本单元,顺序结构,选择结构,循环结构,图2.18是当型循环的应用例子，图2.19是直到型循环的应用例子。 图2.18 图2.19,三种基本结构的特点 (1) 只有一个入口 (2) 只有一个出口 (3) 结构内的每一部分都有机会被执行到 (4) 结构内不存在“死循环”(无终止的循环),基本结构不一定只限于上面三种，只要具有上述4个特点的都可以作为基本结构,例2.6 求12 3 4 5。,开始,1 t,2 i,t i t,i +1 i,i 5,结束,Y,N,开始,1 t,2 i,t i

9、t,i +1 i,i 5,结束,Y,N,打印,练习： 求2+4+6+200的和。,例2.7 有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩,开始,1 i,gi80,打印ni，gi,i +1i,i50,结束,Y,N,Y,N,例2.8 判定20002500年中的每一年是否闰年，将结果输出。,求A、B、C三数中的最大数。,例2.9 求1-1/2+1/3-1/4+1/99-1/100。,例2.10 对一个大于或等于3的正整数，判断它是不是一个素数。,传统流程图的弊端 传统的流程图用流程线

10、指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。 这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。,2.4.3 用N-S流程图表示算法,既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么基本结构之间的流程线就属多余的了。 1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，。这种流程图又称N-S结构化流程图。,N-S流程图用以下的流程图符号：,(1) 顺序结构:

11、 (2) 选择结构： (3) 循环结构：,例2.11 求12 3 4 5。,例2.12 有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩,例2.13 判定20002500年中的每一年是否闰年，将结果输出。,例2.14 求1-1/2+1/3-1/4+1/99-1/100。,例2.5 对一个大于或等于3的正整数，判断它是不是一个素数。,结构化的算法 由一些基本结构顺序组成的 每个基本结构又可以包含其他的基本结构 在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之

12、内(如循环中流程的跳转) 一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法,练习： 1、求2+4+6+200的和。 2、求A、B、C三数中的最大数。,2.4.4 用伪代码表示算法,传统的流程图和N-S图表示算法，直观易懂，但画起来比较费事。因此，流程图适宜表示一 个算法，但在设计算法过程中使用不是很理想。为了设计算法时方便，常用一种称为伪代码(pseudo code)的工具。 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图

13、形符号，因此书写方便 、格式紧凑，也比较好懂，便于向计算机语言算法(即程序)过渡,例2.16 求5!,开始 置t的初值为1 置i的初值为2 当i=5，执行下面操作： 使t=ti 使i=i+1 (循环体到此结束) 打印t的值 结束,BEGIN(算法开始) 1=t 2=i while it i+1=i print t END(算法结束),例2.17 打印出50个学生中成绩高于80分者的学号和成绩,BEGIN(算法开始) 1=i while ii 1=i while ii END(算法结束),例2.18 打印20002500年中的每一年是否闰年,BEGIN(算法开始) 2000=y while yy

14、 END(算法结束),例2.19求1-1/2+1/3-1/4+1/99-1/100,BEGIN (算法开始) 1= sum 2= deno 1= sign while deno sign sign1/deno=term sum+term=sum deno+1=deno print sum END (算法结束),2.4.6 用计算机语言表示算法,例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语言表示

15、。,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.5 结构化程序设计方法,(1) 自顶向下； (2) 逐步细化； (3) 模块化设计； (4) 结构化编码。,例2.22 将1到1000之间的素数打印出来。 我们已在本章中讨论过判别素数的方法，现在采用“筛法”来求素数表。所谓“筛法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的著名数学家。

16、他采取的方法是 ，在一张纸上写上1到1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数 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,具体做法如下： (1) 先将1挖掉(因为1不是素数)。 (2) 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。 (3) 用3去除它后面各数，把3的倍数挖掉。 (4) 分别用