枚举法解决百元买百鸡.ppt

枚举法实例 信息工程学院 主讲教师 门瑞 什么是枚举法 信息工程学院 基本思想 枚举也称穷举 指的是从问题可能的解的集合中一一列举各元素 用题目给定的条件判定哪些是无用的 哪些是有用的 能使命题成立 即为其解 本质上属于搜索算法 什么是枚举法 信息工程学院 特点 容易理解 步骤单一 得到的结果肯定是正确的 通常会涉及到求极值 如最大 最小等 数据量大的话 可能会造成时间崩溃 引子 信息工程学院 例1 以下式子中的每个汉字代表一个数字 求出这些汉字代表的数字分别是多少 慕课制作组X慕 组组组组组组 枚举法 信息工程学院 计算机解决枚举问题 算法简单 精确度高 常用多重循环解决枚举问题 while循环 for循环 效率低 当问题的规模变大 循环的阶数增加 执行的速度严重变慢 百元买百鸡问题 例2 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 问鸡翁 母 雏各几何 解题思路 设鸡翁 鸡母 鸡雏的数量分别为x y z 则有以下方程x y z 1005x 3y z 3 100此三元一次方程有多个解 可用枚举法求解 信息工程学院 百元买百鸡问题 C语言解法一 main intx y z for x 1 x 100 x for y 1 y 100 y for z 1 z 100 z if z 3 0 信息工程学院 百元买百鸡问题 C语言解法一 信息工程学院 main intx y z for x 1 x 100 x for y 1 y 100 y for z 1 z 100 z if z 3 0 枚举次数 100 100 100 100万次 2020 3 17 9 可编辑 百元买百鸡问题 限定变量的取值范围x的取值范围是1 x 20y的取值范围是1 y 33减少循环的层数 判断时间z 100 x y 信息工程学院 有没有更好的解法呢 百元买百鸡问题 C语言解法二 main intx y z for x 1 x 20 x for y 1 y 33 y if 100 x y 3 0 枚举次数 20 33 660次 百元买百鸡问题 有没有更好的解法呢 信息工程学院 百元买百鸡问题 x y z 1005x 3y z 3 100 y 25 7 4 xz 75 3 4 x x 4ky 25 7kz 75 3k 化简 令x 4k 分析题意可知 k只能取1 2 3 信息工程学院 百元买百鸡问题 C语言解法三 main intk for k 1 k 3 k printf 鸡翁 d只 鸡母 d只 鸡雏 d只 n 4k 25 7k z 枚举次数 3次 信息工程学院 枚举法 信息工程学院 优化策略 对问题多加分析 减少循环重数和次数 合理选择用于枚举的变量 减少每种情况的判断时间 是否有其他更好的方法 知识拓展 信息工程学院 试用枚举法解决以下两个问题 从1 10的10个数中 每次取2个数 要使它们的和大于10 一共有多少种取法 从学校到少年宫有4条东西走向的马路和3条南北走向的马路 小