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