2、利用穷举法解题 ◆优化策略 减少穷举次数 合理选择用于穷举的变量 ●注意穷举的顺序 减少判断每种情况的时间
2、利用穷举法解题 优化策略 ◼ 减少穷举次数 ⚫ 合理选择用于穷举的变量 ⚫ 注意穷举的顺序 ◼ 减少判断每种情况的时间
21百钱买百鸡☆ ◆鸡翁一,值钱五,鸡母一,值钱三,鸡 雏三,值钱一。百钱买百鸡,问鸡翁、母、 雏各几何? ◆根据题意列方程: 5X+3y+z/3=100 X+y+z=100 (x,y2z>=0;3整除z)
2.1 百钱买百鸡 根据题意列方程： 鸡翁一，值钱五，鸡母一，值钱三，鸡 雏三，值钱一。百钱买百鸡，问鸡翁、母、 雏各几何？ 5x + 3y + z/3 = 100 x + y + z = 100 (x, y, z >= 0; 3整除z)
最简单直接的做法 根据方程写程序: ◆for(x=0;X<=100;x++) 穷举次数: 101+100+,+ for(y=0;y<=100-X;y++) 1=5151 次 z=100-X- if(z%3=0 &&15*x+9y+z=300) cout<<x<<<<y<<<<z<<endl
最简单直接的做法 for (x = 0; x <= 100; x++) for (y = 0; y <= 100 - x; y++) { z = 100 - x - y; if (z % 3 == 0 && 15 * x + 9 * y +z==300) cout<<x<<' '<<y<<''<<z<<endl; } 根据方程写程序： 穷举次数： 101+100+……+ 1 = 5151次
另解 ◆x<10/5=20 y=100/3=33 5X+3y+z/3=100 ◆观察方程的 X+y+z=100 特点,消去 (x,y,z>=0;3整除z) 个未知数z 7X+4y=100 x+y+z=100 (x,y2z>=0;3整除z)
另解 5x + 3y + z/3 = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) 7x + 4y = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) 观察方程的 特点，消去 一个未知数z x <= =20 y<= =33 100/5 100/3
穷举次数大大减少 根据整理后的方程写程序:◆x<=1007=14 ◆for(x=0;X<=14;x++) y<=L100/425 y=100-7*x; if(y 4)continue; else y /=4; z=100-X if(z %o 3)continue; cout<x<<y<<x<cend;、穷举次数: 5151VS14
穷举次数大大减少 for (x = 0; x <= 14; x++) { y = 100 - 7 * x; if (y % 4) continue; else y /= 4; z = 100 - x - y; if (z % 3) continue; cout<<x<<' '<<y<<' '<<z<<endl; } 根据整理后的方程写程序： 穷举次数： 5151 VS 14 x <= =14 y<= =25 100/ 7 100/ 4