一、穷举法概述.ppt

《一、穷举法概述.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举算法例生活实例统计出班级中感冒的学生数流程图☞什么是枚举算法p21采用“搜索”的方法对所有可能逐一判断保留符合要求的解，舍弃不符合要求的☞枚举算法本质p21一一“列举”问题所有可能检验每个可能是否是问题的解记录所有问题解例1算法举例一张单据上有一个5位数的编号，其百位和十位数处已经变得模糊不清，但是知道这个数是37或67的倍数。现在要设计一个算法找出所有满足这些条件的5位数，并统计这些5位数的个数。数字的推算关键点十位、百位的变化不过是00~99，所以我们可以尝试所有的可能性，25006、25016、25026……25

2、996看看所有的数字中哪些能被37或67整除。解题步骤：１.分析问题枚举所有问题的可能解25xx6，范围是多少？２.确定方法采用？？结构３.用流程图表示算法流程图开始j=0j<=99Yn=25006+j*10n能否被37或者67整除Y输出j,nj=j+1结束NNj是十位和百位上的数十位、百位的变化范围是00~99代码：变量的定义：Dimj,nasinteger循环控制：Forj=0to99n=25006+j*10ifnmod37=0ornmod67=0thenprintj,n开始j=0j<=99Yn=25006+j*10n

3、能否被37或者67整除Y输出j,nj=j+1结束NNnextj枚举法计算容量比较大，需要优化。用钥匙开门的时候，当钥匙有一大堆，我们就要首先排除一部分钥匙孔不一致的钥匙，从而缩小枚举范围，进行优化。枚举算法解题过程解题过程分两步：逐一列举可能的解的范围。这个过程用循环结构实现。对每一个列举可能的解进行检验，判断是否为真正的解。这个过程用分支结构实现。枚举算法=循环结构+分支结构，循环结构内嵌套选择结构课堂总结1.枚举算法=循环结构+分支结构2.做到既不遗漏任何一个解、也不重复.3.枚举算法效率较低.注：并不是所有的问题都可

4、以使用枚举算法来求解，只有当问题的所有可能解的个数不太多时，并在可以接受的时间内得到问题的所有解，才有可能使用枚举算法。作业：编程序求100以内所有的素数的和。（提示：素数是指除了能被1和其本身整除以外，其他数都不能被整除。）