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

程序设计讲义之三枚举算法枚举法也称穷举法、穷举搜索法算法思想: 对所有可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。算法特点: 算法简单,但执行效率低。因此枚举法的关键在于提高编程效率。例1、求水仙花数// 程序 1:对数循环# include < stdio .h> void main() { int i,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 < stdio .h> void main( ) { int n,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 < stdio .h> void main() { int x,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 < stdio .h> void main() { int x,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 < stdio .h> void main() { int x,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 < stdio .h> void main() { int x,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 < stdio .h> void main() { int x,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); }}思考: 上面程序的存在什么问题,为什么会出现问题?