第2章程序的灵魂--算法(2)

1、第第2章章 程序的灵魂程序的灵魂算法算法一个程序应包含以下两方面的内容：一个程序应包含以下两方面的内容：(1)对数据的描述对数据的描述。在程序中要指定数据的类型和数据的组织形式，。在程序中要指定数据的类型和数据的组织形式，即数据结构。即数据结构。(2)对操作的描述对操作的描述。即操作步骤，也就是算法。即操作步骤，也就是算法。数据是操作的对象，操作的目的是对数据进行加工处理，以得到数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。期望的结果。程序程序 = 数据结构数据结构 + 算法算法如果采用结构化程序设计的方法还必须指定一种计算机语言。如果采用结构化程序设计的方法还必须指定一

2、种计算机语言。程序程序 = 算法算法 + 数据结构数据结构 + 程序设计方法程序设计方法 + 语言工具和环境语言工具和环境算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。合适的方法。2.1 算法的概念算法的概念做任何事情都要有一定的步骤，在程序设计中这种步骤就称为做任何事情都要有一定的步骤，在程序设计中这种步骤就称为“算法算法”例如：求例如：求1+2+3+100，即，即有两种算法：有两种算法：1. 先进行先进行1+2，再加，再加3，直到直到100.2. =100+(1+99)+(2+98)+(49+51)+50=100

3、+49X100+50=5050不同的算法可获得相同的结果，但方法有优劣之分，因此，为了有不同的算法可获得相同的结果，但方法有优劣之分，因此，为了有效地进行解题，不仅需要保证算法的正确，还要考虑算法的质量，效地进行解题，不仅需要保证算法的正确，还要考虑算法的质量，选择合适的算法。选择合适的算法。计算机算法可分为两大类：计算机算法可分为两大类：1. 数值运算算法数值运算算法 (例如：解方程，求定积分等例如：解方程，求定积分等)2. 非数值运算算法非数值运算算法 (用于事务处理等用于事务处理等)1001nn1001nn2.2 简单算法举例简单算法举例例例2.1 求求1X2X3X4X51. 传统算法：

4、传统算法：1*2=22*3=66*4=2424*5=120(算法简单，通用性差算法简单，通用性差)2. 常用计算机算法：设变量常用计算机算法：设变量p为被乘数，变量为被乘数，变量i为乘数。为乘数。S1：p=1S2: i=2S3: p*ipS4: i+1iS5: 若若i5，返回，返回S3；否则结束。；否则结束。当求任意项乘积时，只需改变当求任意项乘积时，只需改变S5的条件即可。的条件即可。例例2.2 有有50个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在80分以上的学号和分以上的学号和成绩输出。用成绩输出。用n表示学生学号，表示学生学号，n1代表第一个学生学号，代表第一个学生学号，ni

5、代表代表第第i个学生的学号，用个学生的学号，用g代表学生成绩，代表学生成绩，gi代表第代表第i个学生成绩。个学生成绩。算法表示如下：算法表示如下：S1: 1iS2: 如果如果gi80，则输出，则输出ni和和gi；否则不输出。；否则不输出。S3: i+1iS4: 如果如果i50，返回，返回S2，继续执行；否则算法结束。，继续执行；否则算法结束。变量变量i作为下标，用来控制序号作为下标，用来控制序号(第第i个学生，第个学生，第i个学生的成绩个学生的成绩)。当当i超过超过50时，表示时，表示50个学生成绩处理完毕，算法结束。个学生成绩处理完毕，算法结束。例例2.3判定判定20002500年中的每一年

6、是否闰年，将结果输出。年中的每一年是否闰年，将结果输出。闰年条件：闰年条件：1. 能被能被4整除，但不能被整除，但不能被100整除。整除。 2. 能被能被100整除，又能被整除，又能被400整除。整除。算法表示如下算法表示如下: (设设y为被检测年份为被检测年份)S1: 2000yS2: 若若y不能被不能被4整除，则输出整除，则输出y “不是闰年不是闰年”，然后转到，然后转到S6S3: 若若y能被能被4整除，不能被整除，不能被100整除，输出整除，输出y “是闰年是闰年”。然后转到。然后转到S6S4: 若若y能被能被100整除，又能被整除，又能被400整除，输出整除，输出y “是闰年是闰年”。

7、然后转到。然后转到S6S5: 输出输出y “不是闰年不是闰年”S6: y+1yS7: 当当y2500时时,转转S2继续执行，否则算法停止。继续执行，否则算法停止。在这个算法采取了多次判断，逐步缩小范围，直至执行在这个算法采取了多次判断，逐步缩小范围，直至执行S5时，只可能时，只可能是是“非闰年非闰年”。例例2.410019914131211求算法可表示如下：算法可表示如下：S1: sign=1S2: sum=1S3: deno=2S4: sign=(-1)*signS5: term=sign*(1/deno)S6: sum=sum+termS7: deno=deno+1S8: 若若deno10

8、0返回返回S4；否则算法结束。；否则算法结束。例例2.5 对一个大于或等于对一个大于或等于3的正整数，判断它是否是一个的正整数，判断它是否是一个素数。素数。算法可表示如下：算法可表示如下：S1: 输入输入n的值的值S2: i=2(i作为除数作为除数)S3: n被被i除，得余数除，得余数rS4: 如果如果r=0，表示，表示n能被能被i整除，则输出整除，则输出n“不是素数不是素数”，算法结束，算法结束，否则执行否则执行S5S5: i+1iS6: 如果如果in-1，返回，返回S3；否则输出；否则输出n“是素数是素数”，然后结束。，然后结束。注：注：S6也可表示为也可表示为in2.3 算法的特性算法的

9、特性(1) 有穷性。一个算法应包含有限的操作步骤，而不能是无限的。有穷性。一个算法应包含有限的操作步骤，而不能是无限的。(2) 确定性。算法中的每一步骤应当是确定的，而不应该是含糊的、确定性。算法中的每一步骤应当是确定的，而不应该是含糊的、模棱两可的。模棱两可的。(3) 有零个或多个输入。所谓输入是指在程序执行时需要从外部取有零个或多个输入。所谓输入是指在程序执行时需要从外部取得必要的信息。得必要的信息。(4) 有一个或多个输出。算法的目的是为了求解，有一个或多个输出。算法的目的是为了求解，“解解”就是输出。就是输出。(5) 有效性。算法中的每一个步骤都应当有效执行，并得到确定的有效性。算法中

10、的每一个步骤都应当有效执行，并得到确定的结果。结果。程序设计中经常可以利用现成的程序或系统提供的函数库帮助我程序设计中经常可以利用现成的程序或系统提供的函数库帮助我们完成一些复杂的运算过程。们完成一些复杂的运算过程。2.4 怎样表示一个算法怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的方法有：自然语为了表示一个算法，可以用不同的方法。常用的方法有：自然语言、言、传统流程图传统流程图、结构化流程图结构化流程图、伪代码、伪代码、PAD图等。图等。2.4.1 用传统流程图表示算法用传统流程图表示算法常用流程图符号：常用流程图符号：起止框输入输出框判断框处理框或流程线连接点注释框流程图的流

11、程图的3种基本结构种基本结构AB顺序结构顺序结构选择结构选择结构循环结构循环结构PABPAPPAPA成立成立不成立不成立不成立不成立成立成立不成立不成立不成立不成立成立成立成立成立当型当型直到型直到型例例2.6 求求5！的算法流程图！的算法流程图开始开始1t2ii+1it*iti5输出输出t结束结束YN例例2.7 输出输出50名学生中成绩在名学生中成绩在80分以上的分以上的学号的算法流程图学号的算法流程图开始开始1igi80i+1ii50结束结束Y输出输出ni;giNNYY例例2.8 判定判定20002500年中的每一年是否闰年的算法流程图年中的每一年是否闰年的算法流程图开始开始Y2500结束

12、结束输出输出y“是闰年是闰年”2000yY不能被不能被4整除整除Y不能被不能被400整除整除输出输出y“是闰年是闰年”输出输出y“不是闰年不是闰年”输出输出y“不是闰年不是闰年”y+1yY不能被不能被100整除整除YYYYNNN开始开始结束结束y+1y例例2.9的的算算法法流流程程图图1 10 00 01 19 99 91 14 41 13 31 12 21 1求求1 1开始开始deno100结束结束1sum2deno1sign输出输出sumsign*(1/deno)term(-1)*signsignsum+termsumdeno+1deno例例2.10 判断素数的算法流程图判断素数的算法流程

13、图开始开始r=0?结束结束2in/i的余数的余数r输入输入ni+1i输出输出n“不是素数不是素数”in?输出输出n“是素数是素数”YYNN2.4.2 用用N-S流程图表示算法流程图表示算法流程图的流程图的3种基本结构种基本结构顺序结构顺序结构选择结构选择结构循环结构循环结构ABP不成立不成立成立成立ABAA当当P1成立成立直到直到P1成立成立当当型型直直到到型型例例2.11 求求5！的！的N-S流程图流程图1t2it*iti+1i直到直到i5输出输出t例例2.12 输出输出50名学生中成绩在名学生中成绩在80分以上的学号的分以上的学号的N-S流流程图程图1igi80是是否否输出输出ni和和gii+1i直到直到i50例例2.13 判断闰年的判断闰年的N-S流程图流程图2000yy/4的余数为的余数为0？是是否否y/100的余数不为的余数不为0？是是否否y/400的余数为的余数为0？是是否否输出输出y“是闰年是闰年”输出输出y“是闰年是闰年”输出输出y“非闰年非闰年”输出输出y“非闰年非闰年”Y+1y直到直到y2500S流程图S流程图- -的N的N1001001 199991 14 41