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

《高中信息技术枚举算法.ppt》由会员分享，可在线阅读，更多相关《高中信息技术枚举算法.ppt（16页珍藏版）》请在优知文库上搜索。

1、枚举算法例例1:一天小明回家看见妈妈好像有什么心事，于是小明关心地询问妈妈，怎么回一天小明回家看见妈妈好像有什么心事，于是小明关心地询问妈妈，怎么回事？妈妈告诉小明，她不小心将单位的记录账目的单据碰到了污迹，现在很难认事？妈妈告诉小明，她不小心将单位的记录账目的单据碰到了污迹，现在很难认出，这个数字是：出，这个数字是：113702?,怎么办？小明想了一想后，问妈妈这数有什么特点？怎么办？小明想了一想后，问妈妈这数有什么特点？妈妈说：妈妈说：“这数是这数是144的整数的整数倍倍”，马上，小明就帮助妈妈解决了这个问题。，马上，小明就帮助妈妈解决了这个问题。 第一步：列出所有可能的解第一步：列出所有

2、可能的解 1137020113702111370221137023、1137029第二步：第二步：根据条件，检验出真正的解根据条件，检验出真正的解 一一列举这些解的同时，检验每一个可一一列举这些解的同时，检验每一个可能解是否满足条件：是能解是否满足条件：是144的整数的整数倍，如果是，倍，如果是，则是我们要找的真正解，否则就不是则是我们要找的真正解，否则就不是 。 枚举法：象这种列举出问题的枚举法：象这种列举出问题的所有可能解所有可能解，并在逐一列举，并在逐一列举的过程中，检验每个可能解是否是的过程中，检验每个可能解是否是问题的真正解问题的真正解，若是，我们，若是，我们采纳这个解，否则抛弃它，

3、这种解决问题的方法叫做枚举法。采纳这个解，否则抛弃它，这种解决问题的方法叫做枚举法。 注意：在列举的过程中不能遗漏，也不应重复。注意：在列举的过程中不能遗漏，也不应重复。枚举算法找到的真正解不一定是唯一的。枚举算法找到的真正解不一定是唯一的。第一步：列出所有可能的解第一步：列出所有可能的解X=输出X开始i=0i=9Ti=i+1结束F1137020+i返回第一步：列出所有可能的解第一步：列出所有可能的解 1137020113702111370221137023、1137029第二步：根据条件，检验出真正的解第二步：根据条件，检验出真正的解 开始i=0i=9X=1137020+ii=i+1结束TF

4、TFX mod 144=0或者或者int(x/144)=x/144输出X开始i=0i=9X=1137020+iX mod 144=0输出XTi=i+1F结束TF请同学们把程序填写完整问题的诊断问题的诊断Private Sub Command1_Click()Dim i, x As LongList1.Cleari = 0Do While i = 9 x = 1137020 + i If x Mod 144 = 0 Then List1.AddItem (Str(x) 输出X的意思else nothingLoopEnd Sub开始i=0i=9X=1137020+iX mod 144=0输出XTi

5、=i+1F结束TFEnd ifi=i+1编程中存在的问题分支语句 实现分支结构的语句if 应该与end if成对出现，单分支语句中不存在else语句。 二是在书写的时候，要注意执行语句的缩进，这样使程序看起来十分清晰，以方便我们的调试。 If 条件 then 语句组1 else 语句组2 end if编程中存在的问题循环语句 当循环语句中遗漏了当循环语句中遗漏了loop（表示循环）的（表示循环）的语句，以及在计数法控制循环中缺少了循语句，以及在计数法控制循环中缺少了循环变量增量的语句环变量增量的语句,而造成了死循环。而造成了死循环。Do while 条件条件 循环体循环体 循环变量循环变量=循

6、环变量循环变量+步长步长loop例例2：如果模糊数字是：如果模糊数字是249?1616，它是，它是144的整的整数倍数倍 。第一步：列出所有可能的解第一步：列出所有可能的解249001624901162490216、24910162491116、24920162492116、2499916开始第二步：根据条件，检验出真正的解第二步：根据条件，检验出真正的解i=_i=X=i=i+1结束TF992490016+i*100X mod 144=0输出XTF0提高题（模糊数据二）：模糊数字是提高题（模糊数据二）：模糊数字是465？7？6，它，它是是144的整数倍的整数倍 。第一步：列出所有可能的解第一步

7、：列出所有可能的解千位数为千位数为0 ，十位数从十位数从09一一枚举：一一枚举： 4650706465071646507264650736、4650796千位数为千位数为1 ，十位数从十位数从09一一枚举一一枚举： 4651706465171646517264651736、4651796千位数为千位数为9 ，十位数从十位数从09一一枚一一枚举举： 、4659706465971646597264659736、4659796开始i=9i=i+1结束结束TF注意：注意：在列举出所有解的过程中，在列举出所有解的过程中，既不能遗漏也不应重复。既不能遗漏也不应重复。十位数从09一一枚举0i提高题（模糊数据

8、二）：模糊数字是提高题（模糊数据二）：模糊数字是465？7？6，它，它是是144的整数倍的整数倍 。第一步：列出所有可能的解第一步：列出所有可能的解千位数为千位数为0 ，十位数从十位数从09过一遍：过一遍： 4650706465071646507264650736、4650796千位数为千位数为1 ，十位数从十位数从09过一遍：过一遍： 4651706465171646517264651736、4651796千位数为千位数为9 ，十位数从十位数从09过一遍：过一遍： 、4659706465971646597264659736、4659796开始i=0=9j=9j=0X=j=j+1i=i+1结束

9、结束TFTF4650706+1000*i+10*j注意：注意：在列举出所有解的过程中，在列举出所有解的过程中，既不能遗漏也不应重复。既不能遗漏也不应重复。i提高题（模糊数据二）：模糊数字是提高题（模糊数据二）：模糊数字是465？7？6，它是，它是144的的整数倍整数倍 。第二步：根据条件，找出真正的解第二步：根据条件，找出真正的解开始i=0i=9j=9j=0X=j=j+1i=i+1结束结束TFTF4650706+1000*i+10*jX mod 144=0输出XTF千位数为千位数为0 ，十位数从十位数从09过一遍：过一遍： 4650706465071646507264650736、465079

10、6千位数为千位数为1 ，十位数从十位数从09过一遍：过一遍： 4651706465171646517264651736、4651796千位数为千位数为9 ，十位数从十位数从09过一遍：过一遍： 、4659706465971646597264659736、4659796注意注意 在双重循环中，外循环每变化一次，内循在双重循环中，外循环每变化一次，内循环变量要取遍所有可能的值。环变量要取遍所有可能的值。请同学们列举生活中可以使用枚举算法来解请同学们列举生活中可以使用枚举算法来解决的问题决的问题课堂小结1、什么是枚举法：、什么是枚举法： 列举列举出问题的出问题的所有可能解所有可能解，并在逐一列举的过

11、程中，并在逐一列举的过程中，检验检验每个可能解是否是每个可能解是否是问题的真正解问题的真正解，若是，我们采纳，若是，我们采纳这个解，否则抛弃它。这个解，否则抛弃它。2、枚举法的特点：、枚举法的特点：在列举的过程中，在列举的过程中，真正解不一定唯一真正解不一定唯一既不能遗漏也不应重复，既不能遗漏也不应重复，3、注意：、注意： 并不是所有的问题都可以使用枚举算法来寻找答案的，仅当问题的并不是所有的问题都可以使用枚举算法来寻找答案的，仅当问题的所有可能解的个数不太多时，才有可能使用枚举法，才可能在有限的时所有可能解的个数不太多时，才有可能使用枚举法，才可能在有限的时间内获得问题的解间内获得问题的解 。 当可能解的个数很多的时候，当可能解的个数很多的时候，我们可以根据问题的性质不同，采用其他我们可以根据问题的性质不同，采用其他比较好的搜索算法寻找答案，如递归算法，深度优先算法、广度优先算法、比较好的搜索算法寻找答案，如递归算法，深度优先算法、广度优先算法、动态归划等动态归划等来解决问题。来解决问题。在很多时候，实现枚举算法的结构是在很多时候，实现枚举算法的结构是循环结构嵌套分支结构循环结构嵌套分支结构.作业 复习枚举算法，预习冒泡排序算法。复习枚举算法，预习冒泡排序算法。