算法实例(枚举算法)

小越中学信息技术组 第 二 章 算 法 实 例 2.1枚举算法 一、作业回顾表扬：张娴雯孙莹、黄豪炳A、B两数交换问题：（借用第三者）方法一：CA：AB：BC（加减法）方法二：AA+B：BAB：AAB（非零乘除法）方法三：AA+B：BAB：AAB4、称盐问题1、 左 边 放 1、 1、 2、 5法 码 ， 共 9克2、 右 边 放 9克 食 盐3、 拿 掉 法 码 ， 将 食 盐 平 分 ， 即 得5、判断构成三解形 开始输入三边a,b,c1 1a+b=ca+c=bb+c0?负数sum2=sum2+nc2=c2+1 YNY N 想 一 想 ： 一 天 早 上 ， 数 学 课 代 表 收 好 了 数 学 练 习 本 ， 他 的 同桌 物 理 课 代 表 收 好 了 物 理 练 习 本 ， 但 是 由 于 一 些 意外 ， 两 种 练 习 本 混 在 了 一 起 。 现 在 要 把 混 在 一 起 的74本 练 习 本 区 分 开 ， 假 如 你 是 数 学 课 代 表 ， 你 会 怎么 做 ？ 请 讲 出 你 的 解 决 方 案 。 C=74Y 列 举检 验是 否 继 续 列 举Y NC=C+1打 开 一 本 作 业是 数 学 作 业 吗放 在 左 边 放 在 右 边Y NC=1 N 试 一 试 ： 请 用 自 己 的 话 试 着 总 结 什 么 是 枚 举 法 。这 种 列 举 出 所 有 可 能 的 情 况 并 逐 一 进 行 检 验 ， 根据 检 验 的 结 果 执 行 相 应 操 作 的 方 法 就 是 枚 举 法。枚举法的基本思想：是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是符合条件的，哪些是不符合条件的，去掉。能使命题成立，即为其解。其实质是一一列举所有可能，过滤掉不合要求，保留符合要求。枚举法的优点：由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的 正确性比较容易证明。枚举法的缺点： 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。 练 一 练 ： 学 校 体 育 馆 买 进 100个 篮 球 ， 只 有 “ 斯 伯 丁 ” 和 “ 摩腾 ” 两 个 牌 子 ， 为 运 输 方 便 将 它 们 混 在 了 一 起 运 来 。请 你 设 计 一 个 算 法 ， 帮 助 器 材 保 管 员 统 计 共 有 多 少个 “ 斯 伯 丁 ” 篮 球 。 要 求 ： 请 将 你 解 决 问 题 的 流 程 图 绘 制 出 来 。 开 始J=100C=0,J=1Y NN 输 出 C结 束拿 出 一 个 篮 球是 斯 伯 丁 吗C=C+1Y 列 举检 验J=J+1 研 究 范 围 列 举检 验是 否 继 续 列 举Y N 枚 举 法 的 结 构 特 点 ：逐 一 列 举 和 检 验 ， 用 循 环 结 构 实 现 。关 键 步 骤 ： 确 定 范 围 、 列 举 、 检 验 。 检 验 就 是 对 某 个 给 定 的 条 件 进 行 判断 ， 根 据 判 断 的 不 同 结 果 执 行 不 同 操 作 ， 所 以检 验 可 用 分 支 结 构 实 现 。是 数 学 作 业 吗放 在 左 边 放 在 右 边Y N 若 一 个 三 位 数 X=100a+10b+c（ a、 b、 c都 是 个 位 数 ） ， 满 足a3+b3+c3=X,则 X称 为 水 仙 花 数 ， 请 设 计 算 法 ， 找 出 所 有 的 水仙 花 数 。 列 举 检 验研 究 范 围 100 = X = 999分 别 得 到 三 位 数 的 百 位 a、 十 位 b、 个 位 ca3+b3+c3=X 开 始 结 束 X=100X=999分 别 得 到 三 位数 的 百 位 a、十 位 b、 个 位 ca3+b3+c3=X输 出 X X=X+1a=int(X/100)c=X % 10b=(X-100*a-c)/10YY NN 枚 举 法 的 注 意 点 ：1、 选 定 合 适 的 研 究 对 象 的 范 围 。2、 找 到 判 断 正 确 解 的 条 件 ， 列 举 。3、 逐 一 检 验 范 围 内 的 所 有 研 究 对 象。 例 1： 涂 抹 数 字一 张 单 据 上 有 一 个 5位 数 的 编 码 ， 其 千 位 数 和 百 位 数 已 经 变 得模 糊 不 请 。 但 是 知 道 这 个 5位 数 是 57或 67的 倍 数 。 现 在 要 设 计一 个 算 法 ， 输 出 所 有 满 足 这 些 条 件 的 5位 数 ， 并 统 计 这 样 的 数的 个 数 。 No.1 47分析:范 围 ： 首 先 ， 千 位 数 和 百 位 数 可 以 填 上 00， 01， 02， 97， 98，99； 得 到 10047， 10147， 19947。 建 一 个 循 环 变 量 为 j， 从 0到 99的 一 个 循 环 ， 每 一 个 可 能 解 n的 值 为 10047+j*100列 举 ： 其 次 ， 对 每 一 个 n判 断 是 否 能 被 57或 67整 除 。 若 是 ， 输 出 一 组 解 ， 解 的个 数 +1； 若 不 是 ， 舍 弃检 验 ： n mod 57=0 or n mod 67=0 (其 他 判 断 方 法 ） 算法描述1、计数器c 02、j 03、判断j100,是转4，否转向 94、可能解 n 10047+100*j5、判断n是否57或67的倍数，是转向6；否转向86、计数器cc+1；7、输出真正的解n8、jj+1；转向 39、输出解的个数 C10、结束j100Y N开始c 0 j j+1结束c c+1输出 nn 10047+j*100 n mod 57=0或n mod 67=0 NYj 0 输出 j 上虞区小越中学信息技术组 编写程序深化思考题：一张单据上有一个5位数的编码，其千位数和十位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。No.1 4 7 范 围 ： 鸡 翁 列 举 ： x=20Y N开始x 0 x x+1结束y=33 Ny y+1y 0 Yx y z0 0 1000 1 990 2 98 0 33 67 20 33 47 z 100-x-y输出x,y,z5*x+3*y+z/3=100 NY 范 围 ： 列 举 ： 检 验 ： x=74Y N开始x 1 x x+1y=200 Ny y+1y 1 结束Yx*8+y*3=600?输出x,y值假如要求：1、大盒是偶数的呢？2、大盒数量要超过小盒的数量深化思考题 思 考 题 ： 如 果 你 是 体 育 委 员 ， 假 设为 了 教 学 的 需 要 ， 要 对总 共 60个 篮 球 进 行 分 组 。要 求 如 下 ： 1、 A类 组 每 组 有 4个 球 ，B类 组 每 组 有 6个 球 ； 2、 A类 组 和 B类 组 的 数 量都 不 能 为 0。请 设 计 一 个 算 法 ， 输 出 所有 可 能 的 分 组 方 案 。 开始A=1A=14B=1B=10A*4+B*6=50输出A,BB=B+1 A=A+1结束NYY NY N P251、 2、 3题作业： 分 析 ： 千位数和十位数上的数字只能是0-9中的一个。1 0 4 0 71 0 4 1 71 0 4 2 71 0 4 3 71 0 4 4 71 0 4 5 71 0 4 6 71 0 4 7 71 0 4 8 71 0 4 9 7i j 1 9 4 0 71 9 4 1 71 9 4 2 71 9 4 3 71 9 4 4 71 9 4 5 71 9 4 6 71 9 4 7 71 9 4 8 71 9 4 9 7i ji 从0变化到9；j从0变化到9。因此，需要构造一个双重循环。可能的解n 10407+1000*i+10*j 双 重 循 环 的 构 造1、i 02、判断i=9；是转向3，否则转向73、j 04、判断j=9；是转向5，否则转向65、j j+1； 转向46、i i+1；转向27、结束i=9Y N开始i 0 i i+1结束j=9 Nj j+1j 0 Y 思 考 ：右 面 的 流 程图 有 没 有 问题 i=9Y N开始i 0 i i+1结束j=9 Nj j+1j 0 Y 算 法 描 述j+1；转向 410、i i+1；转向 2 i=9Y N开始i 0 i i+1j=9 Nj j+1j 0 Y c 0 c 结束12 c c+1输出 nn 10047+j*100 n mod 57=0或n mod 67=0 NY 2 1 X: 1-74 Y: 1-118 Z: 1-293 x=74Y N开始x 1 x x+1y=118 Ny y+1y 1 Y z z+1 结束z=293z 1 判断真正的解 Y N