枚举法解决百元买百鸡文库

,LOGO,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,LOGO,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,LOGO,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,信息工程学院,*,枚举法实例,信息工程学院,主讲教师：门瑞,什么是枚举法,信息工程学院,根本思想,枚举也称穷举，指的是从问题可能的解的集合中一一列举各元素。,用题目给定的条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。,本质上属于搜索算法,什么是枚举法,信息工程学院,特点,容易理解，步骤单一。,得到的结果肯定是正确的。,通常会涉及到求极值如最大，最小等。,数据量大的话，可能会造成时间崩溃。,引子,信息工程学院,【,例,1】,以下式子中的每个汉字代表一个数字，求出这些汉字代表的数字分别是多少？,慕课制作组,X,慕,组组组组组组,枚举法,信息工程学院,计算机解决枚举问题,算法简单、精确度高。,常用多重循环解决枚举问题,(while,循环、,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)&(x+y+z=100)&(5*x+3*y+z/3=100),printf(“,鸡,翁,%d,只，鸡母,%d,只，鸡雏,%d,只,n,x,y,z);,信息工程学院,百元买百鸡问题,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);,枚举次数：,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)&(5*x+3*y+(100-x-y)/3=100),z=100-x-y;,printf(“,鸡,翁,%d,只，鸡母,%d,只，鸡雏,%d,只,n,x,y,z);,枚举次数：,20,*,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条南北走向的马路，小明从学校步行到少年宫只许向东或向南行走，最多有多少种走法？,谢谢观看,信息工程学院,主讲教师：门瑞,