04穷举法

穷举法概述•穷举法的基本思想是不重复、不遗漏地穷举所有可能情况，从中寻找满足条件的结果。•穷举法充分利用了计算机处理的高速特性，避免复杂的逻辑推理过程，使问题简单化。•使用穷举法的关键是要确定正确的穷举的范围。例1：百钱百鸡问题。公鸡5文钱1只,母鸡3文钱1只,小鸡一文钱3只。100文钱如何卖100只鸡?•条件分析设买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。•基本算法思想，上述方程属于不定方程，解并不唯一，因此，可用穷举法对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*x+3*y+z/3==100另一方法是：把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==100main(){intx,y,z,j=1;printf(Possiblesolutionstobuy100fowlswhith100wen:\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=%-2dhen=%-2dchicken=%-2d\n,j,x,y,z);j++;}}}运行结果：Possiblesolutionstobuy100fowlswhith100wen:1:cock=0hen=25chicken=752:cock=4hen=18chicken=783:cock=8hen=11chicken=814:cock=12hen=4chicken=84例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;#includestdio.hmain(){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,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^3例3：中国余数定理：“有物不知几何，三三数余一，五五数余二，七七数余三，问：物有几何？”。编程求1000以内所有解。•穷举范围：整数m为：1~1000。•判断式：m%3==1&&m%5==2&&m%7==3#includestdio.hmain(){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(\n);}}运行结果：52157262367472577682787892997上机练习题1.马克思手稿中的数学题：有30个人，其中有男人、女人和小孩，在一家饭馆吃饭共花了50先令；每个男人花3先令，每个女人花2先令，每个小孩花1先令，问男人、女人和小孩各有几人？2.爱因斯坦的数学题：有一条长阶梯，若每步跨2阶，则最后剩1阶；若每步跨3阶，则最后剩2阶；若每步跨5阶，则最后剩4阶；若每步跨6阶，则最后剩5阶；只有每步跨7阶，最后才正好一阶不剩。请问，这条长阶梯共有多少阶？3.把整数316表示为两个数之和，使其中一个数能被13整除，而另一个数能被11整除，求解这两个数。4.要实现10年达到国民经济总值翻两番的目标，问国民生产年平均增长率至少应为百分之几？（精确到一位小数，即xx.x%）main()/*1*/{intx,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)printf(%2d:men=%2dwomen=%2dchildren=%2d\n,++count,x,y,z);}运行结果：1:men=0women=20children=102:men=1women=18children=113:men=2women=16children=124:men=3women=14children=135:men=4women=12children=146:men=5women=10children=157:men=6women=8children=168:men=7women=6children=179:men=8women=4children=1810:men=9women=2children=1911:men=10women=0children=20main()/*2*//*用while循环结构*/{inti=1;while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0)))i++;printf(Stairs_number=%d\n,i);}main()/*用for循环结构*/{inti;for(i=1;i%2!=1||i%3!=2||i%5!=4||i%6!=5||i%7!=0;i++);printf(Stairs_number=%d\n,i);}运行结果：Stairs_number=1193.把整数316表示为两个数之和，使其中一个数能被13整除，而另一个数能被11整除，求解这两个数。main()/*3*/{intn1,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*/{inti,j,y=0;floatx;for(i=100;y==0;i++)for(j=1,x=1.0;j=10;j++)if((x=x*(1+i/1000.0))=4){printf(%.1f%%\n,i/10.);y=1;break;}}main()/*4*/{intj,y=0;floatx,k;for(k=10.;y==0;k+=0.1)for(j=1,x=1.0;j=10&&y==0;j++)if((x=x*(1+k/100.))=4){printf(%.1f%%\n,k);y=1;}}