Java 大师之路

方 林 2008 年 12 月

序 如 何 成 为 一 名 Java 程 序 设 计 的 专 家 和 大 师 呢? 这 是 困 扰 程 序 员 软 件 工 程 师 和 资 深 软 件 工 程 师 的 一 大 难 题 很 多 毕 业 5 6 年 的 软 件 工 程 师 在 有 了 一 定 的 Java 程 序 设 计 经 验 和 动 手 能 力 之 后, 往 往 会 遇 到 相 当 长 一 段 时 间 的 技 术 瓶 颈 期 很 多 人 在 此 期 间 在 技 术 和 动 手 能 力 上 几 乎 再 也 无 法 得 到 实 质 性 提 高 有 的 认 为 程 序 设 计 不 过 如 此, 发 出 了 还 有 什 么 我 编 不 了 的 程 序 呢? 的 疑 问 ; 更 多 的 人 则 厌 倦 了 千 篇 一 律 毫 无 趣 味 的 程 序 设 计 工 作, 转 行 当 了 项 目 经 理 这 本 书 就 是 写 给 那 些 有 了 一 定 程 序 设 计 经 验, 还 没 有 厌 倦 程 序 设 计, 但 是 不 知 道 如 何 进 一 步 提 高 的 人 看 的 作 为 我 的 目 标 读 者, 你 们 可 能 更 多 地 是 靠 个 人 经 验 编 写 Java 程 序 也 许 你 们 编 写 了 很 多 年 程 序, 积 累 了 丰 富 的 Java 编 程 经 验, 非 常 熟 悉 Java 语 法 和 J2EE 上 的 各 种 开 源 工 具, 这 也 是 一 部 分 人 之 所 以 骄 傲 的 理 由 但 是 个 人 经 验 永 远 也 不 能 与 积 累 了 几 百 年 或 上 百 年 的 数 学 和 计 算 机 理 论 相 提 并 论 后 者 所 提 供 的 方 法 早 就 被 证 明 了 是 程 序 设 计 的 最 简 单 最 直 接 最 容 易 的 方 法 所 以 如 果 你 还 没 有 有 意 识 地 系 统 地 使 用 你 在 大 学 期 间 学 习 的 计 算 机 科 学 理 论 和 数 学 知 识 指 导 程 序 设 计 ( 比 如 你 不 知 道 编 译 原 理 除 了 对 开 发 编 译 程 序 有 用 外 在 一 般 的 程 序 设 计 中 还 有 什 么 用 ), 那 么 这 本 书 就 特 别 适 合 你 这 本 书 的 目 的 在 于 揭 示 数 学 和 计 算 机 科 学 理 论 在 (Java) 程 序 设 计 中 的 重 要 作 用 和 价 值, 帮 助 你 突 破 个 人 经 验 的 桎 梏, 深 刻 理 解 隐 藏 在 Java 语 法 背 后 的 奥 秘 希 望 读 完 这 本 书 之 后, 你 能 够 轻 松 度 过 上 面 提 到 的 那 个 技 术 瓶 颈 期, 真 正 意 识 到 数 学 和 计 算 机 理 论 的 重 要 作 用, 从 而 为 成 为 Java 程 序 设 计 方 面 的 专 家 和 大 师 打 下 坚 实 的 理 论 基 础 2

目 录 3 目 录 第 一 章 引 言... 8 1.1. 兴 趣 才 是 学 习 的 主 要 动 力... 8 1.2. 计 算 机 科 学 理 论 的 趣 味 在 哪 里?... 8 1.3. 本 书 跟 学 习 计 算 机 理 论 无 关... 9 1.4. 对 你 的 要 求... 9 第 二 章 自 顶 向 下 的 程 序 设 计... 11 2.1. 100 的 阶 乘... 11 2.1.1. 错 误 的 解 法... 11 2.1.2. 使 用 BigInteger?... 11 2.1.3. 自 己 定 义 状 态 可 变 的 大 整 数... 12 2.1.4. 关 于 恒 类 (immutable class)... 14 2.1.5. 通 过 这 个 例 子 你 学 到 了 什 么?... 15 2.2. 五 猴 分 桃 问 题... 16 2.2.1. 一 个 容 易 的 解 法... 16 2.2.2. 一 点 改 进 考 虑 任 意 个 猴 子... 17 2.2.3. 第 二 点 改 进 加 大 步 长... 18 2.2.4. 逆 向 思 维... 19 2.2.5. 数 学 解... 20 第 三 章 递 归 程 序 设 计... 21 3.1. 递 归 和 数 学 归 纳 法... 21 3.1.1. 第 一 个 例 子 Hanoi 塔... 21 3.1.2. 递 归 背 后 的 数 学 原 理... 22 3.1.3. Hanoi 塔 问 题 的 递 归 解... 22 3.2. 一 些 有 趣 的 递 归 程 序... 24 3.2.1. 字 符 串 通 配 符 匹 配... 24 3.2.2. 兔 子... 26 3.2.3. 组 合 和 排 列... 27 3.2.3.1. 组 合... 27 3.2.3.2. 排 列... 28 3.2.4. 人 字 形 的 铁 路... 29 3.2.5. 五 升 的 杯 子 和 三 升 的 杯 子 倒 出 四 升 水... 31 3.2.5.1. 错 误 的 递 归... 31 3.2.5.2. 新 参 数 组 合 一 定 要 更 接 近 于 边 界... 34 3.2.5.3. 保 存 状 态 法... 34 3.3. 递 归 程 序 非 递 归 化... 37 3.3.1. 函 数 调 用 的 实 质... 37 3.3.1.1. 函 数 返 回 时 应 该 返 回 到 下 一 行... 37 3.3.1.2. 用 堆 栈 来 保 存 返 回 地 址... 38 3.3.1.3. 运 行 堆 栈 还 用 来 保 存 参 数... 39 3.3.1.4. 返 回 地 址 入 栈 的 次 序... 39 3.3.1.5. 参 数 入 栈 的 次 序 与 可 变 参 数... 40 3.3.1.6. Java 的 可 变 参 数 是 另 一 回 事... 40 3.3.1.7. 控 制 运 行 堆 栈 的 代 码 应 该 放 在 哪 里?... 41 3.3.1.8. cdecl 和 pascal 申 明... 42 3.3.1.9. 运 行 堆 栈 常 用 来 保 存 哪 些 数 据?... 42 3.3.2. 递 归 调 用 与 一 般 函 数 调 用... 43 3.3.3. 非 递 归 中 序 遍 历... 43

目 录 3.3.4. 递 归 程 序 非 递 归 化 示 例... 45 3.3.4.1. 第 一 步 : 给 代 码 的 每 一 个 行 加 行 号... 45 3.3.4.2. 第 二 步 : 使 用 Stack, push(), pop() 和 goto 替 换 递 归 调 用... 45 3.3.4.3. 第 三 步 : 用 while 替 换 if 和 goto... 46 3.3.4.4. 第 四 步 : 用 while 循 环 处 理 返 回 地 址 60... 47 3.3.4.5. 第 五 步 : 消 除 最 后 的 goto 30 语 句... 48 3.3.4.6. 第 六 步 : 删 除 goto 10... 49 3.3.4.7. 第 七 步 : 用 30 取 代 返 回 地 址 70... 50 3.3.4.8. 第 八 步 : 提 前 执 行 弹 出 操 作... 52 3.3.4.9. 第 九 步 : 删 除 与 返 回 地 址 60 有 关 的 操 作... 53 3.3.4.10. 第 十 步 : 返 回 地 址 30 也 不 需 要 了... 54 3.3.4.11. 第 十 一 步 : 消 除 node 与 stack 栈 顶 的 重 复... 55 3.4. 哑 元 与 不 可 递 归 性... 56 3.4.1. 什 么 是 哑 元... 56 3.4.2. 哑 元 与 参 数 的 差 别... 57 第 四 章 数 的 进 制... 59 4.1. 猜 姓 名 问 题... 59 4.1.1. 神 算 子 的 秘 密... 59 4.1.2. 神 算 子 程 序... 59 4.1.2.1. getpages() 函 数... 60 4.1.2.2. playgame() 函 数... 62 4.1.3. 通 用 的 神 算 子 程 序... 63 4.2. 100 瓶 药 水... 64 4.2.1. 相 同 的 解 法... 64 4.2.2. 二 分 法... 64 4.3. 十 二 个 小 球 问 题... 64 4.3.1. 人 工 解... 65 4.3.2. 计 算 机 解... 67 4.3.2.1. 小 球 的 三 进 制 编 码... 68 4.3.2.2. 调 整 编 码... 69 4.3.2.3. 开 始 称 天 平... 70 4.3.2.4. 程 序... 70 4.4. 囚 犯 问 题... 73 4.4.1. 用 一 进 制 解 决 问 题... 74 4.4.2. 用 程 序 模 拟 解 的 过 程... 75 第 五 章 继 承 接 口 和 代 理... 77 5.1. 动 态 定 连... 77 5.1.1. 什 么 是 动 态 定 连... 77 5.1.2. 动 态 定 连 是 如 何 实 现 的... 77 5.1.3. C++ 是 如 何 实 现 动 态 定 连 的... 78 5.1.4. 抽 象 函 数 不 能 是 静 态 (static) 的... 79 5.2. 为 什 么 JAVA 不 支 持 多 继 承... 79 5.2.1. 不 支 持 多 继 承 并 非 仅 仅 是 个 语 法 规 定... 79 5.2.2. 分 布 式 开 发 与 多 继 承... 79 5.2.3. Java 语 言 必 须 提 供 中 间 代 码... 80 5.2.4. Java 语 言 不 支 持 多 继 承... 80 5.3. 接 口 中 不 能 定 义 成 员 变 量 类 变 量 和 函 数 体... 81 5.3.1. 接 口 中 不 能 有 成 员 变 量 和 类 变 量 却 可 以 有 类 常 数... 81 5.3.2. 为 什 么 接 口 中 的 函 数 没 有 同 样 问 题?... 82 4

目 录 5 5.3.3. 同 名 变 量 或 常 数... 82 5.4. 接 口 中 的 函 数 只 能 是 公 开 (PUBLIC) 的... 83 5.4.1. 静 态 定 连 和 动 态 定 连... 83 5.4.2. protected 的 真 正 含 义... 83 5.4.3. 接 口 中 的 方 法 法 只 能 是 公 开 的... 84 5.5. 外 部 接 口 和 类 可 以 是 受 保 护 的 吗?... 84 5.6. 接 口 的 实 现... 85 5.6.1. 接 口 中 不 能 定 义 函 数 体... 85 5.6.2. 接 口 的 静 态 实 现... 85 5.6.3. 接 口 的 动 态 实 现... 85 5.6.4. 代 理 (Proxy) 就 是 接 口 的 动 态 实 现... 86 5.6.5. 接 口 的 动 态 实 现 与 代 理 设 计 模 式 的 差 别... 89 5.7. 小 结... 89 第 六 章 常 用 设 计 模 式 的 实 质... 91 6.1. 事 件 监 听 (EVENT-LISTENER) 模 式... 91 6.1.1. 事 件 类... 91 6.1.2. 监 听 器... 92 6.1.3. 添 加 和 删 除 监 听 器... 92 6.1.4. 深 入 思 考 之 一 : 避 免 重 复 以 及 同 步... 93 6.1.5. 深 入 思 考 之 二 : 异 步 执 行 监 听 函 数... 94 6.1.6. 事 件 的 触 发... 95 6.1.7. 事 件 监 听 模 式 的 实 质 是 回 调... 96 6.1.8. 事 件 监 听 模 式 应 用... 97 6.2. 工 厂 (FACTORY) 模 式... 97 6.2.1. 工 厂 模 式 的 实 质... 97 6.2.2. 工 厂 模 式 的 典 型 示 例... 97 6.2.3. Spring 的 工 厂 模 式... 98 6.3. 单 例 (SINGLETON) 模 式... 98 6.3.1. 可 替 换 的 单 例... 98 6.3.2. 不 可 替 换 的 单 例... 99 6.3.3. 静 态 方 法 封 装... 99 6.4. 代 理 模 式 (PROXY PATTERN)... 99 6.4.1. 什 么 是 代 理 模 式... 99 6.4.2. 代 理 的 作 用... 100 6.4.3. JDK 中 的 代 理 设 计 模 式 的 示 例... 101 6.4.4. 代 理 的 一 些 细 节... 101 6.5. 装 饰 (DECORATOR) 模 式... 101 6.5.1. 与 代 理 模 式 的 相 似 性 和 差 异... 101 6.5.2. 为 什 么 不 使 用 继 承... 103 6.6. 适 配 器 (ADAPTER) 模 式... 103 6.6.1. 与 装 饰 模 式 的 相 似 性 和 差 异... 103 6.6.2. 适 配 器 的 制 作... 104 6.7. 桥 接 (BRIDGE) 模 式... 104 6.7.1. 桥 接 模 式 的 实 质... 104 6.7.2. 桥 接 模 式 的 应 用... 105 6.7.3. 桥 接 模 式 的 代 价... 106 6.8. 面 板 (FACADE) 模 式... 107 6.8.1. 什 么 是 面 板 模 式... 107 6.8.2. JDK 中 的 面 板 模 式... 107

目 录 6.9. 创 建 者 (BUILDER) 模 式... 108 6.9.1. 创 建 者 模 式 和 工 厂 模 式 的 差 别... 108 6.9.2. 创 建 者 模 式 示 例... 108 第 七 章 搜 索... 110 7.1. 搜 索 和 搜 索 树... 110 7.1.1. 最 短 路 径 问 题... 110 7.1.2. 关 于 搜 索 树 的 若 干 理 论... 111 7.1.3. 关 于 搜 索 树 的 若 干 错 误 理 解... 112 7.1.4. 关 于 搜 索 树 的 重 要 假 设... 112 7.2. 通 用 搜 索 算 法... 113 7.2.1. 文 字 描 述 的 通 用 搜 索 算 法... 113 7.2.2. 状 态 接 口... 113 7.2.3. 访 问 者 接 口... 115 7.2.4. 搜 索 引 擎 核 心 数 据 结 构 类 型... 116 7.2.5. 处 理 访 问 者... 118 7.2.6. 搜 索 引 擎 核 心 代 码... 119 7.3. 八 数 码 问 题... 120 7.3.1. 通 用 打 印 程 序... 121 7.3.2. 八 数 码 问 题 的 主 程 序... 121 7.3.3. 八 数 码 状 态 中 的 数 据 结 构... 122 7.3.4. 八 数 码 状 态 的 辅 助 函 数... 122 7.3.5. 八 数 码 状 态 的 核 心 程 序... 124 7.4. 华 容 道 问 题... 126 7.4.1. 华 容 道 问 题 的 主 程 序... 126 7.4.2. 华 容 道 状 态 的 数 据 结 构 和 辅 助 类 型... 127 7.4.3. 华 容 道 状 态 的 初 步 定 义... 129 7.4.4. 华 容 道 状 态 的 核 心 程 序... 130 7.5. 倒 水 问 题... 133 7.5.1. 倒 水 问 题 的 主 程 序... 133 7.5.2. 倒 水 问 题 的 状 态... 134 7.6. A* 搜 索... 136 7.6.1. A* 搜 索 与 通 用 搜 索 的 差 异... 136 7.6.2. 估 计 耗 费 是 实 际 耗 费 的 下 限... 136 7.6.3. A* 算 法 中 数 据 结 构 的 变 化... 137 7.6.4. A* 算 法 的 Java 实 现... 138 7.7. 结 束 语... 139 第 八 章 博 弈... 140 8.1. 博 弈 和 搜 索... 140 8.1.1. 博 弈 和 搜 索 的 异 同... 140 8.1.2. 得 分... 140 8.2. 简 单 博 弈 算 法... 141 8.2.1. 博 弈 树 的 扩 展... 141 8.2.2. 布 局 接 口 Layout... 142 8.2.3. 简 单 博 弈 算 法... 143 第 九 章 模 式 识 别... 145 9.1. 一 维 模 式 识 别... 145 6

目 录 第 十 章 编 译 技 术... 146 10.1. 单 词 句 子 和 语 法... 146 10.2. 自 顶 向 下 递 归 子 程 序... 146 第 十 一 章 多 线 程... 147 11.1. 生 产 者 - 消 费 者... 147 11.1.1. Buffer... 147 11.1.2. 舞 会 问 题 : 一 种 特 殊 的 生 产 者 消 费 者 问 题... 147 11.1.3. 水 分 子 诞 生... 147 11.1.4. 一 对 多 的 配 对 问 题... 148 11.1.5. 多 对 多 的 配 对 问 题... 148 11.2. 读 写 问 题... 148 11.2.1. 一 般 读 写 问 题... 148 11.2.2. 桥... 148 11.3. 模 拟 电 梯... 148 第 十 二 章 JAVA 的 高 级 话 题... 150 12.1. 关 于 JAVA 的 一 些 错 误 认 识... 150 12.1.1. Java 中 不 含 有 指 针... 150 12.1.2. 为 什 么 interface 可 以 多 实 现... 150 12.2. 两 种 类 型 的 集 合 (SET)... 150 12.3. 弱 连 接... ERROR! BOOKMARK NOT DEFINED. 12.3.1. 垃 圾 回 收 和 释 放... Error! Bookmark not defined. 12.3.2. 弱 连 接... Error! Bookmark not defined. 12.4. 代 理 (PROXY)... 154 12.5. 定 义 和 使 用 自 己 的 标 注 (ANNOTATION)... 154 12.6. 范 型... 155 12.6.1. 范 型 与 数 组... 155 12.6.2. 自 说 明 的 范 型... 155 12.7. 内 部 类... 155 12.7.1. 内 部 类 与 外 部 类 的 异 同... 155 12.7.2. 静 态 内 部 类 与 动 态 内 部 类... 155 7

第 一 章 引 言 1.1. 兴 趣 才 是 学 习 的 主 要 动 力 第 一 章 引 言 你 学 习 计 算 机 科 学 理 论 ( 如 数 据 结 构 编 译 原 理 等 ) 时 是 不 是 很 刻 苦? 先 别 急 着 回 答 是 或 者 不 是 请 先 想 想 学 习 真 的 必 须 是 一 件 苦 差 事 吗? 你 可 能 会 觉 得 奇 怪 : 学 习 不 是 苦 事, 难 道 是 一 件 乐 事 不 成? 与 你 的 想 象 相 反, 学 习 计 算 机 科 学 理 论 的 确 可 以 成 为 一 件 很 有 趣 味 很 好 玩 的 事 情 无 论 学 习 什 么, 如 果 你 不 得 不 刻 苦, 不 得 不 硬 着 头 皮, 结 果 居 然 还 能 学 得 好 能 够 学 以 致 用 能 够 自 愿 地 钻 研 它, 那 不 是 天 方 夜 谭 吗? 我 从 不 认 为 达 尔 文 牛 顿 和 爱 因 斯 坦 会 觉 得 他 们 的 学 习 和 研 究 是 一 件 苦 差 事, 恰 恰 相 反, 他 们 一 定 从 中 获 得 了 巨 大 的 快 乐 也 许 我 们 并 无 雄 心 去 获 得 象 他 们 那 么 大 的 成 就, 但 是 享 受 学 习 和 研 究 的 快 乐 还 是 做 得 到 的 想 想 看, 为 什 么 几 乎 没 有 人 认 为 打 电 脑 游 戏 是 一 件 苦 差 事? 就 连 那 些 最 反 对 子 女 打 游 戏 的 家 长, 自 己 打 起 游 戏 来 也 是 乐 此 不 疲 毫 不 含 糊 的 我 敢 说, 看 我 这 本 书 的 读 者 99% 都 有 过 通 宵 打 游 戏 的 经 历,99% 为 打 游 戏 饿 过 肚 子 就 连 我, 昨 天 晚 上 在 电 脑 上 下 围 棋 还 下 到 半 夜 两 点 半, 被 我 夫 人 好 一 通 数 落 所 以 说 我 们 打 游 戏 的 劲 头 真 的 可 以 用 废 寝 忘 食 通 宵 达 旦 来 形 容 这 股 子 劲 头 如 果 用 来 学 习, 你 的 领 导 同 事 老 师 或 父 母 一 定 会 感 到 非 常 欣 慰 只 可 惜 我 们 通 常 是 被 迫 学 习 的, 真 正 对 学 习 感 兴 趣 的 人 凤 毛 麟 角 问 题 是, 为 什 么 打 游 戏 我 们 就 能 刻 苦, 学 习 就 不 行 了 呢? 原 因 很 简 单 : 打 游 戏 我 们 感 兴 趣 啊 如 果 学 习 我 们 也 能 感 兴 趣 的 话 这 并 不 是 不 可 能 的 我 们 就 不 会 需 要 别 人 来 督 促 和 鞭 策 了, 我 们 自 己 就 会 自 动 地 学 习 和 钻 研! 至 于 刻 苦 学 习 之 类 其 实 误 人 子 弟 的 说 教, 对 我 们 来 说 就 会 是 一 个 笑 话 画 匠 和 画 家 有 什 么 差 异? 歌 星 和 歌 唱 家 的 区 别 是 什 么? 你 想 成 为 一 个 高 级 程 序 员, 还 是 成 为 一 名 程 序 设 计 大 师? 如 果 你 刻 苦 学 习, 那 么 你 最 多 能 成 为 一 个 好 一 点 的 画 匠 歌 星 或 高 级 程 序 员 但 是 如 果 你 想 成 为 一 名 画 家 歌 唱 家 或 者 程 序 设 计 大 师, 那 你 必 须 能 够 享 受 编 程 所 带 来 的 快 乐! 1.2. 计 算 机 科 学 理 论 的 趣 味 在 哪 里? 这 本 书 是 写 给 有 一 定 程 序 设 计 经 验 的 Java 软 件 工 程 师 和 资 深 软 件 工 程 师 看 的 你 还 记 得 计 算 机 科 学 包 括 哪 些 主 要 分 支 和 科 目 吗? 答 案 是 : 数 据 结 构 人 工 智 能 编 译 原 理 操 作 系 统 计 算 机 算 法 高 级 程 序 设 计 语 言 理 论 模 式 识 别 计 算 数 学 高 等 数 学 离 散 数 学 当 然, 计 算 机 理 论 远 远 不 止 这 些 但 是 第 一, 目 前 大 学 本 科 阶 段 学 习 的 计 算 机 理 论 8

第 一 章 引 言 主 要 就 是 这 些 了 ; 第 二, 能 真 正 理 解 和 掌 握 这 些 理 论 你 就 已 经 很 不 错 了, 完 全 有 资 格 召 开 新 闻 发 布 会 宣 布 自 己 是 程 序 设 计 大 师 了 要 不 要 兴 冲 冲 地 马 上 就 去 约 见 记 者? 且 慢! 学 过 与 掌 握 根 本 就 是 两 回 事 你 学 过 数 据 结 构 是 吧? 那 你 说 说 你 在 软 件 公 司 实 际 开 发 软 件 项 目 时, 如 何 使 用 二 叉 树 及 其 遍 历 算 法 的? 傻 眼 了 吧? 当 年 你 学 过 数 据 结 构 考 完 试 之 后 你 就 把 劳 什 子 二 叉 树 丢 到 爪 哇 国 去 了 进 公 司 搞 项 目 开 发 也 全 凭 个 人 经 验 来, 反 正 无 非 就 是 搜 索 统 计 排 序, 烦 是 烦 得 要 死, 难 却 难 不 到 哪 去, 哪 里 还 用 得 着 什 么 二 叉 树! 这 就 是 你 只 能 开 发 一 些 普 通 应 用, 却 不 能 开 发 大 型 应 用 大 规 模 应 用, 不 能 开 发 系 统 软 件 平 台 软 件 的 原 因! 你 不 相 信? 你 会 说 : 我 开 发 的 那 些 应 用 也 是 大 规 模 应 用, 我 不 也 搞 成 了 么? 也 没 二 叉 树 什 么 事! 唉! 一 身 叹 息 曾 经 沧 海 难 为 水, 除 却 巫 山 不 是 云 你 的 那 些 大 规 模 应 用, 在 大 师 ( 比 如 我 ) 的 眼 里, 不 过 是 小 菜 一 碟 只 要 你 没 有 应 用 数 学 和 计 算 机 理 论 做 指 导, 你 的 那 些 大 规 模 应 用 就 像 大 棚 蔬 菜 上 面 的 薄 膜, 大 是 够 大 的, 却 没 有 什 么 厚 度 这 么 说 吧 : 你 一 定 很 熟 悉 Tomcat 吧? 你 能 不 能 照 着 Tomcat 的 样 子 也 开 发 一 个 应 用 服 务 器 玩 玩? 你 肯 定 大 惊 失 色 : 那 是 Apache 的 那 帮 牛 人 搞 的, 我 怎 么 能 跟 他 们 比? 问 题 是,Apache 的 那 帮 人 固 然 很 牛, 但 也 是 吃 五 谷 杂 粮 的, 也 没 见 头 上 长 了 一 个 角 他 们 能 搞 出 Tomcat 以 及 一 大 堆 叫 人 眼 花 缭 乱 的 系 统 软 件 和 平 台 软 件 的 原 因 不 是 因 为 他 们 是 神, 而 是 因 为 他 们 用 数 学 和 计 算 机 理 论 指 导 了 自 己 的 设 计 和 编 程 如 果 你 学 会 了 用 数 学 和 计 算 机 理 论 指 导 编 程, 而 不 是 闭 着 眼 睛 瞎 编, 那 么 你 也 能 搞 出 Tomcat Eclipse Struts Hibernate 或 Spring 等 这 么 复 杂 的 系 统 平 台 或 框 架 出 来 即 使 开 发 一 般 应 用, 你 的 程 序 也 会 显 得 简 洁 容 易 扩 展 容 易 阅 读 容 易 排 错 你 就 会 明 白 程 序 越 简 洁 功 能 反 而 越 强 大 的 道 理, 以 及 为 什 么 会 有 空 间 效 率 时 间 效 率 同 时 提 高 的 事 情 发 生 1.3. 本 书 跟 学 习 计 算 机 理 论 无 关 计 算 机 理 论 所 涉 及 到 的 科 目 有 那 么 多, 但 是 本 书 并 不 试 图 详 细 讲 解 这 些 理 论 的 每 一 个 方 面 这 是 因 为 一 方 面 你 的 教 科 书 已 经 很 好 地 完 成 了 这 个 任 务 ; 另 一 方 面 如 果 这 样 的 话 这 本 书 就 会 有 好 几 千 页 那 么 您 购 买 这 本 书 的 成 本 就 会 跟 您 一 年 的 大 学 学 费 差 不 多 虽 然 我 认 为 花 一 年 的 学 费 学 一 点 真 正 有 用 的 东 西 比 在 大 学 里 忙 着 追 女 孩 要 有 意 义 得 多, 也 有 助 于 您 毕 业 以 后 在 真 正 应 该 追 女 孩 的 时 候 提 高 自 己 的 竞 争 力, 但 问 题 是 您 购 买 这 本 书 的 经 济 承 受 力 和 兴 趣 也 会 大 大 降 低 所 以 我 只 是 让 你 体 验 为 什 么 那 些 计 算 机 科 学 理 论 是 有 趣 的 好 玩 的, 它 怎 么 就 帮 你 编 出 别 人 不 能 或 很 难 编 出 的 程 序 甚 至 我 可 能 并 不 一 开 场 就 提 及 那 些 曾 经 让 你 万 分 讨 厌 的 概 念 ( 比 如 二 叉 树 ) 或 理 论 名 词, 而 是 在 不 知 不 觉 中 让 你 自 己 ( 记 住 : 是 你 自 己, 而 不 是 我 ) 发 现 或 者 推 导 出 理 论 当 你 体 验 到 了 这 种 快 乐, 发 现 自 己 也 可 以 象 福 尔 摩 斯 那 样 进 行 推 理 时, 你 自 然 而 然 就 会 回 头 翻 出 教 科 书 或 者 上 网 进 行 详 细 学 习 就 像 你 打 电 脑 游 戏 一 样, 根 本 就 不 需 要 别 人 督 促 你 1.4. 对 你 的 要 求 首 先, 这 本 书 不 是 写 给 程 序 设 计 初 学 者 看 的 它 的 目 标 读 者 是 那 些 已 经 很 会 编 程 序, 但 是 想 更 进 一 步 提 高 的 人 您 最 好 至 少 自 学 过 数 据 结 构 操 作 系 统 和 计 算 机 组 成 比 如 你 9

第 一 章 引 言 知 道 什 么 是 二 叉 树 参 数 传 递 堆 栈 和 补 码 等 如 果 你 还 学 习 过 编 译 原 理 人 工 智 能 高 级 程 序 设 计 语 言 理 论 或 计 算 机 算 法, 那 就 更 好 了 你 会 获 得 更 多 的 快 乐 相 反, 对 于 初 学 者 来 说, 有 很 多 理 论 和 概 念 您 是 不 清 楚 的 一 本 书 如 果 读 不 顺 畅 的 话, 是 很 难 耐 心 读 下 去 的 而 耐 心 读 书 恰 恰 是 我 最 不 希 望 发 生 的 其 次, 这 本 书 是 用 Java 语 言 写 例 子 程 序 的 所 以 你 应 该 比 较 熟 悉 Java 语 言 了 最 好 有 两 到 三 年 以 上 Java 编 程 经 验 能 够 较 深 刻 地 理 解 封 装 继 承 接 口 重 定 义 等 概 念 还 是 那 句 话, 我 们 不 是 写 给 初 学 者 看 的 第 三, 你 本 来 就 对 程 序 设 计 有 兴 趣 只 是 不 知 道 如 何 更 进 一 步 提 高 更 关 键 的 是 : 你 目 前 还 无 法 做 到 在 程 序 设 计 过 程 中 显 示 地 自 然 而 然 地 主 动 地 应 用 计 算 机 理 论 和 数 学 知 识 那 是 不 是 说 这 本 书 只 适 合 于 计 算 机 或 相 关 专 业 的 人 呢? 不 是 因 为 有 很 多 非 计 算 机 或 相 关 专 业 的 人 编 程 序 却 很 在 行, 甚 至 自 学 了 计 算 机 专 业 的 课 程 这 些 自 学 的 人 往 往 比 专 业 学 生 更 有 兴 趣 学 习 我 本 人 虽 然 是 计 算 机 专 业 毕 业, 甚 至 硕 士 和 博 士 也 都 是 计 算 机 软 件 专 业 毕 业, 但 是 其 实 大 多 数 课 程 是 我 自 学 的 这 是 因 为 我 对 编 程 太 有 兴 趣 了, 当 年 上 课 的 时 候 我 根 本 就 等 不 及 教 师 慢 悠 悠 的 讲 课 进 度 老 师 在 上 面 讲 到 第 二 章 的 时 候, 我 在 下 面 已 经 看 到 第 八 章 了 我 急 于 想 知 道 科 学 家 们 又 讲 了 什 么 有 趣 好 玩 的 新 知 识, 以 至 于 我 可 以 用 来 编 出 让 同 学 们 不 可 思 议 的 程 序 所 以 专 业 不 专 业 什 么 的 根 本 不 重 要 10

第 二 章 自 顶 向 下 的 程 序 设 计 第 二 章 自 顶 向 下 的 程 序 设 计 计 算 机 科 学 理 论 就 像 数 学, 真 正 需 要 你 牢 记 的 公 理 就 那 么 几 条, 其 他 的 都 是 定 理 什 么 是 定 理? 定 理 就 是 从 公 理 和 概 念 直 接 或 间 接 推 导 出 来 的 结 论 我 们 进 行 程 序 设 计 的 第 一 条 公 理 就 是 : 程 序 设 计 应 该 遵 循 自 顶 向 下 先 整 体 后 局 部 的 原 则 下 面 让 我 们 看 一 个 求 100 阶 乘 的 简 单 例 子 2.1. 100 的 阶 乘 我 们 来 编 第 一 个 程 序 : 求 100 的 阶 乘 ( 即 1 2 3... 100) 的 精 确 解 例 如 2!=2, 3!=6,4!=24, 2.1.1. 错 误 的 解 法 也 许 对 于 一 个 象 您 这 样 的 熟 手 来 说, 求 100 的 阶 乘 是 不 是 太 简 单 了? 只 需 从 1 到 100 连 乘 100 次 不 就 行 了? 您 也 许 一 分 钟 就 可 以 把 程 序 搞 定, 比 如 : 例 2.1-1 package com.training.topdown; public class Factorial { public static void main(string args[]) { int n = 100; int result = 1; for(int i = 2; i <= n; i++) result *= i; System.out.printf("%d!=%s\n", n, result); 但 是 当 你 真 正 运 行 这 个 程 序 的 时 候, 它 打 印 出 来 的 结 果 居 然 是 100!=0 哪 里 出 了 毛 病?Java 的 int 型 只 有 4 个 字 节 (32 位 ), 除 1 个 符 号 位 外 Java 能 表 示 的 最 大 整 数 只 能 是 2 31-1, 大 约 是 20 亿 而 13 的 阶 乘 就 已 经 超 过 62 亿 何 况 100? 所 以 int 型 是 远 远 不 够 的 那 么 用 long 型 行 不 行? 也 不 行 long 型 占 8 个 字 节 最 大 的 long 型 值 是 2 63-1, 约 900 亿 亿 这 个 数 虽 然 已 经 不 小 了, 但 是 对 于 100 的 阶 乘 来 说, 恐 怕 连 杯 水 车 薪 都 谈 不 上 因 为 900 亿 亿 不 过 是 19 个 十 进 制 位 而 100 的 阶 乘 有 多 少 十 进 制 位?158 个! 2.1.2. 使 用 BigInteger? 对 于 一 个 象 你 一 样 的 Java 高 手 来 说, 问 题 还 是 不 难 解 决 你 可 以 使 用 BigInteger 这 11

第 二 章 自 顶 向 下 的 程 序 设 计 个 类 来 代 替 int, 并 用 BigInteger 的 multiply() 函 数 代 替 int 型 的 乘 法 运 算 即 可 比 如 : 例 2.1-2 package com.training.topdown; import java.math.biginteger; public class FactorialWithBigInteger { public static void main(string args[]) { int n = 100; BigInteger result = BigInteger.ONE; // 等 价 于 result = 1 for(int i = 2; i <= n; i++) { result = result.multiply(new BigInteger(Integer.toString(i))); // 等 价 于 result *= i System.out.println(i + "!=" + result); 请 比 较 例 2.1-1 和 例 2.1-2, 请 特 别 注 意 例 2.1-2 中 的 两 个 注 释 虽 然 我 们 把 数 据 的 类 型 从 int 改 为 BigInteger, 但 是 程 序 的 逻 辑 并 没 有 发 生 丝 毫 改 变 所 以 我 们 进 行 软 件 设 计 时, 就 应 该 按 照 算 法 的 逻 辑 进 行 设 计, 至 于 用 什 么 进 行 实 现, 是 用 int 还 是 用 BigInteger 相 对 于 设 计 来 说 是 不 那 么 重 要 的 也 就 是 说 设 计 比 实 现 更 重 要 以 后 在 提 到 Java 的 接 口 和 类 时, 我 们 还 会 讲 到 这 一 点 显 然 例 2.1-2 的 确 能 够 漂 亮 地 给 出 100! 的 精 确 解 但 问 题 是 : 第 一, 不 见 得 每 一 个 人 都 象 你 一 样 那 么 熟 悉 Java 也 许 有 人 不 熟 悉 BigInteger; 第 二, 更 重 要 的 是,BigInteger 是 一 个 恒 类 (immutable class, 参 见 2.1.4), 即 类 的 域 (field) 或 者 说 状 态 永 久 保 持 不 变 所 以 BigInteger 对 象 本 身 是 不 会 保 留 multiply() 运 算 的 结 果 的 要 想 得 到 乘 法 的 结 果, 只 能 在 函 数 返 回 时 返 回 一 个 新 的 BigInteger 对 象 所 以 每 一 次 result 和 i 相 乘 ( 即 调 用 multiply()) 都 会 导 致 Java 虚 拟 机 JVM 在 内 存 中 构 造 一 个 新 的 BigInteger 对 象 由 于 要 表 示 大 整 数,BigInteger 对 象 是 很 耗 内 存 的 更 重 要 的 是, 新 的 BigInteger 对 象 将 立 刻 被 赋 值 给 变 量 result( 即 result *= i), 这 样 result 中 原 来 保 留 的 老 的 BigInteger 对 象 就 被 覆 盖 ( 将 被 自 动 垃 圾 回 收 ) 从 而 导 致 每 一 轮 循 环 都 要 进 行 一 次 内 存 请 求 和 回 收, 不 停 地 来 回 折 腾 当 然 回 收 行 为 的 真 正 发 生 时 间 可 以 推 迟 到 JVM 空 闲 的 时 候 由 Java 自 动 进 行, 但 是 第 一, 这 毕 竟 是 JVM 的 一 个 负 担 ; 第 二, 内 存 请 求 则 是 不 可 推 迟 的, 必 须 当 场 得 到 回 应 这 意 味 着 被 占 用 的 内 存 数 量 会 越 来 越 大 2.1.3. 自 己 定 义 状 态 可 变 的 大 整 数 如 果 想 解 决 这 个 问 题, 我 们 可 以 自 己 定 义 一 个 状 态 可 变 的 大 整 数 类 型 MutableBigInt 12

第 二 章 自 顶 向 下 的 程 序 设 计 其 中 含 有 三 个 主 要 方 法 : multiply(int num) 用 来 把 当 前 大 整 数 与 一 个 int 型 整 数 num 相 乘, 结 果 将 保 留 在 当 前 大 整 数 中 所 以 这 个 函 数 的 返 回 类 型 是 void 这 与 BigInteger 的 multiply() 函 数 不 同 tostring() 用 来 把 当 前 大 整 数 转 换 成 一 个 字 符 串 从 而 方 便 打 印 输 出 带 一 个 int 型 参 数 的 构 造 函 数 这 个 参 数 表 示 这 个 大 整 数 的 初 值 例 2.1-3 package com.training.topdown; import java.util.arraylist; import java.util.list; /*************** 可 改 变 状 态 的 大 整 数 ***************/ public class MutableBigInt { List<Integer> digits = new ArrayList<Integer>(); /*************** 构 造 函 数 ***************/ public MutableBigInt(int value) { digits.add(value); /*************** 乘 法 函 数 ***************/ public void multiply(int value) { int more = 0; for(int i = 0; i < digits.size(); i++) { int mul = digits.get(i) * value + more; digits.set(i, mul % 10); more = mul / 10; while(more > 0) { digits.add(more % 10); more /= 10; 13

第 二 章 自 顶 向 下 的 程 序 设 计 /*************** 转 换 为 字 符 串 以 方 便 打 印 ***************/ @Override public String tostring() { StringBuilder sb = new StringBuilder(); for(int i = digits.size() - 1; i >= 0; i--) sb.append(digits.get(i)); return sb.tostring(); 然 后 我 们 把 例 2.1-1 中 result 的 类 型 改 为 MutableBigInt, 并 用 multiply() 函 数 调 用 替 换 *= 运 算 即 可 结 果 如 下 : 例 2.1-4 package com.training.topdown; public class FactorialWithMutableBigInt { public static void main(string args[]) { int n = 100; MutableBigInt result = new MutableBigInt(1); for(int i = 2; i <= n; i++) result.multiply(i); // 乘 法 的 结 果 将 替 换 result 中 原 来 的 大 整 数 System.out.printf("%d!=%s\n", n, result); 上 述 方 法 之 所 以 能 够 成 功 的 关 键 在 于 我 们 深 刻 地 理 解 了 *= 运 算 的 含 义 即 把 当 前 整 数 与 另 一 个 整 数 相 乘, 乘 得 的 结 果 还 要 替 换 掉 原 来 被 乘 数 2.1.4. 关 于 恒 类 (immutable class) i 恒 类 的 一 个 特 点 是 : 这 样 的 类 的 属 性 的 值 是 不 会 发 生 变 化 的 一 个 推 论 是 : 恒 类 中 只 有 getter 函 数, 而 没 有 setter 函 数 换 句 话 说, 你 可 以 获 得 恒 类 对 象 的 属 性, 但 是 不 能 改 变 它 恒 类 的 属 性 的 初 值 一 般 是 由 构 造 函 数 设 置 的 比 如,Number 的 八 个 常 用 子 类 Integer Float Long Double Byte Short i 属 性, 有 的 教 材 称 为 实 例 变 量 或 者 成 员 变 量 本 书 无 差 别 地 使 用 这 三 个 概 念 14

第 二 章 自 顶 向 下 的 程 序 设 计 BigInteger BigDecimal 等 都 是 恒 类 String 和 Boolean 也 是 你 不 可 能 改 变 这 些 对 象 内 的 任 何 一 个 属 性 的 值 Number 的 另 外 两 个 子 类 AtomicInteger 和 AtomicLong 不 是 恒 类, 你 可 以 改 变 其 中 某 些 属 性 的 值 String 也 是 恒 类 这 使 得 两 个 字 符 串 的 拼 接 等 运 算 很 耗 时, 因 为 我 们 必 须 用 第 三 个 String 对 象 来 保 存 运 算 的 结 果 比 如 设 有 字 符 串 a = abc 和 b = def, 则 a + b 的 结 果 是 abcdef 但 是 这 个 结 果 既 不 能 保 存 在 对 象 a 中, 也 不 能 保 存 在 对 象 b 中 原 因 是 字 符 串 对 象 内 虽 然 的 确 存 在 着 一 个 字 符 数 组 类 型 的 属 性 保 存 了 字 符 串 中 所 有 字 符 的 值, 问 题 是 你 不 可 能 改 变 该 属 性 的 值 从 而 改 变 字 符 串 的 内 容 一 个 补 救 的 办 法 是 使 用 StringBuilder 后 者 提 供 了 一 堆 的 方 法 方 便 您 在 一 个 字 符 串 的 前 面 后 面 或 中 间 插 入 或 删 除 一 个 或 若 干 个 字 符 只 需 最 后 调 用 tostring() 方 法 就 能 把 一 个 StringBuilder 对 象 转 化 为 一 个 字 符 串 对 象 幸 运 的 是 : 现 在 绝 大 多 数 Java 编 译 器 都 自 动 地 把 字 符 串 先 转 化 为 StringBuilder 对 象, 然 后 再 执 行 拼 接 等 操 作 也 就 是 说 设 有 两 个 字 符 串 a 和 b, 则 c = a + b 被 编 译 成 : 例 2.1-5 StringBuilder sa = new StringBuilder(a); c = sa.append(b).tostring(); 既 然 恒 类 有 这 样 那 样 的 麻 烦 ( 不 能 改 变 内 部 状 态 必 须 寻 找 另 外 的 空 间 存 贮 运 算 结 果 等 等 ), 为 什 么 Java 还 提 供 恒 类 呢? 这 是 因 为 : 第 一, 我 们 可 以 保 证 恒 类 对 象 上 的 函 数 没 有 副 作 用 (Side-effect) 假 设 变 量 a 和 b 分 别 指 向 一 个 BigInteger 类 型 的 对 象, 则 只 要 a 和 b 不 变, 运 算 a.multiply(b) 的 结 果 也 永 远 不 变 这 个 性 质 对 于 一 些 与 数 学 有 关 的 对 象 很 重 要 与 之 相 反 System.currentTimeMillis() 函 数 就 是 有 副 作 用 的, 因 为 每 次 调 用 它 返 回 的 结 果 都 不 一 样 副 作 用 的 另 一 个 含 义 是, 这 样 的 函 数 必 然 会 改 变 某 个 成 员 变 量 或 类 变 量 的 值 第 二, 两 个 相 同 恒 类 类 型 的 对 象 可 以 共 享 数 据 结 构 而 不 会 产 生 问 题 例 如 字 符 串 的 拼 接 操 作 可 以 这 样 定 义 : 如 果 两 个 字 符 串 a 和 b 中 的 任 何 一 个 字 符 串 ( 假 设 a) 是 空 字 符 串, 则 a+b 的 结 果 就 是 b 而 不 必 另 行 构 造 一 个 与 b 相 同 的 新 字 符 串 注 意 : 这 样 的 优 化 并 非 仅 仅 对 String 有 效, 对 包 括 BigInteger 在 内 的 所 有 恒 类 类 型 来 说 共 享 数 据 结 构 都 不 会 有 问 题 比 如 BigInteger 的 multiply(b) 来 说, 如 果 b 的 值 等 于 1 则 直 接 返 回 this 即 可 有 人 可 能 怀 疑 说 : 两 个 对 象 共 享 数 据 结 构, 线 程 安 全 方 面 会 不 会 有 问 题? 我 非 常 赞 赏 怀 疑 精 神, 能 独 立 问 出 这 样 问 题 的 人 绝 不 会 是 一 只 菜 鸟 对 于 恒 类 对 象 来 说, 其 状 态 是 永 久 不 变 的, 所 以 即 使 有 多 个 线 程 同 时 读 取 同 一 个 对 象 的 状 态, 也 不 会 有 问 题 2.1.5. 通 过 这 个 例 子 你 学 到 了 什 么? 即 使 是 计 算 100 的 阶 乘, 算 法 的 结 构 与 计 算 5 的 阶 乘 的 算 法 相 比 也 仅 仅 是 把 int 换 成 了 一 个 我 们 自 己 另 外 定 义 的 类 MutableBigInt 而 已 所 以 首 先 请 把 复 杂 性 放 到 一 边, 尽 量 先 把 程 序 的 框 架 结 构 理 清 楚, 而 不 必 关 心 细 枝 末 节 在 考 虑 程 序 各 模 块 的 结 构 和 相 互 关 系 时, 应 该 首 先 考 虑 主 程 序, 然 后 再 考 虑 被 主 程 序 调 用 的 其 他 程 序 即 应 该 遵 循 自 顶 向 下 先 整 体 后 局 部 的 顺 序 在 没 有 MutableBigInt 时, 我 们 可 以 在 main() 函 数 中 用 int 代 替 它, 先 把 程 序 的 框 架 搭 好 然 后 再 考 虑 在 15

第 二 章 自 顶 向 下 的 程 序 设 计 MutableBigInt 中 要 用 到 哪 些 函 数, 以 及 每 个 函 数 的 参 数 和 返 回 类 型 至 于 每 个 函 数 内 部 实 现 的 细 节 应 该 留 到 编 写 MutableBigInt 类 时 再 考 虑 即 应 该 首 先 考 虑 函 数 的 签 名 (Signature, 也 称 为 函 数 头 ), 然 后 再 考 虑 函 数 的 实 现 2.2. 五 猴 分 桃 问 题 有 五 只 猴 子 上 山 采 桃 忙 活 了 一 天 以 后 他 们 采 了 一 大 堆 桃 子 正 当 他 们 决 定 分 桃 的 时 候 天 黑 了, 他 们 决 定 第 二 天 再 来 分 桃 子, 现 在 各 自 回 家 休 息 去 吧! 第 二 天 一 早, 第 一 个 猴 子 来 了 他 等 了 一 会 儿, 心 想 : 与 其 等 他 们 不 到, 不 如 我 现 在 就 分 桃 吧 还 能 省 点 时 间 呢! 于 是 他 把 桃 子 分 成 了 相 等 的 五 堆 最 后 发 现 还 多 出 一 只 桃 子 他 想 : 这 多 出 的 桃 子 当 然 应 该 属 于 劳 苦 功 高 的 我 喽! 于 是 他 吃 了 那 只 桃 子, 然 后 抱 起 属 于 自 己 的 那 一 堆 桃 子, 走 了 过 了 一 会 第 二 只 猴 子 来 了 他 并 不 知 道 第 一 只 猴 子 来 过 他 等 了 一 会 不 见 有 其 他 猴 来 于 是 也 把 桃 子 分 成 了 五 堆 也 发 现 多 出 一 只 桃 子 于 是 他 老 实 不 客 气 地 也 吃 了 那 只 桃 子, 然 后 抱 起 一 堆 桃 子, 走 了 之 后 第 三 第 四 乃 至 第 五 只 猴 子 也 干 了 同 样 的 事 情 : 把 剩 下 的 桃 子 分 成 相 等 的 五 堆, 发 现 多 了 一 只 桃 子, 吃 了 它, 抱 起 一 堆 桃 子, 然 后 拜 拜 问 题 是 : 请 编 写 程 序 计 算 最 初 有 几 个 桃 子? 2.2.1. 一 个 容 易 的 解 法 一 个 最 容 易 想 到 的 解 法 是 把 桃 子 的 总 数 peaches 从 1,2,3,, 开 始 每 次 加 一 的 循 环 直 到 遇 到 第 一 个 能 被 猴 子 分 光 的 数 按 照 自 顶 向 下 的 考 虑 顺 序, 这 个 程 序 的 主 函 数 应 该 是 这 样 的 : 例 2.2-1 package com.training.topdown; public class MonkeyAndPeach1 { public static void main(string args[]) { int peaches = 1; while(true) { // 桃 子 的 总 数 if(isdistributable(peaches)) { // 如 果 这 么 多 桃 子 可 以 被 5 只 猴 子 分 掉 System.out.println("The number of peaches is " + peaches); break; peaches++; // 否 则 桃 子 的 数 目 加 1 16

第 二 章 自 顶 向 下 的 程 序 设 计 请 注 意 例 2.2-1 中 黑 体 标 示 的 isdistributable() 函 数 这 个 函 数 实 际 上 我 们 还 没 有 编 写 但 这 并 不 妨 碍 我 们 在 主 函 数 中 引 用 它 自 顶 向 下 的 程 序 设 计 方 法 就 是 要 我 们 关 注 被 调 用 函 数 的 功 能, 而 不 去 关 心 它 的 实 现 这 里 isdistributable(peaches) 函 数 的 含 义 很 清 晰, 就 是 判 断 peaches 个 桃 子 能 否 被 猴 子 们 分 掉 ( 可 见 给 函 数 取 个 好 名 字 是 多 么 重 要 ) 如 果 能, 就 返 回 true, 否 则 返 回 false 这 样 main() 函 数 的 算 法 流 程 是 不 是 很 清 晰 易 懂? 如 此 清 晰 简 洁 的 流 程 也 为 我 们 以 后 排 错 或 增 加 新 的 功 能 提 供 了 便 利 但 是 很 多 人 ( 包 括 那 些 很 会 编 程 序 的 熟 手 ) 却 习 惯 于 先 编 写 小 的 次 要 的 被 调 用 的 函 数, 然 后 再 去 编 写 大 的 主 要 的 调 用 函 数 的 函 数 这 种 习 惯 就 好 比 做 房 子 先 垒 砖 头 后 搭 框 架 一 样 也 许 这 并 不 妨 碍 你 做 出 小 磨 房 小 牛 棚, 但 想 做 出 摩 天 大 楼 高 速 公 路 长 江 大 桥 那 是 绝 对 不 可 能 的 一 定 要 先 有 规 划 和 框 架, 然 后 再 关 注 细 节 因 为 我 们 几 乎 可 以 百 分 之 一 百 地 肯 定 主 函 数 没 有 问 题, 所 以 我 们 现 在 就 可 以 把 精 力 集 中 到 isdistributable() 函 数 上 去, 专 门 研 究 n 个 桃 子 能 否 被 五 个 猴 子 分 掉 我 们 看 看 每 个 猴 子 是 怎 么 办 事 的? 无 非 就 是 吃 掉 了 一 个 桃 子, 然 后 把 剩 下 的 桃 子 分 成 了 五 等 份 还 拿 走 了 其 中 一 等 份 问 题 的 关 键 就 在 于 桃 子 可 能 无 法 五 等 分, 程 序 应 该 就 在 这 里 返 回 false 所 以 isdistributable(peaches) 函 数 可 以 这 样 编 写 : 例 2.2-2 public static boolean isdistributable(int peaches) { for(int i = 0; i < 5; i++) { peaches--; // 循 环 五 次 // 吃 掉 一 个 桃 子 if(peaches % 5!= 0) // 桃 子 能 不 能 5 等 分? return false; peaches -= peaches / 5; // 拿 走 五 分 之 一 return true; 我 们 把 isdistribute 函 数 加 入 到 例 2.2-1 的 类 MonkeyAndPeach1 中 去, 然 后 运 行 这 个 类 就 可 以 得 到 正 确 结 果 答 案 是 3121 2.2.2. 一 点 改 进 考 虑 任 意 个 猴 子 如 果 是 六 个 七 个 八 个 甚 至 任 意 多 个 猴 子 分 桃 呢? 由 于 上 述 自 顶 向 下 的 程 序 设 计 思 路 非 常 清 晰, 所 以 我 们 只 需 要 在 isdistributable() 函 数 中 增 加 一 个 参 数 monkeys 用 来 表 明 有 多 少 个 猴 子 即 可 则 代 码 可 以 很 容 易 地 改 为 : 例 2.2-3 17

第 二 章 自 顶 向 下 的 程 序 设 计 public static boolean isdistributable(int peaches, int monkeys) { for(int i = 0; i < monkeys; i++) { peaches--; if(peaches % monkeys!= 0) return false; peaches -= peaches / monkeys; return true; 这 里 我 们 可 以 看 到 良 好 的 程 序 结 构 是 如 何 有 助 于 我 们 增 加 功 能 的 2.2.3. 第 二 点 改 进 加 大 步 长 由 于 第 一 个 猴 子 是 吃 了 一 个 桃 子, 剩 下 的 桃 子 五 等 分 的, 所 以 桃 子 的 个 数 必 定 是 5K+1, 其 中 K=1,2,3, 所 以 主 函 数 中 循 环 变 量 的 步 长 可 以 改 为 5: 例 2.2-4 public class MonkeyAndPeach2 { public static void main(string args[]) { int peaches = 1; while (true) { if (isdistributable(peaches, 5)) { System.out.println( The number of peaches is + peaches); break; peaches += 5; // 步 长 从 1 改 为 5, 运 行 速 度 提 高 到 约 5 倍 这 等 于 程 序 的 速 度 提 高 了 约 5 倍! 其 中 的 while 循 环 要 执 行 625 次, 而 上 个 算 法 要 执 行 3121 次 现 在 你 是 不 是 觉 得 深 入 地 思 考 一 个 程 序 是 不 是 也 有 那 么 一 点 好 玩 了? 18

第 二 章 自 顶 向 下 的 程 序 设 计 2.2.4. 逆 向 思 维 我 们 为 什 么 一 定 要 从 第 一 个 猴 子 开 始 考 虑 呢? 我 们 也 可 以 从 最 后 一 个 猴 子 开 始 考 虑 假 设 最 后 一 个 猴 子 走 了 之 后 剩 下 的 四 堆 桃 子 里 每 一 堆 有 n 个 桃 子, 则 他 来 之 前 桃 子 就 有 5n+1 个 我 们 然 后 计 算 第 四 第 三 第 二 第 一 个 猴 子 来 之 前 的 桃 子 总 数 即 可 我 们 把 这 种 计 算 用 getpeaches(currentpeaches) 函 数 表 示 其 中 currentpeaches 表 示 最 后 一 个 猴 子 分 桃 之 前 的 桃 子 总 数 返 回 结 果 是 第 一 个 猴 子 分 桃 之 前 的 桃 子 总 数 如 果 是 0, 则 意 味 着 根 据 当 前 currentpeaches 无 法 计 算, 否 则 大 于 0 就 是 我 们 想 要 知 道 的 最 初 的 桃 子 数 代 码 如 下 : 例 2.2-5 package com.training.topdown; public class MonkeyAndPeach3 { public static void main(string args[]) { int pilepeaches = 1; while (true) { int peaches = getpeaches(5 * pilepeaches + 1); if(peaches > 0) { System.out.println("The number of peaches is " + peaches); break; pilepeaches++; public static int getpeaches(int currentpeaches) { for(int i = 0; i < 4; i++) { if(currentpeaches % 4 == 0) currentpeaches = currentpeaches / 4 * 5 + 1; else return 0; return currentpeaches; 19

第 二 章 自 顶 向 下 的 程 序 设 计 其 中 的 while 循 环 仅 需 执 行 255 次 即 可 2.2.5. 数 学 解 这 个 有 趣 的 问 题 其 实 有 一 个 很 简 单 的 数 学 解 你 只 需 要 借 给 这 群 猴 子 4 个 桃 子, 从 而 保 证 了 第 一 个 猴 子 能 够 五 等 分 所 有 的 桃 子 第 一 个 猴 子 抱 走 一 堆 桃 子 后, 你 发 现 他 并 没 有 比 以 前 多 拿 桃 子, 你 借 给 他 们 的 4 个 桃 子 又 传 给 了 第 二 个 猴 子,, 以 此 类 推, 每 个 猴 子 都 能 五 等 分 所 有 的 桃 子 最 后 你 再 拿 走 借 给 他 们 的 4 个 桃 子 所 以 你 出 借 4 个 桃 子 之 后, 这 堆 桃 子 能 够 5 次 被 5 整 除, 所 以 答 案 就 是 5 5 K 4 个 桃 子, 其 中 K=1,2,3, 最 少 应 该 有 5 5 4 即 3121 个 这 正 是 我 们 要 的 答 案 当 然 我 们 的 目 的 并 不 是 真 的 要 解 决 五 猴 分 桃 问 题, 而 是 掌 握 自 顶 向 下 的 程 序 设 计 方 法 20

第 三 章 递 归 程 序 设 计 第 三 章 递 归 程 序 设 计 递 归 函 数 就 是 指 函 数 自 己 调 用 自 己 如 果 一 个 函 数 直 接 调 用 了 自 己 那 这 种 递 归 就 是 直 接 递 归 如 果 通 过 其 他 函 数 间 接 地 调 用 了 自 己 那 就 是 间 接 递 归 有 趣 的 是, 不 管 是 直 接 递 归 间 接 递 归 还 是 函 数 之 间 的 普 通 调 用, 计 算 机 内 部 都 是 统 一 处 理 的, 甚 至 根 本 就 不 区 分 某 个 函 数 调 用 是 递 归 的 还 是 非 递 归 的 这 个 问 题 与 函 数 调 用 和 参 数 传 递 机 制 有 关, 其 中 有 很 多 有 趣 的 现 象 和 结 论, 我 们 将 在 后 面 章 节 提 到 3.1. 递 归 和 数 学 归 纳 法 3.1.1. 第 一 个 例 子 Hanoi 塔 递 归 程 序 的 一 个 著 名 例 子 就 是 Hanoi 塔 ( 中 文 翻 译 为 河 内 塔 或 汉 诺 塔 ) 问 题 这 里 先 简 单 介 绍 一 下 这 个 问 题 有 三 根 杆 子 A B C A 杆 上 套 有 若 干 中 间 有 孔 的 碟 子 碟 子 的 直 径 大 小 不 一, 并 且 小 的 碟 子 垒 在 大 的 碟 子 上 呈 金 字 塔 状 ( 参 见 图 3.1-1) 规 则 允 许 你 从 任 何 一 个 杆 子 上 取 最 上 面 一 个 碟 子 然 后 移 到 另 外 任 何 一 个 杆 子 上, 条 件 是 这 个 碟 子 不 能 比 它 下 面 的 那 张 碟 子 大 游 戏 的 目 的 是 把 所 有 碟 子 从 A 杆 全 部 移 到 C 杆 上 有 很 多 高 级 程 序 设 计 语 言 的 教 材 都 把 Hanoi 塔 作 为 第 一 个 递 归 程 序 的 例 子 介 绍 给 大 家 比 如 一 个 C 语 言 的 例 子 是 : 例 3.1-1 void move(char from, char to, int dish) { printf( move %d from %c to %c\n, dish, from, to); void hanoi(char a, char b, char c, int n) { if(n == 1) else { move(a, c, 1); hanoi(a, c, b, n-1); move(a, c, n); hanoi(b, a, c, n-1); 图 3.1-1 Hanoi 塔 问 题 21

第 三 章 递 归 程 序 设 计 遗 憾 的 是, 在 我 所 认 识 的 几 千 个 同 事 同 学 朋 友 和 学 生 当 中, 几 乎 没 有 一 个 人 在 第 一 眼 看 到 这 个 程 序 时 就 能 够 独 立 地 理 解 它 当 然 现 在 你 可 能 已 经 觉 得 这 个 程 序 实 在 是 太 简 单 了, 但 是 你 真 地 了 解 递 归 程 序 背 后 的 数 学 原 理 吗? 3.1.2. 递 归 背 后 的 数 学 原 理 还 记 得 你 初 中 高 中 时 代 怎 么 使 用 数 学 归 纳 法 的 吗? 比 如 你 用 数 学 归 纳 法 如 何 证 明 前 n 个 奇 数 的 和 等 于 n 2? 即 : 1+3+5+ +(2n-1) = n 2 第 一 步, 当 n=1 时,1=1 2 成 立 第 二 步 归 纳 假 设, 设 n=k 时, 等 式 成 立 即 1+3+5+ +(2k-1) = k 2 最 后 一 步 推 导, 当 n=k+1 时, 等 式 的 左 边 是 1+3+ +(2k-1)+(2k-1+2) = k 2 +2k+1 = (k+1) 2 与 右 边 相 等 所 以 原 等 式 对 于 任 意 自 然 数 n 成 立 也 就 是 说, 数 学 归 纳 法 要 走 三 步 : 第 一 步, 边 界 条 件 上 的 证 明, 即 证 明 原 问 题 在 参 数 边 界 上 ( 如 上 例 中 的 n=1) 成 立 这 一 步 往 往 不 需 要 复 杂 的 论 证, 一 般 可 以 直 接 得 出 结 论 第 二 步 是 归 纳 假 设 即 假 设 当 参 数 更 接 近 边 界 时 ( 比 如 上 例 中 k 比 k+1 更 接 近 1) 结 论 成 立 第 三 步 推 导, 根 据 第 二 步 的 假 设 推 导 出 结 论 也 成 立 奇 妙 的 是, 递 归 程 序 设 计 的 步 骤 与 之 一 一 对 应 也 分 为 三 步 : 1) 找 到 参 数 的 边 界 条 件, 计 算 边 界 条 件 成 立 时 的 输 出 这 一 步 往 往 不 需 要 复 杂 的 计 算, 一 般 可 以 直 接 输 出 结 果 2) 递 归 假 设 假 设 函 数 在 参 数 更 接 近 边 界 时 能 够 得 到 期 望 的 输 出 程 序 设 计 难 道 可 以 假 设? 是 的, 可 以 假 设 这 就 是 计 算 机 科 学 的 魅 力 3) 推 导 根 据 第 二 步 的 假 设 计 算 函 数 的 输 出 所 以 只 要 确 定 好 函 数 的 参 数, 然 后 按 照 这 三 步 编 程 就 能 写 出 比 较 漂 亮 又 好 理 解 的 递 归 程 序 3.1.3. Hanoi 塔 问 题 的 递 归 解 考 虑 Hanoi 塔 问 题 第 一 步, 请 问 在 什 么 情 况 下 Hanoi 塔 问 题 最 容 易 解 决? 那 当 然 是 只 有 一 个 碟 子 的 情 况 这 时 只 要 直 接 把 那 张 碟 子 从 A 移 到 C 杆 上 即 可 第 二 步 递 归 假 设 一 般 地, 递 归 假 设 时, 参 数 或 参 数 组 合 应 该 比 原 参 数 更 接 近 于 边 界 在 Hanoi 塔 问 题 中, 碟 子 的 个 数 为 1 时 是 边 界 条 件, 所 以 可 以 假 设 碟 子 的 个 数 是 n-1 时 我 们 可 以 任 意 地 把 这 n-1 张 碟 子 从 一 个 杆 移 到 另 一 个 杆 n 是 原 来 碟 子 的 个 数 你 可 能 会 问, 我 怎 么 把 这 n-1 张 碟 子 从 一 个 杆 移 到 另 一 个 杆 呢? 不 要 问 我 为 什 么, 因 为 这 是 假 设 的 我 完 全 可 以 假 设 太 阳 是 黑 的, 地 球 是 方 的 说 到 底, 那 只 是 假 设 而 已! 第 三 步, 推 导 根 据 第 二 步 的 假 设, 我 们 可 以 把 n-1 张 碟 子 从 任 意 一 个 杆 移 到 另 一 个 杆 所 以 我 们 可 以 把 A 杆 上 最 下 面 的 那 张 最 大 的 碟 子 排 除 在 外, 先 把 它 上 面 n-1 张 碟 子 22

第 三 章 递 归 程 序 设 计 移 到 B 杆 上 参 见 图 3.1-1 和 图 3.1-2 图 3.1-2 n-1 张 碟 子 先 从 A 杆 移 到 B 杆 接 下 来 把 最 大 的 那 张 碟 子 从 A 杆 直 接 移 到 C 杆 参 见 图 3.1-3 图 3.1-3 最 大 的 碟 子 从 A 杆 直 接 移 到 C 杆 最 后 再 把 B 杆 上 的 n-1 个 碟 子 全 部 移 到 C 杆 上 参 见 图 3.1-4 图 3.1-4 n-1 张 碟 子 再 从 B 杆 移 到 C 杆 现 在 我 们 再 回 过 头 来 分 析 C 语 言 写 的 hanoi 塔 程 序, 就 会 有 新 的 认 识 : 例 3.1-2 void hanoi(char a, char b, char c, int n) { if(n == 1) // 递 归 边 界, 一 张 碟 子 最 好 移 动, 直 接 从 a 移 到 c 即 可 else { move(a, c, 1); hanoi(a, c, b, n-1); // 递 归 假 设,n-1 张 碟 子 可 以 从 a 移 到 b,c 是 过 渡 move(a, c, n); // 把 编 号 为 n 的 碟 子 从 a 直 接 移 到 c 23

第 三 章 递 归 程 序 设 计 hanoi(b, a, c, n-1); // 递 归 假 设,n-1 张 碟 子 再 从 b 移 到 c,a 是 过 渡 一 般 地, 对 边 界 条 件 的 判 断 应 该 放 在 递 归 假 设 之 前 进 行 就 像 数 学 归 纳 法 必 须 首 先 保 证 要 证 明 的 定 理 / 公 式 在 边 界 条 件 上 成 立, 然 后 我 们 才 能 进 行 归 纳 假 设 所 以 边 界 条 件 的 判 断 和 处 理 也 应 该 在 递 归 假 设 之 前 进 行 这 是 递 归 能 够 正 常 终 止 的 前 提 在 Hanoi 塔 例 子 中, 对 边 界 条 件 的 判 断 就 是 在 函 数 的 开 始 处 首 先 执 行 的 这 种 现 象 在 递 归 程 序 中 非 常 普 遍 3.2. 一 些 有 趣 的 递 归 程 序 3.2.1. 字 符 串 通 配 符 匹 配 假 设 * 可 以 匹 配 0 个 或 0 个 以 上 的 字 符,? 可 以 匹 配 且 仅 匹 配 一 个 字 符 请 写 一 个 递 归 函 数 match(pattern, str) 判 断 字 符 串 str 是 否 与 模 式 pattern 匹 配 我 们 按 照 递 归 程 序 三 部 曲 来 考 虑 这 个 函 数 第 一, 边 界 条 件 在 什 么 情 况 下 我 们 可 以 直 接 判 断 str 是 否 与 pattern 匹 配? 显 然, 如 果 str 是 个 空 字 符 串 的 话, 那 pattern 也 必 须 是 个 空 字 符 串 两 者 才 能 匹 配 反 过 来, 如 果 pattern 是 个 空 字 符 串 的 话, 那 它 也 只 能 和 空 字 符 串 匹 配 所 以 这 个 边 界 条 件 是 str.isempty() 或 pattern.isempty() 第 二, 递 归 假 设 假 设 在 pattern 或 者 str 比 原 来 少 一 个 字 符 情 况 下 match 函 数 总 能 正 确 地 判 定 二 者 是 否 匹 配 第 三 步, 推 导 我 们 可 以 考 虑 pattern 的 第 一 个 字 符, 根 据 它 是 否 是 通 配 符 决 定 是 否 把 str 的 第 一 个 字 符 删 除 由 于 pattern 和 str 两 者 中 至 少 有 一 个 其 头 字 符 被 删 除, 根 据 第 二 步 递 归 假 设,match 函 数 可 以 判 定 剩 下 的 字 符 相 互 之 间 是 否 匹 配 ( 因 为 这 样 更 接 近 于 边 界 ) 这 样 我 们 就 能 判 定 原 pattern 和 str 之 间 是 否 匹 配 代 码 如 下 : 例 3.2-1 package com.training.recursion; public class StringMatch { public static boolean match(string pattern, String str) { if(pattern.isempty()) // 边 界 条 件 之 一 return str.isempty(); if(str.isempty()) // 边 界 条 件 之 二 return pattern.isempty(); switch(pattern.charat(0)) { // 根 据 头 字 符 的 不 同 分 别 处 理 24

第 三 章 递 归 程 序 设 计 case '?': return match(pattern.substring(1), str.substring(1)); case '*': return match(pattern.substring(1), str) match(pattern, str.substring(1)); default: return pattern.charat(0) == str.charat(0) && match(pattern.substring(1), str.substring(1)); 一 个 众 所 周 知 的 事 实 是 : 字 符 串 处 理 既 耗 时 间 又 耗 内 存 我 们 可 以 在 StringMatch 中 增 加 一 个 重 载 的 match 函 数 : 例 3.2-2 private static boolean match(string pattern, int patternfrom, String str, int strfrom) { 其 中 patternfrom 用 来 指 明 模 式 串 从 pattern 的 第 几 个 字 符 开 始 ;strfrom 用 来 指 明 字 符 串 从 str 的 第 几 个 字 符 开 始 把 这 个 函 数 用 类 似 于 例 3.2-1 那 样 的 方 法 做 成 递 归 函 数 然 后 令 match(string pattern, String str) 函 数 直 接 调 用 match(pattern, 0, str, 0) 即 可 这 样 运 算 时 就 不 需 要 调 用 String.substring() 函 数 完 整 代 码 如 下 : 例 3.2-3 package com.training.recursion; public class StringMatch2 { public static boolean match(string pattern, String str) { return match(pattern, 0, str, 0); private static boolean match(string pattern, int patternfrom, String str, int strfrom) { if (patternfrom >= pattern.length()) return strfrom >= str.length(); if (strfrom >= str.length()) return patternfrom >= pattern.length(); 25

第 三 章 递 归 程 序 设 计 switch (pattern.charat(patternfrom)) { case '?': return match(pattern, patternfrom + 1, str, strfrom + 1); case '*': return match(pattern, patternfrom + 1, str, strfrom) match(pattern, patternfrom, str, strfrom + 1); default: return pattern.charat(patternfrom) == str.charat(strfrom) && match(pattern, patternfrom + 1, str, strfrom + 1); 3.2.2. 兔 子 一 对 刚 出 生 的 小 白 兔 两 个 月 后 就 成 熟 并 生 下 一 对 兔 子, 之 后 每 个 月 都 能 生 一 对 兔 子 现 在 给 你 一 对 刚 出 生 的 小 白 兔, 问 n 个 月 后 有 几 对 兔 子? 显 然, 递 归 边 界 是 n=0 或 1 递 归 假 设 也 很 好 做 下 面 考 虑 推 导 当 n>2 时, 每 个 月 的 兔 子 总 数 由 上 个 月 的 兔 子 总 数 和 本 月 新 出 生 的 兔 子 组 成 而 本 月 新 出 生 的 兔 子 数 与 两 个 月 前 的 兔 子 总 数 相 同, 因 为 那 时 即 使 是 刚 出 生 的 兔 子 现 在 也 成 熟 了 所 以, 本 题 的 解 就 是 著 名 的 斐 波 纳 奇 (Fibnacci) 数 列 : 例 3.2-4 package com.training.recursion; public class Rabit { public static int getrabits(int n) { switch(n) { case 0: case 1: return 1; default: return getrabits(n-1) + getrabits(n-2); 26

第 三 章 递 归 程 序 设 计 上 述 递 归 程 序 中 存 在 重 复 计 算 的 问 题 例 如 为 了 计 算 getrabits(5) 就 要 计 算 getrabit(4) 和 getrabit(3), 而 为 了 计 算 getrabits(4) 就 要 计 算 getrabit(3) 和 getrabit(2), 其 中 getrabit(3) 就 被 重 复 计 算 了 这 就 导 致 运 算 速 度 的 下 降 解 决 的 办 法 之 一 就 是 在 计 算 过 程 中 保 留 中 间 计 算 结 果 关 于 这 个 问 题 我 们 将 在 7.1 节 解 决 3.2.3. 组 合 和 排 列 3.2.3.1. 组 合 从 5 个 不 同 的 小 球 里 任 取 3 个 的 组 合 有 多 少? 这 是 一 个 典 型 的 组 合 问 题, 答 案 是 C(5, 2) 即 10 种 但 是 我 们 现 在 并 不 是 要 用 数 学 方 法 求 组 合 的 解, 而 是 要 求 编 写 一 个 递 归 函 数 combination(m, n) 以 求 得 从 m 个 小 球 里 任 取 n 个 的 组 合 数, 其 中 n m 始 终 成 立 我 们 根 据 递 归 程 序 三 部 曲 来 考 虑 这 个 函 数 第 一, 递 归 边 界 在 什 么 情 况 下, 组 合 数 可 以 直 接 求 得, 而 不 必 进 行 递 归? 显 然 当 n=0 时, 不 论 m 等 于 多 少, 组 合 数 都 是 1 把 n=0 作 为 递 归 边 界 已 经 足 够 了 但 是, 如 果 还 有 其 他 边 界 则 也 应 该 考 虑 在 内 更 多 的 边 界 将 有 助 于 程 序 在 递 归 过 程 中 更 快 地 接 近 边 界 从 而 有 助 于 程 序 速 度 的 提 高 和 减 少 占 用 内 存 我 们 考 虑 n=1, 这 也 是 一 种 简 单 情 况 此 时 组 合 数 等 于 m, 也 能 直 接 得 到 答 案 而 不 用 递 归 另 外 如 果 n=m, 则 意 味 着 把 所 有 的 小 球 都 选 中, 这 样 的 组 合 数 只 有 1 个 第 二, 递 归 假 设 我 们 假 设 只 要 把 m 和 n 做 更 接 近 于 边 界 的 变 化, 则 组 合 数 总 能 求 得 出 来 第 三, 递 归 推 导 我 们 把 最 后 一 个 小 球 Z 拎 出 来 单 独 考 虑 如 果 最 后 取 出 来 的 n 个 小 球 里 不 包 含 Z, 这 种 情 况 相 当 于 从 Z 之 前 的 m-1 个 小 球 里 取 n 个, 根 据 递 归 假 设, 共 有 combination(m-1, n) 种 组 合 反 之, 如 果 取 出 来 的 n 个 小 球 里 包 含 Z, 这 种 情 况 相 当 于 从 Z 之 前 的 m-1 个 小 球 里 取 n-1 个 然 后 和 Z 一 起 组 成 n 个 小 球 的 组 合, 根 据 递 归 假 设, 共 有 combination(m-1, n-1) 种 组 合 所 以 递 归 程 序 形 如 ( 为 了 可 读 性, 我 用 total 代 替 m, 用 select 代 替 n): 例 3.2-5 package com.training.recursion; public class Combination { public static int combination(int total, int select) { switch(select) { case 0: case 1: default: return 1; return total; 27

第 三 章 递 归 程 序 设 计 if(select == total) return 1; return combination(total-1, select-1) + combination(total-1, select); 这 个 例 子 告 诉 我 们, 即 使 没 有 学 过 数 学, 我 们 也 知 道 C(m, n) = C(m-1, n-1) + C(m-1, n) 参 见 例 3.2-5 的 最 后 一 个 return 语 句 让 我 们 象 中 国 古 代 科 学 家 杨 辉 那 样 把 所 有 组 合 数 按 m 的 不 同 分 行 排 列, 就 会 得 到 如 图 3.2-1 那 样 的 杨 辉 三 角 根 据 上 述 公 式, 我 们 知 道 每 个 组 合 数 都 等 于 它 肩 膀 上 的 两 个 数 的 和 计 算 机 的 递 归 理 论 和 数 学 得 到 同 一 个 结 论, 这 是 证 明 科 学 理 论 殊 路 同 归 的 又 一 个 例 子 3.2.3.2. 排 列 排 列 和 上 节 中 的 组 合 非 常 相 似, 不 同 的 是 1)n=m 不 能 作 为 边 界 ;2) 第 三 步 推 导 略 有 不 同 : 如 果 最 后 一 个 小 球 Z 被 选 中, 那 它 与 其 他 n-1 个 被 选 中 的 小 球 之 间 有 n 种 不 同 的 排 列 即 Z 可 以 排 在 第 1 个 小 球 之 前 第 2 个 小 球 之 前 第 n-1 个 小 球 之 前 或 者 第 n-1 个 小 球 之 后, 共 n 种 情 况 所 以 求 排 列 数 的 程 序 是 ( 为 了 可 读 性, 用 total 代 替 m, 用 select 代 替 n): 例 3.2-6 package com.training.recursion; public class Permutation { public static int permutation(int total, int select) { switch (select) { case 0: return 1; case 1: return total; default: int result = select * permutation(total - 1, select - 1); if (total > select) { result += permutation(total - 1, select); m=0 1 m=1 1 1 m=2 1 2 1 m=3 1 3 3 1 m=4 1 4 6 4 1 图 3.2-1 杨 辉 三 角 28

第 三 章 递 归 程 序 设 计 return result; 3.2.4. 人 字 形 的 铁 路 如 图 3.2-2, 有 一 段 人 字 形 的 铁 路, 火 车 只 能 从 右 边 铁 路 线 驶 进, 并 且 只 能 从 左 边 铁 路 线 驶 出 驶 进 来 的 火 车 可 以 停 在 人 字 形 的 上 半 部 分 ( 直 线 ) 铁 路 线 上, 从 而 让 后 进 来 的 火 车 先 从 左 边 铁 路 线 驶 出 当 然 它 也 可 以 进 来 之 后 不 作 停 留 直 接 驶 出 假 设 右 边 有 n 列 火 车, 问 从 左 边 驶 出 的 n 列 火 车 的 排 列 有 多 少 种? 图 3.2-2 人 字 形 铁 路 问 题 : 火 车 只 能 右 边 进 左 边 出 比 如 假 设 右 边 有 3 列 火 车 A B C, 则 从 左 边 驶 出 的 火 车 的 排 列 只 有 5 种 :ABC ACB BAC BCA 和 CBA 3 列 火 车 的 所 有 6 种 排 列 里 唯 有 CAB 是 不 可 能 的 这 一 题 的 递 归 边 界 和 假 设 都 是 比 较 容 易 的 难 的 是 推 导 与 3.2.2 节 的 排 列 组 合 一 样, 我 们 可 以 把 一 列 火 车 拎 出 来 单 独 考 虑 只 不 过, 在 排 列 组 合 那 一 题 中 我 们 考 虑 的 是 最 后 一 个 小 球, 而 在 这 一 题 中, 我 们 考 虑 的 是 第 一 列 火 车 假 设 第 一 列 火 车 第 i 个 驶 出 (i=1, 2,,n), 则 排 在 它 之 前 驶 出 的 火 车 有 i-1 辆 这 一 题 的 巧 妙 之 处 就 在 于 这 i-1 辆 排 在 它 之 前 驶 出 的 火 车 恰 好 在 驶 入 时 是 排 在 第 一 列 火 车 之 后 的 i-1 列 火 车 也 就 是 说, 第 一 列 火 车 要 想 第 i 个 驶 出, 则 紧 随 其 后 的 i-1 列 火 车 必 须 先 驶 出, 剩 下 的 n-i 列 火 车 必 须 在 它 之 后 驶 出 见 图 3.2-3 29

第 三 章 递 归 程 序 设 计 为 什 么? 因 为 第 一 列 火 车 要 想 第 i 个 驶 出, 则 它 进 入 人 字 形 铁 路 后 就 必 须 停 在 直 线 铁 路 上 直 到 有 i-1 列 火 车 驶 出 问 题 是 第 一 列 之 后 的 火 车 要 么 不 驶 入, 要 么 必 然 比 第 一 列 火 车 先 驶 出, 后 进 先 出 嘛! 所 以 最 后 驶 入 的 n-i 列 火 车 必 然 在 第 一 列 火 车 之 后 驶 出 人 字 形 铁 路, 否 则 就 会 导 致 第 一 列 火 车 之 前 会 有 多 于 i-1 列 的 火 车 驶 出 根 据 递 归 假 设, 先 驶 出 的 i-1 列 火 车 有 多 少 种 排 列 以 及 后 驶 出 的 n-i 列 火 车 有 多 少 种 排 列 我 们 都 是 能 计 算 出 来 的 不 要 问 我 为 什 么, 因 为 这 是 递 归 假 设 所 以 递 归 程 序 就 是 : 例 3.2-7 package com.training.recursion; public class Train { public static int get(int trains) { 图 3.2-3 人 字 形 铁 路 问 题 : 第 一 列 火 车 要 想 第 i 个 驶 出, 则 它 随 后 的 i-1 列 火 车 必 须 先 驶 出 if (trains < 2) return 1; int result = 0; for (int i = 1; i <= trains; i++) result += get(i-1) * get(trains-i); return result; 是 不 是 不 可 思 议 的 简 单? 这 就 是 递 归 的 魅 力 30

第 三 章 递 归 程 序 设 计 3.2.5. 五 升 的 杯 子 和 三 升 的 杯 子 倒 出 四 升 水 给 你 一 大 一 小 两 只 没 有 刻 度 的 杯 子, 大 杯 子 的 容 量 是 5 升, 小 杯 子 的 容 量 是 3 升 你 能 用 这 两 只 杯 子 倒 出 4 升 水 来 吗? 这 一 题 有 两 个 参 数 water1 和 water2 water1 表 示 大 杯 子 中 目 前 的 水 量,water2 表 示 小 杯 子 中 目 前 的 水 量 water1 和 water2 的 初 值 都 是 0, 表 示 杯 子 中 没 有 水 我 们 首 先 考 虑 递 归 边 界 :water1 和 water2 满 足 什 么 条 件 时 我 们 可 以 直 接 给 出 答 案 而 不 用 进 行 递 归? 显 然,water1 和 water2 只 要 有 一 个 等 于 目 标 水 量 即 4, 那 么 我 们 就 有 了 这 么 多 水, 不 用 再 倒 来 到 去 了 递 归 假 设 是 只 要 water1 或 water2 比 原 值 更 接 近 目 标 水 量, 那 么 我 们 就 能 判 断 它 能 否 倒 出 那 么 多 水 递 归 推 导 要 分 为 八 种 情 况 考 虑 : 如 果 一 个 杯 子 不 满, 那 么 我 们 可 以 给 它 装 满 水 因 为 有 两 只 杯 子, 所 以 这 有 两 种 情 况 ; 如 果 一 个 杯 子 里 有 水, 那 么 我 们 可 以 把 它 倒 空, 这 也 有 两 种 情 况 ; 把 一 个 杯 子 里 的 水 全 部 倒 到 另 一 个 杯 子 里 去, 前 提 是 两 个 杯 子 中 的 水 的 总 量 小 于 等 于 后 者 的 容 量 从 而 不 会 让 后 者 漫 出 来 这 也 有 两 种 情 况 ; 把 一 个 杯 子 里 的 水 往 另 一 个 杯 子 里 倒, 把 后 者 装 满, 同 时 前 者 还 留 一 点 水, 前 提 是 两 个 杯 子 中 的 水 总 量 大 于 后 者 的 容 量 这 也 有 两 种 情 况 递 归 推 导 时 就 按 照 这 八 种 情 况 分 别 考 虑 就 可 以 了 3.2.5.1. 错 误 的 递 归 我 们 首 先 给 出 主 程 序, 参 见 例 3.2-8 主 函 数 将 调 用 pourwater(c1, c2, g) 子 函 数 用 以 测 试 用 容 量 分 别 是 c1 和 c2 的 两 个 杯 子 是 否 能 够 倒 出 g 升 水 出 来 pourwater() 函 数 将 用 输 入 的 三 个 参 数 构 造 一 个 Water 对 象, 通 过 调 用 该 类 对 象 的 pour() 方 法 判 断 倒 水 是 否 成 功 例 3.2-8 package com.training.recursion; public class Water { public static void main(string args[]) { pourwater(5, 3, 4); pourwater(5, 4, 2); pourwater(6, 9, 2); pourwater(6, 9, 3); private static void pourwater(int capacity1, int capacity2, int goal) { 31

第 三 章 递 归 程 序 设 计 Water water = new Water(capacity1, capacity2, goal); System.out.printf("capacity1 = %d, capacity2 = %d ==> goal: %d. Is it possible? %s!\n", capacity1, capacity2, goal, water.pour()? "Yes" : "No"); 根 据 上 一 小 节 的 考 虑 我 们 安 排 pour() 函 数 调 用 重 载 函 数 pour(water1, water2), 其 中 water1 和 water2 分 别 是 当 前 两 个 杯 子 中 的 水 量 pour(water1, water2) 是 一 个 递 归 程 序, 见 例 3.2-9 注 意 : Water 类 中 有 三 个 成 员 变 量 保 留 两 个 杯 子 的 容 量 和 目 标 水 量, 因 为 这 三 个 值 相 对 于 函 数 pour() 的 每 次 调 用 来 说 是 不 变 的, 这 就 是 之 所 以 把 他 们 放 在 成 员 变 量 中 而 不 是 作 为 参 数 进 行 传 递 的 原 因 例 3.2-9 package com.training.recursion; public class Water { public static void main(string args[]) { private static void pourwater(int capacity1, int capacity2, int goal) { int capacity1, capacity2; // 两 个 杯 子 的 容 量 int goal; // 目 标 水 量, 要 倒 出 多 少 水 public Water(int capacity1, int capacity2, int goal) { this.capacity1 = capacity1; this.capacity2 = capacity2; this.goal = goal; public boolean pour() { return pour(0, 0); 32

第 三 章 递 归 程 序 设 计 private boolean pour(int water1, int water2) { if(water1 == goal water2 == goal) return true; if(water1 < capacity1 && pour(capacity1, water2)) return true; if(water2 < capacity2 && pour(water1, capacity2)) return true; if(water1 > 0 && pour(0, water2)) return true; if(water2 > 0 && pour(water1, 0)) return true; int total = water1 + water2; if(total <= capacity2) { if(pour(0, total)) return true; else { if(pour(total - capacity2, capacity2)) return true; if(total <= capacity1) { if(pour(total, 0)) return true; else { if(pour(capacity1, total - capacity1)) return true; return false; 33

第 三 章 递 归 程 序 设 计 递 归 函 数 pour(water1, water2) 几 乎 是 完 全 按 照 上 一 小 节 的 讨 论 编 写 的, 但 这 个 解 对 吗? 一 旦 你 运 行 这 个 程 序 你 很 快 就 会 发 现 它 抛 出 了 StackOverflowError 这 意 味 着 递 归 没 有 中 止, 换 句 话 说, 递 归 边 界 (water1 == goal water2 == goal) 永 远 无 法 到 达 3.2.5.2. 新 参 数 组 合 一 定 要 更 接 近 于 边 界 产 生 这 个 错 误 的 原 因 是 : 以 例 3.2-9 中 pour(water1, water2) 函 数 的 第 一 个 if 为 例, 递 归 调 用 pour(capacity1, water2) 中 的 参 数 组 合 (capacity1, water2) 一 定 会 比 原 参 数 组 合 (water1, water2) 更 接 近 边 界 吗? 显 然 不 一 定 这 就 是 错 误 的 根 源 递 归 时 一 定 要 保 证 新 的 参 数 组 合 要 比 原 来 的 参 数 组 合 更 接 近 于 边 界 否 则 参 数 组 合 就 会 出 现 从 (0,0) (5, 0) (5,3) (0,3) (0,0) 的 无 限 循 环 而 如 果 你 能 保 证 新 产 生 的 参 数 组 合 比 原 参 数 组 合 更 接 近 于 边 界, 则 上 述 循 环 是 不 可 能 产 生 的 在 本 章 前 面 的 例 子 中, 无 论 是 Hanoi 塔 字 符 串 匹 配 兔 子 问 题 排 列 组 合 还 是 人 字 形 铁 路 问 题, 递 归 中 新 的 参 数 或 参 数 组 合 总 是 比 原 来 的 参 数 或 参 数 组 合 更 接 近 于 边 界 比 如 Hanoi 塔 问 题 中 表 示 碟 子 个 数 的 第 四 个 参 数 n( 例 3.1-2) 总 是 在 不 断 地 减 一, 因 而 绝 对 不 会 出 现 参 数 重 复 3.2.5.3. 保 存 状 态 法 如 果 你 无 法 保 证 新 参 数 组 合 更 接 近 于 边 界, 怎 么 办? 这 恰 恰 是 人 工 智 能 所 要 回 答 的 一 个 重 要 问 题, 即 : 当 状 态 出 现 重 复 时, 我 们 该 怎 么 办? 从 这 个 意 义 上 讲, 递 归 其 实 是 人 工 智 能 搜 索 方 法 的 一 个 特 例 ( 实 际 是 深 度 优 先 搜 索 的 一 个 特 例, 这 里 我 们 再 次 看 到 不 同 科 学 理 论 殊 路 同 归 的 性 质 ) 我 们 在 后 面 关 于 人 工 智 能 的 章 节 中 还 会 谈 到 这 个 问 题 现 在 我 们 有 一 个 简 单 的 方 法 解 决 这 个 问 题 如 果 出 现 参 数 重 复, 则 意 味 着 到 目 前 为 止 的 递 归 路 径 其 实 是 行 不 通 的, 注 定 要 回 到 原 点 重 新 再 来 所 以 我 们 可 以 把 参 数 组 合 保 存 下 来, 一 旦 递 归 过 程 中 发 现 当 前 参 数 组 合 与 保 存 的 某 个 参 数 组 合 相 同, 我 们 就 终 止 递 归 避 免 出 现 无 限 循 环 如 果 我 们 把 参 数 的 组 合 称 为 解 决 问 题 过 程 中 的 一 个 状 态, 则 我 们 把 这 种 保 存 参 数 组 合 的 方 法 称 为 保 存 状 态 法 根 据 这 个 思 路, 我 们 把 参 数 water1 和 water2 封 装 到 类 State 中, 然 后 在 递 归 函 数 中 增 加 一 个 参 数 visited 用 来 保 存 访 问 过 的 参 数 组 合 注 意, 为 了 能 够 判 断 两 个 状 态 是 否 相 等, 我 们 要 重 定 义 State 的 hashcode() 和 equals(object) 函 数 ( 这 个 问 题 我 们 以 后 还 会 谈 到 ) 这 样 我 们 的 程 序 就 被 改 成 : 例 3.2-10 package com.training.recursion; import ; public class Water { public static void main(string args[]) { private static void pourwater(int capacity1, int capacity2, int goal) { 34

第 三 章 递 归 程 序 设 计 int capacity1, capacity2; // 两 个 杯 子 的 容 量 int goal; // 要 倒 出 多 少 水 public Water(int capacity1, int capacity2, int goal) { private static final class State { int water1, water2; State(int water1, int water2) { this.water1 = water1; this.water2 = water2; @Override public int hashcode() { return (water1 << 16) water2; @Override public boolean equals(object obj) { if(!(obj instanceof State)) return false; State st = (State)obj; return this.water1 == st.water1 && this.water2 == st.water2; public boolean pour() { return pour(new State(0, 0), new HashSet<State>()); private boolean pour(state state, Set<State> visited) { if(state.water1 == goal state.water2 == goal) return true; 35

第 三 章 递 归 程 序 设 计 if(visited.contains(state)) // 100 return false; // 110 visited.add(state); if(state.water1 < capacity1 && pour(new State(capacity1, state.water2), visited)) return true; if(state.water2 < capacity2 && pour(new State(state.water1, capacity2), visited)) return true; if(state.water1 > 0 && pour(new State(0, state.water2), visited)) return true; if(state.water2 > 0 && pour(new State(state.water1, 0), visited)) return true; int total = state.water1 + state.water2; if(total <= capacity2) { if(pour(new State(0, total), visited)) return true; else { if(pour(new State(total - capacity2, capacity2), visited)) return true; if(total <= capacity1) { if(pour(new State(total, 0), visited)) return true; else { if(pour(new State(capacity1, total - capacity1), visited)) return true; visited.remove(state); // 200 return false; // 210 36

第 三 章 递 归 程 序 设 计 注 意,visited 集 合 仅 用 来 保 存 当 前 递 归 路 径 上 的 状 态 所 以 递 归 终 止 ( 即 return false) 之 前 应 该 把 当 前 状 态 从 集 合 中 删 除, 这 就 是 为 什 么 要 在 return false 之 前 执 行 visited.remove(state) 的 原 因 ( 参 见 例 3.2-10 中 用 //200 和 //210 标 记 的 行 ) 但 是 令 人 惊 讶 的 是, 例 3.2-10 中 用 //100 和 //110 标 记 的 行 在 return 语 句 之 前 并 没 有 删 除 当 前 状 态 state, 而 让 它 继 续 在 visited 集 合 中 保 持 存 在 这 是 因 为 如 果 我 们 把 state 从 visited 集 合 中 删 除, 则 下 次 如 果 再 遇 到 相 同 的 状 态, 程 序 还 是 会 对 它 递 归 求 解 这 样 我 们 不 但 避 免 无 限 循 环 的 递 归, 还 大 大 加 快 了 程 序 运 行 的 速 度 上 面 的 解 法 仅 仅 回 答 了 我 们 能 不 能 如 果 能 的 话, 怎 样 才 能 倒 出 那 么 多 水 呢? 以 及 如 何 用 最 少 的 次 数 倒 出 那 么 多 水 呢? 我 们 将 在 后 面 关 于 搜 索 的 章 节 中 回 答 这 两 个 问 题 3.3. 递 归 程 序 非 递 归 化 所 谓 递 归 程 序 的 非 递 归 化 是 指 用 非 递 归 ( 如 循 环 条 件 语 句 ) 的 方 法 实 现 递 归 思 想 至 少 有 以 下 几 个 理 由 促 使 我 们 讨 论 递 归 程 序 的 非 递 归 化 : 第 一, 递 归 的 奥 秘 是 什 么, 计 算 机 内 部 是 如 何 实 现 递 归 的? 第 二, 递 归 往 往 以 牺 牲 时 间 和 空 间 效 率 为 代 价 换 取 程 序 的 简 洁 和 高 可 读 性, 但 有 时 您 可 能 需 要 优 先 考 虑 时 空 效 率, 这 时 非 递 归 方 法 往 往 比 递 归 方 法 有 效 ; 第 三, 并 不 是 所 有 的 程 序 设 计 语 言 都 支 持 递 归, 比 如 Fortran77 就 不 支 持 如 何 用 这 样 的 语 言 开 发 递 归 思 想 的 程 序? 另 外, 你 不 想 知 道 Fortran 77 不 支 持 递 归 的 根 本 原 因 吗? 别 担 心 你 不 懂 Fortran 77, 它 的 语 法 与 一 般 高 级 语 言 没 有 什 么 大 的 差 异 更 重 要 的 是, Fortran 77 不 支 持 递 归 有 着 深 刻 的 原 因, 而 与 其 语 法 没 有 关 系 3.3.1. 函 数 调 用 的 实 质 3.3.1.1. 函 数 返 回 时 应 该 返 回 到 下 一 行 设 有 函 数 main() 调 用 m1(),m1() 调 用 m2(), 参 见 图 3.3-1 函 数 调 用 :main() m1() m2() main() m1() m2() 10: 110: 210: 20: 120: 220: 30: 130: Call m2(x) 230: 40: Call m1(a, b) 140: 240: 50: 150: 250 Return 60: 160: Return 70 图 3.3-1 main() 调 用 m1(),m1() 调 用 m2() 37

第 三 章 递 归 程 序 设 计 图 中 的 箭 头 指 明 程 序 运 行 的 流 程 比 如 main() 函 数 执 行 到 第 40 行 时, 遇 到 Call 语 句, 计 算 机 就 跳 转 到 m1() 的 第 一 行 即 110 行 继 续 执 行 m1() 函 数 执 行 到 第 130 行 时, 遇 到 Call 语 句 又 跳 转 到 m2() 的 第 一 行 即 210 行 继 续 执 行 在 m2() 中 执 行 到 250 行 的 Return 语 句 时, 计 算 机 又 跳 转 到 m1() 中 Call m2(x) 的 那 一 句 的 下 一 行 即 140 行 执 行 执 行 到 160 行 又 遇 到 Return 语 句, 则 跳 转 到 main() 函 数 中 Call m1(a,b) 的 下 一 行 即 第 50 行 继 续 执 行 综 上 所 述, 我 们 得 到 第 一 个 结 论 : 函 数 调 用 完 毕 之 后 应 该 返 回 到 调 用 语 句 的 下 一 行 继 续 执 行 3.3.1.2. 用 堆 栈 来 保 存 返 回 地 址 请 看 上 节 的 函 数 调 用 示 例 :main() m1() m2() 函 数 m1() 比 m2() 先 调 用, 但 是 却 后 返 回 函 数 调 用 总 有 这 个 性 质 : 先 调 用 的 函 数 总 是 后 返 回 或 者 反 过 来 说 也 一 样 : 后 调 用 的 函 数 先 返 回 为 了 能 够 让 计 算 机 从 一 系 列 被 调 用 的 函 数 中 正 确 返 回 ( 或 者 说 正 确 地 找 到 返 回 地 址 ), 我 们 该 用 什 么 样 的 数 据 结 构 保 存 每 次 函 数 调 用 的 返 回 地 址 呢? 既 然 是 先 调 用 的 后 返 回, 则 堆 栈 就 是 最 合 适 不 过 的 数 据 结 构 函 数 调 用 :main() m1() m2() main() m1() m2() 10: 110: 210: 20: 120: 220: 2 30: 1 130: Call m2(x) 230: 40: Call m1(a, b) 140: 3 240: 50: 4 150: 250 Return 60: 160: Return 70 运 行 堆 栈 的 变 化 情 况 : 1 push(50) 50 2 push(140) 140 50 3 pop() 140 被 弹 出 140 50 4 pop() 50 被 弹 出 50 图 3.3-2 用 堆 栈 保 存 返 回 地 址 图 3.3-2 显 示 了 堆 栈 是 如 何 被 用 来 保 存 返 回 地 址 的 ( 这 个 堆 栈 常 常 被 称 为 运 行 堆 栈 ) 图 中 计 算 机 每 次 遇 到 Call 语 句, 都 把 下 一 句 的 地 址 作 为 返 回 地 址 压 入 堆 栈 ( 见 第 1 步 和 第 2 步 ) 每 次 遇 到 Return 语 句, 都 从 当 前 堆 栈 的 栈 顶 弹 出 一 个 数 据 作 为 返 回 地 址, 然 后 转 到 该 返 回 地 址 所 指 定 的 位 置 处 继 续 运 行 比 如 计 算 机 运 行 到 m2() 函 数 的 第 250 行 时 遇 到 Return 语 句, 堆 栈 发 生 一 次 pop 操 作 ( 见 第 3 步 ), 计 算 机 根 据 弹 出 的 返 回 地 38

第 三 章 递 归 程 序 设 计 址 140 转 到 第 140 行 ( 位 于 m1() 函 数 内 ) 运 行, 从 而 实 现 了 从 被 调 用 函 数 m2() 向 调 用 函 数 m1() 的 返 回 同 样 道 理, 计 算 机 运 行 到 m1() 函 数 第 160 行 时 遇 到 Return 语 句, 堆 栈 再 次 发 生 pop 操 作 ( 见 第 4 步 ), 使 计 算 机 从 m1() 返 回 到 main() 函 数 的 第 50 行 继 续 运 行 3.3.1.3. 运 行 堆 栈 还 用 来 保 存 参 数 运 行 堆 栈 绝 不 仅 仅 用 来 保 存 返 回 地 址, 它 还 可 以 被 用 来 保 存 函 数 调 用 时 的 参 数 函 数 调 用 :main() m1(a, b) m2(x) main() m1() m2() 10: 110: 210: 20: 120: 220: 2 30: 1 130: Call m2(x) 230: 40: Call m1(a, b) 140: 3 240: 50: 4 150: 250 Return 60: 160: Return 70 运 行 堆 栈 的 变 化 情 况 1 push(50); push(b); push(a); a b 50 2 push(140); push(x); x 140 a b 50 3 pop(); pop(); a b 50 4 pop(); pop(); pop(); 图 3.3-3 用 运 行 堆 栈 保 存 返 回 地 址 和 参 数 图 3.3-3 显 示 了 用 运 行 堆 栈 保 存 返 回 地 址 和 参 数 时, 运 行 堆 栈 在 函 数 调 用 和 返 回 时 的 变 化 情 况 与 图 3.3-2 相 比, 两 者 有 以 下 不 同 图 3.3-3 遇 到 Call 语 句 时, 应 该 先 向 运 行 堆 栈 压 入 返 回 地 址, 然 后 压 入 参 数 设 有 n 个 参 数, 则 应 该 执 行 n+1 次 push 操 作 图 3.3-3 遇 到 Return 语 句 时, 应 该 首 先 把 参 数 全 部 弹 出, 设 有 n 个 参 数, 则 运 行 堆 栈 应 该 执 行 n 次 push 操 作 然 后 追 加 执 行 一 次 pop 操 作 以 便 弹 出 返 回 地 址, 并 根 据 返 回 地 址 决 定 计 算 机 应 该 跳 转 到 哪 里 继 续 执 行 3.3.1.4. 返 回 地 址 入 栈 的 次 序 一 般 地, 返 回 地 址 应 该 比 参 数 先 入 栈, 这 样 我 们 就 可 以 通 过 栈 顶 直 接 计 算 参 数 的 位 置 了 如 果 返 回 地 址 比 参 数 后 入 栈, 则 该 返 回 地 址 位 于 栈 顶 位 置 那 么 计 算 参 数 地 址 的 时 候 就 需 要 首 先 减 去 返 回 地 址 所 占 据 的 空 间 这 会 影 响 到 函 数 调 用 的 效 率 在 特 别 情 况 下, 比 如 3.3.1.5 小 节 和 3.3.1.7 小 节 为 了 实 现 可 变 参 数, 返 回 地 址 也 可 以 39

第 三 章 递 归 程 序 设 计 后 入 栈 3.3.1.5. 参 数 入 栈 的 次 序 与 可 变 参 数 如 果 仔 细 观 察 图 3.3-3, 你 会 发 现 对 同 一 次 函 数 调 用 来 说, 其 参 数 入 栈 的 次 序 似 乎 是 相 反 的 : 第 一 个 参 数 最 后 入 栈, 最 后 一 个 参 数 第 一 个 入 栈 也 就 是 说, 参 数 按 从 右 往 左 逆 序 入 栈 这 对 吗? 试 想 如 果 第 一 个 参 数 先 入 栈, 则 在 它 的 上 方 压 着 第 二 个 参 数, 在 第 二 个 参 数 的 上 方 压 着 第 三 个 参 数,, 以 此 类 推 最 后 一 个 参 数 则 位 于 当 前 栈 顶 ( 参 见 图 3.3-4) 也 就 是 说, 堆 栈 的 栈 顶 指 针 指 向 的 并 非 是 第 一 个 参 数, 而 是 最 后 一 个 参 数! 也 就 是 说 顺 序 入 栈 的 参 数 是 按 逆 序 搜 索 的 如 果 仅 仅 是 不 得 不 按 逆 序 搜 索 参 数 的 话, 也 许 不 足 以 说 服 你 接 受 参 数 应 该 逆 序 而 不 是 顺 序 入 栈 的 策 略 但 是 对 于 像 C 语 言 的 可 变 参 数 这 样 的 机 制 来 说, 参 数 逆 序 入 栈 则 是 不 得 不 接 受 的 选 择 Why? 这 是 因 为 所 谓 可 变 参 数 就 是 参 数 的 个 数 和 类 型 不 确 定, 如 果 参 数 按 顺 序 入 栈, 则 我 们 如 何 确 定 第 一 个 参 数 的 位 置? 别 忘 了 它 被 不 确 定 数 量 和 类 型 的 其 他 参 数 压 在 最 下 面 呢 如 果 参 数 逆 序 入 栈 的 话, 则 栈 顶 指 针 指 向 的 就 是 第 一 个 参 数, 其 位 置 是 确 定 的 有 了 第 一 个 参 数, 我 们 就 可 以 确 定 其 他 参 数 的 位 置 这 里 有 两 种 方 法 可 以 使 用 : 1) 可 以 根 据 第 一 个 参 数 中 的 信 息 确 定 所 有 其 他 参 数 的 类 型 和 长 度 从 而 计 算 出 它 们 的 位 置 ( 就 象 C 语 言 著 名 的 printf() 函 数 所 做 的 那 样 ) 或 者 2) 也 可 以 事 先 约 定 好 参 数 的 类 型, 比 如 第 一 个 参 数 是 int 型, 第 二 个 是 float 型,, 从 而 保 证 我 们 能 够 计 算 出 所 有 参 数 的 位 置 所 以 参 数 逆 序 入 栈 不 但 为 我 们 顺 序 搜 寻 参 数 带 来 便 利, 更 重 要 的 是, 它 是 实 现 可 变 参 数 的 关 键 3.3.1.6. Java 的 可 变 参 数 是 另 一 回 事 栈 顶 指 针 最 后 一 个 参 数 第 二 个 参 数 第 一 个 参 数 图 3.3-4 参 数 顺 序 入 栈 值 得 注 意 的 是,Java 也 提 供 了 可 变 参 数 机 制, 但 是 这 与 C/C++ 的 可 变 参 数 完 全 不 是 一 回 事 Java 可 变 参 数 的 实 质 是 数 组 即 所 有 可 变 的 参 数 其 实 是 放 在 一 个 数 组 中 的 比 如 设 有 可 变 参 数 函 数 : void m(int a, String b) { 则 这 个 函 数 的 申 明 类 似 ( 但 不 等 价 ) 于 : void m(int a, String[] b) { 在 m() 函 数 内 部 引 用 b 时,b 也 就 是 一 个 String 数 组 类 型, 比 如 可 以 通 过 b.length 获 得 数 组 的 长 度 即 可 变 参 数 的 个 数 调 用 m() 函 数 时, m(20, abc, def, gh ); 等 价 于 : m(20, new String[]{ abc, def, gh ); 事 实 上, 上 述 两 种 调 用 方 式 都 是 Java 允 许 的 所 以 Java 可 变 参 数 的 实 质 是 : 帮 助 你 40

第 三 章 递 归 程 序 设 计 在 函 数 调 用 时 少 写 一 些 像 new String[]{ 这 样 的 代 码 那 么 为 什 么 又 说 上 述 两 种 方 式 虽 然 类 似 但 并 不 等 价 呢? 原 因 在 于 可 变 参 数 必 须 是 最 后 一 个 参 数, 即 只 能 放 在 最 后 一 个 参 数 类 型 之 后 并 且 一 个 参 数 列 表 中 最 多 只 能 有 一 个 可 变 参 数 而 数 组 参 数 没 有 这 个 限 制, 随 便 第 几 个 参 数 都 可 以 是 数 组 参 数, 而 且 可 以 有 任 意 多 个 数 组 参 数 我 想, 勤 奋 好 学 的 你 一 定 会 打 破 沙 锅 问 ( 文 ) 到 底 : 为 什 么 只 能 是 最 后 一 个 参 数 是 可 变 参 数? 为 什 么 不 能 有 多 个 可 变 参 数? 先 回 答 第 一 个 问 题 设 有 函 数 : m(int a, int b) 则 Java 编 译 器 在 遇 到 形 如 m(12, 8, 56); 的 函 数 调 用 的 时 候 就 会 遇 到 困 难 因 为 编 译 器 从 左 往 右 扫 描 参 数 列 表 时, 并 不 清 楚 到 底 应 该 把 前 几 个 整 数 ( 12? 或 者 12, 8? 或 则 12, 8, 56?) 合 并 成 一 个 数 组 因 为 别 忘 了, 我 们 假 设 可 变 参 数 之 后 是 可 以 有 其 他 参 数 的 也 许 你 会 说 那 当 然 是 把 12, 8 两 个 参 数 合 并 成 一 个 数 组 喽, 56 赋 值 给 参 数 b! 但 是 遗 憾 的 是, 你 的 这 个 策 略 实 际 上 是 从 右 往 左 扫 描 参 数 列 表, 这 不 符 合 编 译 器 的 习 惯 但 是 如 果 我 们 约 定 可 变 参 数 只 能 是 最 后 一 个 参 数, 并 且 其 他 参 数 不 能 是 可 变 参 数 则 函 数 调 用 时, 编 译 器 可 以 很 容 易 地 确 定 哪 些 参 数 应 该 合 并 成 一 个 数 组 假 设 m() 函 数 的 定 义 是 : m(string a, float b, int c) 则 函 数 调 用 m( abc, 12.04, 8, 56); 中 前 两 个 参 数 必 然 与 参 数 a b 分 别 对 应, 剩 下 的 参 数 8,56 就 应 该 合 并 成 一 个 数 组, 然 后 与 c 对 应 这 些 信 息 在 编 译 器 从 左 往 右 扫 描 整 个 参 数 列 表 时 很 容 易 获 得 3.3.1.7. 控 制 运 行 堆 栈 的 代 码 应 该 放 在 哪 里? 运 行 堆 栈 上 的 操 作 主 要 有 两 个 :push() 和 pop() 现 在 的 问 题 是, 这 些 操 作 的 代 码 应 该 放 在 哪 里 执 行 呢? 如 果 是 解 释 执 行 的 语 言 (Java 就 是 解 释 执 行 的 ), 那 么 解 释 器 可 以 执 行 这 样 的 操 作 函 数 本 身 以 及 调 用 函 数 的 语 句 都 不 必 关 心 它 们 但 是 对 于 像 C 语 言 这 样 直 接 编 译 成 本 地 代 码 (Native Codes) 的 语 言 来 说, 编 译 结 果 中 必 须 包 含 对 运 行 堆 栈 的 控 制 main() m1(a, b) main() m1() 10: 110: 20: push(60) 120: 30: push(b) 130: 40: push(a) 140: 50: Call m1() 150: pop() 60: 160: pop() 70: 170 goto pop() 调 用 端 被 调 用 函 数 图 3.3-5 pop() 操 作 位 于 被 调 用 函 数 内 push() 操 作 只 能 放 在 函 数 的 调 用 端 ( 参 见 图 3.3-5) 而 不 能 放 在 被 调 用 函 数 内 部, 因 为 被 调 用 函 数 不 可 能 知 道 应 该 往 堆 栈 中 压 入 哪 些 参 数 而 pop() 操 作 可 以 放 在 以 下 两 个 地 方 之 一 : 被 调 用 函 数 的 最 后 ( 参 见 图 3.3-5) 或 者 41

第 三 章 递 归 程 序 设 计 调 用 端 ( 参 见 图 3.3-6) 请 注 意, 在 上 述 两 种 方 法 里, 返 回 地 址 分 别 是 在 所 有 参 数 之 前 和 之 后 入 栈 的 ( 为 什 么?) 现 在 的 问 题 是, 上 述 两 种 方 法 有 什 么 区 别 吗? 如 果 pop() 操 作 位 于 调 用 端, 这 意 味 着 每 一 个 调 用 端 都 要 有 一 组 pop 操 作 如 果 被 调 用 函 数 是 一 个 经 常 被 调 用 的 函 数, 那 么 就 会 有 许 多 地 方 存 在 这 种 pop() 操 作 相 反, 如 果 pop() 操 作 位 于 被 调 用 函 数 内 部, 那 么 无 论 一 个 函 数 被 调 用 了 多 少 次, 调 用 端 都 不 必 执 行 pop() 操 作 既 然 这 样, 那 pop() 操 作 位 于 调 用 端 还 有 什 么 意 义 呢? 其 意 义 就 是 : 实 现 了 可 变 参 数 参 数 可 变, 意 味 着 调 用 端 压 入 运 行 堆 栈 的 参 数 个 数 不 确 定, 这 样 我 们 就 不 能 指 望 被 调 用 函 数 能 够 事 先 预 测 有 多 少 参 数 入 栈 于 是 就 只 能 由 调 用 端 来 执 行 pop() 操 作, 因 为 调 用 端 显 然 明 确 地 知 道 有 多 少 参 数 入 栈 所 以 总 结 起 来, 要 实 现 可 变 参 数, 必 须 满 足 以 下 条 件 : 1) 参 数 必 须 逆 序 入 栈 ; 2) 返 回 地 址 必 须 在 参 数 之 后 入 栈 ; 3) 出 栈 操 作 必 须 在 调 用 端 执 行 3.3.1.8. cdecl 和 pascal 申 明 main() m1(a, b) main() m1() 10: 110: 20: push(b) 120: 30: push(a) 130: 40: push(60) 140: 50: Call m1() 150: 60: pop() 160: 70: pop() 170 goto pop() 80:... 调 用 端 被 调 用 函 数 图 3.3-6 pop() 操 作 位 于 调 用 端 正 是 由 于 上 述 差 异,Visual C++ 中 约 定, 一 个 函 数 如 果 用 cdecl 申 明, 这 意 味 着 其 参 数 以 传 统 的 C 语 言 方 式 出 入 栈, 即 参 数 从 右 往 左 逆 序 入 栈 并 且 由 调 用 端 弹 出 这 样 做 是 为 了 保 证 可 变 参 数 的 实 现 如 果 用 pascal 申 明, 这 意 味 着 其 参 数 以 Pascal 语 言 方 式 出 入 栈 (Pascal 语 言 不 允 许 可 变 参 数 ), 即 参 数 从 左 往 右 顺 序 入 栈 并 且 由 被 调 用 函 数 负 责 弹 出 作 为 一 个 高 级 程 序 员, 你 应 该 明 白 其 中 的 差 异 和 各 自 的 优 缺 点, 知 道 该 在 什 么 情 况 下 选 用 哪 种 申 明 3.3.1.9. 运 行 堆 栈 常 用 来 保 存 哪 些 数 据? 通 过 以 上 分 析, 我 们 知 道 运 行 堆 栈 常 用 来 保 存 返 回 地 址 和 参 数 另 外, 函 数 的 局 部 变 量 和 临 时 变 量 也 需 要 保 存 到 运 行 堆 栈 中 所 谓 临 时 变 量 是 指 计 算 机 内 部 为 了 计 算 程 序 的 运 行 结 果 而 临 时 设 置 的 变 量 比 如 为 了 计 算 a+b+c, 计 算 机 首 先 计 算 a+b 的 结 果, 并 把 结 果 保 存 到 一 个 临 时 变 量 里 面, 然 后 计 算 这 个 临 时 变 量 与 c 的 和 另 外, 对 于 Pascal 语 言 来 说, 为 了 使 程 序 员 能 够 在 函 数 和 过 程 内 定 义 子 函 数 或 子 过 程, 运 行 堆 栈 还 要 保 存 Display 表 不 明 白 什 么 是 Display 表 的 读 者 可 以 略 过 这 句 话 42

第 三 章 递 归 程 序 设 计 3.3.2. 递 归 调 用 与 一 般 函 数 调 用 以 上 分 析 都 是 对 一 般 函 数 调 用 来 说 的 但 是 这 个 分 析 对 递 归 调 用 来 说 同 样 成 立 如 果 一 个 函 数 内 部 递 归 调 用 自 己, 那 么 与 一 般 函 数 调 用 一 样, 递 归 调 用 时 也 是 压 入 返 回 地 址 和 参 数, 然 后 跳 转 到 被 调 用 函 数 的 第 一 行 即 可 唯 一 不 同 的 是, 递 归 调 用 所 要 跳 转 的 目 的 地 就 是 当 前 调 用 函 数 的 第 一 行 所 谓 递 归 无 非 就 是 调 用 函 数 和 被 调 用 函 数 是 同 一 个 函 数 罢 了 所 以 计 算 机 内 部 其 实 并 不 区 分 递 归 还 是 非 递 归, 更 不 区 分 直 接 递 归 和 间 接 递 归 只 要 遇 到 函 数 调 用, 就 向 运 行 堆 栈 中 压 入 返 回 地 址 和 参 数, 然 后 跳 转 到 被 调 用 函 数 的 第 一 行 就 可 以 了! 原 来 递 归 和 一 般 函 数 调 用 并 没 有 多 大 差 异, 它 们 背 后 的 实 质 居 然 完 全 相 同 像 这 样 不 同 的 概 念 和 理 论 殊 路 同 归, 最 后 归 结 为 同 样 实 质 的 现 象 在 计 算 机 理 论 和 数 学 中 比 比 皆 是, 这 也 是 我 们 学 习 它 们 的 最 大 趣 味 来 源 之 一 现 在 为 了 证 实 我 们 的 理 论 ( 即 递 归 调 用 与 非 递 归 调 用 实 质 相 同 ), 我 们 考 察 二 叉 树 的 非 递 归 中 序 遍 历 算 法 3.3.3. 非 递 归 中 序 遍 历 图 3.3-7 给 出 了 一 棵 二 叉 树 及 其 对 应 图 3.3-7 二 叉 树 的 中 序 遍 历 的 中 序 二 叉 树 中 序 遍 历 的 递 归 算 法 非 常 简 单 也 很 容 易 理 解, 参 见 例 3.3-2 例 3.3-1 则 给 出 了 二 叉 树 中 的 结 点 BianryNode 的 定 义 例 3.3-1 BinaryNode 的 定 义 package com.training.recursion; 中 序 :DBEAFCG public interface BinaryNode { Object getvalue(); BinaryNode getleft(); BinaryNode getright(); 例 3.3-2 二 叉 树 中 序 遍 历 的 递 归 算 法 package com.training.recursion; import java.util.stack; 43

第 三 章 递 归 程 序 设 计 abstract public class BinaryVisitor { public void visitrim_recursively(binarynode node) { if (node!= null) { visitrim_recursively(node.getleft()); visit(node.getvalue()); visitrim_recursively(node.getright()); public abstract void visit(object value); 现 在 我 们 试 图 按 照 上 节 的 理 论 把 例 3.3-2 中 的 递 归 算 法 改 写 成 一 个 非 递 归 算 法 当 然, 很 多 教 材 已 经 给 出 了 二 叉 树 中 序 遍 历 的 非 递 归 算 法 的 例 子, 比 如 例 3.3-3 就 是 一 个 例 子 我 们 的 目 的 是 : 把 例 3.3-2 中 的 递 归 函 数 visitrim_recursively() 的 代 码 进 行 变 换, 最 后 得 到 一 个 与 例 3.3-3 中 非 递 归 函 数 visitrim_unrecursively() 的 代 码 一 模 一 样 的 程 序! 例 3.3-3 二 叉 树 中 序 遍 历 的 非 递 归 算 法 public void visitrim_unrecursively(binarynode node) { Stack<BinaryNode> stack = new Stack<BinaryNode>(); while (true) { while (node!= null) { stack.push(node); node = node.getleft(); if (stack.isempty()) return; node = stack.pop(); visit(node.getvalue()); node = node.getright(); 44

第 三 章 递 归 程 序 设 计 3.3.4. 递 归 程 序 非 递 归 化 示 例 3.3.4.1. 第 一 步 : 给 代 码 的 每 一 个 行 加 行 号 这 一 步 的 结 果 参 见 例 3.3-4 加 行 号 的 目 的 是 为 了 方 便 后 面 引 用 指 定 的 行 例 3.3-4 给 递 归 函 数 的 每 一 行 一 个 编 号 10: 20: 30: 40: 50: 60: 70: public void visitrim_recursively(binarynode node) { if (node!= null) { visitrim_recursively(node.getleft()); visit(node.getvalue()); visitrim_recursively(node.getright()); 3.3.4.2. 第 二 步 : 使 用 Stack, push(), pop() 和 goto 替 换 递 归 调 用 这 一 步 的 结 果 参 见 例 3.3-5 注 意, 原 递 归 函 数 中 没 有 用 到 局 部 变 量, 而 临 时 变 量 虽 然 有 用 到, 但 是 在 高 级 语 言 编 程 中 不 必 考 虑 所 以 运 行 堆 栈 中 只 需 压 入 返 回 地 址 和 唯 一 的 参 数 即 可 例 3.3-5 用 push(), pop() 和 goto 替 换 递 归 调 用 public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(70); stack.push(node); // 定 义 运 行 堆 栈 // 压 入 主 程 序 返 回 地 址 70 // 压 入 参 数 node 10: if (node!= null) { 20: node = node.getleft(); stack.push(30); stack.push(node); goto 10; // 模 拟 visitrim_recursively(node.getleft()); // 压 入 返 回 地 址 30 // 压 入 参 数 node // 跳 到 函 数 的 第 一 句 30: visit(node.getvalue()); 45

第 三 章 递 归 程 序 设 计 40: node = node.getright(); stack.push(60); stack.push(node); goto 10; // 模 拟 visitrim_recursively(node.getright()); // 压 入 返 回 地 址 60 // 压 入 参 数 node // 跳 到 函 数 的 第 一 句 50: 60: stack.pop(); switch(stack.pop()) { case 30: node = stack.top().node; goto 30; case 60: node = stack.top().node; goto 60; case 70: return; // 弹 出 唯 一 的 参 数 // 弹 出 返 回 地 址, 并 根 据 该 地 址 进 行 跳 转 70: 3.3.4.3. 第 三 步 : 用 while 替 换 if 和 goto if 打 头 goto 结 尾 的 一 组 语 句 可 以 用 一 个 while 循 环 代 替 结 果 参 见 例 3.3-6 例 3.3-6 用 while 替 换 if 和 goto public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(70); stack.push(node); 10: while(node!= null) { // if 被 while 替 换 20: node = node.getleft(); stack.push(30); 46

第 三 章 递 归 程 序 设 计 stack.push(node); goto 10; 30: visit(node.getvalue()); 40: node = node.getright(); stack.push(60); stack.push(node); goto 10; // 删 除 goto 50: 60: stack.pop(); switch(stack.pop()) { case 30: node = stack.top().node; goto 30; case 60: node = stack.top().node; goto 60; case 70: return; 70: 3.3.4.4. 第 四 步 : 用 while 循 环 处 理 返 回 地 址 60 请 看 例 3.3-6 中 函 数 结 尾 的 switch 语 句, 当 返 回 地 址 是 60 时, 实 际 执 行 的 是 一 个 循 环 我 们 就 用 一 个 while 循 环 处 理 这 个 60, 结 果 参 见 例 3.3-7 例 3.3-7 用 while 循 环 处 理 返 回 地 址 60 public void visitrim_recursively(binarynode node) { 47

第 三 章 递 归 程 序 设 计 Stack stack =... ; stack.push(70); stack.push(node); 10: while(node!= null) { 20: node = node.getleft(); stack.push(30); stack.push(node); goto 10; 30: visit(node.getvalue()); 40: node = node.getright(); 41: stack.push(60); 42: stack.push(node); 50: 60: stack.pop(); addr = stack.pop(); while(addr == 60) addr = stack.pop(); if(addr == 70) return; node = stack.top(); goto 30; 原 来 代 码 switch(stack.pop()) { case 30: node = stack.top().node; goto 30; case 60: node = stack.top().node; goto 60; case 70: return; 70: 3.3.4.5. 第 五 步 : 消 除 最 后 的 goto 30 语 句 方 法 是 把 例 3.3-7 中 第 30 40 41 42 行 的 代 码 统 统 移 到 后 面 并 加 上 一 个 goto 10 语 句 结 果 参 见 例 3.3-8 例 3.3-8 消 除 最 后 的 goto 30 语 句 public void visitrim_recursively(binarynode node) { 48

第 三 章 递 归 程 序 设 计 Stack stack =... ; stack.push(70); stack.push(node); 10: while(node!= null) { 20: node = node.getleft(); stack.push(30); stack.push(node); goto 10; 50: 60: stack.pop(); addr = stack.pop(); while(addr == 60) addr = stack.pop(); if(addr == 70) return; node = stack.top(); goto 30; // 删 除 goto 30 30: visit(node.getvalue()); // 第 30 行 移 到 这 里 40: 41: 42: node = node.getright(); stack.push(60); stack.push(node); goto 10; // 第 40 41 42 行 移 到 这 里 // 最 后 还 要 加 一 个 goto 语 句 70: 3.3.4.6. 第 六 步 : 删 除 goto 10 第 一 个 goto 10 语 句 完 全 多 余, 可 以 直 接 删 除 第 二 个 goto 10 语 句 可 以 用 一 个 while(true) 死 循 环 代 替 结 果 参 见 例 3.3-9 例 3.3-9 删 除 goto 10 语 句 49

第 三 章 递 归 程 序 设 计 public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(70); stack.push(node); 10: while(true) { while(node!= null) { 20: node = node.getleft(); stack.push(30); stack.push(node); goto 10; // 用 以 取 代 第 43 行 goto 语 句 的 死 循 环 // 这 个 goto 语 句 完 全 多 余 50: 60: stack.pop(); addr = stack.pop(); while(addr == 60) addr = stack.pop(); if(addr == 70) return; node = stack.top(); 30: visit(node.getvalue()); 40: 43: node = node.getright(); stack.push(60); stack.push(node); goto 10; // 这 个 goto 语 句 可 以 用 第 10 行 的 while(true) 代 替 70: 3.3.4.7. 第 七 步 : 用 30 取 代 返 回 地 址 70 如 果 运 行 堆 栈 中 的 当 前 返 回 地 址 是 70 时, 把 这 个 地 址 弹 出 堆 栈 之 后, 堆 栈 中 必 50

第 三 章 递 归 程 序 设 计 然 为 空 所 以 我 们 可 以 用 判 断 堆 栈 是 否 为 空 的 办 法 取 代 判 断 返 回 地 址 是 否 是 70 这 样 做 的 好 处 是 返 回 地 址 从 原 来 的 三 个 变 为 两 个 : 30 和 60 结 果 参 见 例 3.3-10 例 3.3-10 用 30 取 代 返 回 地 址 70 public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(30); stack.push(node); // 原 来 压 入 的 返 回 地 址 70 用 30 代 替 10: while(true) { while(node!= null) { 20: node = node.getleft(); stack.push(30); stack.push(node); 50: 60: 62: 63: 64: stack.pop(); addr = stack.pop(); while(addr == 60) addr = stack.pop(); if(stack.isempty()) return; node = stack.top(); // 用 判 断 堆 栈 是 否 为 空 取 代 对 返 回 地 址 70 的 判 断 30: visit(node.getvalue()); 40: node = node.getright(); 70: stack.push(60); stack.push(node); 注 意, 原 来 压 入 的 返 回 地 址 70 就 可 以 用 30 代 替 可 能 有 人 会 问, 为 什 么 不 用 60 代 替 呢? 请 注 意 例 3.3-10 中 的 第 62 63 和 64 行, 在 判 断 堆 栈 是 否 为 空 之 前, 如 果 返 回 地 址 ( 即 addr) 是 60, 则 需 要 执 行 一 个 循 环, 所 以 用 60 是 不 合 适 的, 我 51

第 三 章 递 归 程 序 设 计 们 只 能 选 择 30 3.3.4.8. 第 八 步 : 提 前 执 行 弹 出 操 作 请 看 例 3.3-11 第 63 行, 返 回 地 址 是 60 时, 堆 栈 总 会 执 行 一 个 pop() 操 作 而 不 会 执 行 其 他 操 作 所 以 我 们 可 以 在 压 入 60 之 前 就 执 行 这 个 pop() 操 作, 从 而 为 堆 栈 节 省 空 间 然 后 60 也 就 不 必 压 入 堆 栈 了 由 于 返 回 地 址 只 剩 下 唯 一 的 30 了, 所 以 改 为 压 入 30 例 3.3-11 提 前 执 行 弹 出 操 作 public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(30); stack.push(node); 10: while(true) { while(node!= null) { 20: node = node.getleft(); 50: stack.push(30); stack.push(node); 60: 62: 63: 64: stack.pop(); addr = stack.pop(); while(addr == 60) addr = stack.pop(); if(stack.isempty()) return; node = stack.top(); // 返 回 地 址 是 60 时 总 是 导 致 堆 栈 的 一 个 弹 出 操 作 30: visit(node.getvalue()); 40: node = node.getright(); stack.pop(); stack.push(30); stack.push(node); // 我 们 可 以 在 压 入 60 之 前 执 行 弹 出 操 作 // 然 后 压 入 唯 一 的 地 址 30 而 不 是 60 52

第 三 章 递 归 程 序 设 计 70: 3.3.4.9. 第 九 步 : 删 除 与 返 回 地 址 60 有 关 的 操 作 由 于 堆 栈 中 的 地 址 不 可 能 是 60, 所 以 所 有 与 之 有 关 的 语 句 都 可 以 删 除 了 结 果 参 见 例 3.3-12 例 3.3-12 删 除 与 返 回 地 址 60 有 关 的 操 作 public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(30); stack.push(node); 10: while(true) { while(node!= null) { 20: node = node.getleft(); 50: stack.push(30); stack.push(node); 60: 62: 63: 64: stack.pop(); addr = stack.pop(); while(addr == 60) addr = stack.pop(); if(stack.isempty()) return; node = stack.top(); // 与 返 回 地 址 60 有 关 的 操 作 都 可 以 删 除 30: visit(node.getvalue()); 40: node = node.getright(); stack.pop(); stack.push(30); stack.push(node); 53

第 三 章 递 归 程 序 设 计 70: 3.3.4.10. 第 十 步 : 返 回 地 址 30 也 不 需 要 了 没 有 好 也 就 无 所 谓 坏, 没 有 阴 也 就 无 所 谓 阳 一 个 事 物 如 果 没 有 对 立 面 的 话, 那 它 就 没 有 存 在 的 理 由 了 作 为 唯 一 的 返 回 地 址, 30 本 身 也 不 再 被 需 要 我 们 删 除 所 有 压 入 返 回 地 址 30 的 操 作, 结 果 参 见 例 3.3-13 例 3.3-13 返 回 地 址 30 不 必 压 入 堆 栈 了 public void visitrim_recursively(binarynode node) { Stack stack =... ; stack.push(30); stack.push(node); // 唯 一 的 返 回 地 址 不 必 压 入 堆 栈 10: while(true) { while(node!= null) { 20: node = node.getleft(); stack.push(30); stack.push(node); // 唯 一 的 返 回 地 址 不 必 压 入 堆 栈 50: 60: stack.pop(); stack.pop(); if(stack.isempty()) return; node = stack.top(); // 堆 栈 中 已 经 没 有 返 回 地 址 了 30: visit(node.getvalue()); 40: node = node.getright(); stack.pop(); stack.push(30); // 唯 一 的 返 回 地 址 不 必 压 入 堆 栈 54

第 三 章 递 归 程 序 设 计 stack.push(node); 70: 3.3.4.11. 第 十 一 步 : 消 除 node 与 stack 栈 顶 的 重 复 请 看 例 3.3-13, 你 会 发 现 变 量 node 和 堆 栈 stack 的 栈 顶 元 素 是 重 复 的 这 就 提 示 了 我 们 可 以 删 除 这 个 栈 顶 元 素 从 而 为 堆 栈 再 节 省 一 个 单 位 空 间, 结 果 参 见 例 3.3-14 例 3.3-14 node 不 必 入 栈 public void visitrim_recursively(binarynode node) { Stack<BinaryNode> stack = new Stack<BinaryNode>() ; stack.push(node); // node 不 必 入 栈 10: while(true) { while(node!= null) { 20: stack.push(node); node = node.getleft(); // 当 前 node 入 栈 // node 指 向 另 一 个 元 素, 该 元 素 原 来 要 入 栈 的, // 现 在 不 必 了 50: 60: 63: stack.pop(); if(stack.isempty()) return; node = stack.pop(); // 当 前 参 数 已 经 不 在 栈 顶 了 // 当 前 参 数 只 须 保 存 在 node 中 而 不 是 栈 顶 30: visit(node.getvalue()); 40: node = node.getright(); stack.pop(); stack.push(node); // 当 前 参 数 已 经 不 在 栈 顶 了 // node 不 必 压 入 堆 栈 55

第 三 章 递 归 程 序 设 计 70: 比 较 例 3.3-14 与 例 3.3-3, 你 会 发 现 两 个 例 子 中 的 代 码 完 全 一 致 这 就 是 计 算 机 理 论 的 魅 力 3.4. 哑 元 与 不 可 递 归 性 3.4.1. 什 么 是 哑 元 哑 元 (Dummy) 是 Fortran 77 所 特 有 的 一 个 概 念 它 看 起 来 非 常 类 似 于 参 数 比 如, 参 数 有 形 式 参 数 ( 简 称 形 参 ) 和 实 际 参 数 ( 简 称 实 参 ), 形 参 是 被 调 用 函 数 内 部 用 来 引 用 实 参 的, 实 参 是 调 用 端 实 际 传 给 被 调 用 函 数 的 参 数 对 应 的, 哑 元 是 被 调 用 函 数 ( 或 子 过 程, 以 下 无 差 别 的 使 用 这 两 个 概 念 ) 内 部 用 来 引 用 实 元 的, 实 元 是 调 用 端 实 际 与 哑 元 相 结 合 的 数 据 参 数 传 递 的 概 念 在 Fortran 77 中 被 哑 实 结 合 所 代 替 既 然 如 此, 科 学 家 们 为 什 么 要 搞 出 两 套 概 念 呢? 有 鉴 于 Fortran 77 诞 生 得 非 常 早, 干 脆 取 消 形 参 实 参 参 数 传 递 等 概 念, 都 叫 做 哑 元 实 元 哑 实 结 合 算 了! 也 免 得 那 么 多 的 莘 莘 学 子 们 牺 牲 了 那 么 多 的 脑 细 胞 还 没 搞 懂 什 么 是 参 数 传 递 当 然, 科 学 家 们 是 不 会 故 意 为 同 一 个 概 念 取 两 个 名 字 的 虽 然 我 给 我 太 太 取 了 十 几 个 名 字 比 如 哈 内 达 令 等 等, 那 是 我 对 她 的 爱 称, 名 称 越 多 表 示 我 越 爱 她 但 是 如 果 科 学 家 们 对 科 学 概 念 也 取 多 个 名 字, 那 就 会 给 公 众 交 流 带 来 很 大 障 碍 所 以 如 果 没 有 必 要 的 话, 一 个 概 念 只 有 一 个 名 字 是 最 科 学 的 所 以 哑 元 和 参 数 仅 仅 是 表 面 相 同, 他 们 其 实 是 两 个 完 全 不 同 的 东 西 我 们 已 经 知 道 参 数 是 放 在 运 行 堆 栈 里 面 的 哑 元 呢? 呵 呵, 哑 元 与 堆 栈 毫 不 相 干, 它 和 返 回 地 址 一 起 就 放 在 内 存 中 固 定 m() 函 数 10: x 20: y 30: 返 回 地 址 40: m() 函 数 开 始 50: 60: 70: Return 的 位 置 处, 一 般 地 它 们 和 函 数 的 代 码 ( 编 译 后 的 结 果 ) 放 在 一 起 比 如 函 数 m(x, y) 有 两 个 参 数 x 和 y, 则 编 译 后 x 和 y 就 放 在 m 函 数 体 的 头 部 或 尾 部 ( 参 见 图 3.4-1) 当 然, 局 部 变 量 和 临 时 变 量 也 和 哑 元 一 样 放 在 内 存 中 相 对 固 定 位 置 处, 图 3.4-1 忽 略 了 它 们 以 图 3.4-1 为 例, 所 谓 哑 实 结 合 就 是 在 函 数 调 用 m(12, 25) 时, 把 实 元 12 25 和 返 回 地 址 分 别 放 入 内 存 10 号 20 号 和 30 号 位 置 处 那 这 与 参 数 有 什 么 区 别 呢? 头 部 函 数 体 图 3.4-1 哑 元 返 回 地 址 和 函 数 体 一 样, 都 是 放 在 内 存 中 相 对 固 定 的 位 置 处 56

第 三 章 递 归 程 序 设 计 void hanoi(char a, char b, char c, int n) { if(n == 1) move(a, c, 1); else { hanoi(a, c, b, n-1); move(a, c, n); hanoi(b, a, c, n-1); 跳 到 第 一 次 递 归 调 用 之 后 返 回 地 址 A 参 数 a B 参 数 b C 参 数 c 3 参 数 n 跳 到 第 一 次 递 归 调 用 之 后 返 回 地 址 A 参 数 a C 参 数 b B 参 数 c 4 参 数 n 跳 出 hanoi 函 数 返 回 地 址 A 参 数 a B 参 数 b C 参 数 c 5 参 数 n 运 行 堆 栈 图 3.4-2 运 行 堆 栈 3 次 递 归 调 用 hanoi() 函 数 后 的 状 态 3.4.2. 哑 元 与 参 数 的 差 别 哑 元 与 参 数 的 最 大 差 异 是 : 哑 元 永 远 只 有 一 个 备 份 这 就 象 函 数 的 函 数 体 在 内 存 中 不 可 能 有 两 个 备 份 一 样 但 是 参 数 是 独 立 于 函 数 体 存 在 于 运 行 堆 栈 中 的, 对 同 一 个 函 数 m(x, y) 来 说, 它 的 参 数 x 和 y 在 运 行 堆 栈 中 可 以 有 多 个 备 份 以 递 归 函 数 hanoi(a, b, c, n) 为 例 ( 参 见 例 3.1-2), 假 设 主 程 序 调 用 hanoi( A, B, C, 5) 则 3 次 递 归 调 用 以 后, 运 行 堆 栈 的 状 态 如 图 3.4-2 所 示 运 行 堆 栈 中 出 现 了 3 个 返 回 地 址,3 个 参 数 a 参 数 b 和 参 数 c 正 是 由 于 每 次 递 归 调 用 时 计 算 机 都 会 向 运 行 堆 栈 压 入 参 数, 从 而 保 证 了 每 次 递 归 调 用 的 参 数 不 会 同 上 一 次 递 归 调 用 的 参 数 相 混 淆 而 哑 元 保 存 在 内 存 中 相 对 固 定 的 位 置, 同 一 个 哑 元 在 内 存 中 只 有 一 个 备 份, 因 而 对 同 一 个 哑 元 赋 值 将 导 致 该 哑 元 的 旧 值 被 覆 盖 所 以 哑 元 的 存 在 将 导 致 被 递 归 调 用 的 函 数 的 参 数 混 乱, 因 而 Fortran 77 约 定 函 数 的 递 归 调 用 是 不 允 许 的, 连 间 接 递 归 都 不 行! 那 么 哑 元 就 没 有 优 势 了 吗? 哑 元 以 不 允 许 递 归 为 代 价 换 来 的 好 处 是 : 哑 元 存 在 于 内 存 相 对 固 定 的 地 方, 而 参 数 是 放 在 堆 栈 里 的, 所 以 哑 元 的 定 位 比 较 直 接, 而 参 数 的 定 位 必 须 计 算 运 行 堆 栈 的 栈 顶 指 针 + 参 数 相 对 于 栈 顶 的 偏 移 所 以 参 数 的 定 位 要 多 计 算 一 次 加 法 ( 或 减 法, 取 决 于 堆 栈 开 口 是 向 下 还 是 向 上 ) 所 以 Fortran 77 程 序 相 对 于 其 它 使 用 参 数 的 高 级 语 言 速 度 要 快 由 于 科 学 计 算 往 往 计 算 量 巨 大, 对 程 序 的 运 行 速 度 要 求 较 高, 因 而 Fortran 77 是 高 级 语 言 中 特 别 适 合 编 写 科 学 计 算 程 序 的 语 言 而 递 归 提 高 了 程 序 的 简 洁 性 和 可 读 性, 但 是 运 行 速 度 就 受 到 了 一 定 限 制 所 以 后 来 的 Fortran 语 言 对 Fortran 77 进 行 了 改 进, 允 许 程 序 员 选 择 使 用 参 数 或 哑 元 57

第 三 章 递 归 程 序 设 计 作 为 一 个 高 级 程 序 员, 你 应 该 明 白 两 者 的 差 异 以 及 各 自 的 优 缺 点, 从 而 做 出 正 确 的 选 择 58

第 四 章 数 的 进 制 第 四 章 数 的 进 制 计 算 机 中 常 用 的 进 制 是 二 进 制, 我 们 日 常 生 活 中 常 用 的 是 十 进 制 您 可 能 会 觉 得 很 奇 怪 : 进 制 虽 然 重 要 但 并 不 很 复 杂 和 困 难, 它 有 必 要 成 为 一 本 专 门 面 向 高 级 程 序 员 的 教 材 中 单 独 的 一 章 吗? 为 了 回 答 这 个 问 题, 先 来 看 看 第 一 个 问 题 : 猜 姓 名 4.1. 猜 姓 名 问 题 90 年 代 初 的 一 天 我 在 上 海 浦 东 的 一 条 马 路 边 闲 逛 忽 然 看 见 有 一 群 人 聚 在 一 起 看 算 命 那 个 算 命 先 生 的 身 前 铺 有 七 张 纸, 每 张 纸 上 密 密 麻 麻 地 写 有 五 六 十 个 姓 氏 他 说 他 是 个 神 算 子, 只 要 告 诉 他 哪 几 张 纸 上 有 你 的 姓, 他 就 知 道 你 姓 什 么 有 这 等 怪 事? 旁 边 有 人 不 信, 拿 起 纸 来 试 了 试 结 果 百 发 百 中, 我 们 的 神 算 子 先 生 每 次 都 能 准 确 猜 出 对 方 的 姓 自 然 大 家 对 他 的 神 术 也 就 比 较 相 信 了, 有 不 少 人 掏 钱 请 他 算 了 命 当 然 这 位 神 算 子 是 个 大 骗 子, 你 能 独 立 看 出 他 的 骗 术 在 哪 里 吗? 4.1.1. 神 算 子 的 秘 密 秘 密 就 在 那 七 张 纸 上 因 为 你 必 须 首 先 告 诉 人 家 你 的 姓 出 现 在 那 几 张 纸 上, 那 么 这 七 张 纸 的 排 列 组 合 可 以 表 示 多 少 姓 氏? 这 不 难 计 算, 答 案 是 2 7-1 即 127 个 姓 氏 所 以 把 百 家 姓 中 的 每 个 姓 用 七 位 的 二 进 制 进 行 编 码, 然 后 根 据 0 或 1 决 定 相 应 的 姓 氏 是 否 要 写 到 对 应 的 纸 上 即 可 比 如 百 家 姓 中 前 八 个 姓 的 编 码 如 下 : 表 4.1-1 姓 氏 的 二 进 制 编 码 及 其 所 属 纸 张 姓 氏 Page7 Page6 Page5 Page4 Page3 Page2 Page1 1. 赵 0 0 0 0 0 0 1 2. 钱 0 0 0 0 0 1 0 3. 孙 0 0 0 0 0 1 1 4. 李 0 0 0 0 1 0 0 5. 周 0 0 0 0 1 0 1 6. 吴 0 0 0 0 1 1 0 7. 郑 0 0 0 0 1 1 1 8. 王 0 0 0 1 0 0 0 如 果 上 表 中 某 个 单 元 的 值 是 1, 则 其 横 向 对 应 的 姓 氏 就 应 该 写 到 纵 向 对 应 的 纸 上 比 如 第 一 张 纸 (Page1) 上 就 应 该 写 赵 孙 周 郑 等 姓 氏 吴 就 应 该 写 到 第 二 (Page2) 和 第 三 张 (Page3) 纸 上 现 在 你 就 可 以 表 演 神 算 子 了 比 如 有 人 告 诉 你 说 他 的 姓 氏 出 现 在 第 一 和 第 三 张 纸 上 这 意 味 着 他 的 姓 氏 的 编 码 是 0000101, 即 第 5 个 姓, 所 以 他 姓 周! 4.1.2. 神 算 子 程 序 现 在 我 们 编 一 个 程 序 模 拟 神 算 子 猜 名 字 的 过 程 这 个 程 序 一 旦 成 功, 大 家 就 可 以 上 59

第 四 章 数 的 进 制 街 骗 钱 了 如 有 收 获 务 必 记 住 给 本 书 作 者 方 博 士 分 一 半 红 如 被 警 察 或 城 管 抓 住 则 与 本 人 毫 无 关 系! 这 个 程 序 首 先 要 用 一 个 数 据 结 构 表 示 各 种 姓 氏 结 合 Java 的 实 际 情 况, 我 们 用 一 个 字 符 串 数 组 names 来 存 储 姓 氏 的 拼 音 姓 氏 在 这 个 字 符 串 数 组 中 的 下 标 就 是 它 的 编 码 问 题 是, 下 标 是 从 0 开 始 计 数 的, 而 我 们 只 能 从 1 开 始 编 码,0 是 不 能 用 的 解 决 这 个 问 题 的 办 法 有 两 个 :1) 在 进 行 下 标 和 编 码 之 间 的 转 换 时 进 行 加 1 或 减 1 操 作 ;2) 在 names 数 组 的 0 下 标 处 插 入 一 个 无 用 姓 氏 比 如 null 你 认 为 哪 个 方 法 更 好? 第 一 个 方 法 以 牺 牲 速 度 换 空 间 第 二 个 方 法 相 反, 以 多 用 一 个 单 位 空 间 换 来 下 标 和 编 码 之 间 的 直 接 对 应 他 们 之 间 还 有 一 个 更 重 要 的 差 别 : 前 者 的 代 码 要 比 后 者 复 杂 这 样 一 分 析, 你 知 道 该 使 用 哪 个 办 法 了 吧? 根 据 自 顶 向 下 的 程 序 设 计 原 则, 我 们 首 先 考 虑 主 程 序 主 程 序 首 先 调 用 getpages() 函 数 以 获 得 神 算 子 的 那 些 写 满 姓 氏 的 纸 张 然 后 循 环 执 行 playgame() 玩 这 个 游 戏 直 到 不 想 玩 为 止 主 程 序 形 如 : 例 4.1-1 package com.training.numeralsystem; import java.util.arraylist; import java.util.scanner; "Wei"; public class GuessName { public static void main(string args[]) { String[] names = {null, "Zhao", "Qian", "Sun", "Li", String pages[] = getpages(names); "Zhou", "Wu", "Zheng", "Wang", "Feng", "Chen", "Chu", Scanner scanner = new Scanner(System.in); do { playgame(names, pages); System.out.println("Play again(y/n)?"); while(!"n".equalsignorecase(scanner.nextline())); 接 下 来 我 们 的 精 力 就 可 以 分 别 集 中 在 getpages() 和 playnextgame() 两 个 子 函 数 上 4.1.2.1. getpages() 函 数 getpages() 函 数 的 目 的 是 根 据 输 入 的 所 有 姓 氏 计 算 要 准 备 多 少 张 纸, 以 及 每 张 纸 上 应 该 写 哪 些 姓 氏 可 以 这 样 考 虑 : 把 姓 氏 的 二 进 制 编 码 从 右 到 左 分 别 称 为 第 0 位 第 1 位 60

第 四 章 数 的 进 制 第 2 位, 参 见 图 4.1-1 然 后 把 要 生 成 的 纸 张 按 第 0 张 第 1 张 第 2 张 的 次 序 排 序, 依 序 考 虑 图 4.1-1 姓 氏 二 进 制 编 码 的 每 一 位 对 于 第 i 张 (i=0, 1, 2, ) 纸, 凡 是 二 进 制 编 码 的 第 i 位 是 1 的 姓 氏 都 应 该 加 入 到 这 张 纸 中 如 果 没 有 一 个 姓 氏 加 入 到 某 张 纸 中, 则 意 味 着 这 张 纸 是 多 余 的 所 以 getpages() 函 数 可 以 这 样 编 写 : 例 4.1-2 package com.training.numeralsystem; import java.util.arraylist; import java.util.scanner; public class GuessName { public static void main(string args[]) { private static String[] getpages(string[] names) { ArrayList<String> result = new ArrayList<String>(); int index = 0; String page = getpage(names, 0); while(page!= null) { result.add(page); page = getpage(names, ++index); return result.toarray(new String[result.size()]); 再 实 现 getpage(names, index) 函 数, 即 把 二 进 制 编 码 第 i 位 是 1 的 姓 氏 都 应 该 加 入 到 一 张 纸 中, 然 后 返 回 这 张 纸 如 果 没 有 一 个 姓 氏 加 入, 则 返 回 null: 例 4.1-3 package com.training.numeralsystem; 61

第 四 章 数 的 进 制 import public class GuessName { public static void main(string args[]) { private static String[] getpages(string names) { private static String getpage(string name[], int index) { String result = ""; int mask = 1 << index; for(int i = 1; i < name.length; i++) { if((i & mask) > 0) result += " " + name[i]; return result.isempty()? null : result; 4.1.2.2. playgame() 函 数 playgame(pages) 子 函 数 的 目 的 是 带 领 用 户 玩 一 次 游 戏 函 数 将 在 命 令 行 上 循 环 首 先 显 示 神 算 子 的 每 一 张 纸, 询 问 用 户 这 张 纸 上 是 否 有 他 的 姓 氏, 记 录 并 计 算 用 户 的 输 入 这 样 考 虑 未 必 是 最 优 的, 可 能 你 更 乐 意 通 过 一 个 GUI 界 面 跟 用 户 交 互 我 的 目 的 仅 仅 是 让 你 体 验 用 自 顶 向 下 的 方 法 如 何 理 清 你 自 己 头 脑 中 程 序 设 计 的 思 路 : 例 4.1-4 package com.training.numeralsystem; import java.util.arraylist; import java.util.scanner; public class GuessName { public static void main(string args[]) { private static String[] getpages(string[] names) { private static String getpage(string name[], int index) { 62

第 四 章 数 的 进 制 private static void playgame(string[] names, String pages[]) { int result = 0; int power = 1; Scanner scanner = new Scanner(System.in); for(int i = 0; i < pages.length; i++) { System.out.println(pages[i]); System.out.println("Is your family name in this line (Y/N)?"); String input = scanner.nextline(); if("y".equalsignorecase(input)) result += power; else if(!"n".equalsignorecase(input)) return; power <<= 1; System.out.println(0 < result && result < names.length? "Your family name is " + names[result] : "Your input is error."); 4.1.3. 通 用 的 神 算 子 程 序 在 前 面 程 序 中, 为 了 保 证 汉 字 的 输 入 和 显 示 正 常, 我 们 用 拼 音 来 表 示 汉 字 所 以 我 们 需 要 用 一 个 字 符 串 数 组 String[] 来 存 储 所 有 姓 氏 的 拼 音 但 有 时 我 们 可 能 希 望 直 接 使 用 汉 字, 从 而 可 以 用 类 似 于 \u0000 赵 钱 孙 李 周 吴 郑 王 这 样 的 字 符 串 来 存 储 姓 氏 这 样 我 们 就 需 要 编 写 一 个 通 用 的 程 序 以 便 剥 离 姓 氏 等 具 体 业 务 信 息, 而 把 精 力 集 中 在 编 码 的 计 算 和 转 换 上 以 下 是 这 个 通 用 程 序 的 核 心 代 码 : 例 4.1-5 package com.training.numeralsystem; import java.util.linkedlist; import java.util.list; public class BinarySystem { public static List<Integer> getnumbersspecifieddigiton(int max, int digitindex) { 63

第 四 章 数 的 进 制 List<Integer> result = new LinkedList<Integer>(); int mask = 1 << digitindex; for(int num = 1; num <= max; num++) { if((num & mask) > 0) result.add(num); return result.isempty()? null : result; 其 中 getnumbersspecifieddigiton(max, digitindex) 返 回 一 个 1 到 max 之 间 的 整 数 列 表, 其 中 每 个 整 数 的 第 digitindex 位 为 1 至 于 如 何 改 造 GuessName 以 便 使 用 这 个 通 用 函 数 留 待 读 者 考 虑 4.2. 100 瓶 药 水 有 100 瓶 药 水, 其 中 有 且 仅 有 一 瓶 是 变 质 的, 但 外 表 看 不 出 来 现 在 有 一 台 非 常 灵 敏 但 很 昂 贵 的 机 器 可 以 检 测 出 药 水 中 的 微 量 变 质 成 分 请 设 计 一 个 方 案 用 最 少 的 次 数 就 可 以 检 测 出 哪 瓶 药 水 是 变 质 的 4.2.1. 相 同 的 解 法 这 一 题 与 上 一 节 中 的 猜 姓 名 的 解 法 完 全 相 同 即 把 每 瓶 药 水 从 1 到 100 编 码 凡 编 码 二 进 制 的 第 i 位 (i=0,1,2, ) 是 1 的, 从 这 瓶 药 水 中 取 一 滴 参 与 第 i 次 检 测 每 次 检 测 的 药 水 由 从 相 应 的 药 水 瓶 中 取 出 的 若 干 滴 混 合 而 成 检 测 时 若 发 现 被 检 测 的 混 合 药 水 变 质 就 记 一 个 二 进 制 1, 否 则 记 0 最 后 把 所 有 的 0 1 凑 在 一 起 构 成 一 个 二 进 制 码, 它 的 值 是 多 少 就 意 味 着 第 几 瓶 药 水 是 变 质 的 显 然, 一 共 只 需 要 7 次 检 测 就 可 以 确 定 变 质 的 药 水 是 哪 一 瓶 由 于 方 法 相 同, 这 里 不 再 给 出 程 序 4.2.2. 二 分 法 如 果 你 认 为 上 述 二 进 制 编 码 法 理 解 起 来 有 那 么 一 点 点 困 难, 那 么 二 分 法 不 但 从 另 一 个 角 度 解 释 了 二 进 制 编 码 法, 而 且 更 容 易 理 解 : 把 所 有 药 水 分 为 两 组, 每 组 50 瓶 从 第 一 组 的 50 瓶 药 水 中 各 取 一 滴 混 合 起 来 然 后 做 第 一 次 检 测, 如 果 变 质, 则 意 味 着 变 质 药 水 在 第 一 组, 否 则 就 在 第 二 组 50 瓶 中 把 确 定 存 在 变 质 药 水 的 50 瓶 药 水 再 分 为 两 组, 每 组 25 瓶, 重 复 上 述 检 测 同 样 仅 需 要 经 过 7 次 检 测 也 可 以 确 定 变 质 的 药 水 是 哪 一 瓶 二 分 法 的 实 质 是 把 一 个 数 (100) 不 断 的 除 以 2 的 过 程 它 实 质 上 与 二 进 制 编 码 法 是 等 价 的 科 学 在 这 里 又 巧 妙 地 表 演 了 一 次 殊 路 同 归 4.3. 十 二 个 小 球 问 题 有 12 个 外 形 一 模 一 样 的 小 球 和 一 架 天 平 有 且 仅 有 一 个 小 球 的 重 量 与 其 他 小 球 不 同, 64

第 四 章 数 的 进 制 可 能 重 些 也 可 能 轻 些, 但 外 表 看 不 出 来 其 他 小 球 则 重 量 完 全 一 样 现 在 要 求 你 用 天 平 仅 称 三 次, 就 能 把 那 个 与 众 不 同 的 小 球 找 出 来 还 要 知 道 它 是 轻 的 还 是 重 的 如 果 你 是 第 一 次 接 触 这 道 题, 那 么 请 不 要 认 为 这 道 题 很 容 易 实 际 上 它 在 我 遇 到 的 所 有 智 力 题 中 几 乎 是 最 难 的 我 大 概 是 1990 年 第 一 次 遇 到 这 道 题, 至 今 近 20 年 了, 从 没 有 遇 到 一 个 人 独 立 解 决 这 道 题! 当 然 如 果 你 尝 试 之 后 觉 得 它 太 难 你 可 以 很 容 易 从 网 上 或 本 书 下 面 说 明 中 获 得 答 案 4.3.1. 人 工 解 把 12 个 小 球 分 成 3 组, 每 组 4 个 先 用 天 平 称 第 一 组 和 第 二 组 第 一 组 在 左, 第 二 组 在 右 这 时 会 有 三 种 情 况 : 1) 左 边 重 右 边 轻, 参 见 图 4.3-1 这 意 味 着 坏 球 如 果 是 重 球 的 话 一 定 在 第 一 组 中, 如 果 是 轻 球 的 话 一 定 在 第 二 组 中 图 4.3-1 第 一 次 称 量 第 一 种 情 况 : 左 边 重 右 边 轻 现 在 从 第 二 组 中 任 意 取 出 3 个 放 到 一 边 ( 注 意, 这 3 个 球 中 存 在 可 能 的 轻 球 ), 留 下 1 个 仍 然 在 右 边 托 盘 上 再 从 左 边 第 一 组 中 任 取 出 3 个 放 到 天 平 右 边 托 盘 上 再 从 第 三 组 中 取 3 个 好 球 放 在 天 平 左 边 托 盘 上, 进 行 第 二 次 称 量 参 见 图 4.3-2 65

第 四 章 数 的 进 制 图 4.3-2 在 第 一 种 情 况 下 移 动 小 球 图 4.3-3 第 一 种 情 况 下 的 第 二 次 称 量 图 4.3-3 显 示 天 平 第 二 次 称 这 时 又 有 三 种 可 能 : 天 平 平 衡 这 意 味 着 放 到 旁 边 去 的 3 个 第 二 组 的 球 中 必 有 一 个 坏 球, 而 且 还 一 定 是 个 轻 球 从 中 任 取 两 个 放 到 天 平 两 端 作 第 三 次 称 量 : 若 平 衡, 则 确 定 唯 一 剩 下 的 那 个 第 二 组 的 球 是 坏 的 轻 球 ; 或 不 平 衡 则 轻 的 那 端 是 坏 球 左 边 轻 右 边 重, 即 与 图 4.3-1 相 反 这 意 味 着 刚 才 从 左 边 移 到 右 边 的 3 个 第 一 组 的 球 中 有 坏 球 并 且 是 个 重 球 从 中 任 取 两 个 放 到 天 平 两 端 作 第 三 次 称 量 : 若 平 衡, 则 确 定 唯 一 剩 下 的 那 个 第 一 组 的 球 是 坏 的 重 球 ; 或 不 平 衡 则 重 的 那 端 是 坏 球 左 边 重 右 边 轻, 即 与 图 4.3-1 相 同 这 意 味 着 如 果 坏 球 是 个 重 球 的 话 那 它 一 定 是 左 边 托 盘 里 唯 一 剩 下 的 那 个 第 一 组 的 球 ; 如 果 坏 球 是 个 轻 球 的 话 那 它 一 定 是 右 边 托 盘 里 唯 一 剩 下 的 那 个 第 二 组 的 球 我 们 拿 起 其 66

第 四 章 数 的 进 制 中 的 一 个 跟 一 个 好 球 称 一 称 就 行 了 2) 第 一 次 称 时 如 果 左 边 轻 右 边 重, 这 种 情 况 跟 图 4.3-1 所 示 的 情 况 是 对 称 的 按 照 上 文 的 讨 论 我 们 只 需 再 称 两 次 就 必 然 可 以 找 到 那 个 坏 球 还 知 道 轻 重 3) 最 后 一 种 情 况 就 是 第 一 次 称 时 两 边 平 衡 那 坏 球 一 定 在 第 三 组 中 我 们 从 中 任 取 3 个 和 1 个 好 球 一 起 如 图 4.3-4 所 示 那 样 进 行 第 二 次 称 量 4.3.2. 计 算 机 解 图 4.3-4 第 一 次 称 量 平 衡 时 的 第 二 次 称 量 这 样 就 有 三 种 情 况 : 平 衡 则 唯 一 剩 下 的 那 个 第 三 组 的 球 是 坏 球, 我 们 再 用 天 平 把 它 和 一 个 好 球 称 一 下 就 知 道 它 是 轻 的 还 是 重 的 左 边 重 右 边 轻 这 意 味 着 如 果 坏 球 是 个 重 球 的 话, 那 它 就 是 左 边 托 盘 里 唯 一 的 那 个 第 三 组 的 球 ; 如 果 坏 球 是 个 轻 球 的 话, 那 它 一 定 是 右 边 托 盘 里 两 个 球 之 一 我 们 把 右 边 的 两 个 球 放 到 天 平 的 两 端 作 第 三 次 称 量 : 如 果 平 衡, 则 图 4.3-4 中 左 边 唯 一 一 个 第 三 组 的 球 是 坏 球, 并 且 是 个 重 球 ; 如 果 不 平 衡, 则 轻 的 那 端 是 坏 球 左 边 轻 右 边 重 这 种 情 况 跟 上 面 情 况 是 对 称 的, 把 上 面 文 字 中 轻 重 两 个 字 交 换 即 可 说 明 这 种 情 况 如 果 我 跟 你 说 12 个 小 球 问 题 可 以 编 一 个 程 序 来 解, 而 且 这 个 程 序 并 不 复 杂, 你 相 信 吗? 计 算 机 科 学 的 一 个 巨 大 魅 力 就 在 于 她 能 让 计 算 机 做 出 许 多 不 可 思 议 的 事 情, 包 括 解 这 个 用 人 脑 要 想 破 头 的 12 小 球 问 题 为 什 么 人 类 习 惯 使 用 十 进 制 呢? 因 为 人 的 两 只 手 恰 好 有 十 个 手 指 头, 计 数 方 便 如 果 外 星 人 有 八 个 手 指 头, 那 我 敢 肯 定 他 们 常 用 的 是 八 进 制 不 信 你 就 逮 一 个 外 星 人 给 我 看 看? 计 算 机 为 什 么 要 用 二 进 制 呢? 因 为 绝 大 多 数 电 子 元 器 件 的 状 态 有 两 种 : 接 通 或 关 闭 电 流 高 或 低 磁 性 有 或 无 如 果 外 星 人 的 元 器 件 的 状 态 主 要 有 三 种 的 话 我 相 信 他 们 的 计 算 机 会 使 用 三 进 制 所 以 二 进 制 也 好, 十 进 制 也 好, 八 进 制 也 好, 甚 至 三 进 制 也 好, 本 身 并 无 孰 优 孰 劣 计 数 的 能 力 也 是 相 同 的 ( 如 果 你 愿 意 甚 至 用 一 进 制 也 行 在 后 面 章 节 中 我 就 会 提 到 一 进 制 ) 差 别 仅 在 于 用 起 来 是 否 方 便 67