4.2枚举算法的程序实现

枚举算法帮助文件枚举算法帮助文件 一 构建新知 一 构建新知 课中完成 1 枚举算法 枚举算法的定义 按问题本身的性质 一一列举出该问题所有可能的解 并在逐一列举的过程中检验每 个可能解是否是问题的真正解 若是 则采纳这个解 否则抛弃它 在列举的过程中应 注意不能重复也不能遗漏 枚举算法解题的基本思路 常用结构 循环嵌套分支 1 确定枚举范围和判定条件 2 一一枚举可能的解 验证是否是问题的解 枚举算法的关键 1 一一枚举 2 逐一检验 二 学生练习 二 学生练习 课中完成 1 查找勺子 勺子放在学校仓库的箱子里 编号从 01 50 根据线索一 勺子放在编号为 3 和 7 的 倍数的箱子里 在学校仓库中查找出所有的勺子 画出流程图并编程输出 一一列举的范围 逐一检验的条件 文件保存 以班级 学号 01 保存在 Z 高一 N 班 枚举算法文件夹中 2 勺子装盒 假设共有 140 把勺子 要装盒运送到十八岁成人仪式现场 现有大 小两种盒子 小盒每盒可装 10 个 大盒每盒可装 15 个 要求大小盒子都要用到且每盒都 条件 是否继续列举 列举 F F T T 检验 操作 1 条件 是否继续列举 列举 F F T T 检验 条件 是否继续列举 列举 F F T T 检验 操作 2 必须装满 求出所有可能的装盒方案 并统计出方案数 复杂枚举问题可用循环结构嵌套 循环结构 双重循环 本课任务 思考一一列举的范围 和正确书定检验条件 画流程图和编程输出 本节课选做 修改完善算法并进行适当优化 比一比谁的程序效率最高 界面设计及参考程序如下 Private Sub Command1 Click Dim i As Integer j As Integer t As Integer t 0 Text2 Text For i 0 To 100 For j 0 To 100 If i 0 And j 0 And 10 i 15 j 140 Then Text2 Text Text2 Text Str i Str j Chr 13 Chr 10 t t 1 End If Next j Next i Text1 Text Str t End Sub 小结小结 枚举算法的特点 枚举算法实现的基本结构是用循环结构一一列举 用分支结构逐个检验 由此可以看出 枚举算法的一般结构应为 循环结构嵌套分支结构 一些较复杂的枚举问题可能涉及循环 结构嵌套循环结构 双重循环 枚举算法的局限性 并不是所有的问题都可以使用枚举算法来寻找答案 仅当问题的所有可能解的个数不 太多时 才有可能使用枚举算法 在可以接受的时间内得到问题的所有解 三 作业三 作业 阅读资料一 水仙花数 若一个三位数x 100a 10b c a b c都是个位数 满足 a3 b3 c3 x 则x称为水 仙花数 参考答案 153 370 371 407 以此类推 一个四位数x 1000a 100b 10c d a b c d都是个位数 满足 a4 b4 c4 d4 x 则x称为水仙花数 参考答案 1634 8208 9474 1 寻找三位水仙花数 要求 在作业本上画流程图和编程 难点分析 如何将一个三位数中各个位的数字取出 百位数数值 a 十位数数值 b 个位数数值 c 参考流程图如下 流程图中的 i 表示三位数 开始 i 输出 i i a b c i i 1 结束 Y N N Y 学习拓展学习拓展 选做 画流程图 1 第 2 章例 4 中 一份被涂抹的单据后续 如果被涂抹数字是 如下图 其它条件不 变 该如何推算 分析 检验条件不变 那么关键是如何用变量描述所有可能的五位数 很明显 可以用两 个变量 i 和 j 来分别描述百位和个位上可能的数 假设百位上为 i 个位上为 j 则 i 和 j 的范围都是 0 9 这个五