c语言第2章 算法.ppt

《c语言第2章 算法.ppt》由会员分享，可在线阅读，更多相关《c语言第2章 算法.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1,第 2 章 程序的灵魂算法,2,2.1 算法的概念,解决某问题,用编程语言描述的一组计算机能够识别和执行的指令。,对数据的描述,程序,对操作的描述,3,4,Nikiklaus Wirth提出的公式：,程序=数据结构+算法,程序=算法+数据结构+程序设计方法+语言工具和环境,5,2.2 简单算法举例,这样的算法虽然正确，但太繁琐。,6,改进的算法,如果计算100！只需将S5:若i5改成i100即可。,7,考虑如果S5步骤写成：若i b,c=m,ac,bc,b=m,c=m,a=m,Y,N,Y,N,N,Y,打印m,例2.7 输入3个数,将最大数送到M中打印输出。,19,例 2.8将例2.2的算法

2、用流程图表示。,20,例2.9判断素数流程图,转移太多流程杂乱,21,传统流程图的弊端用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。流程图对流程线的使用没有限制，使得流程图变得毫无规律，如同一碗面条(a bowl of spaghetti)。,22,2、三种基本结构的表示（1）顺序结构,条件,语句1,语句2,Y,N,语句1,语句2,（2）选择结构,a,b,a,b,23,条件,语句,条件,语句,（3）循环结构,a) 当型循环,b) 直到型循环,Y,N,Y,N,a,a,b,b,24,三种基本结构的特点：,（1）只有一个入口（2）只有一个出口（3）不存在死语句（4）不存在死循环,由

3、以上三种基本结构组成的算法结构,可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和跳转。,25,N-S图用层层嵌套的方框图形来描述程序算法，避免了流程图中出现的流程线，有效控制了无条件转移，体现了结构化描述方法。,N-S图的基本结构框图,语句A,语句B,语句A,语句B,条件,Y,N,1、顺序结构,2、选择结构,26,语句组,（3）循环结构,a) 当型循环,b) 直到循环,当条件成立,语句组,直到条件成立,27,例11： 用N-S图表示有50个学生，要求将他们之中成绩在80分以上者打印出来。,28,例12:判别n是否为素数：

4、,1=w i+1=i,输入n; 0=w; 2=i,n除i的余数=r,打印n是素数 打印n不是素数,r=0,直到i 或w0,W = 0,N,Y,Y,N,标志,结束循环,？,？,29,N-S图比文字描述直观、形象、易于理解；比流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的。N-S图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进行就可以了，十分方便。,30,2.4.5 用伪代码表示算法,伪代码用介于自然语言和计算机语言之间的文字和符号来描述算法。,大话爱情C语言,31,32,伪代码书写格式比较自由，可以随手写下

5、去，容易表达出设计者的思想。用伪代码写的算法容易修改，容易写出结构化的算法。但是，用伪代码写算法不如流程图直观，可能出现逻辑上的错误。,33,2.4.6 用计算机语言表示算法,我们的任务是用计算机解题，就是用计算机实现算法；用计算机语言表示算法必须严格遵循所用语言的语法规则。,34,例2.11求12345用C语言表示。,main()int i,t; t=1; i=2; while(i=5)t=t*i;i=i+1;printf(%dn,t);,35,例 2.12 求,main() int sigh=1; float deno=2.0,sum=1.0,term; while(deno=100) s

6、igh= -sigh; term= sigh/ deno; sum=sum+term; deno=deno+1; printf(%fn,sum);,36,一、结构化程序设计思想,自顶向下：先从全局、整体设计逐步细化：将一个问题分解成几个较小的问题解决模块化： 将一个大任务分解成若干个较小的部分， 每 个部分承担一定功能，称为“功能模块”结构化编码：将每一模块用计算机语言表示并组合。,2.5 结构化程序设计方法,37,我的大学生活,学习,业余生活,感情生活,大一,大二,大三,大四,60分万岁,考研,找工作,补考,逛街,体育锻炼,电子竞技,技能提升,一见钟情,愈败愈勇,success,不堪回首,公

7、务员,IT公司,38,输入100个数存入x1，x2,x100,打印x1.x100中不等于0的数,S1,NS流程图,让x1x2,.x100中的非素标志变为0,S3,S2,输入xi,当i=100,i=i+1,i=1,S1细化,xi0,当i=100,i=i+1,i=1,Y,N,打印xi,S3细化,例2.13 给100个整数，打印输出其中的素数,39,输入100个数存入X1，x2,x100,打印1.x100中不等于0的数,S1,NS流程图,让x1，x100中的非素变为0,S3,S2,判断xi是否是素数，若不是则将xi=0,当i=100,i=i+1,i=1,S2细化,r=0,rsqrt(xi),S21细

8、化,40,输入xi,当i=100,i=i+1,i=1,当i sqrt(xi),i=i+1,xi0,当i=100,i=i+1,i=1,Y,N,打印xi,输入100个数存入X1，x2,x100,打印x1.x100中不等于0的数,让x1，x100中的非素变为0,细化后的流程图,41,从上面的例子中可以看出，结构化程序设计方法是解决复杂问题的有效的方法。,42,总结,算法的特点算法的表示（重点掌握流程图、N-S流程图）,43,作业,用传统流程图表示和N-S图表示求解以下问题的算法 1.一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如，6的因子为1、2、3，而6=1+2+3，因此6是“完数”。找出1000以内的所有“完数”。 2.求两个数m，n的最大公约数和最小公倍数。,