C语言穷举法经典例题.ppt
第第3 3章章 程序控制结构程序控制结构枚举法（穷举法）枚举法（穷举法）“笨人之法笨人之法”：把所有可能的情况一一测试，筛选出符合把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。条件的各种结果进行输出。分析：分析：这是个不定方程这是个不定方程三元一次方程组问题三元一次方程组问题 （三个变量，两个方程）（三个变量，两个方程）xyz=100 5x3yz/3=100 设公鸡为设公鸡为x只，母鸡为只，母鸡为y只，小鸡为只，小鸡为z只。只。第第3 3章章 程序控制结构程序控制结构百元买百鸡问题分析百元买百鸡问题分析x xy yz=100z=1005x5x3y3yz/3=100z/3=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章章 程序控制结构程序控制结构百元买百鸡问题分析百元买百鸡问题分析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章章 程序控制结构程序控制结构优化优化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章章 程序控制结构程序控制结构继续优化继续优化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章章 程序控制结构程序控制结构课堂讨论：谁做的好事？课堂讨论：谁做的好事？有四位同学中的一位做了好事，不留名，表扬信来了有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。之后，校长问这四位是谁做的好事。A A说：不是我。说：不是我。B B说：是说：是C C。C C说：是说：是D D。D D说：说：C C胡说。胡说。已知三个人说的是真话，一个人说的是假话。现在要根据已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。这些信息，找出做了好事的人。第第3 3章章 程序控制结构程序控制结构编程思路：编程思路：编程思路：编程思路：如何找到该人，一定是如何找到该人，一定是如何找到该人，一定是如何找到该人，一定是“先假设该人是做好事者，然先假设该人是做好事者，然先假设该人是做好事者，然先假设该人是做好事者，然后到每句话中去测试看有几句是真话后到每句话中去测试看有几句是真话后到每句话中去测试看有几句是真话后到每句话中去测试看有几句是真话”。“有三句是真话就有三句是真话就有三句是真话就有三句是真话就确定是该人，否则换下一人再试确定是该人，否则换下一人再试确定是该人，否则换下一人再试确定是该人，否则换下一人再试”。比如，比如，比如，比如，先假定是先假定是先假定是先假定是A A A A同学，让同学，让同学，让同学，让 thismanthismanthismanthisman=A;=A;=A;=A;代入到四句话中代入到四句话中代入到四句话中代入到四句话中 A A A A说：说：说：说：thismanthismanthismanthisman!=!=!=!=A A A A;A A A A!=!=!=!=A A A A假，值为假，值为假，值为假，值为0 0 0 0。B B B B说：说：说：说：thismanthismanthismanthisman=C C C C;A A A A=C C C C假，值为假，值为假，值为假，值为0 0 0 0。C C C C说：说：说：说：thismanthismanthismanthisman=D D D D;A A A A=D D D D假，值为假，值为假，值为假，值为0 0 0 0。D D D D说：说：说：说：thismanthismanthismanthisman!=!=!=!=D D D D;A A A A!=!=!=!=D D D D真，值为真，值为真，值为真，值为1 1 1 1。显然，不是显然，不是AA做的好事（做的好事（四个关系表达式值的和为四个关系表达式值的和为1 1）第第3 3章章 程序控制结构程序控制结构再试再试再试再试B B B B同学，让同学，让同学，让同学，让thismanthismanthismanthisman=B B B B;代入到四句话中代入到四句话中代入到四句话中代入到四句话中A A A A说：说：说：说：thismanthismanthismanthisman!=!=!=!=A A A A;B B B B!=!=!=!=A A A A真，值为真，值为真，值为真，值为1 1 1 1。B B B B说：说：说：说：thismanthismanthismanthisman=C C C C;B B B B=C C C C假，值为假，值为假，值为假，值为0 0 0 0。C C C C说：说：说：说：thismanthismanthismanthisman=D D D D;B B B B=D D D D假，值为假，值为假，值为假，值为0 0 0 0。D D D D说：说：说：说：thismanthismanthismanthisman!=!=!=!=D D D D;B B B B!=!=!=!=D D D D真，值为真，值为真，值为真，值为1 1 1 1。显然，不是显然，不是BB所为（所为（四个关系表达式值的和为四个关系表达式值的和为2 2）第第3 3章章 程序控制结构程序控制结构再试再试再试再试C C C C同学，让同学，让同学，让同学，让thismanthismanthismanthisman=C C C C;代入到四句话中代入到四句话中代入到四句话中代入到四句话中A A A A说：说：说：说：thismanthismanthismanthisman!=!=!=!=A A A A;C C C C!=!=!=!=A A A A真，值为真，值为真，值为真，值为1 1 1 1。B B B B说：说：说：说：thismanthismanthismanthisman=C C C C;C C C C=C C C C真，值为真，值为真，值为真，值为1 1 1 1。C C C C说：说：说：说：thismanthismanthismanthisman=D D D D;C C C C=D D D D假，值为假，值为假，值为假，值为0 0 0 0。D D D D说：说：说：说：thismanthismanthismanthisman!=!=!=!=D D D D;C C C C!=!=!=!=D D D D真，值为真，值为真，值为真，值为1 1 1 1。显然，就是显然，就是C C做了好事（做了好事（四个关系表达式值之和为四个关系表达式值之和为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=(thisman!=D);cond=sa+sb+sc+sd;if(cond=3)printf(做好事的人是：做好事的人是：%cn,thisman);第第3 3章章 程序控制结构程序控制结构利用穷举法求解趣味智力题利用穷举法求解趣味智力题(韩信点兵韩信点兵)韩信有一队兵，他想知道有多少人，便让士兵排队报韩信有一队兵，他想知道有多少人，便让士兵排队报数。按从数。按从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开始试验开始试验
