《选修1《穷举法》ppt课件3 高中信息技术.ppt》由会员分享，可在线阅读，更多相关《选修1《穷举法》ppt课件3 高中信息技术.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 穷举法(CompleteSearch)1概 述 穷举法的基本思想是不重复、不遗漏地穷举所有 可能情况(问题的规模不是特别大)，从中寻找满足条件的结果。穷举法充分利用了计算机处理的高速特性，避免 复杂的逻辑推理过程，使问题简单化。使用穷举法的关键是要确定正确的穷举的范围和满足判断式。2枚举法的优化方法：1）减少枚举的变量，在使用枚举法之前，先考虑一下解元素之间的关联，将一些非枚举不可的解元素列为枚举变量，其他元素通过计算得出解元素的可能值。2）减少枚举变量的值域3例1：百钱百鸡问题。公鸡5文钱1只,母鸡3文钱1只,小鸡一文钱3只。100文钱如何卖100只鸡?条件分析 设买 x 只公鸡，y 只母
2、鸡，z 只小鸡，则有：x+y+z=100 5x+3y+z/3=100 且：x、y、z 都是整数；0 x 20；0 y 33；0 z 99；z30。4 基本算法思想，上述方程属于不定方程，解并不唯一，因此，可用穷举法穷举法对x、y、z的所有组合情况，测试满足条件的解。具体是：把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=1005 另一方法是：把
3、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=0&5*x+3*y+z/3=100&x+y+z=1006main()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=1
4、00)printf(%2d:cock=%-2d hen=%-2d chicken=%-2dn,j,x,y,z);j+;7金手指考试网http:/ 8运行结果：Possible solutions to buy 100 fowls whith 100 wen:1:cock=0 hen=25 chicken=75 2:cock=4 hen=18 chicken=78 3:cock=8 hen=11 chicken=81 4:cock=12 hen=4 chicken=849例2：打印出所有的“水仙花数”。所谓“水仙花 数”是指一个三位正整数，其各位数字的立方和 等于该数本身，例如：153=13+5
5、3+33。穷举范围：穷举范围：即把所有的三位正整数100999按题 意一一进行判断。判断式：判断式：如果一个三位正整数n的百位、十位、个位上的数字分别为i、j、k，则判断式为：n=i3+j3+k3 如何分解三位数如何分解三位数n的百位、十位、个位：的百位、十位、个位：百位：i=n/100;十位：j=(n/10)%10;个位：k=n%10;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,
6、i,j,k);运行结果：153 13+53+33370 33+73+03371 33+73+13407 43+03+7311例3：中国余数定理：“有物不知几何，三三数余一，五五数余二，七七数余三，问：物有几何？”。编程求1000以内所有解。穷举范围：穷举范围：整数m为：11000。判断式：判断式：m%3=1&m%5=2&m%7=312#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 2
7、62 367 472 577 682 787 892 997131.马克思手稿中的数学题：有30个人，其中有男人、女人和小孩，在一家饭馆吃饭共花了50先令；每个男人花3先令，每个女人花2先令，每个小孩花1先令，问男人、女人和小孩各有几人？2.爱因斯坦的数学题：有一条长阶梯，若每步跨2 阶，则最后剩1阶；若每步跨3阶，则最后剩2阶；若每步跨5阶，则最后剩4阶；若每步跨6阶，则最后剩 5阶；只有每步跨7阶，最后才正好一阶不剩。请问，这条长阶梯共有多少阶？练习题143.把整数316表示为两个数之和，使其中一个数能被 13整除，而另一个数能被11整除，求解这两个数。4.小张现有面值为1元、2元和5元的
8、钞票（假设每种钞票的数量都足够多），如果小张想从这些钞票中取出30张用来换取小李的100元，问有小张有多少种取法？输出每种取法中各种面额钞票的张数。5.将19这9个数字填入到9个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三个三位数是第一行的2倍，第三行的三位数是第一行的三倍，应怎样填数。如图19238457615陈婷有一个EMAIL邮箱的密码是一个5位数。但因为有一段比较长的日子没有打开这个邮箱了，陈婷把这个密码给忘了。不过陈婷自己是8月1日出生，而她妈妈的生日则是9月1日，她特别喜欢把同时是81和91的倍数用作密码。陈婷还记得这个密码的中间一位(百位数)是1。你能设计一个程序帮她找回这个密码吗？7.有5只猴子分桃子，第一只猴子先去分，把一只桃子扔海里，然后平均分了剩下的桃子，自己拿走了一份；第2只猴子也是把一只桃子扔进海里，然后也平均分了剩下的桃子拿走了一份；第3，4，5只猴子都按照这样的方法分了桃子，请问桃子最少有多少只？16