lesson8计算机算法初步

《lesson8计算机算法初步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lesson8计算机算法初步学习目标:31掌握几个常用的解题算法：穷举、迭代3穷举法2概述穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。根据问题中的部分条件（已知的条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。3穷举法21、旅行途中发现自己忘记了开锁的密码，怎么办？2、从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。3穷举法2穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。穷举解题步骤：1、问题解的可能搜索的范围：用循环或循环嵌套结构实现2、写出符合问题解的条

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

3、*列举小于x大于1的所有整数*/if(x%t==0)break;if(t==x)/*是否通过循环条件出口*/printf(“%disprime”,x);elseprintf(“%disn’tprime”,x);return0;}注意判断是否是素数的条件与判断位置lesson8_01.c如果要找一个范围内那些是素数怎么改写程序？#includeintmain(){inti,x,y,t,j=0;do{printf("Inputnumericalrange(x,y,x

4、

5、y<3

6、

7、x>y);for

8、(i=x;i<=y;i++){for(t=2;t

9、有限的，都不会超过100。通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购买这些鸡所用的花费，但这个题目要求找出那些花费正好100枚且鸡的总数也为100只的情况。因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。算法描述#include#includeintmain(){intx,y,z;for(x=0;x<=100/5;x++)for(y=0;y<=100/3;y++)for(z=0;z<=100;z++){if(x+y+z==100&&15*x+9*y+z==300)printf(“x=%d,y=%d,z=%d

10、n”,x,y,z);}return0;}3课堂练习3１、求所有的三位水仙花数若一个3位自然数的各位数字的3次方之和等于它本身,则称这个自然数为水仙花数。例如:153(153=13+33+53)是水仙花数#includeintmain(){inti,j,k,x;for(x=100;x<1000;x++){i=x/100;j=x/10%10;k=x%10;if(i*i*i+j*j*j+k*k*k==x)printf("x=%d",x);}return0;}3递推与迭代法4概述递推是计算机数值计算中的一个重要算法。其基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算，进

11、而充分利用计算机擅长重复计算的特点。采用递推法进行问题求解的关键在于找出递推公式和边界条件。3递推与迭代法4例3：等比数列求和等比数列是指在一组数据中，后项和前项之间存在着一个固定的比例关系。例如：整数序列3、15、75、375的初值是3，后项与前项是5倍的关系，即前项乘以5得到后项。本题要求给定等比序列的首项和比例，计算这个数列的前10项之和。3递推与迭代法4问题分析等比数列的递推公式为：ite