《枚举算法.ppt》由会员分享，可在线阅读，更多相关《枚举算法.ppt（15页珍藏版）》请在三一文库上搜索。
1、上次作业,流程图：,VB代码： Dim w as long Dim p as double w=val(text1.text) If w= 0 then p=1.33*w+1.08*w*0.9 p=round(p,2) text2.text=str(p) Else text2.text=“用水量不能为负数” End if,开始,结束,输入用水量w,w=0?,N,Y,显示：“用水量不能为负数”,P=1.33*w+1.08*w*0.9,对p小数部分保留两位小数,输出p,枚 举 算 法,枚举算法,1.定义:P22 有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并
2、对所得的结果逐一进行判断，过滤掉那些不合要求，保留那些符和要求，这种方法叫做枚举算法。 2.思想方法： 按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能的解是否是问题的真正解，若是，则采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏，也不能重复。,一 一列举出所有可能的解,（列举范围）,检验每个可能的解是否是真正的解,（检验条件）,循环结构 （重复模式）,分支结构 （选择模式）,循环嵌套分支,应用枚举算法,问题1：找出11000中所有能被7 和11整除的数。,分析： 列举范围：i：1,1000 检验条件：i能被7和11整除,将流程图补充完整：,开始,i =
3、1,Y,Y,N,N,输出 i,i = i+1,结束,i=1000?,i mod 7=0and i mod11=0?,应用枚举算法,问题2：一张单据上有一个5位数的号码，它的十位和个位数字已被涂抹的看不清，但知道这个5位数是37的倍数，设计一个算法，找出该单据可能的号码。,分析： 列举范围：n：12800,12899 检验条件：n是37的倍数,NO.128*,将流程图补充完整：,开始,结束,输出n,n=12800,Y,Y,N,N,n=12899?,n mod 37=0?,n = n+1,应用枚举算法,问题3：对上题进行修改，这个5位数的千位和百位模糊不清，是37的倍数，设计一个算法，找出该单据可
4、能的号码。,分析： 列举范围：n：10028,19928 检验条件：n是37的倍数,NO.1*28,将流程图补充完整：,开始,结束,输出n,n=10028,Y,Y,N,N,n =19928?,n mod 37=0?,n =n+100,将流程图补充完整：,开始,结束,输出n,j = 0,Y,Y,N,N,n mod 37 =0?,j =99?,n =10028+j*100,j=j+1,1、以下运用枚举算法，“求11000的偶数”的算法，正确的是：,巩固枚举算法,开始,结束,输出i,i = 1,Y,Y,N,N,开始,结束,输出 i,i = 2,Y,N,i=1000?,i = i+2,i=1000?,
5、i mod 2=0?,i = i+1,图1,图2,巩固枚举算法,2、以下运用枚举算法: “求11000中，能被3或5整除的数” 指出其中的错误并改正。,开始,结束,输出i,i = 1,Y,N,i1000?,i mod 3=0 and ? i mod 5=0,i = i+2,N,i=1000?,or,i = i+1,归纳小结,1）枚举算法的思想 2）实现方法：循环嵌套分支 2）适用情况（可能解的个数不太多时）,作 业,问题1：求水仙花数。若一个三位数，它的各位上的数字的立方 和等于它本身，则称该数为水仙花数。要求设计一个算 法输出所有的水仙花数。例如：13+53+33=153 （难度：） 问题2：有一单据上有一个5位数，其千位和十位上的数字看不 清，但知道这个5位数是37的倍数，请设计一个算法， 找出该单据可能的号码。1*2*8 （难度：） 问题3：包装600个变形金刚，要求是： 1）包装的规格分别是：小盒每盒装12个，大盒每盒装15个 2）每种规格的盒数都不能为0 请设计一个算法，输出所有可能的包装方案。 （难度： ）,