枚举算法3解读.ppt

算法应用 例题2： 一张单据上有一个5位数的编码，其千位数和十位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。 分析： 千位数和十位数上的数字只能是0-9中的一个。 双重循环的构造 1、i ←0 2、判断i=9；是转向3，否则转向7 3、j ←0 4、判断j=9；是转向5，否则转向6 5、j ←j+1； 转向4 6、i ←i+1；转向2 7、结束 思考：右面的流程图有没有问题 完整算法的三大部分组成： 输入部分 处理部分 输出部分 任何问题的算法流程图框架： 开始 结束 输入 输出 处理 什么是枚举算法 有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不符合要求的，保留那些符合要求的，这种方法叫枚举算法。 并不是所有的问题都可以使用枚举算法来求解，只有当问题的所有可能解的个数不太多时，并在可以接受的时间内得到问题的所有解，才有可能使用枚举算法 。 枚举算法的解题过程分两步 逐一列举可能的解的范围。这个过程用循环结构实现 并对每一个列举可能的解进行检验，判断是否为真正的解 。 这个过程用选择结构实现 枚举算法=循环结构+选择结构 循环结构内嵌套选择结构 枚举算法的结构流程图框架： 开始 结束 输入 输出 循环结构 分支结构 作用：逐一列举可能解的范围 作用：逐一检验可能解的是否是真解 处理部分 例题2： 一份单据中被涂抹的数字的推算。 一张单据上有一个5位数字组成的编号，其千位数和百位数处已经变得模糊不清，如下所示。但是知道这个5位数是57或67的倍数。现要求设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。 流程图 No.1 4 7 7 0 4 0 1 7 1 4 0 1 7 2 4 0 1 7 3 4 0 1 7 4 4 0 1 7 5 4 0 1 7 6 4 0 1 7 7 4 0 1 7 8 4 0 1 7 9 4 0 1 i j 7 0 4 9 1 7 1 4 9 1 7 2 4 9 1 7 3 4 9 1 7 4 4 9 1 7 5 4 9 1 7 6 4 9 1 7 7 4 9 1 7 8 4 9 1 7 9 4 9 1 i j i 从0变化到9；j从0变化到9。因此，需要构造一个双重循环。 可能的解 n ←10407+1000*i+10*j i=9 Y N 开始 i ←0 i ←i+1 结束 j=9 N j ←j+1 j ←0 Y i=9 Y N 开始 i ←0 i ←i+1 结束 j=9 N j ←j+1 j ←0 Y i=9 Y N 开始 i ←0 i ←i+1 j=9 N j ←j+1 j ←0 Y c ←0 输出c 结束 1 2 c ←c+1 输出 n n ←10407+i*1000+j*10 n mod 57=0或 n mod 67=0 N Y 2 1 例题3： 1000以内素数的推算 素数，也叫质数。判断一个数是否为素数，可以使用素数的定义。通常我们称自然数n是一个素数，是指只有1和n本身才能整除它（1不是素数，2是最小的素数），即一个素数除了它本身以外，不可能分解为其他自然数的乘积。 流程图 例题2：包装600个变形金刚，要求是：（1）包装的规格分别是：小盒每盒12个，大盒每盒15个。（2）每种规格的盒数都不能为0。请设计一个算法，输出所有可能的包装方案。[文件名：包装方案] 解题思路：假设大盒、小盒的数量分别为i ,j ，那么可推导出 15*i+12*j =600, 根据每种规格的盒数都不能为0，得出i=600 / 15 -1 ； j=600 / 12 - 1；只要满足这两个条件的i,j值，都是是符合要求的方案。本题可通过枚举的方法，通过多重循环，逐一的检验每一个可能的i,j值，最终得出所有可能的包装方案。 i40 Y N 开始 i ←i+1 j50 N j ←j+1 j ←1 Y i←1 结束 1 2 n=n+1 输出 i,j i * 15 + j * 12 = 600 N Y 2 1 n=0 输出 n 例题2：包装600个变形金刚，要求是：（1）包装的规格分别是：小盒每盒12个，大盒每盒15个。（2）每种规格的盒数都不能为0。请设计一个算法，输出所有可能的包装方案。 [文件名：包装方案] n = 0 For i = 1 To 600 / 15 - 1 For j = 1 To 600 / 12 - 1 If i * 15 + j * 12 = 600 Then Print 大盒： +