《枚举法解决百元买百鸡精品课件》由会员分享，可在线阅读，更多相关《枚举法解决百元买百鸡精品课件（16页珍藏版）》请在金锄头文库上搜索。
1、枚举法实例,什么是枚举法,信息工程学院,基本思想,枚举也称穷举，指的是从问题可能的解的集合中一一列举各元素。 用题目给定的条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。 本质上属于搜索算法,什么是枚举法,信息工程学院,特点,容易理解，步骤单一。 得到的结果肯定是正确的。 通常会涉及到求极值（如最大，最小等）。 数据量大的话，可能会造成时间崩溃。,引子,信息工程学院,【例1】以下式子中的每个汉字代表一个数字，求出这些汉字代表的数字分别是多少？,慕课制作组 X 慕,组组组组组组,枚举法,信息工程学院,计算机解决枚举问题,算法简单、精确度高。 常用多重循环解决枚举问题(while循环、
2、for循环)。 效率低当问题的规模变大，循环的阶数增加，执行的速度严重变慢。,百元买百鸡问题,【例2】鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？,解题思路： 设鸡翁、鸡母、鸡雏的数量分别为x，y，z，则有以下方程 x+y+z=100 5x+3y+z/3=100 此三元一次方程有多个解，可用枚举法求解。,信息工程学院,百元买百鸡问题,C语言解法一：,main() int x, y, z; for(x=1;x=100;x+) for(y=1;y=100;y+) for(z=1;z=100;z+) if(z%3=0) ,信息工程学院,百元买百鸡问题,C语言解法
3、一：,信息工程学院,main() int x, y, z; for(x=1;x=100;x+) for(y=1;y=100;y+) for(z=1;z=100;z+) if(z%3=0) ,枚举次数： 100*100*100=100万次！,百元买百鸡问题,限定变量的取值范围 x的取值范围是1=x=20 y的取值范围是1=y=33 减少循环的层数、判断时间 z=100-x-y,信息工程学院,有没有更好的解法呢？,百元买百鸡问题,C语言解法二：,main() int x,y,z; for(x=1;x=20;x+) for(y=1;y=33;y+) if(100-x-y)%3=0) ,枚举次数： 2
4、0*33=660次！,百元买百鸡问题,有没有更好的解法呢？,信息工程学院,百元买百鸡问题,x+y+z=100 5x+3y+z/3=100,y=25-7/4*x z=75+3/4*x,x=4k y=25-7k z=75+3k,化简,令x=4k,分析题意可知： k只能取1,2,3,信息工程学院,百元买百鸡问题,C语言解法三：,main() int k; for(k=1;k=3;k+) printf(“鸡翁%d只，鸡母%d只，鸡雏%d只n,4k,25-7k,z); ,枚举次数： 3次！,信息工程学院,枚举法,信息工程学院,优化策略,对问题多加分析，减少循环重数和次数。 合理选择用于枚举的变量。 减少每种情况的判断时间。 是否有其他更好的方法。,知识拓展,信息工程学院,试用枚举法解决以下两个问题,从110的10个数中，每次取2个数，要使它们的和大于10，一共有多少种取法？ 从学校到少年宫有4条东西走向的马路和3条南北走向的马路，小明从学校步行到少年宫（只许向东或向南行走），最多有多少种走法？,谢谢观看,信息工程学院,主讲教师：门瑞,
