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