程序设计培训讲义3：枚举算法.ppt

程序设计讲义之三枚举算法枚举法也称穷举法、穷举搜索法 算法思想: 对所有可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。算法特点: 算法简单,但执行效率低。因此枚举法的关键在于提高编程效率。例1、求水仙花数//程序1:对数循环#include<>voidmain(){ inti,a,b,c; for(i=100;i<=999;i++) { a=i/100; b=i/10%10; c=i%10; if(a*a*a+b*b*b+c*c*c==i) printf("%d\n",i); }}//程序2:对数的各位数字循环#include<>voidmain(){ intn,a,b,c; for(a=1;a<=9;a++) for(b=0;b<=9;b++) for(c=0;c<=9;c++) { n=a*100+b*10+c; if(n==a*a*a+b*b*b+c*c*c) printf("%d\n",n); } }例2、百鸡百钱问题设母鸡每只5元,公鸡每只3元,小鸡1元3只。现用100元买100只鸡,求出所有可能的解。算法分析: 设母鸡、公鸡、小鸡分别为x、y、z只,则应满足下面2个条件: x+y+z=100 5x+3y+z/3=100对于此类实际问题,还需考虑x,y,z的取值范围: 0<=x<=100 0<=y<=100 0<=z<=100//程序1:有问题的程序#include<>voidmain(){ intx,y,z; for(x=0;x<=100;x++) for(y=0;y<=100;y++) for(z=0;z<=100;z++) if(x+y+z==100&&5*x+3*y+z/3==100) printf("%d,%d,%d\n",x,y,z);}思考:1、上面的程序能否输出所有可能的解? 2、上面的程序是否输出了错误的解? 3、上面的程序的时间复杂度?//程序2:正确的程序#include<>voidmain(){ intx,y,z; for(x=0;x<=100;x++) for(y=0;y<=100;y++) for(z=0;z<=100;z++) if(z%3==0&&x+y+z==100 &&5*x+3*y+z/3==100) printf("%d,%d,%d\n",x,y,z);}问题:上面程序的执行速度太慢,如何解决?//程序3:改进后的程序#include<>voidmain(){ intx,y,z; for(x=0;x<=100;x++) for(y=0;y<=100;y++) { z=100-x-y; if(z%3==0&&5*x+3*y+z/3==100) printf("%d,%d,%d\n",x,y,z); } }问题:上面程序的执行速度还可以加快,如何修改?//程序4:对程序3改进后的程序#include<>voidmain(){ intx,y,z; for(x=0;x<=20;x++) for(y=0;y<=99;y++) { z=100-x-y; if(z%3==0&&5*x+3*y+z/3==100) printf("%d,%d,%d\n",x,y,z); } }思考: 是否可以将对y的循环改成对z的循环?//程序5:对程序3的另一种改进#include<>voidmain(){ intx,y,z; for(x=0;x<=20;x++) for(z=0;z<=99;z=z+3) { y=100-x-z; if(5*x+3*y+z/3==100) printf("%d,%d,%d\n",x,y,z); } } 思考: 上面程序的存在什么问题,为什么会出现问题?