枚举算法(修改).ppt

《枚举算法(修改).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举算法及其程序实现枚举算法的基本思想是把问题所有的可能解一一地罗列出来，并对每一个可能解进行判断，以确定这个可能解是否是问题的真正解。在设计枚举算法时，必须注意的是：（1）不能遗漏任何一个真正解，这是问题本身所要求的；（2）尽可能地使可能解的罗列范围最小，这是为了提高解决问题的效率。什么是枚举算法实践活动1.单据中被涂抹数字的推算问题：一张单据上有一个5位数的编号n，如图1所示，其百位数和十位数处已经变得模糊不清，但是知道这个5位数是37或67的倍数。现在要设计一个算法，找出所有满足这些条件的5位数。并统计这些5位数的个数。（1）.算法分析：中间两位数字可以有从00到99共计100

2、种可能，罗列出问题所有可能的解并判断nmod37=0ORnmod67=0是否成立来检验是否为真正的解。（点击打开算法分析）采用枚举算法的条件仅当问题的所有可能解不太多的时候，才可以使用枚举法。枚举算法的解题过程分两步逐一列举可能的解的范围。这个过程用循环结构实现逐一检验可能的解这个过程用选择结构实现枚举算法=循环结构+选择结构循环结构内嵌套选择结构（2）.算法动画演示（点击打开Flash动画）（3）.分析并编写程序代码：①程序界面设计：控件属性值的设置如下表对象名属性名属性值Form1Caption涂抹数字推算List1list空白Command1Caption计算②分析算法流程，编写代

3、码；PrivateSubCommand1_Click()DimjAsInteger,nAsInteger,cAsIntegerc=0List1.ClearForj=0To99n=25006+j*10’生成每一种可能解IfnMod37=0OrnMod67=0Then‘判断是否满足条件List1.AddItemStr(n)c=c+1EndIfNextjList1.AddItem"总计有"+Str(c)+"个五位数"EndSub③运行调试程序;(点击打开)课堂练习单据中被涂抹数字的推算问题，请将划线处填写完整：PrivateSubCommand1_Click()DimjA

4、sInteger,nAsInteger,cAsIntegerc=0List1.Clear________________’(1)Dowhilen<=25996IfnMod37=0OrnMod67=0ThenList1.AddItemStr(n)c=c+1EndIf________________’(2)LoopList1.AddItem"总计有"+Str(c)+"个五位数"EndSubn=25006n=n+10枚举法解题过程逐一列举可能的解逐一检验可能的解枚举法解题的难点：1、构造循环2、确定可能的解例题2：一张单据上有一个5位数的编码，其千位数和十位数已经变得模

5、糊不请。但是知道这个5位数是37或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。No.147分析：千位数和十位数上的数字只能是0-9中的一个。10407104171042710437104471045710467104771048710497ij分析：千位数和十位数上的数字只能是0-9中的一个。11407114171142711437114471145711467114771148711497ij19407194171942719437194471945719467194771948719497iji从0变化到9；j从0变化到9。因此，需要构造一个双重循

6、环。可能的解n←10407+1000*i+10*j双重循环的构造1、i←02、判断i<=9；是转向3，否则转向73、j←04、判断j<=9；是转向5，否则转向65、j←j+1；转向46、i←i+1；转向27、结束i<=9YN开始i←0i←i+1结束j<=9Nj←j+1j←0Y思考：右面的流程图有没有问题i<=9YN开始i←0i←i+1结束j<=9Nj←j+1j←0Y算法描述1、c←0；i←02、判断i<=9；是转向3，否则转向113、j←04、判断j<=9；是转向5，否则转向105、n←10407+1000*i+10*j6、判断n是否57或67的倍数，是转向7；否转向97、计数器c←c

7、+1；8、输出一个真正的解n9、j←j+1；转向410、i←i+1；转向211、输出解的个数c12、结束i<=9YN开始i←0i←i+1j<=9Nj←j+1j←0Yc←0c结束12c←c+1输出nn←10047+j*100nmod37=0或nmod67=0NY21②分析算法流程，编写代码；PrivateSubCommand1_Click()DimjAsInteger,nAsInteger,cAsIntegerc=0List1.