1.24枚举算法(双重)研究.ppt

有一类问题可以采用一种盲目的搜索方法, 在搜索结果的过程中,把各种可能的情况都考虑到,并对所得的结果逐一进行判断,过滤掉那些不合要求的,保留那些合乎要求的结果,这种方法叫做枚举算法。关键点: 注意点: 既不能遗漏、也不应该重复一一列举、逐一检验列举:检验: 用重复模式实现用选择模式实现重复模式嵌套选择模式结构: Y N 列举条件一张单据上有一个 5位数的编号,其千位数和百位数处已经变得模糊不清。但是知道这个 5 位数是 57的倍数。现在要设计一个算法,输出所有满足这些条件的 5位数,并统计这样的数的个数。列举: 检验: 用a 表示这个 5位数,则初值: 10047 终值: 19947 步长: 100 a:5位数 c:个数开始 c ←0 a≤19947 Y a能被 57 整除 Y c ← c+1 a ← a+100 N结束 N 输出 a 输出 c a ←10047 用a 表示千位和百位上的数字,则初值: 0终值: 99 步长: 1 a:填入的数字 n:5位数 c:个数开始 c ←0a≤99Y n ← 10047+a × 100 n能被 57 整除 Y c ← c+1 a ← a+1 N 结束 N输出 n 输出 c a←0 a:5位数 c:个数 a:填入的数字 n:5位数 c:个数开始 c ←0a≤19947 Y a能被 57 整除 Y c ← c+1 a ←a+ 100 N结束 N 输出 a 输出 c a ←10047 开始 c ←0a≤99Y n ← 10047+a × 100 n能被 57 整除 Y c ← c+1 a ←a+ 1 N 结束 N输出 n 输出 c a←0思思考考一张单据上有一个 5位数的编号,其千位数和十位数处已经变得模糊不清。但是知道这个 5位数是 57的倍数。现在要设计一个算法, 输出所有满足这些条件的 5位数,并统计这样的数的个数。列举: 检验: 双重循环的结构双重循环的结构 Y N 条件 e step Y N条件 e step 比较以下两个流程图有何不同? Y N x ← 1 x ← x + 1 N y ← y + 1 y ← 0 Y x ≤2y ≤2