穷举法经典例题

1、第第3 3章章 程序控制结构程序控制结构枚举法（穷举法）枚举法（穷举法） “笨人之法笨人之法”： 把所有可能的情况一一测试，筛选出符合把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。条件的各种结果进行输出。分析：分析： 这是个不定方程这是个不定方程三元一次方程组问题三元一次方程组问题 （三个变量，两个方程）（三个变量，两个方程） xyz=100 5x3yz/3=100 设公鸡为设公鸡为x只，母鸡为只，母鸡为y只，小鸡为只，小鸡为z只。只。 第第3 3章章 程序控制结构程序控制结构百元买百鸡问题分析百元买百鸡问题分析x xy yz=100z=1005x5x3y3yz/3=100z/3

2、=100三重循环第第3 3章章 程序控制结构程序控制结构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【讨论讨论】为什么多了几组解为什么多了几组解? ? ? ?第第3 3章章 程序控制结构程序控制结构百元买百鸡问题分析百元买百鸡问题

3、分析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多万次）运算。多万次）运算。第第3 3章章 程序控制结构程

4、序控制结构优化优化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） 第第3 3章章 程序控制结构程序控制结构第第3 3章章

5、程序控制结构程序控制结构继续优化继续优化void main() int x,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=%dn,x,y,z); 取取x=14,y=25 只进行只进行1526= 390 次运算次运算第第3 3章章 程序控制结构程序控制结构课堂讨论：谁做的好事？课堂讨论：谁做的好事？ 有四位同学中的一位做了好事，不留名，表扬信来了有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。之后，校长问这四

6、位是谁做的好事。 A A说：不是我。说：不是我。 B B说：是说：是C C。 C C说：是说：是D D。 D D说：说：C C胡说。胡说。 已知三个人说的是真话，一个人说的是假话。现在要根据已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。这些信息，找出做了好事的人。第第3 3章章 程序控制结构程序控制结构显然，不是显然，不是AA做的好事（做的好事（四个关系表达式值的和为四个关系表达式值的和为1 1）第第3 3章章 程序控制结构程序控制结构显然，不是显然，不是BB所为（所为（四个关系表达式值的和为四个关系表达式值的和为2 2）第第3 3章章 程序控制结构程序控制结构

7、显然，就是显然，就是CC做了好事（做了好事（四个关系表达式值之和为四个关系表达式值之和为3 3）这时，我们可以理出头绪，要用枚举法，一个人一个人地去这时，我们可以理出头绪，要用枚举法，一个人一个人地去试，四句话中有三句为真，该人即所求。试，四句话中有三句为真，该人即所求。第第3 3章章 程序控制结构程序控制结构#includevoid 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

8、=(thisman != D);cond=sa+sb+sc+sd;if (cond=3) printf(做好事的人是：做好事的人是：%cn, thisman);第第3 3章章 程序控制结构程序控制结构利用穷举法求解趣味智力题利用穷举法求解趣味智力题(韩信点兵韩信点兵)韩信有一队兵，他想知道有多少人，便让士兵排队报韩信有一队兵，他想知道有多少人，便让士兵排队报数。按从数。按从1至至5报数，最末一个士兵报的数为报数，最末一个士兵报的数为1；按从；按从1至至6报数，最末一个士兵报的数为报数，最末一个士兵报的数为5；按从；按从1至至7报数，报数，最末一个士兵报的数为最末一个士兵报的数为4；最后再按从；

9、最后再按从1至至11报数，最报数，最末一个士兵报的数为末一个士兵报的数为10。你知道韩信至少有多少兵吗？。你知道韩信至少有多少兵吗？设兵数为设兵数为x，则，则x应满足：应满足：x%5 = 1 & x%6 = 5 & x%7 = 4 & x%11 = 10穷举法对穷举法对x从从1开始试验开始试验第第3 3章章 程序控制结构程序控制结构#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); /*属于属

10、于“瞎猫碰死耗子瞎猫碰死耗子”的做法的做法*/穷举法求解韩信点兵穷举法求解韩信点兵第第3 3章章 程序控制结构程序控制结构#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); /*死循环死循环永远不会退出的循环永远不会退出的循环*/穷举法求解韩信点兵穷举法求解韩信点兵第第3 3章章 程序控制结构程序控制结构穷举法求解韩信点兵：方案穷举法求解韩信点兵：方案1-goto#include void main()int x;for (x=1

11、; ;x+) if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); goto END; END: ;第第3 3章章 程序控制结构程序控制结构穷举法求解韩信点兵：方案穷举法求解韩信点兵：方案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 3章章 程序控制结构程序控制结构穷举法求解韩信点兵穷举法求解韩信点兵:方案方案3-标志变量标志变量#include void main()int x; int find =