《算法复习-枚举法》PPT课件

《《算法复习-枚举法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法复习枚举法回顾>>循环结构循环的三要素？？？sum←0i<=10i←0sum=sum+ii=i+1NY开始结束输出sum循环变量置初值循环的终止条件循环体思考：A．在一串钥匙中找到所有能开启某扇门的钥匙。B．将一箱苹果中烂的苹果挑出来。枚举法的概念：又称穷举法，是根据问题给定的一部分条件，列出所有的可能解，然后再逐一验证哪些解能够满足问题的全部条件，从而得到问题的真正的解。枚举法是效率较低的一种算法。但是它又充分利用了计算机运算速度快的特点，其优点也很明显：思路简单，准确率高。采用枚举算法解题的基本思路：1.确定枚举对象、枚举范围和判定条件；2.一一枚举可能的解，验证是否是问题的解。实

2、例一：最近警方抓获一批制造伪钞的犯罪分子，并发现制造假币用的模版，但是由于受到损坏，模板上编号的个位数和十位数已经模糊不清，我们看到的后六位数仅仅是5190□□，同时据情报称，在他们制造的这批假币中，编号有一定的规律，后六位数能被42整除。请用枚举法的思路，设计一个算法，判断出所有符合这些条件的6位编号。根据枚举法的解题思路：问题一：枚举对象、范围是什么？519000～519099问题二：检验正确解的判定条件是什么？前面四位是5190；能被42整除。519000mod42=0?,519001mod42=0?……...5190099mod42=0?问题三：使用何种结构？循环请先完成下列问题：

3、1、设置变量2、循环变量的取值范围3、循环变量的变化规律4、需要符合的条件5、算法功能人民币编号后六位d519000~519099d←d+1编号dmod42=0?输出：编号d1、设置变量编号d2、循环变量的取值范围519000<=d<=5190993、循环变量的变化规律d=d+14、需要符合的条件dmod42<>0?5、算法功能输出d开始NYYN输出：d结束d←519000d>519099dmod42<>0?d←d+1实例二：1）判断自然数193是不是质数2）如果该自然数为N，怎么来修改流程图？3）求1000以内的质数，并将它们输出。1）判断自然数193是不是质数问题一：什么是质数？在自然

4、数集合内，除了1，只能被1和本身整除的数叫做质数(或素数)问题二：能否用枚举法？枚举些什么？枚举出所有被除数枚举对象、范围2～192循环控制变量i判定条件193不能被其整除193mod1<>0枚举对象、范围2～192(循环控制变量i)判定条件193不能被其整除(193mod1<>0)开始YY输出193是质数NN结束开始i＝2i<=192Y193modi<>0Y输出193是质数i=i+1NN输出193不是质数枚举对象、范围2～192(循环控制变量i)判定条件193不能被其整除(193mod1<>0)结束2）如果该自然数为N，怎么来修改流程图？分类讨论：N<21不是质数N=22是质数N>2Nm

5、odi=0?开始i＝2i<=192Y193modi=0Y输出193是质数i=i+1NN结束输出193不是质数开始i＝2N=2YNmodi=0Y输出N是质数i=i+1NN输出N不是质数YNNYY结束3）求1000以内的质数，并将它们输出。在问题2）的基础上，把2）的过程循环执行了1000遍，N=1,2,....,1000枚举对象、范围循环变量N1～1000判定条件N是质数（即问题2）枚举对象、范围1～1000循环变量N判定条件N是质数（即问题2的流程图）3）求1000以内的质数，并将它们输出。开始结束NN是不是质数N＝1N<=1000N=N+1Y使用枚举法的条件：仅当问题所有可能解不太多，否

6、则失去解题的意义枚举法解题过程：逐一列举可能的解逐一检验可能的解枚举法解题的难点：构造循环确定可能的解题的注意事项，不重复、不遗漏开始第2问判断N是否为质数N＝1N<=1000YN结束N=N+1i＝2N=2YNmodi=0Y输出N是质数i=i+1NNi<=N－1N<2YNNYY练习1用数字1，2，3可以组成多少个不同的三位数？分别是哪几个数？2在700以内找这样的自然数，使这个自然数是奇数，且是11的倍数。3求由偶数数码（不包括0）组成，且能被13整除的最小三位数。4商店里卖的电池有3节一盒和5节一盒两种包装，请找出一个尽可能小的数，凡购买的节数超过这个数时，售货员就不必拆盒。5某天全班3

7、0个人出游，分别乘坐5辆小型旅行车，每车限乘7人，且不能有空车，问如何安排？