04穷举法.ppt

《04穷举法.ppt》由会员分享，可在线阅读，更多相关《04穷举法.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 穷举法概 述 穷举法的基本思想是不重复、不遗漏地穷举所有 可能情况，从中寻找满足条件的结果。穷举法充分利用了计算机处理的高速特性，避免 复杂的逻辑推理过程，使问题简单化。使用穷举法的关键是要确定正确的穷举的范围。例1：百钱百鸡问题。公鸡5文钱1只,母鸡3文钱1只,小鸡一文钱3只。100文钱如何卖100只鸡?条件分析 设买 x 只公鸡，y 只母鸡，z 只小鸡，则有：x+y+z=100 5x+3y+z/3=100 且：x、y、z 都是整数；0 x 20；0 y 33；0 z 99；z30。基本算法思想，上述方程属于不定方程，解并不唯一，因此，可 用穷举法穷举法对 x、y、z 的所有组合情况，测试

2、满足 条件的解。具体是：把x可能值020和y可能值033用二重循环来组 合，每个x和y组合都可得到z值，即z=100-x-y，若x、y、z值使5x+3y+z/3=100成立，则该组x、y、z即为一组所求值。即：穷举范围：穷举范围：x:020,y:033,z:100-x-y 判断式：判断式：z%3=0&5*x+3*y+z/3=100 另一方法是：把x可能值020、y可能值033和z 可能值099用三重循环来组合，若x、y、z值使 5x+3y+z/3=100和x+y+z=100同时成立，则该组x、y、z即为一组所求值。即：穷举范围：穷举范围：x:020,y:033,z:099 判断式：判断式：z%

3、3=0&5*x+3*y+z/3=100&x+y+z=100main()int x,y,z,j=1;printf(Possible solutions to buy 100 fowls whith 100 wen:n);for(x=0;x=20;x+)for(y=0;y=33;y+)z=100-x-y;if(z%3=0&5*x+3*y+z/3=100)printf(%2d:cock=%-2d hen=%-2d chicken=%-2dn,j,x,y,z);j+;运行结果：Possible solutions to buy 100 fowls whith 100 wen:1:cock=0 hen=

4、25 chicken=75 2:cock=4 hen=18 chicken=78 3:cock=8 hen=11 chicken=81 4:cock=12 hen=4 chicken=84例2：打印出所有的“水仙花数”。所谓“水仙花 数”是指一个三位正整数，其各位数字的立方和 等于该数本身，例如：153=13+53+33。穷举范围：穷举范围：即把所有的三位正整数100999按题 意一一进行判断。判断式：判断式：如果一个三位正整数n的百位、十位、个位上的数字分别为i、j、k，则判断式为：n=i3+j3+k3 如何分解三位数如何分解三位数n的百位、十位、个位：的百位、十位、个位：百位：i=n/10

5、0;十位：j=(n/10)%10;个位：k=n%10;#include stdio.hmain()int n,i,j,k;for(n=100;n=999;n+)i=n/100;j=(n/10)%10;k=n%10;if(n=i*i*i+j*j*j+k*k*k)printf(%d=%d3+%d3+%d3n,n,i,j,k);运行结果：153 13+53+33370 33+73+03371 33+73+13407 43+03+73例3：中国余数定理：“有物不知几何，三三数余一，五五数余二，七七数余三，问：物有几何？”。编程求1000以内所有解。穷举范围：穷举范围：整数m为：11000。判断式：判断

6、式：m%3=1&m%5=2&m%7=3#include stdio.hmain()int m,count=0;for(m=1;m=1000;m+)if(m%3=1&m%5=2&m%7=3)printf(%5d,m);count+;if(count%5=0)printf(n);运行结果：52 157 262 367 472 577 682 787 892 997上机练习题1.马克思手稿中的数学题：有30个人，其中有男人、女人和小孩，在一家饭馆吃饭共花了50先令；每 个男人花3先令，每个女人花2先令，每个小孩花 1先令，问男人、女人和小孩各有几人？2.爱因斯坦的数学题：有一条长阶梯，若每步跨2 阶

7、，则最后剩1阶；若每步跨3阶，则最后剩2阶；若每步跨5阶，则最后剩4阶；若每步跨6阶，则 最后剩 5阶；只有每步跨7阶，最后才正好一阶 不剩。请问，这条长阶梯共有多少阶？3.把整数316表示为两个数之和，使其中一个数能被 13整除，而另一个数能被11整除，求解这两个数。4.要实现10年达到国民经济总值翻两番的目标，问 国民生产年平均增长率至少应为百分之几？（精确 到一位小数，即xx.x%）main()/*1 */int x,y,z,count=0;for(x=0;x16;x+)for(y=0;y26;y+)for(z=0;z51;z+)if(x+y+z=30&3*x+2*y+z=50)prin

8、tf(%2d:men=%2d women=%2d children=%2dn,+count,x,y,z);运行结果：1:men=0 women=20 children=10 2:men=1 women=18 children=11 3:men=2 women=16 children=12 4:men=3 women=14 children=13 5:men=4 women=12 children=14 6:men=5 women=10 children=15 7:men=6 women=8 children=16 8:men=7 women=6 children=17 9:men=8 wome

9、n=4 children=1810:men=9 women=2 children=1911:men=10 women=0 children=20main()/*2 */*用 while 循环结构*/int i=1;while(!(i%2=1)&(i%3=2)&(i%5=4)&(i%6=5)&(i%7=0)i+;printf(Stairs_number=%dn,i);main()/*用 for 循环结构 */int i;for(i=1;i%2!=1|i%3!=2|i%5!=4|i%6!=5|i%7!=0;i+);printf(Stairs_number=%dn,i);运行结果：Stairs_nu

10、mber=1193.把整数316表示为两个数之和，使其中一个数能被 13整除，而另一个数能被11整除，求解这两个数。main()/*3 */int n1,n2;for(n1=1;n1316;n1+)n2=316-n1;if(n1%13=0)&(n2%11=0)printf(n1=%d,n2=%d,n1,n2);运行结果：n1=52,n2=264n1=195,n2=121main()/*4 */int i,j,y=0;float x;for(i=100;y=0;i+)for(j=1,x=1.0;j=4)printf(%.1f%n,i/10.);y=1;break;main()/*4 */int j,y=0;float x,k;for(k=10.;y=0;k+=0.1)for(j=1,x=1.0;j=4)printf(%.1f%n,k);y=1;