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

算法复习 枚举法 回顾循环结构 循环的三要素？？？ 思考： A．在一串钥匙中找到所有能开启某扇门的钥匙。 B． 将一箱苹果中烂的苹果挑出来。 枚举法的概念： 又称穷举法，是根据问题给定的一部分条件，列出所有的可能解，然后再逐一验证哪些解能够满足问题的全部条件，从而得到问题的真正的解。 枚举法是效率较低的一种算法。但是它又充分利用了计算机运算速度快的特点，其优点也很明显：思路简单，准确率高。 采用枚举算法解题的基本思路： 1.确定枚举对象、枚举范围和判定条件； 2.一一枚举可能的解，验证是否是问题的解。 实例一： 最近警方抓获一批制造伪钞的犯罪分子，并发现制造假币用的模版，但是由于受到损坏，模板上编号的个位数和十位数已经模糊不清，我们看到的后六位数仅仅是5190□□，同时据情报称，在他们制造的这批假币中，编号有一定的规律，后六位数能被42整除。 请用枚举法的思路，设计一个算法，判断出所有符合这些条件的6位编号。 根据枚举法的解题思路： 问题一：枚举对象、范围是什么？ 519000～519099 问题二：检验正确解的判定条件是什么？ 前面四位是5190； 能被42整除。 519000 mod 42=0?, 519001mod 42=0? ……... 5190099mod 42=0? 问题三：使用何种结构？ 循环 请先完成下列问题： 1、设置变量 2、循环变量的取值范围 3、循环变量的变化规律 4、需要符合的条件 5、算法功能 实例二： 1）判断自然数193是不是质数 2）如果该自然数为N，怎么来修改流程图？ 3）求1000以内的质数，并将它们输出。 1）判断自然数193是不是质数 问题一：什么是质数？ 在自然数集合内，除了1，只能被1和本身整除的数叫做质数(或素数) 问题二：能否用枚举法？枚举些什么？ 枚举出所有被除数 枚举对象、范围 2～192 循环控制变量 i 判定条件 193不能被其整除 193mod10 2）如果该自然数为N，怎么来修改流程图？ 分类讨论： N2 1不是质数 N=2 2是质数 N2 N mod i=0? 3）求1000以内的质数，并将它们输出。 在问题2）的基础上，把2）的过程循环执行了1000遍，N=1,2,....,1000 枚举对象、范围 循环变量N 1～1000 判定条件 N是质数（即问题2） 使用枚举法的条件：仅当问题所有可能解不太 多，否则失去解题的意义 枚举法解题过程： 逐一列举可能的解 逐一检验可能的解 枚举法解题的难点： 构造循环 确定可能的解题的注意事项， 不重复、不遗漏 练 习 1 用数字1，2，3可以组成多少个不同的三位数？分别是哪几个数？ 　2 在700以内找这样的自然数，使这个自然数是奇数，且是11的倍数。 　3 求由偶数数码（不包括0）组成，且能被13整除的最小三位数。 　4 商店里卖的电池有3节一盒和5节一盒两种包装，请找出一个尽可能小的数，凡购买的节数超过这个数时，售货员就不必拆盒。 5? 某天全班30个人出游，分别乘坐5辆小型旅行车，每车限乘7人，且不能有空车，问如何安排？ * * sum ← 0 i = 10 i ← 0 sum= sum+i i=i+1 N Y 开 始 结 束 输出sum 1、设置变量 编号d 2、循环变量的取值范围 519000=d=519099 3、循环变量的变化规律 d=d+1 4、需要符合的条件 d mod 420? 5、算法功能 输出d 开始 N Y Y N 输出：d 结束 d←519000 d519099 d mod 420? d←d+1 枚举对象、范围 2～192 ( 循环控制变量 i ) 判定条件 193不能被其整除 (193mod10) 开始 Y Y 输出193是质数 N N 结束 开始 i＝2 i=192 Y 193 mod i0 Y 输出193是质数 i=i+1 N N 输出193不是质数 枚举对象、范围 2～192 ( 循环控制变量 i ) 判定条件 193不能被其整除 (193mod10) 结束 开始 i