高中信息技术枚举算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,枚举算法,1,.,例1:,一天小明回家看见妈妈好像有什么心事，于是小明关心地询问妈妈，怎么回事？妈妈告诉小明，她不小心将单位的记录账目的单据碰到了污迹，现在很难认出，这个数字是：113702?,怎么办？小明想了一想后，问妈妈这数有什么特点？妈妈说：“这数是144,的整数,倍”，马上，小明就帮助妈妈解决了这个问题。,第一步：列出所有可能的解,113702,0,113702,1,113702,2,113702,3,、,、,、,113702,9,第二步：,根据条件，检验出真正的解,一一列举这些解的同时，检验每一个可,能解是否满足条件：是,144,的整数,倍，如果是，,则是我们要找的真正解，否则就不是,。,枚举法：象这种列举出问题的,所有可能解,，并在逐一列举,的过程中，检验每个可能解是否是,问题的真正解,，若是，我们,采纳这个解，否则抛弃它，这种解决问题的方法叫做枚举法。,注意：在列举的过程中不能遗漏，也不应重复。,枚举算法找到的真正解不一定是唯一的。,2,.,第一步：列出所有可能的解,X=,输出X,开始,i=0,i=9,T,i=i+1,结束,F,1137020+i,返回,第一步：列出所有可能的解,113702,0,113702,1,113702,2,113702,3,、,、,、,113702,9,3,.,第二步：根据条件，检验出真正的解,开始,i=0,i=9,X=1137020+i,i=i+1,结束,T,F,T,F,X mod 144=0,或者,int(x/144)=x/144,输出X,开始,i=0,i=9,X=1137020+i,X mod 144=0,输出X,T,i=i+1,F,结束,T,F,4,.,请同学们把程序填写完整,5,.,问题的诊断,Private Sub Command1_Click(),Dim i,x As Long,List1.Clear,i=0,Do While i=9,x=1137020+i,If x Mod 144=0 Then,List1.AddItem(Str(x)输出X的意思,else,nothing,Loop,End Sub,开始,i=0,i=9,X=1137020+i,X mod 144=0,输出X,T,i=i+1,F,结束,T,F,End if,i=i+1,6,.,编程中存在的问题分支语句,实现分支结构的语句if 应该与end if成对出现，单分支语句中不存在else语句。,二是在书写的时候，要注意执行语句的缩进，这样使程序看起来十分清晰，以方便我们的调试。,If 条件 then 语句组1 else 语句组2 end if,7,.,编程中存在的问题循环语句,当循环语句中遗漏了loop（表示循环）的语句，以及在计数法控制循环中缺少了循环变量增量的语句,而造成了死循环。,Do while 条件,循环体,循环变量=循环变量+步长,loop,8,.,例,2,：如果模糊数字是,249?,16，它是,144,的整数倍,。,第一步：列出所有可能的解,249,00,16,249,01,16,249,02,16,、,249,10,16,249,11,16,、,249,20,16,249,21,16,、,249,99,16,开始,第二步：根据条件，检验出真正的解,i=,_,i=,X=,i=i+1,结束,T,F,99,2490016+i*100,X mod 144=0,输出X,T,F,0,9,.,提高题（模糊数据二）：模糊数字是,465,？,7,？,6,，它是,144,的整数倍,。,第一步：列出所有可能的解,千位数为,0,，,十位数从,0,9,一一枚举：,465,0,7,0,6,465,0,7,1,6,465,0,7,2,6,465,0,7,3,6,、,465,0,7,9,6,千位数为,1,，,十位数从,0,9,一一枚举,：,465,1,7,0,6,465,1,7,1,6,465,1,7,2,6,465,1,7,3,6,、,465,1,7,9,6,千位数为,9,，,十位数从,0,9,一一枚举,：,、,465,9,7,0,6,465,9,7,1,6,465,9,7,2,6,465,9,7,3,6,、,465,9,7,9,6,开始,i=,=9,i=i+1,结束,T,F,注意：,在列举出所有解的过程中，,既不能遗漏也不应重复。,十位数从09一一枚举,0,i,10,.,提高题（模糊数据二）：模糊数字是,465,？,7,？,6,，它是,144,的整数倍,。,第一步：列出所有可能的解,千位数为,0,，,十位数从,0,9,过一遍：,465,0,7,0,6,465,0,7,1,6,465,0,7,2,6,465,0,7,3,6,、,465,0,7,9,6,千位数为,1,，,十位数从,0,9,过一遍：,465,1,7,0,6,465,1,7,1,6,465,1,7,2,6,465,1,7,3,6,、,465,1,7,9,6,千位数为,9,，,十位数从,0,9,过一遍：,、,465,9,7,0,6,465,9,7,1,6,465,9,7,2,6,465,9,7,3,6,、,465,9,7,9,6,开始,i=0,=9,j=9,j=0,X=,j=j+1,i=i+1,结束,T,F,T,F,4650706+1000*i+10*j,注意：,在列举出所有解的过程中，,既不能遗漏也不应重复。,i,11,.,提高题（模糊数据二）：模糊数字是,465,？,7,？,6,，它是,144,的整数倍,。,第二步：根据条件，找出真正的解,开始,i=0,i=9,j=9,j=0,X=,j=j+1,i=i+1,结束,T,F,T,F,4650706+1000*i+10*j,X mod 144=0,输出X,T,F,千位数为,0,，,十位数从,0,9,过一遍：,465,0,7,0,6,465,0,7,1,6,465,0,7,2,6,465,0,7,3,6,、,465,0,7,9,6,千位数为,1,，,十位数从,0,9,过一遍：,465,1,7,0,6,465,1,7,1,6,465,1,7,2,6,465,1,7,3,6,、,465,1,7,9,6,千位数为,9,，,十位数从,0,9,过一遍：,、,465,9,7,0,6,465,9,7,1,6,465,9,7,2,6,465,9,7,3,6,、,465,9,7,9,6,12,.,注意,在双重循环中，外循环每变化一次，内循环变量要取遍所有可能的值。,13,.,请同学们列举生活中可以使用枚举算法来解决的问题,14,.,课堂小结,1、什么是枚举法：,列举,出问题的,所有可能解,，并在逐一列举的过程中，,检验,每个可能解是否是,问题的真正解,，若是，我们采纳,这个解，否则抛弃它。,2、枚举法的特点：,在列举的过程中，,真正解不一定唯一,既不能遗漏也不应重复，,3、注意：,并不是所有的问题都可以使用枚举算法来寻找答案的，仅当问题的,所有可能解的个数不太多时，才有可能使用枚举法，才可能在有限的时,间内获得问题的解,。,当可能解的个数很多的时候，,我们可以根据问题的性质不同，采用其他,比较好的搜索算法寻找答案，如递归算法，深度优先算法、广度优先算法、,动态归划等,来解决问题。,在很多时候，实现枚举算法的结构是,循环结构嵌套分支结构.,15,.,作业,复习枚举算法，预习冒泡排序算法。,16,.,