第2章_算法--程序的灵魂[1]

第2章算法—程序的灵魂一个程序应包含以下两方面的内容：(1)对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构。(2)对操作的描述。即操作步骤，也就是算法。数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。程序=数据结构+算法如果采用结构化程序设计的方法还必须指定一种计算机语言。程序=算法+数据结构+程序设计方法+语言工具和环境算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。2.1什么是算法做任何事情都要有一定的步骤，在程序设计中这种步骤就称为“算法”例如：求1+2+3+…+100，即有两种算法：1.先进行1+2，再加3，…直到100.2.=100+(1+99)+(2+98)+…+(49+51)+50=100+49X100+50=5050不同的算法可获得相同的结果，但方法有优劣之分，因此，为了有效地进行解题，不仅需要保证算法的正确，还要考虑算法的质量，选择合适的算法。计算机算法可分为两大类：1.数值运算算法(例如：解方程，求定积分等)2.非数值运算算法(用于事务处理等)1001nn1001nn2.2简单的算法举例例2.1求1X2X3X4X51.传统算法：1*2=2→2*3=6→6*4=24→24*5=120(算法简单，通用性差)2.常用计算机算法：设变量p为被乘数，变量i为乘数。S1：p=1S2:i=2S3:p*i→pS4:i+1→iS5:若i≤5，返回S3；否则结束。当求任意项乘积时，只需改变S5的条件即可。例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个学生，第i个学生的成绩)。当i超过50时，表示50个学生成绩处理完毕，算法结束。例2.3判定2000—2500年中的每一年是否闰年，将结果输出。闰年条件：1.能被4整除，但不能被100整除。2.能被100整除，又能被400整除。算法表示如下:(设y为被检测年份)S1:2000→yS2:若y不能被4整除，则输出y“不是闰年”，然后转到S6S3:若y能被4整除，不能被100整除，输出y“是闰年”。然后转到S6S4:若y能被100整除，又能被400整除，输出y“是闰年”。然后转到S6S5:输出y“不是闰年”S6:y+1→yS7:当y≤2500时,转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:若deno≤100返回S4；否则算法结束。例2.5对一个大于或等于3的正整数n，判断它是否是一个素数。算法可表示如下：S1:输入n的值S2:i=2(i作为除数)S3:n被i除，得余数rS4:如果r=0，表示n能被i整除，则输出n“不是素数”，算法结束，否则执行S5S5:i+1→iS6:如果i≤n-1，返回S3；否则输出n“是素数”，然后结束。注：S6也可表示为i≤√n2.3算法的特性(1)有穷性。一个算法应包含有限的操作步骤，而不能是无限的。(2)确定性。算法中的每一步骤应当是确定的，而不应该是含糊的、模棱两可的。(3)有零个或多个输入。所谓输入是指在程序执行时需要从外部取得必要的信息。(4)有一个或多个输出。算法的目的是为了求解，“解”就是输出。(5)有效性。算法中的每一个步骤都应当有效执行，并得到确定的结果。程序设计中经常可以利用现成的程序或系统提供的函数库帮助我们完成一些复杂的运算过程。2.4怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的方法有：自然语言、传统流程图、结构化流程图、伪代码、PAD图等。2.4.1用传统流程图表示算法常用流程图符号：起止框输入输出框判断框处理框或流程线连接点注释框流程图的3种基本结构AB顺序结构选择结构循环结构PABPAPPAPA成立不成立不成立成立不成立不成立成立成立当型直到型例2.6求5！的算法流程图开始1→t2→ii+1→it*i→ti5输出t结束YN例2.7输出50名学生中成绩在80分以上的学号的算法流程图开始1→igi≥80i+1→ii＞50结束Y输出ni;giNNYY例2.8判定2000—2500年中的每一年是否闰年的算法流程图开始Y2500结束输出y“是闰年”2000→yY不能被4整除Y不能被400整除输出y“是闰年”输出y“不是闰年”输出y“不是闰年”y+1→yY不能被100整除YYYYNNN开始结束y+1→y例2.9的算法流程图1001991413121求1开始deno100结束1→sum2→deno1→sign输出sumsign*(1/deno)→term(-1)*sign→signsum+term→sumdeno+1→deno例2.10判断素数的算法流程图开始r=0?结束2→in/i的余数→r输入ni+1→i输出n“不是素数”i√n?输出n“是素数”YYNN2.4.2用N-S流程图表示算法流程图的3种基本结构顺序结构选择结构循环结构ABP不成立成立ABAA当P1成立直到P1成立当型直到型例2.11求5！的N-S流程图1→t2→it*i→ti+1→i直到i5输出t例2.12输出50名学生中成绩在80分以上的学号的N-S流程图1→igi≥80是否输出ni和gii+1→i直到i50例2.13判断闰年的N-S流程图2000→yy/4的余数为0？是否y/100的余数不为0？是否y/400的余数为0？是否输出y“是闰年”输出y“是闰年”输出y“非闰年”输出y“非闰年”Y+1→y直到y2500S流程图-的N1001991413121例2.14求11→sum2→deno1→sign(-1)*sign→signsign*1/deno→termsum+term→sumdeno+1→deno直到deno100输出sum例2.15判别素数的N-S流程图输入n0→w2→in/i的余数→rr=0?是否1→wi+1→i直到√n或w≠0w=0?是否输出n“是素数”输出n“不是素数”