c语言枚举法(穷举法).ppt

《c语言枚举法(穷举法).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举法（穷举法）“笨人之法”：把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。分析：这是个不定方程——三元一次方程组问题（三个变量，两个方程）x＋y＋z=1005x＋3y＋z/3=100设公鸡为x只，母鸡为y只，小鸡为z只。百元买百鸡问题分析x＋y＋z=1005x＋3y＋z/3=100三重循环voidmain(){intx,y,z;for(x=0;x<=100;x++)for(y=0;y<=100;y++)for(z=0;z<=100;z++){if(x+y+z==100&&5*x+3*y+z/3==100)printf("x=%d,y=%d,z=%d",x,

2、y,z);}}结果：x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84【讨论】为什么多了几组解??百元买百鸡问题分析voidmain(){intx,y,z;for(x=0;x<=100;x++)for(y=0;y<=100;y++)for(z=0;z<=100;z++){if(z%3==0&&x+y+z==100&&5*x+3*y+z/3==100)printf("x=%d,y=%d,z=%d",x,y,z);}}结果：x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=

3、84【讨论】此为“最笨”之法——要进行101×101×101=1030301次（100多万次）运算。优化voidmain(){intx,y,z;for(x=0;x<=100;x++)for(y=0;y<=100;y++){z=100-x-y;if(z%3==0&&5*x+3*y+z/3==100)printf("cocks=%d,hens=%d,chickens=%d",x,y,z);}}【讨论】令z=100-x-y只进行101×101=10201次运算（前者的1%）取x<=20,y<=33只进行21×34=714次运算（第1种运算的6.9e-4）继续优化voidmain

4、(){intx,y,z;for(x=0;x<=14;x++)for(y=0;y<=25;y++)if(7*x+4*y==100){z=100-x-y;printf("cocks=%d,hens=%d,chickens=%d",x,y,z);}}取x<=14,y<=25只进行15×26=390次运算利用穷举法求解趣味智力题(韩信点兵)韩信有一队兵，他想知道有多少人，便让士兵排队报数。按从1至5报数，最末一个士兵报的数为1；按从1至6报数，最末一个士兵报的数为5；按从1至7报数，最末一个士兵报的数为4；最后再按从1至11报数，最末一个士兵报的数为10。你知道韩信至少有多少兵吗

5、？设兵数为x，则x应满足：x%5==1&&x%6==5&&x%7==4&&x%11==10穷举法对x从1开始试验#includevoidmain(){intx;for(x=1;x<5000;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d",x);}}}/*属于“瞎猫碰死耗子”的做法*/穷举法求解韩信点兵#includevoidmain(){intx;for(x=1;;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d

6、n",x);}}}/*死循环——永远不会退出的循环*/穷举法求解韩信点兵穷举法求解韩信点兵：方案1-goto#includevoidmain(){intx;for(x=1;;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d",x);gotoEND;}}END:;}穷举法求解韩信点兵：方案2-break#includevoidmain(){intx;for(x=1;;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d"

7、,x);break;}}}穷举法求解韩信点兵:方案3-标志变量#includevoidmain(){intx;intfind=0;/*设置找到标志为假*/for(x=1;!find;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d",x);find=1;}}}课堂讨论：谁做的好事？有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：C胡说。已知三个人说的