资源描述：
《选修1《穷举法》ppt课件3高中信息技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、穷举法(Complete Search)1概述•穷举法的基本思想是不重复、不遗漏地穷举所有可能情况(问题的规模不是特别大)，从中寻找满足条件的结果。•穷举法充分利用了计算机处理的高速特性，避免复杂的逻辑推理过程，使问题简单化。•使用穷举法的关键是要确定正确的穷举的范围和满足判断式。2枚举法的优化方法：1）减少枚举的变量，在使用枚举法之前，先考虑一下解元素之间的关联，将一些非枚举不可的解元素列为枚举变量，其他元素通过计算得出解元素的可能值。2）减少枚举变量的值域3例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；z％3＝0。4•基本算法思想，上述方程属于不定方程，解并不唯一，因此，可用穷举法对x、y、z的所有组合情况，测试满足条件的解。具体是：把x可能值0~20和y可能值0~33用二重循环来组合，每个x和y组合都可得到z值，即z=100-x-y，若x、y、z值使5x+3y+z/3=100成立，则该组x、y、z即为一组所求值。即：穷举范围：x:0~20,y:0~33,z:100-x-y判断式：z%3==0&&5*
3、x+3*y+z/3==1005另一方法是：把x可能值0~20、y可能值0~33和z可能值0~99用三重循环来组合，若x、y、z值使5x+3y+z/3=100和x+y+z=100同时成立，则该组x、y、z即为一组所求值。即：穷举范围：x:0~20,y:0~33,z:0~99判断式：z%3==0&&5*x+3*y+z/3==100&&x+y+z==1006main(){intx,y,z,j=1;printf("Possiblesolutionstobuy100fowlswhith100wen:");for(x=0;x<=20;x++)for(y=0;y<=3
4、3;y++){z=100-x-y;if(z%3==0&&5*x+3*y+z/3==100){printf("%2d:cock=%-2dhen=%-2dchicken=%-2d",j,x,y,z);j++;}}}7金手指考试网http://www.jszksw.net/2016年金手指驾驶员考试科目一科目四 元贝驾考网http://www.yuanbeijiakao.net科目一科目四仿真考试题C1Grammar8运行结果：Possiblesolutionstobuy100fowlswhith100wen:1:cock=0hen=25chicken=75
5、2:cock=4hen=18chicken=783:cock=8hen=11chicken=814:cock=12hen=4chicken=849例2：打印出所有的“水仙花数”。所谓“水仙花数”是指一个三位正整数，其各位数字的立方和等于该数本身，例如：153=13+53+33。•穷举范围：即把所有的三位正整数100~999按题意一一进行判断。•判断式：如果一个三位正整数n的百位、十位、个位上的数字分别为i、j、k，则判断式为：n=i3+j3+k3•如何分解三位数n的百位、十位、个位：百位：i=n/100;十位：j=(n/10)%10;个位：k=n%10;10
6、#include"stdio.h"main(){intn,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=%d^3+%d^3+%d^3",n,i,j,k);}}运行结果：153＝1^3+5^3+3^3370＝3^3+7^3+0^3371＝3^3+7^3+1^3407＝4^3+0^3+7^311例3：中国余数定理：“有物不知几何，三三数余一，五五数余二，七七数余三，问：物有几何？”。编程求1000以内所有解。•穷举范围：整数m
7、为：1~1000。•判断式：m%3==1&&m%5==2&&m%7==312#include"stdio.h"main(){intm,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("");}}运行结果：52157262367472577682787892997131.马克思手稿中的数学题：有30个人，其中有男人、女人和小孩，在一家饭馆吃饭共花了50先令；每个男人花3先令，每个女人花2先令，每个小孩花1先
8、令，问男人、女人和小孩各有几人？2.爱因斯坦的数学题
