枚举法解决百元买百鸡.ppt

《枚举法解决百元买百鸡.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举法实例信息工程学院主讲教师：门瑞什么是枚举法信息工程学院基本思想枚举也称穷举，指的是从问题可能的解的集合中一一列举各元素。用题目给定的条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。本质上属于搜索算法什么是枚举法信息工程学院特点容易理解，步骤单一。得到的结果肯定是正确的。通常会涉及到求极值（如最大，最小等）。数据量大的话，可能会造成时间崩溃。引子信息工程学院【例1】以下式子中的每个汉字代表一个数字，求出这些汉字代表的数字分别是多少？慕课制作组X慕组组组组组组枚举法信息工程学院计算

2、机解决枚举问题算法简单、精确度高。常用多重循环解决枚举问题(while循环、for循环)。效率低——当问题的规模变大，循环的阶数增加，执行的速度严重变慢。百元买百鸡问题【例2】鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？解题思路：设鸡翁、鸡母、鸡雏的数量分别为x，y，z，则有以下方程x+y+z=1005x+3y+z/3=100此三元一次方程有多个解，可用枚举法求解。信息工程学院百元买百鸡问题C语言解法一：main(){intx,y,z;for(x=1;x<=

3、100;x++)for(y=1;y<=100;y++)for(z=1;z<=100;z++)if((z%3==0)&&(x+y+z==100)&&(5*x+3*y+z/3==100))printf(“鸡翁%d只，鸡母%d只，鸡雏%d只",x,y,z);}信息工程学院百元买百鸡问题C语言解法一：信息工程学院main(){intx,y,z;for(x=1;x<=100;x++)for(y=1;y<=100;y++)for(z=1;z<=100;z++)if((z%3==0)&&(x+y+z==1

4、00)&&(5*x+3*y+z/3==100))printf(“鸡翁%d只，鸡母%d只，鸡雏%d只",x,y,z);}枚举次数：100*100*100=100万次！百元买百鸡问题限定变量的取值范围x的取值范围是1<=x<=20y的取值范围是1<=y<=33减少循环的层数、判断时间z=100-x-y信息工程学院有没有更好的解法呢？百元买百鸡问题C语言解法二：main(){intx,y,z;for(x=1;x<=20;x++)for(y=1;y<=33;y++)if(((100-x-y)%3==

5、0)&&(5*x+3*y+(100-x-y)/3==100)){z=100-x-y;printf(“鸡翁%d只，鸡母%d只，鸡雏%d只",x,y,z);}}枚举次数：20*33=660次！百元买百鸡问题有没有更好的解法呢？信息工程学院百元买百鸡问题x+y+z=1005x+3y+z/3=100y=25-7/4*xz=75+3/4*xx=4ky=25-7kz=75+3k化简令x=4k分析题意可知：k只能取1,2,3信息工程学院百元买百鸡问题C语言解法三：main(){intk;for(k=1;k

6、<=3;k++)printf(“鸡翁%d只，鸡母%d只，鸡雏%d只",4k,25-7k,z);}枚举次数：3次！信息工程学院枚举法信息工程学院优化策略对问题多加分析，减少循环重数和次数。合理选择用于枚举的变量。减少每种情况的判断时间。是否有其他更好的方法。知识拓展信息工程学院试用枚举法解决以下两个问题从1—10的10个数中，每次取2个数，要使它们的和大于10，一共有多少种取法？从学校到少年宫有4条东西走向的马路和3条南北走向的马路，小明从学校步行到少年宫（只许向东或向南行走），最多有多少种走

7、法？谢谢观看信息工程学院主讲教师：门瑞