C语言穷举法经典例题.ppt

,第二级,第三级,第3章 程序控制结构,枚举法（穷举法）,“笨人之法”：,把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。,分析：,这是个不定方程三元一次方程组问题,（三个变量，两个方程）,xyz=100,5x3yz/3=100,设公鸡为,x,只，母鸡为,y,只，小鸡为,z,只。,百元买百鸡问题分析,xyz=100,5x3yz/3=100,三重循环,void main(),int x,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=%dn,x,y,z);,结果：,x=0,y=25,z=75,x=4,y=18,z=78,x=8,y=11,z=81,x=12,y=4,z=84,【讨论】为什么多了几组解?,?,百元买百鸡问题分析,void main(),int x,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=%dn,x,y,z);,结果：,x=0,y=25,z=75,x=4,y=18,z=78,x=8,y=11,z=81,x=12,y=4,z=84,【讨论】,此为“最笨”之法要进行101101101=1030301次（100多万次）运算。,优化,void main(),int x,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=%dn,x,y,z);,【讨论】,令z=100-x-y 只进行101101=10201 次运算（前者的1%）,取x=20,y=33 只进行2134=714 次运算（第1种运算的6.9e-4）,编程思路：,如何找到该人，一定是“先假设该人是做好事者，然后到每句话中去测试看有几句是真话”。“有三句是真话就确定是该人，否则换下一人再试”。,比如，,先假定是A同学，让 thisman=A;,代入到四句话中,A说：thisman!=A;A!=A假，值为0。,B说：thisman=C;A=C假，值为0。,C说：thisman=D;A=D假，值为0。,D说：thisman!=D;A!=D真，值为1。,显然，不是A做的好事（,四个关系表达式值的和为1,）,再试B同学，让thisman=B;,代入到四句话中,A说：thisman!=A;B!=A真，值为1。,B说：thisman=C;B=C假，值为0。,C说：thisman=D;B=D假，值为0。,D说：thisman!=D;B!=D真，值为1。,显然，不是B所为（,四个关系表达式值的和为2,）,再试C同学，让thisman=C;,代入到四句话中,A说：thisman!=A;C!=A真，值为1。,B说：thisman=C;C=C真，值为1。,C说：thisman=D;C=D假，值为0。,D说：thisman!=D;C!=D真，值为1。,显然，就是C做了好事（,四个关系表达式值之和为3,）,这时，我们可以理出头绪，要用枚举法，一个人一个人地去试，四句话中有三句为真，该人即所求。,#include,void main(),char,thisman;,int,sa,sb,sc,sd,cond;,for,(thisman=A;thisman=D;thisman+),sa=(thisman!=A);,sb=(thisman=C);,sc=(thisman=D);,sd=(thisman!=,D);,cond=sa+sb+sc+sd;,if,(cond=3),printf(做好事的人是：%cn,thisman);,利用穷举法求解趣味智力题,(韩信点兵),韩信有一队兵，他想知道有多少人，便让士兵排队报数。按从1至5报数，最末一个士兵报的数为1；按从1至6报数，最末一个士兵报的数为5；按从1至7报数，最末一个士兵报的数为4；最后再按从1至11报数，最末一个士兵报的数为10。你知道韩信至少有多少兵吗？,设兵数为,x,，则,x,应满足：,x,%5=1&,x,%6=5&,x,%7=4&,x,%11=10,穷举法对x从1开始试验,#,include,void main(),int,x;,for,(x=1;,x 5000,;x+),if,(x%5=1&x%6=5&x%7=4&x%11=10),printf(x=%dn,x);,/*,属于“瞎猫碰死耗子”的做法*,/,穷举法求解韩信点兵,#,include,void main(),int,x;,for,(x=1;x+),if,(x%5=1&x%6=5&x%7=4&x%11=10),printf(x=%dn,x);,/*,死循环,永远不会退出的循环,*/,穷举法求解韩信点兵,穷举法求解韩信点兵：方案1-goto,#,include,void main(),int,x;,for,(x=1;x+),if,(x%5=1&x%6=5&x%7=4&x%11=10),printf(x=%dn,x);,goto,END;,END:;,穷举法求解韩信点兵：方案2-break,#,include,void main(),int,x;,for,(x=1;x+),if,(x%5=1&x%6=5&x%7=4&x%11=10),printf(x=%dn,x);,break;,穷举法求解韩信点兵:方案3-标志变量,#,include,void main(),int,x;,int,find=0;/*,设置找到标志为假*,/,for,(x=1;,!find,;x+),if,(x%5=1&x%6=5&x%7=4&x%11=10),printf(x=%dn,x);,find=1;,