c语言程序设计3(算法初步)课件.ppt

《c语言程序设计3(算法初步)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、利用计算机求解问题的一般过程（1）问题分析阶段（2）数据结构设计阶段（3）算法设计阶段计算机解题的步骤。（4）编码与调试阶段用某种程序设计语言描述的解题算法-----计算机程序。第3章计算机算法初步3.1算法的概念正确、易读、高效、通用算法描述例：求n!即1×2×3×…×n设两个变量，p存放乘积，i存放乘数。S1:输入nS2:使p=1S3:使i=2S4:使p×i,乘积仍放在变量p中,可表示为p×ipS5:使i的值加1,即i+1iS6:判断i>n否。是：输出p;不是：返回S4执行步骤S4以及其后的步骤。开始2i，1

2、pp×ipi+1ii>n?输入n结束NY打印pP65例1（自学）：求解一元二次方程问题分析假设一元二次方程可以书写成ax2+bx+c=0。可以看出，任何一个一元二次方程都由三个系数a、b、c惟一确定，所以，首先需要用户输入三个系数，然后再根据一元二次方程的求解规则计算最终的结果，并将结果显示输出。算法描述NNYY开始输入a,b,cb2-4actt<0t=0结束输出一个解输出“无解”输出两个解#include#includemain(){inta,b,c,t;printf(“Inpu

3、ta,b,c:”);scanf(“%d%d%d”,&a,&b,&c);t=b*b–4*a*c;if(t<0)printf(“Nosolution”);elseif(t==0)printf(“X=%lf”,-b/(2.0*a));else{doublet0;t0=sqrt((double)t);printf(“X1=%lf,X2=%lf”,(-b+t0)/(2*a),(-b-t0)/(2*a));}}程序代码3.2穷举法概述列举出每一个可能性，逐个进行排查。P67例2：判断给定整数是否是素数。所谓素数是指仅能被

4、1和自身整除，且大于等于2的数值。问题分析为了检查一个整数是不是素数，可以采用穷举法。假设给定的整数用x表示，则判断过程就是确认x不能整除以2~x-1之间的任何整数。这就需要一一列举出2~x-1之间的每个整数进行排查。算法描述NY开始输入x2ttmain(){intx,t;printf(“Enteraninteger:”);scanf(“%d”,&x);for(t=2;t

5、*/if(x%t==0)break;if(t==x)/*是否通过循环条件出口*/printf(“%disprime”,x);elseprintf(“%disn’tprime”,x);}程序代码P69例3：百钱买百鸡。问题分析假设：公鸡x只，母鸡y只，小鸡z只。5x+3y+z/3=100x+y+z=100公鸡数量在0100/5母鸡数量在0100/3小鸡数量在0100，或：100-x-y有钱百枚，希望买一百只鸡；公鸡5枚钱一只，母鸡3枚钱一只，而小鸡3只1枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只

6、母鸡和几只小鸡。算法描述NY开始x加1结束5x+3y+z/3==100x<=100/5y<=100/3y加10x0yz=100-x-y输出x,y,zNYNY#include#includemain(){intx,y,z;for(x=0;x<=100/5;x++)for(y=0;y<=100/3;y++){z=100-x-y;if(15*x+9*y+z==300)printf(“x=%d,y=%d,z=%d”,x,y,z);}}程序代码递推法与迭代法是基于分步递增方式进行求解的解题

7、方法。递推法的基本方法：其基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算，将解决问题的过程分为若干个步骤，每个步骤都产生一个子解，每个子解都是由前面若干个子解生成的，它们均与问题规模相关，且是相关问题规模的完整解。3.3递推与迭代法采用递推法进行问题求解的关键在于找出递推公式和边界条件。如：求阶乘的递推公式：n!=n*(n-1)!边界条件：0！=1迭代法的基本方法迭代法与递推法类似，也是递增求解。但递推法每步得到的解都是对应问题规模的完整解，而迭代法中间步骤得到的解一般只是“近似解”，而不代表子问题的解。例如

8、：计算问题分析等比数列的递推公式为：itemi=itemi-1*ratio后项等于前项乘以比例值sumi=sumi-1+itemi前i项之和等于前i-1项之和加当前项由于在重复上述递推计算之前，需要将第1项的值累加到sum中，所以，需要先将item存入sum中。P71例4：等比数列求和。所谓等比数列是指在一组数据中，