程序设计算法实验 穷举

《程序设计算法实验 穷举》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计算法实验一——穷举算法（黑体，三号）1.穷举简介（小标题：黑体，小四；内容：宋体，五号）穷举法又称列举法，其基本思想是逐一列举问题所涉及的所有情况。从中寻找满足条件的结果。适用于数量较小的问题。2.算法流程或设计思想穷举通常应用循环结构来实现。在循环体中，应用选择结构实施判断筛选，求得所要求的解。使用穷举法的关键是要确定正确的穷举的范围。3.分析算法的时间复杂度4.程序设计中的问题及解决方案5.运行说明（包括实验数据和结果说明）6.主要程序代码（添加程序注释）7.对比解决该问题的其他算法（选作）题目：1.有一堆零件（1000－5000个之间），如果以4个零件为一组进行分组，则多

2、2个零件；如果以7个零件为一组进行分组，则多3个零件；如果以9个零件为一组进行分组，则多5个零件。编程求解这堆零件总数。参考答案：#includevoidmain(){intn,count=0;for(n=1000;n<=5000;n++)if(n%4==2&&n%7==3&&n%9==5){printf("%d",n);count=count+1;if(count%5==0)printf("");}printf("count=%d",count);}1.穷举三位数的水仙花数。水仙花数是指一个n位数(n≥3)，它的每个位上的数字的n次幂之和等于它本身。（例

3、如：13+53+33=153）参考答案：/*2.穷举三位数的水仙花数。水仙花数是指一个n位数(n≥3)，它的每个位上的数字的n次幂之和等于它本身。（例如：13+53+33=153）*/#includevoidmain(){inta,b,c,d;for(a=100;a<=999;a++){b=a/100;c=a/10-b*10;d=a-b*100-c*10;if(b*b*b+c*c*c+d*d*d==a)printf("%d=%d^3+%d^3+%d^3",a,b,c,d);}}1.穷举真分数递增序列中的第k项的值。（可参考课本P19）参考答案：#include

4、tdio.h>voidmain(){inta,b,k,n,i,j,h,t,u,c[3000],d[3000];printf("inputthenumbera,b,k:");scanf("%d%d%d",&a,&b,&k);n=0;for(j=a;j<=b;j++){for(i=1;i<=j-1;i++){for(t=0,u=2;u<=i;u++)if(j%u==0&&i%u==0){t=1;break;}if(t==0){n++;c[n]=i;d[n]=j;}}}for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++)if(c[j]*d[j+1]>c[j+1]*

5、d[j]){h=c[j];c[j]=c[j+1];c[j+1]=h;h=d[j];d[j]=d[j+1];d[j+1]=h;}printf("Thetotalnumberis:n=%d",n);printf("the%dis:%d/%d",k,c[k],d[k]);}1.用精简穷举循环解决百钱百鸡问题。公鸡5文钱1只,母鸡3文钱1只,小鸡一文钱3只。100文钱如何买100只鸡?参考答案：#includevoidmain(){intx,y,z,j=0;printf("possibleplanstobuy100fowlswith100wen:");for(x=

6、0;x<=20;x++)/*外层循环控制鸡翁数*/for(y=0;y<=33;y++)/*内层循环控制鸡母数y在0~33变化*/{z=100-x-y;/*内外层循环控制下，鸡雏数z的值受x,y的值的制约*/if(z%3==0&&5*x+3*y+z/3==100)/*验证取z值的合理性及得到一组解的合理性*/printf("%2d:cock=%2dhen=%2dchicken=%2d",++j,x,y,z);}}1.穷举1-100以内的素数。参考答案：#includevoidmain(){intt,i,j,m=0;//定义循环变量i和j,i用来遍历从100以内的所有

7、数字，j用来遍历从2到i/2for(i=3;i<=100;i++){t=1;//t作为标记，如果在2到i/2间有i的因数，那么将t置为0，否则保持t=1for(j=2;j<=(i/2);j++)//遍历2到i/2{if(i%j==0)//如果i对j求余数等于0，那么说明j是i的因数，所以i不是素数，便将t置为零t=0;}if(t==1)//如果经过上面的筛选后t还是等于1，那么说明i是素数，将其打印处理即可。{m=m+1;printf("%3d