Java 大师之路
|
|
- 总取 路
- 7 years ago
- Views:
Transcription
1 方 林 2008 年 12 月
2 序 如 何 成 为 一 名 Java 程 序 设 计 的 专 家 和 大 师 呢? 这 是 困 扰 程 序 员 软 件 工 程 师 和 资 深 软 件 工 程 师 的 一 大 难 题 很 多 毕 业 5 6 年 的 软 件 工 程 师 在 有 了 一 定 的 Java 程 序 设 计 经 验 和 动 手 能 力 之 后, 往 往 会 遇 到 相 当 长 一 段 时 间 的 技 术 瓶 颈 期 很 多 人 在 此 期 间 在 技 术 和 动 手 能 力 上 几 乎 再 也 无 法 得 到 实 质 性 提 高 有 的 认 为 程 序 设 计 不 过 如 此, 发 出 了 还 有 什 么 我 编 不 了 的 程 序 呢? 的 疑 问 ; 更 多 的 人 则 厌 倦 了 千 篇 一 律 毫 无 趣 味 的 程 序 设 计 工 作, 转 行 当 了 项 目 经 理 这 本 书 就 是 写 给 那 些 有 了 一 定 程 序 设 计 经 验, 还 没 有 厌 倦 程 序 设 计, 但 是 不 知 道 如 何 进 一 步 提 高 的 人 看 的 作 为 我 的 目 标 读 者, 你 们 可 能 更 多 地 是 靠 个 人 经 验 编 写 Java 程 序 也 许 你 们 编 写 了 很 多 年 程 序, 积 累 了 丰 富 的 Java 编 程 经 验, 非 常 熟 悉 Java 语 法 和 J2EE 上 的 各 种 开 源 工 具, 这 也 是 一 部 分 人 之 所 以 骄 傲 的 理 由 但 是 个 人 经 验 永 远 也 不 能 与 积 累 了 几 百 年 或 上 百 年 的 数 学 和 计 算 机 理 论 相 提 并 论 后 者 所 提 供 的 方 法 早 就 被 证 明 了 是 程 序 设 计 的 最 简 单 最 直 接 最 容 易 的 方 法 所 以 如 果 你 还 没 有 有 意 识 地 系 统 地 使 用 你 在 大 学 期 间 学 习 的 计 算 机 科 学 理 论 和 数 学 知 识 指 导 程 序 设 计 ( 比 如 你 不 知 道 编 译 原 理 除 了 对 开 发 编 译 程 序 有 用 外 在 一 般 的 程 序 设 计 中 还 有 什 么 用 ), 那 么 这 本 书 就 特 别 适 合 你 这 本 书 的 目 的 在 于 揭 示 数 学 和 计 算 机 科 学 理 论 在 (Java) 程 序 设 计 中 的 重 要 作 用 和 价 值, 帮 助 你 突 破 个 人 经 验 的 桎 梏, 深 刻 理 解 隐 藏 在 Java 语 法 背 后 的 奥 秘 希 望 读 完 这 本 书 之 后, 你 能 够 轻 松 度 过 上 面 提 到 的 那 个 技 术 瓶 颈 期, 真 正 意 识 到 数 学 和 计 算 机 理 论 的 重 要 作 用, 从 而 为 成 为 Java 程 序 设 计 方 面 的 专 家 和 大 师 打 下 坚 实 的 理 论 基 础 2
3 目 录 3 目 录 第 一 章 引 言 兴 趣 才 是 学 习 的 主 要 动 力 计 算 机 科 学 理 论 的 趣 味 在 哪 里? 本 书 跟 学 习 计 算 机 理 论 无 关 对 你 的 要 求... 9 第 二 章 自 顶 向 下 的 程 序 设 计 的 阶 乘 错 误 的 解 法 使 用 BigInteger? 自 己 定 义 状 态 可 变 的 大 整 数 关 于 恒 类 (immutable class) 通 过 这 个 例 子 你 学 到 了 什 么? 五 猴 分 桃 问 题 一 个 容 易 的 解 法 一 点 改 进 考 虑 任 意 个 猴 子 第 二 点 改 进 加 大 步 长 逆 向 思 维 数 学 解 第 三 章 递 归 程 序 设 计 递 归 和 数 学 归 纳 法 第 一 个 例 子 Hanoi 塔 递 归 背 后 的 数 学 原 理 Hanoi 塔 问 题 的 递 归 解 一 些 有 趣 的 递 归 程 序 字 符 串 通 配 符 匹 配 兔 子 组 合 和 排 列 组 合 排 列 人 字 形 的 铁 路 五 升 的 杯 子 和 三 升 的 杯 子 倒 出 四 升 水 错 误 的 递 归 新 参 数 组 合 一 定 要 更 接 近 于 边 界 保 存 状 态 法 递 归 程 序 非 递 归 化 函 数 调 用 的 实 质 函 数 返 回 时 应 该 返 回 到 下 一 行 用 堆 栈 来 保 存 返 回 地 址 运 行 堆 栈 还 用 来 保 存 参 数 返 回 地 址 入 栈 的 次 序 参 数 入 栈 的 次 序 与 可 变 参 数 Java 的 可 变 参 数 是 另 一 回 事 控 制 运 行 堆 栈 的 代 码 应 该 放 在 哪 里? cdecl 和 pascal 申 明 运 行 堆 栈 常 用 来 保 存 哪 些 数 据? 递 归 调 用 与 一 般 函 数 调 用 非 递 归 中 序 遍 历... 43
4 目 录 递 归 程 序 非 递 归 化 示 例 第 一 步 : 给 代 码 的 每 一 个 行 加 行 号 第 二 步 : 使 用 Stack, push(), pop() 和 goto 替 换 递 归 调 用 第 三 步 : 用 while 替 换 if 和 goto 第 四 步 : 用 while 循 环 处 理 返 回 地 址 第 五 步 : 消 除 最 后 的 goto 30 语 句 第 六 步 : 删 除 goto 第 七 步 : 用 30 取 代 返 回 地 址 第 八 步 : 提 前 执 行 弹 出 操 作 第 九 步 : 删 除 与 返 回 地 址 60 有 关 的 操 作 第 十 步 : 返 回 地 址 30 也 不 需 要 了 第 十 一 步 : 消 除 node 与 stack 栈 顶 的 重 复 哑 元 与 不 可 递 归 性 什 么 是 哑 元 哑 元 与 参 数 的 差 别 第 四 章 数 的 进 制 猜 姓 名 问 题 神 算 子 的 秘 密 神 算 子 程 序 getpages() 函 数 playgame() 函 数 通 用 的 神 算 子 程 序 瓶 药 水 相 同 的 解 法 二 分 法 十 二 个 小 球 问 题 人 工 解 计 算 机 解 小 球 的 三 进 制 编 码 调 整 编 码 开 始 称 天 平 程 序 囚 犯 问 题 用 一 进 制 解 决 问 题 用 程 序 模 拟 解 的 过 程 第 五 章 继 承 接 口 和 代 理 动 态 定 连 什 么 是 动 态 定 连 动 态 定 连 是 如 何 实 现 的 C++ 是 如 何 实 现 动 态 定 连 的 抽 象 函 数 不 能 是 静 态 (static) 的 为 什 么 JAVA 不 支 持 多 继 承 不 支 持 多 继 承 并 非 仅 仅 是 个 语 法 规 定 分 布 式 开 发 与 多 继 承 Java 语 言 必 须 提 供 中 间 代 码 Java 语 言 不 支 持 多 继 承 接 口 中 不 能 定 义 成 员 变 量 类 变 量 和 函 数 体 接 口 中 不 能 有 成 员 变 量 和 类 变 量 却 可 以 有 类 常 数 为 什 么 接 口 中 的 函 数 没 有 同 样 问 题?
5 目 录 同 名 变 量 或 常 数 接 口 中 的 函 数 只 能 是 公 开 (PUBLIC) 的 静 态 定 连 和 动 态 定 连 protected 的 真 正 含 义 接 口 中 的 方 法 法 只 能 是 公 开 的 外 部 接 口 和 类 可 以 是 受 保 护 的 吗? 接 口 的 实 现 接 口 中 不 能 定 义 函 数 体 接 口 的 静 态 实 现 接 口 的 动 态 实 现 代 理 (Proxy) 就 是 接 口 的 动 态 实 现 接 口 的 动 态 实 现 与 代 理 设 计 模 式 的 差 别 小 结 第 六 章 常 用 设 计 模 式 的 实 质 事 件 监 听 (EVENT-LISTENER) 模 式 事 件 类 监 听 器 添 加 和 删 除 监 听 器 深 入 思 考 之 一 : 避 免 重 复 以 及 同 步 深 入 思 考 之 二 : 异 步 执 行 监 听 函 数 事 件 的 触 发 事 件 监 听 模 式 的 实 质 是 回 调 事 件 监 听 模 式 应 用 工 厂 (FACTORY) 模 式 工 厂 模 式 的 实 质 工 厂 模 式 的 典 型 示 例 Spring 的 工 厂 模 式 单 例 (SINGLETON) 模 式 可 替 换 的 单 例 不 可 替 换 的 单 例 静 态 方 法 封 装 代 理 模 式 (PROXY PATTERN) 什 么 是 代 理 模 式 代 理 的 作 用 JDK 中 的 代 理 设 计 模 式 的 示 例 代 理 的 一 些 细 节 装 饰 (DECORATOR) 模 式 与 代 理 模 式 的 相 似 性 和 差 异 为 什 么 不 使 用 继 承 适 配 器 (ADAPTER) 模 式 与 装 饰 模 式 的 相 似 性 和 差 异 适 配 器 的 制 作 桥 接 (BRIDGE) 模 式 桥 接 模 式 的 实 质 桥 接 模 式 的 应 用 桥 接 模 式 的 代 价 面 板 (FACADE) 模 式 什 么 是 面 板 模 式 JDK 中 的 面 板 模 式
6 目 录 6.9. 创 建 者 (BUILDER) 模 式 创 建 者 模 式 和 工 厂 模 式 的 差 别 创 建 者 模 式 示 例 第 七 章 搜 索 搜 索 和 搜 索 树 最 短 路 径 问 题 关 于 搜 索 树 的 若 干 理 论 关 于 搜 索 树 的 若 干 错 误 理 解 关 于 搜 索 树 的 重 要 假 设 通 用 搜 索 算 法 文 字 描 述 的 通 用 搜 索 算 法 状 态 接 口 访 问 者 接 口 搜 索 引 擎 核 心 数 据 结 构 类 型 处 理 访 问 者 搜 索 引 擎 核 心 代 码 八 数 码 问 题 通 用 打 印 程 序 八 数 码 问 题 的 主 程 序 八 数 码 状 态 中 的 数 据 结 构 八 数 码 状 态 的 辅 助 函 数 八 数 码 状 态 的 核 心 程 序 华 容 道 问 题 华 容 道 问 题 的 主 程 序 华 容 道 状 态 的 数 据 结 构 和 辅 助 类 型 华 容 道 状 态 的 初 步 定 义 华 容 道 状 态 的 核 心 程 序 倒 水 问 题 倒 水 问 题 的 主 程 序 倒 水 问 题 的 状 态 A* 搜 索 A* 搜 索 与 通 用 搜 索 的 差 异 估 计 耗 费 是 实 际 耗 费 的 下 限 A* 算 法 中 数 据 结 构 的 变 化 A* 算 法 的 Java 实 现 结 束 语 第 八 章 博 弈 博 弈 和 搜 索 博 弈 和 搜 索 的 异 同 得 分 简 单 博 弈 算 法 博 弈 树 的 扩 展 布 局 接 口 Layout 简 单 博 弈 算 法 第 九 章 模 式 识 别 一 维 模 式 识 别
7 目 录 第 十 章 编 译 技 术 单 词 句 子 和 语 法 自 顶 向 下 递 归 子 程 序 第 十 一 章 多 线 程 生 产 者 - 消 费 者 Buffer 舞 会 问 题 : 一 种 特 殊 的 生 产 者 消 费 者 问 题 水 分 子 诞 生 一 对 多 的 配 对 问 题 多 对 多 的 配 对 问 题 读 写 问 题 一 般 读 写 问 题 桥 模 拟 电 梯 第 十 二 章 JAVA 的 高 级 话 题 关 于 JAVA 的 一 些 错 误 认 识 Java 中 不 含 有 指 针 为 什 么 interface 可 以 多 实 现 两 种 类 型 的 集 合 (SET) 弱 连 接... ERROR! BOOKMARK NOT DEFINED 垃 圾 回 收 和 释 放... Error! Bookmark not defined 弱 连 接... Error! Bookmark not defined 代 理 (PROXY) 定 义 和 使 用 自 己 的 标 注 (ANNOTATION) 范 型 范 型 与 数 组 自 说 明 的 范 型 内 部 类 内 部 类 与 外 部 类 的 异 同 静 态 内 部 类 与 动 态 内 部 类
8 第 一 章 引 言 1.1. 兴 趣 才 是 学 习 的 主 要 动 力 第 一 章 引 言 你 学 习 计 算 机 科 学 理 论 ( 如 数 据 结 构 编 译 原 理 等 ) 时 是 不 是 很 刻 苦? 先 别 急 着 回 答 是 或 者 不 是 请 先 想 想 学 习 真 的 必 须 是 一 件 苦 差 事 吗? 你 可 能 会 觉 得 奇 怪 : 学 习 不 是 苦 事, 难 道 是 一 件 乐 事 不 成? 与 你 的 想 象 相 反, 学 习 计 算 机 科 学 理 论 的 确 可 以 成 为 一 件 很 有 趣 味 很 好 玩 的 事 情 无 论 学 习 什 么, 如 果 你 不 得 不 刻 苦, 不 得 不 硬 着 头 皮, 结 果 居 然 还 能 学 得 好 能 够 学 以 致 用 能 够 自 愿 地 钻 研 它, 那 不 是 天 方 夜 谭 吗? 我 从 不 认 为 达 尔 文 牛 顿 和 爱 因 斯 坦 会 觉 得 他 们 的 学 习 和 研 究 是 一 件 苦 差 事, 恰 恰 相 反, 他 们 一 定 从 中 获 得 了 巨 大 的 快 乐 也 许 我 们 并 无 雄 心 去 获 得 象 他 们 那 么 大 的 成 就, 但 是 享 受 学 习 和 研 究 的 快 乐 还 是 做 得 到 的 想 想 看, 为 什 么 几 乎 没 有 人 认 为 打 电 脑 游 戏 是 一 件 苦 差 事? 就 连 那 些 最 反 对 子 女 打 游 戏 的 家 长, 自 己 打 起 游 戏 来 也 是 乐 此 不 疲 毫 不 含 糊 的 我 敢 说, 看 我 这 本 书 的 读 者 99% 都 有 过 通 宵 打 游 戏 的 经 历,99% 为 打 游 戏 饿 过 肚 子 就 连 我, 昨 天 晚 上 在 电 脑 上 下 围 棋 还 下 到 半 夜 两 点 半, 被 我 夫 人 好 一 通 数 落 所 以 说 我 们 打 游 戏 的 劲 头 真 的 可 以 用 废 寝 忘 食 通 宵 达 旦 来 形 容 这 股 子 劲 头 如 果 用 来 学 习, 你 的 领 导 同 事 老 师 或 父 母 一 定 会 感 到 非 常 欣 慰 只 可 惜 我 们 通 常 是 被 迫 学 习 的, 真 正 对 学 习 感 兴 趣 的 人 凤 毛 麟 角 问 题 是, 为 什 么 打 游 戏 我 们 就 能 刻 苦, 学 习 就 不 行 了 呢? 原 因 很 简 单 : 打 游 戏 我 们 感 兴 趣 啊 如 果 学 习 我 们 也 能 感 兴 趣 的 话 这 并 不 是 不 可 能 的 我 们 就 不 会 需 要 别 人 来 督 促 和 鞭 策 了, 我 们 自 己 就 会 自 动 地 学 习 和 钻 研! 至 于 刻 苦 学 习 之 类 其 实 误 人 子 弟 的 说 教, 对 我 们 来 说 就 会 是 一 个 笑 话 画 匠 和 画 家 有 什 么 差 异? 歌 星 和 歌 唱 家 的 区 别 是 什 么? 你 想 成 为 一 个 高 级 程 序 员, 还 是 成 为 一 名 程 序 设 计 大 师? 如 果 你 刻 苦 学 习, 那 么 你 最 多 能 成 为 一 个 好 一 点 的 画 匠 歌 星 或 高 级 程 序 员 但 是 如 果 你 想 成 为 一 名 画 家 歌 唱 家 或 者 程 序 设 计 大 师, 那 你 必 须 能 够 享 受 编 程 所 带 来 的 快 乐! 1.2. 计 算 机 科 学 理 论 的 趣 味 在 哪 里? 这 本 书 是 写 给 有 一 定 程 序 设 计 经 验 的 Java 软 件 工 程 师 和 资 深 软 件 工 程 师 看 的 你 还 记 得 计 算 机 科 学 包 括 哪 些 主 要 分 支 和 科 目 吗? 答 案 是 : 数 据 结 构 人 工 智 能 编 译 原 理 操 作 系 统 计 算 机 算 法 高 级 程 序 设 计 语 言 理 论 模 式 识 别 计 算 数 学 高 等 数 学 离 散 数 学 当 然, 计 算 机 理 论 远 远 不 止 这 些 但 是 第 一, 目 前 大 学 本 科 阶 段 学 习 的 计 算 机 理 论 8
9 第 一 章 引 言 主 要 就 是 这 些 了 ; 第 二, 能 真 正 理 解 和 掌 握 这 些 理 论 你 就 已 经 很 不 错 了, 完 全 有 资 格 召 开 新 闻 发 布 会 宣 布 自 己 是 程 序 设 计 大 师 了 要 不 要 兴 冲 冲 地 马 上 就 去 约 见 记 者? 且 慢! 学 过 与 掌 握 根 本 就 是 两 回 事 你 学 过 数 据 结 构 是 吧? 那 你 说 说 你 在 软 件 公 司 实 际 开 发 软 件 项 目 时, 如 何 使 用 二 叉 树 及 其 遍 历 算 法 的? 傻 眼 了 吧? 当 年 你 学 过 数 据 结 构 考 完 试 之 后 你 就 把 劳 什 子 二 叉 树 丢 到 爪 哇 国 去 了 进 公 司 搞 项 目 开 发 也 全 凭 个 人 经 验 来, 反 正 无 非 就 是 搜 索 统 计 排 序, 烦 是 烦 得 要 死, 难 却 难 不 到 哪 去, 哪 里 还 用 得 着 什 么 二 叉 树! 这 就 是 你 只 能 开 发 一 些 普 通 应 用, 却 不 能 开 发 大 型 应 用 大 规 模 应 用, 不 能 开 发 系 统 软 件 平 台 软 件 的 原 因! 你 不 相 信? 你 会 说 : 我 开 发 的 那 些 应 用 也 是 大 规 模 应 用, 我 不 也 搞 成 了 么? 也 没 二 叉 树 什 么 事! 唉! 一 身 叹 息 曾 经 沧 海 难 为 水, 除 却 巫 山 不 是 云 你 的 那 些 大 规 模 应 用, 在 大 师 ( 比 如 我 ) 的 眼 里, 不 过 是 小 菜 一 碟 只 要 你 没 有 应 用 数 学 和 计 算 机 理 论 做 指 导, 你 的 那 些 大 规 模 应 用 就 像 大 棚 蔬 菜 上 面 的 薄 膜, 大 是 够 大 的, 却 没 有 什 么 厚 度 这 么 说 吧 : 你 一 定 很 熟 悉 Tomcat 吧? 你 能 不 能 照 着 Tomcat 的 样 子 也 开 发 一 个 应 用 服 务 器 玩 玩? 你 肯 定 大 惊 失 色 : 那 是 Apache 的 那 帮 牛 人 搞 的, 我 怎 么 能 跟 他 们 比? 问 题 是,Apache 的 那 帮 人 固 然 很 牛, 但 也 是 吃 五 谷 杂 粮 的, 也 没 见 头 上 长 了 一 个 角 他 们 能 搞 出 Tomcat 以 及 一 大 堆 叫 人 眼 花 缭 乱 的 系 统 软 件 和 平 台 软 件 的 原 因 不 是 因 为 他 们 是 神, 而 是 因 为 他 们 用 数 学 和 计 算 机 理 论 指 导 了 自 己 的 设 计 和 编 程 如 果 你 学 会 了 用 数 学 和 计 算 机 理 论 指 导 编 程, 而 不 是 闭 着 眼 睛 瞎 编, 那 么 你 也 能 搞 出 Tomcat Eclipse Struts Hibernate 或 Spring 等 这 么 复 杂 的 系 统 平 台 或 框 架 出 来 即 使 开 发 一 般 应 用, 你 的 程 序 也 会 显 得 简 洁 容 易 扩 展 容 易 阅 读 容 易 排 错 你 就 会 明 白 程 序 越 简 洁 功 能 反 而 越 强 大 的 道 理, 以 及 为 什 么 会 有 空 间 效 率 时 间 效 率 同 时 提 高 的 事 情 发 生 1.3. 本 书 跟 学 习 计 算 机 理 论 无 关 计 算 机 理 论 所 涉 及 到 的 科 目 有 那 么 多, 但 是 本 书 并 不 试 图 详 细 讲 解 这 些 理 论 的 每 一 个 方 面 这 是 因 为 一 方 面 你 的 教 科 书 已 经 很 好 地 完 成 了 这 个 任 务 ; 另 一 方 面 如 果 这 样 的 话 这 本 书 就 会 有 好 几 千 页 那 么 您 购 买 这 本 书 的 成 本 就 会 跟 您 一 年 的 大 学 学 费 差 不 多 虽 然 我 认 为 花 一 年 的 学 费 学 一 点 真 正 有 用 的 东 西 比 在 大 学 里 忙 着 追 女 孩 要 有 意 义 得 多, 也 有 助 于 您 毕 业 以 后 在 真 正 应 该 追 女 孩 的 时 候 提 高 自 己 的 竞 争 力, 但 问 题 是 您 购 买 这 本 书 的 经 济 承 受 力 和 兴 趣 也 会 大 大 降 低 所 以 我 只 是 让 你 体 验 为 什 么 那 些 计 算 机 科 学 理 论 是 有 趣 的 好 玩 的, 它 怎 么 就 帮 你 编 出 别 人 不 能 或 很 难 编 出 的 程 序 甚 至 我 可 能 并 不 一 开 场 就 提 及 那 些 曾 经 让 你 万 分 讨 厌 的 概 念 ( 比 如 二 叉 树 ) 或 理 论 名 词, 而 是 在 不 知 不 觉 中 让 你 自 己 ( 记 住 : 是 你 自 己, 而 不 是 我 ) 发 现 或 者 推 导 出 理 论 当 你 体 验 到 了 这 种 快 乐, 发 现 自 己 也 可 以 象 福 尔 摩 斯 那 样 进 行 推 理 时, 你 自 然 而 然 就 会 回 头 翻 出 教 科 书 或 者 上 网 进 行 详 细 学 习 就 像 你 打 电 脑 游 戏 一 样, 根 本 就 不 需 要 别 人 督 促 你 1.4. 对 你 的 要 求 首 先, 这 本 书 不 是 写 给 程 序 设 计 初 学 者 看 的 它 的 目 标 读 者 是 那 些 已 经 很 会 编 程 序, 但 是 想 更 进 一 步 提 高 的 人 您 最 好 至 少 自 学 过 数 据 结 构 操 作 系 统 和 计 算 机 组 成 比 如 你 9
10 第 一 章 引 言 知 道 什 么 是 二 叉 树 参 数 传 递 堆 栈 和 补 码 等 如 果 你 还 学 习 过 编 译 原 理 人 工 智 能 高 级 程 序 设 计 语 言 理 论 或 计 算 机 算 法, 那 就 更 好 了 你 会 获 得 更 多 的 快 乐 相 反, 对 于 初 学 者 来 说, 有 很 多 理 论 和 概 念 您 是 不 清 楚 的 一 本 书 如 果 读 不 顺 畅 的 话, 是 很 难 耐 心 读 下 去 的 而 耐 心 读 书 恰 恰 是 我 最 不 希 望 发 生 的 其 次, 这 本 书 是 用 Java 语 言 写 例 子 程 序 的 所 以 你 应 该 比 较 熟 悉 Java 语 言 了 最 好 有 两 到 三 年 以 上 Java 编 程 经 验 能 够 较 深 刻 地 理 解 封 装 继 承 接 口 重 定 义 等 概 念 还 是 那 句 话, 我 们 不 是 写 给 初 学 者 看 的 第 三, 你 本 来 就 对 程 序 设 计 有 兴 趣 只 是 不 知 道 如 何 更 进 一 步 提 高 更 关 键 的 是 : 你 目 前 还 无 法 做 到 在 程 序 设 计 过 程 中 显 示 地 自 然 而 然 地 主 动 地 应 用 计 算 机 理 论 和 数 学 知 识 那 是 不 是 说 这 本 书 只 适 合 于 计 算 机 或 相 关 专 业 的 人 呢? 不 是 因 为 有 很 多 非 计 算 机 或 相 关 专 业 的 人 编 程 序 却 很 在 行, 甚 至 自 学 了 计 算 机 专 业 的 课 程 这 些 自 学 的 人 往 往 比 专 业 学 生 更 有 兴 趣 学 习 我 本 人 虽 然 是 计 算 机 专 业 毕 业, 甚 至 硕 士 和 博 士 也 都 是 计 算 机 软 件 专 业 毕 业, 但 是 其 实 大 多 数 课 程 是 我 自 学 的 这 是 因 为 我 对 编 程 太 有 兴 趣 了, 当 年 上 课 的 时 候 我 根 本 就 等 不 及 教 师 慢 悠 悠 的 讲 课 进 度 老 师 在 上 面 讲 到 第 二 章 的 时 候, 我 在 下 面 已 经 看 到 第 八 章 了 我 急 于 想 知 道 科 学 家 们 又 讲 了 什 么 有 趣 好 玩 的 新 知 识, 以 至 于 我 可 以 用 来 编 出 让 同 学 们 不 可 思 议 的 程 序 所 以 专 业 不 专 业 什 么 的 根 本 不 重 要 10
11 第 二 章 自 顶 向 下 的 程 序 设 计 第 二 章 自 顶 向 下 的 程 序 设 计 计 算 机 科 学 理 论 就 像 数 学, 真 正 需 要 你 牢 记 的 公 理 就 那 么 几 条, 其 他 的 都 是 定 理 什 么 是 定 理? 定 理 就 是 从 公 理 和 概 念 直 接 或 间 接 推 导 出 来 的 结 论 我 们 进 行 程 序 设 计 的 第 一 条 公 理 就 是 : 程 序 设 计 应 该 遵 循 自 顶 向 下 先 整 体 后 局 部 的 原 则 下 面 让 我 们 看 一 个 求 100 阶 乘 的 简 单 例 子 的 阶 乘 我 们 来 编 第 一 个 程 序 : 求 100 的 阶 乘 ( 即 ) 的 精 确 解 例 如 2!=2, 3!=6,4!=24, 错 误 的 解 法 也 许 对 于 一 个 象 您 这 样 的 熟 手 来 说, 求 100 的 阶 乘 是 不 是 太 简 单 了? 只 需 从 1 到 100 连 乘 100 次 不 就 行 了? 您 也 许 一 分 钟 就 可 以 把 程 序 搞 定, 比 如 : 例 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 能 表 示 的 最 大 整 数 只 能 是 , 大 约 是 20 亿 而 13 的 阶 乘 就 已 经 超 过 62 亿 何 况 100? 所 以 int 型 是 远 远 不 够 的 那 么 用 long 型 行 不 行? 也 不 行 long 型 占 8 个 字 节 最 大 的 long 型 值 是 , 约 900 亿 亿 这 个 数 虽 然 已 经 不 小 了, 但 是 对 于 100 的 阶 乘 来 说, 恐 怕 连 杯 水 车 薪 都 谈 不 上 因 为 900 亿 亿 不 过 是 19 个 十 进 制 位 而 100 的 阶 乘 有 多 少 十 进 制 位?158 个! 使 用 BigInteger? 对 于 一 个 象 你 一 样 的 Java 高 手 来 说, 问 题 还 是 不 难 解 决 你 可 以 使 用 BigInteger 这 11
12 第 二 章 自 顶 向 下 的 程 序 设 计 个 类 来 代 替 int, 并 用 BigInteger 的 multiply() 函 数 代 替 int 型 的 乘 法 运 算 即 可 比 如 : 例 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-2, 请 特 别 注 意 例 中 的 两 个 注 释 虽 然 我 们 把 数 据 的 类 型 从 int 改 为 BigInteger, 但 是 程 序 的 逻 辑 并 没 有 发 生 丝 毫 改 变 所 以 我 们 进 行 软 件 设 计 时, 就 应 该 按 照 算 法 的 逻 辑 进 行 设 计, 至 于 用 什 么 进 行 实 现, 是 用 int 还 是 用 BigInteger 相 对 于 设 计 来 说 是 不 那 么 重 要 的 也 就 是 说 设 计 比 实 现 更 重 要 以 后 在 提 到 Java 的 接 口 和 类 时, 我 们 还 会 讲 到 这 一 点 显 然 例 的 确 能 够 漂 亮 地 给 出 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 的 一 个 负 担 ; 第 二, 内 存 请 求 则 是 不 可 推 迟 的, 必 须 当 场 得 到 回 应 这 意 味 着 被 占 用 的 内 存 数 量 会 越 来 越 大 自 己 定 义 状 态 可 变 的 大 整 数 如 果 想 解 决 这 个 问 题, 我 们 可 以 自 己 定 义 一 个 状 态 可 变 的 大 整 数 类 型 MutableBigInt 12
13 第 二 章 自 顶 向 下 的 程 序 设 计 其 中 含 有 三 个 主 要 方 法 : multiply(int num) 用 来 把 当 前 大 整 数 与 一 个 int 型 整 数 num 相 乘, 结 果 将 保 留 在 当 前 大 整 数 中 所 以 这 个 函 数 的 返 回 类 型 是 void 这 与 BigInteger 的 multiply() 函 数 不 同 tostring() 用 来 把 当 前 大 整 数 转 换 成 一 个 字 符 串 从 而 方 便 打 印 输 出 带 一 个 int 型 参 数 的 构 造 函 数 这 个 参 数 表 示 这 个 大 整 数 的 初 值 例 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
14 第 二 章 自 顶 向 下 的 程 序 设 计 /*************** 转 换 为 字 符 串 以 方 便 打 印 public String tostring() { StringBuilder sb = new StringBuilder(); for(int i = digits.size() - 1; i >= 0; i--) sb.append(digits.get(i)); return sb.tostring(); 然 后 我 们 把 例 中 result 的 类 型 改 为 MutableBigInt, 并 用 multiply() 函 数 调 用 替 换 *= 运 算 即 可 结 果 如 下 : 例 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); 上 述 方 法 之 所 以 能 够 成 功 的 关 键 在 于 我 们 深 刻 地 理 解 了 *= 运 算 的 含 义 即 把 当 前 整 数 与 另 一 个 整 数 相 乘, 乘 得 的 结 果 还 要 替 换 掉 原 来 被 乘 数 关 于 恒 类 (immutable class) i 恒 类 的 一 个 特 点 是 : 这 样 的 类 的 属 性 的 值 是 不 会 发 生 变 化 的 一 个 推 论 是 : 恒 类 中 只 有 getter 函 数, 而 没 有 setter 函 数 换 句 话 说, 你 可 以 获 得 恒 类 对 象 的 属 性, 但 是 不 能 改 变 它 恒 类 的 属 性 的 初 值 一 般 是 由 构 造 函 数 设 置 的 比 如,Number 的 八 个 常 用 子 类 Integer Float Long Double Byte Short i 属 性, 有 的 教 材 称 为 实 例 变 量 或 者 成 员 变 量 本 书 无 差 别 地 使 用 这 三 个 概 念 14
15 第 二 章 自 顶 向 下 的 程 序 设 计 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 被 编 译 成 : 例 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 即 可 有 人 可 能 怀 疑 说 : 两 个 对 象 共 享 数 据 结 构, 线 程 安 全 方 面 会 不 会 有 问 题? 我 非 常 赞 赏 怀 疑 精 神, 能 独 立 问 出 这 样 问 题 的 人 绝 不 会 是 一 只 菜 鸟 对 于 恒 类 对 象 来 说, 其 状 态 是 永 久 不 变 的, 所 以 即 使 有 多 个 线 程 同 时 读 取 同 一 个 对 象 的 状 态, 也 不 会 有 问 题 通 过 这 个 例 子 你 学 到 了 什 么? 即 使 是 计 算 100 的 阶 乘, 算 法 的 结 构 与 计 算 5 的 阶 乘 的 算 法 相 比 也 仅 仅 是 把 int 换 成 了 一 个 我 们 自 己 另 外 定 义 的 类 MutableBigInt 而 已 所 以 首 先 请 把 复 杂 性 放 到 一 边, 尽 量 先 把 程 序 的 框 架 结 构 理 清 楚, 而 不 必 关 心 细 枝 末 节 在 考 虑 程 序 各 模 块 的 结 构 和 相 互 关 系 时, 应 该 首 先 考 虑 主 程 序, 然 后 再 考 虑 被 主 程 序 调 用 的 其 他 程 序 即 应 该 遵 循 自 顶 向 下 先 整 体 后 局 部 的 顺 序 在 没 有 MutableBigInt 时, 我 们 可 以 在 main() 函 数 中 用 int 代 替 它, 先 把 程 序 的 框 架 搭 好 然 后 再 考 虑 在 15
16 第 二 章 自 顶 向 下 的 程 序 设 计 MutableBigInt 中 要 用 到 哪 些 函 数, 以 及 每 个 函 数 的 参 数 和 返 回 类 型 至 于 每 个 函 数 内 部 实 现 的 细 节 应 该 留 到 编 写 MutableBigInt 类 时 再 考 虑 即 应 该 首 先 考 虑 函 数 的 签 名 (Signature, 也 称 为 函 数 头 ), 然 后 再 考 虑 函 数 的 实 现 2.2. 五 猴 分 桃 问 题 有 五 只 猴 子 上 山 采 桃 忙 活 了 一 天 以 后 他 们 采 了 一 大 堆 桃 子 正 当 他 们 决 定 分 桃 的 时 候 天 黑 了, 他 们 决 定 第 二 天 再 来 分 桃 子, 现 在 各 自 回 家 休 息 去 吧! 第 二 天 一 早, 第 一 个 猴 子 来 了 他 等 了 一 会 儿, 心 想 : 与 其 等 他 们 不 到, 不 如 我 现 在 就 分 桃 吧 还 能 省 点 时 间 呢! 于 是 他 把 桃 子 分 成 了 相 等 的 五 堆 最 后 发 现 还 多 出 一 只 桃 子 他 想 : 这 多 出 的 桃 子 当 然 应 该 属 于 劳 苦 功 高 的 我 喽! 于 是 他 吃 了 那 只 桃 子, 然 后 抱 起 属 于 自 己 的 那 一 堆 桃 子, 走 了 过 了 一 会 第 二 只 猴 子 来 了 他 并 不 知 道 第 一 只 猴 子 来 过 他 等 了 一 会 不 见 有 其 他 猴 来 于 是 也 把 桃 子 分 成 了 五 堆 也 发 现 多 出 一 只 桃 子 于 是 他 老 实 不 客 气 地 也 吃 了 那 只 桃 子, 然 后 抱 起 一 堆 桃 子, 走 了 之 后 第 三 第 四 乃 至 第 五 只 猴 子 也 干 了 同 样 的 事 情 : 把 剩 下 的 桃 子 分 成 相 等 的 五 堆, 发 现 多 了 一 只 桃 子, 吃 了 它, 抱 起 一 堆 桃 子, 然 后 拜 拜 问 题 是 : 请 编 写 程 序 计 算 最 初 有 几 个 桃 子? 一 个 容 易 的 解 法 一 个 最 容 易 想 到 的 解 法 是 把 桃 子 的 总 数 peaches 从 1,2,3,, 开 始 每 次 加 一 的 循 环 直 到 遇 到 第 一 个 能 被 猴 子 分 光 的 数 按 照 自 顶 向 下 的 考 虑 顺 序, 这 个 程 序 的 主 函 数 应 该 是 这 样 的 : 例 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
17 第 二 章 自 顶 向 下 的 程 序 设 计 请 注 意 例 中 黑 体 标 示 的 isdistributable() 函 数 这 个 函 数 实 际 上 我 们 还 没 有 编 写 但 这 并 不 妨 碍 我 们 在 主 函 数 中 引 用 它 自 顶 向 下 的 程 序 设 计 方 法 就 是 要 我 们 关 注 被 调 用 函 数 的 功 能, 而 不 去 关 心 它 的 实 现 这 里 isdistributable(peaches) 函 数 的 含 义 很 清 晰, 就 是 判 断 peaches 个 桃 子 能 否 被 猴 子 们 分 掉 ( 可 见 给 函 数 取 个 好 名 字 是 多 么 重 要 ) 如 果 能, 就 返 回 true, 否 则 返 回 false 这 样 main() 函 数 的 算 法 流 程 是 不 是 很 清 晰 易 懂? 如 此 清 晰 简 洁 的 流 程 也 为 我 们 以 后 排 错 或 增 加 新 的 功 能 提 供 了 便 利 但 是 很 多 人 ( 包 括 那 些 很 会 编 程 序 的 熟 手 ) 却 习 惯 于 先 编 写 小 的 次 要 的 被 调 用 的 函 数, 然 后 再 去 编 写 大 的 主 要 的 调 用 函 数 的 函 数 这 种 习 惯 就 好 比 做 房 子 先 垒 砖 头 后 搭 框 架 一 样 也 许 这 并 不 妨 碍 你 做 出 小 磨 房 小 牛 棚, 但 想 做 出 摩 天 大 楼 高 速 公 路 长 江 大 桥 那 是 绝 对 不 可 能 的 一 定 要 先 有 规 划 和 框 架, 然 后 再 关 注 细 节 因 为 我 们 几 乎 可 以 百 分 之 一 百 地 肯 定 主 函 数 没 有 问 题, 所 以 我 们 现 在 就 可 以 把 精 力 集 中 到 isdistributable() 函 数 上 去, 专 门 研 究 n 个 桃 子 能 否 被 五 个 猴 子 分 掉 我 们 看 看 每 个 猴 子 是 怎 么 办 事 的? 无 非 就 是 吃 掉 了 一 个 桃 子, 然 后 把 剩 下 的 桃 子 分 成 了 五 等 份 还 拿 走 了 其 中 一 等 份 问 题 的 关 键 就 在 于 桃 子 可 能 无 法 五 等 分, 程 序 应 该 就 在 这 里 返 回 false 所 以 isdistributable(peaches) 函 数 可 以 这 样 编 写 : 例 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 函 数 加 入 到 例 的 类 MonkeyAndPeach1 中 去, 然 后 运 行 这 个 类 就 可 以 得 到 正 确 结 果 答 案 是 一 点 改 进 考 虑 任 意 个 猴 子 如 果 是 六 个 七 个 八 个 甚 至 任 意 多 个 猴 子 分 桃 呢? 由 于 上 述 自 顶 向 下 的 程 序 设 计 思 路 非 常 清 晰, 所 以 我 们 只 需 要 在 isdistributable() 函 数 中 增 加 一 个 参 数 monkeys 用 来 表 明 有 多 少 个 猴 子 即 可 则 代 码 可 以 很 容 易 地 改 为 : 例
18 第 二 章 自 顶 向 下 的 程 序 设 计 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; 这 里 我 们 可 以 看 到 良 好 的 程 序 结 构 是 如 何 有 助 于 我 们 增 加 功 能 的 第 二 点 改 进 加 大 步 长 由 于 第 一 个 猴 子 是 吃 了 一 个 桃 子, 剩 下 的 桃 子 五 等 分 的, 所 以 桃 子 的 个 数 必 定 是 5K+1, 其 中 K=1,2,3, 所 以 主 函 数 中 循 环 变 量 的 步 长 可 以 改 为 5: 例 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
19 第 二 章 自 顶 向 下 的 程 序 设 计 逆 向 思 维 我 们 为 什 么 一 定 要 从 第 一 个 猴 子 开 始 考 虑 呢? 我 们 也 可 以 从 最 后 一 个 猴 子 开 始 考 虑 假 设 最 后 一 个 猴 子 走 了 之 后 剩 下 的 四 堆 桃 子 里 每 一 堆 有 n 个 桃 子, 则 他 来 之 前 桃 子 就 有 5n+1 个 我 们 然 后 计 算 第 四 第 三 第 二 第 一 个 猴 子 来 之 前 的 桃 子 总 数 即 可 我 们 把 这 种 计 算 用 getpeaches(currentpeaches) 函 数 表 示 其 中 currentpeaches 表 示 最 后 一 个 猴 子 分 桃 之 前 的 桃 子 总 数 返 回 结 果 是 第 一 个 猴 子 分 桃 之 前 的 桃 子 总 数 如 果 是 0, 则 意 味 着 根 据 当 前 currentpeaches 无 法 计 算, 否 则 大 于 0 就 是 我 们 想 要 知 道 的 最 初 的 桃 子 数 代 码 如 下 : 例 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
20 第 二 章 自 顶 向 下 的 程 序 设 计 其 中 的 while 循 环 仅 需 执 行 255 次 即 可 数 学 解 这 个 有 趣 的 问 题 其 实 有 一 个 很 简 单 的 数 学 解 你 只 需 要 借 给 这 群 猴 子 4 个 桃 子, 从 而 保 证 了 第 一 个 猴 子 能 够 五 等 分 所 有 的 桃 子 第 一 个 猴 子 抱 走 一 堆 桃 子 后, 你 发 现 他 并 没 有 比 以 前 多 拿 桃 子, 你 借 给 他 们 的 4 个 桃 子 又 传 给 了 第 二 个 猴 子,, 以 此 类 推, 每 个 猴 子 都 能 五 等 分 所 有 的 桃 子 最 后 你 再 拿 走 借 给 他 们 的 4 个 桃 子 所 以 你 出 借 4 个 桃 子 之 后, 这 堆 桃 子 能 够 5 次 被 5 整 除, 所 以 答 案 就 是 5 5 K 4 个 桃 子, 其 中 K=1,2,3, 最 少 应 该 有 即 3121 个 这 正 是 我 们 要 的 答 案 当 然 我 们 的 目 的 并 不 是 真 的 要 解 决 五 猴 分 桃 问 题, 而 是 掌 握 自 顶 向 下 的 程 序 设 计 方 法 20
21 第 三 章 递 归 程 序 设 计 第 三 章 递 归 程 序 设 计 递 归 函 数 就 是 指 函 数 自 己 调 用 自 己 如 果 一 个 函 数 直 接 调 用 了 自 己 那 这 种 递 归 就 是 直 接 递 归 如 果 通 过 其 他 函 数 间 接 地 调 用 了 自 己 那 就 是 间 接 递 归 有 趣 的 是, 不 管 是 直 接 递 归 间 接 递 归 还 是 函 数 之 间 的 普 通 调 用, 计 算 机 内 部 都 是 统 一 处 理 的, 甚 至 根 本 就 不 区 分 某 个 函 数 调 用 是 递 归 的 还 是 非 递 归 的 这 个 问 题 与 函 数 调 用 和 参 数 传 递 机 制 有 关, 其 中 有 很 多 有 趣 的 现 象 和 结 论, 我 们 将 在 后 面 章 节 提 到 3.1. 递 归 和 数 学 归 纳 法 第 一 个 例 子 Hanoi 塔 递 归 程 序 的 一 个 著 名 例 子 就 是 Hanoi 塔 ( 中 文 翻 译 为 河 内 塔 或 汉 诺 塔 ) 问 题 这 里 先 简 单 介 绍 一 下 这 个 问 题 有 三 根 杆 子 A B C A 杆 上 套 有 若 干 中 间 有 孔 的 碟 子 碟 子 的 直 径 大 小 不 一, 并 且 小 的 碟 子 垒 在 大 的 碟 子 上 呈 金 字 塔 状 ( 参 见 图 3.1-1) 规 则 允 许 你 从 任 何 一 个 杆 子 上 取 最 上 面 一 个 碟 子 然 后 移 到 另 外 任 何 一 个 杆 子 上, 条 件 是 这 个 碟 子 不 能 比 它 下 面 的 那 张 碟 子 大 游 戏 的 目 的 是 把 所 有 碟 子 从 A 杆 全 部 移 到 C 杆 上 有 很 多 高 级 程 序 设 计 语 言 的 教 材 都 把 Hanoi 塔 作 为 第 一 个 递 归 程 序 的 例 子 介 绍 给 大 家 比 如 一 个 C 语 言 的 例 子 是 : 例 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); 图 Hanoi 塔 问 题 21
22 第 三 章 递 归 程 序 设 计 遗 憾 的 是, 在 我 所 认 识 的 几 千 个 同 事 同 学 朋 友 和 学 生 当 中, 几 乎 没 有 一 个 人 在 第 一 眼 看 到 这 个 程 序 时 就 能 够 独 立 地 理 解 它 当 然 现 在 你 可 能 已 经 觉 得 这 个 程 序 实 在 是 太 简 单 了, 但 是 你 真 地 了 解 递 归 程 序 背 后 的 数 学 原 理 吗? 递 归 背 后 的 数 学 原 理 还 记 得 你 初 中 高 中 时 代 怎 么 使 用 数 学 归 纳 法 的 吗? 比 如 你 用 数 学 归 纳 法 如 何 证 明 前 n 个 奇 数 的 和 等 于 n 2? 即 : (2n-1) = n 2 第 一 步, 当 n=1 时,1=1 2 成 立 第 二 步 归 纳 假 设, 设 n=k 时, 等 式 成 立 即 (2k-1) = k 2 最 后 一 步 推 导, 当 n=k+1 时, 等 式 的 左 边 是 (2k-1)+(2k-1+2) = k 2 +2k+1 = (k+1) 2 与 右 边 相 等 所 以 原 等 式 对 于 任 意 自 然 数 n 成 立 也 就 是 说, 数 学 归 纳 法 要 走 三 步 : 第 一 步, 边 界 条 件 上 的 证 明, 即 证 明 原 问 题 在 参 数 边 界 上 ( 如 上 例 中 的 n=1) 成 立 这 一 步 往 往 不 需 要 复 杂 的 论 证, 一 般 可 以 直 接 得 出 结 论 第 二 步 是 归 纳 假 设 即 假 设 当 参 数 更 接 近 边 界 时 ( 比 如 上 例 中 k 比 k+1 更 接 近 1) 结 论 成 立 第 三 步 推 导, 根 据 第 二 步 的 假 设 推 导 出 结 论 也 成 立 奇 妙 的 是, 递 归 程 序 设 计 的 步 骤 与 之 一 一 对 应 也 分 为 三 步 : 1) 找 到 参 数 的 边 界 条 件, 计 算 边 界 条 件 成 立 时 的 输 出 这 一 步 往 往 不 需 要 复 杂 的 计 算, 一 般 可 以 直 接 输 出 结 果 2) 递 归 假 设 假 设 函 数 在 参 数 更 接 近 边 界 时 能 够 得 到 期 望 的 输 出 程 序 设 计 难 道 可 以 假 设? 是 的, 可 以 假 设 这 就 是 计 算 机 科 学 的 魅 力 3) 推 导 根 据 第 二 步 的 假 设 计 算 函 数 的 输 出 所 以 只 要 确 定 好 函 数 的 参 数, 然 后 按 照 这 三 步 编 程 就 能 写 出 比 较 漂 亮 又 好 理 解 的 递 归 程 序 Hanoi 塔 问 题 的 递 归 解 考 虑 Hanoi 塔 问 题 第 一 步, 请 问 在 什 么 情 况 下 Hanoi 塔 问 题 最 容 易 解 决? 那 当 然 是 只 有 一 个 碟 子 的 情 况 这 时 只 要 直 接 把 那 张 碟 子 从 A 移 到 C 杆 上 即 可 第 二 步 递 归 假 设 一 般 地, 递 归 假 设 时, 参 数 或 参 数 组 合 应 该 比 原 参 数 更 接 近 于 边 界 在 Hanoi 塔 问 题 中, 碟 子 的 个 数 为 1 时 是 边 界 条 件, 所 以 可 以 假 设 碟 子 的 个 数 是 n-1 时 我 们 可 以 任 意 地 把 这 n-1 张 碟 子 从 一 个 杆 移 到 另 一 个 杆 n 是 原 来 碟 子 的 个 数 你 可 能 会 问, 我 怎 么 把 这 n-1 张 碟 子 从 一 个 杆 移 到 另 一 个 杆 呢? 不 要 问 我 为 什 么, 因 为 这 是 假 设 的 我 完 全 可 以 假 设 太 阳 是 黑 的, 地 球 是 方 的 说 到 底, 那 只 是 假 设 而 已! 第 三 步, 推 导 根 据 第 二 步 的 假 设, 我 们 可 以 把 n-1 张 碟 子 从 任 意 一 个 杆 移 到 另 一 个 杆 所 以 我 们 可 以 把 A 杆 上 最 下 面 的 那 张 最 大 的 碟 子 排 除 在 外, 先 把 它 上 面 n-1 张 碟 子 22
23 第 三 章 递 归 程 序 设 计 移 到 B 杆 上 参 见 图 和 图 图 n-1 张 碟 子 先 从 A 杆 移 到 B 杆 接 下 来 把 最 大 的 那 张 碟 子 从 A 杆 直 接 移 到 C 杆 参 见 图 图 最 大 的 碟 子 从 A 杆 直 接 移 到 C 杆 最 后 再 把 B 杆 上 的 n-1 个 碟 子 全 部 移 到 C 杆 上 参 见 图 图 n-1 张 碟 子 再 从 B 杆 移 到 C 杆 现 在 我 们 再 回 过 头 来 分 析 C 语 言 写 的 hanoi 塔 程 序, 就 会 有 新 的 认 识 : 例 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
24 第 三 章 递 归 程 序 设 计 hanoi(b, a, c, n-1); // 递 归 假 设,n-1 张 碟 子 再 从 b 移 到 c,a 是 过 渡 一 般 地, 对 边 界 条 件 的 判 断 应 该 放 在 递 归 假 设 之 前 进 行 就 像 数 学 归 纳 法 必 须 首 先 保 证 要 证 明 的 定 理 / 公 式 在 边 界 条 件 上 成 立, 然 后 我 们 才 能 进 行 归 纳 假 设 所 以 边 界 条 件 的 判 断 和 处 理 也 应 该 在 递 归 假 设 之 前 进 行 这 是 递 归 能 够 正 常 终 止 的 前 提 在 Hanoi 塔 例 子 中, 对 边 界 条 件 的 判 断 就 是 在 函 数 的 开 始 处 首 先 执 行 的 这 种 现 象 在 递 归 程 序 中 非 常 普 遍 3.2. 一 些 有 趣 的 递 归 程 序 字 符 串 通 配 符 匹 配 假 设 * 可 以 匹 配 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 之 间 是 否 匹 配 代 码 如 下 : 例 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
25 第 三 章 递 归 程 序 设 计 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 函 数 : 例 private static boolean match(string pattern, int patternfrom, String str, int strfrom) { 其 中 patternfrom 用 来 指 明 模 式 串 从 pattern 的 第 几 个 字 符 开 始 ;strfrom 用 来 指 明 字 符 串 从 str 的 第 几 个 字 符 开 始 把 这 个 函 数 用 类 似 于 例 那 样 的 方 法 做 成 递 归 函 数 然 后 令 match(string pattern, String str) 函 数 直 接 调 用 match(pattern, 0, str, 0) 即 可 这 样 运 算 时 就 不 需 要 调 用 String.substring() 函 数 完 整 代 码 如 下 : 例 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
26 第 三 章 递 归 程 序 设 计 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); 兔 子 一 对 刚 出 生 的 小 白 兔 两 个 月 后 就 成 熟 并 生 下 一 对 兔 子, 之 后 每 个 月 都 能 生 一 对 兔 子 现 在 给 你 一 对 刚 出 生 的 小 白 兔, 问 n 个 月 后 有 几 对 兔 子? 显 然, 递 归 边 界 是 n=0 或 1 递 归 假 设 也 很 好 做 下 面 考 虑 推 导 当 n>2 时, 每 个 月 的 兔 子 总 数 由 上 个 月 的 兔 子 总 数 和 本 月 新 出 生 的 兔 子 组 成 而 本 月 新 出 生 的 兔 子 数 与 两 个 月 前 的 兔 子 总 数 相 同, 因 为 那 时 即 使 是 刚 出 生 的 兔 子 现 在 也 成 熟 了 所 以, 本 题 的 解 就 是 著 名 的 斐 波 纳 奇 (Fibnacci) 数 列 : 例 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
27 第 三 章 递 归 程 序 设 计 上 述 递 归 程 序 中 存 在 重 复 计 算 的 问 题 例 如 为 了 计 算 getrabits(5) 就 要 计 算 getrabit(4) 和 getrabit(3), 而 为 了 计 算 getrabits(4) 就 要 计 算 getrabit(3) 和 getrabit(2), 其 中 getrabit(3) 就 被 重 复 计 算 了 这 就 导 致 运 算 速 度 的 下 降 解 决 的 办 法 之 一 就 是 在 计 算 过 程 中 保 留 中 间 计 算 结 果 关 于 这 个 问 题 我 们 将 在 7.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): 例 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
28 第 三 章 递 归 程 序 设 计 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) 参 见 例 的 最 后 一 个 return 语 句 让 我 们 象 中 国 古 代 科 学 家 杨 辉 那 样 把 所 有 组 合 数 按 m 的 不 同 分 行 排 列, 就 会 得 到 如 图 那 样 的 杨 辉 三 角 根 据 上 述 公 式, 我 们 知 道 每 个 组 合 数 都 等 于 它 肩 膀 上 的 两 个 数 的 和 计 算 机 的 递 归 理 论 和 数 学 得 到 同 一 个 结 论, 这 是 证 明 科 学 理 论 殊 路 同 归 的 又 一 个 例 子 排 列 排 列 和 上 节 中 的 组 合 非 常 相 似, 不 同 的 是 1)n=m 不 能 作 为 边 界 ;2) 第 三 步 推 导 略 有 不 同 : 如 果 最 后 一 个 小 球 Z 被 选 中, 那 它 与 其 他 n-1 个 被 选 中 的 小 球 之 间 有 n 种 不 同 的 排 列 即 Z 可 以 排 在 第 1 个 小 球 之 前 第 2 个 小 球 之 前 第 n-1 个 小 球 之 前 或 者 第 n-1 个 小 球 之 后, 共 n 种 情 况 所 以 求 排 列 数 的 程 序 是 ( 为 了 可 读 性, 用 total 代 替 m, 用 select 代 替 n): 例 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= m= m= 图 杨 辉 三 角 28
29 第 三 章 递 归 程 序 设 计 return result; 人 字 形 的 铁 路 如 图 3.2-2, 有 一 段 人 字 形 的 铁 路, 火 车 只 能 从 右 边 铁 路 线 驶 进, 并 且 只 能 从 左 边 铁 路 线 驶 出 驶 进 来 的 火 车 可 以 停 在 人 字 形 的 上 半 部 分 ( 直 线 ) 铁 路 线 上, 从 而 让 后 进 来 的 火 车 先 从 左 边 铁 路 线 驶 出 当 然 它 也 可 以 进 来 之 后 不 作 停 留 直 接 驶 出 假 设 右 边 有 n 列 火 车, 问 从 左 边 驶 出 的 n 列 火 车 的 排 列 有 多 少 种? 图 人 字 形 铁 路 问 题 : 火 车 只 能 右 边 进 左 边 出 比 如 假 设 右 边 有 3 列 火 车 A B C, 则 从 左 边 驶 出 的 火 车 的 排 列 只 有 5 种 :ABC ACB BAC BCA 和 CBA 3 列 火 车 的 所 有 6 种 排 列 里 唯 有 CAB 是 不 可 能 的 这 一 题 的 递 归 边 界 和 假 设 都 是 比 较 容 易 的 难 的 是 推 导 与 节 的 排 列 组 合 一 样, 我 们 可 以 把 一 列 火 车 拎 出 来 单 独 考 虑 只 不 过, 在 排 列 组 合 那 一 题 中 我 们 考 虑 的 是 最 后 一 个 小 球, 而 在 这 一 题 中, 我 们 考 虑 的 是 第 一 列 火 车 假 设 第 一 列 火 车 第 i 个 驶 出 (i=1, 2,,n), 则 排 在 它 之 前 驶 出 的 火 车 有 i-1 辆 这 一 题 的 巧 妙 之 处 就 在 于 这 i-1 辆 排 在 它 之 前 驶 出 的 火 车 恰 好 在 驶 入 时 是 排 在 第 一 列 火 车 之 后 的 i-1 列 火 车 也 就 是 说, 第 一 列 火 车 要 想 第 i 个 驶 出, 则 紧 随 其 后 的 i-1 列 火 车 必 须 先 驶 出, 剩 下 的 n-i 列 火 车 必 须 在 它 之 后 驶 出 见 图
30 第 三 章 递 归 程 序 设 计 为 什 么? 因 为 第 一 列 火 车 要 想 第 i 个 驶 出, 则 它 进 入 人 字 形 铁 路 后 就 必 须 停 在 直 线 铁 路 上 直 到 有 i-1 列 火 车 驶 出 问 题 是 第 一 列 之 后 的 火 车 要 么 不 驶 入, 要 么 必 然 比 第 一 列 火 车 先 驶 出, 后 进 先 出 嘛! 所 以 最 后 驶 入 的 n-i 列 火 车 必 然 在 第 一 列 火 车 之 后 驶 出 人 字 形 铁 路, 否 则 就 会 导 致 第 一 列 火 车 之 前 会 有 多 于 i-1 列 的 火 车 驶 出 根 据 递 归 假 设, 先 驶 出 的 i-1 列 火 车 有 多 少 种 排 列 以 及 后 驶 出 的 n-i 列 火 车 有 多 少 种 排 列 我 们 都 是 能 计 算 出 来 的 不 要 问 我 为 什 么, 因 为 这 是 递 归 假 设 所 以 递 归 程 序 就 是 : 例 package com.training.recursion; public class Train { public static int get(int trains) { 图 人 字 形 铁 路 问 题 : 第 一 列 火 车 要 想 第 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
31 第 三 章 递 归 程 序 设 计 五 升 的 杯 子 和 三 升 的 杯 子 倒 出 四 升 水 给 你 一 大 一 小 两 只 没 有 刻 度 的 杯 子, 大 杯 子 的 容 量 是 5 升, 小 杯 子 的 容 量 是 3 升 你 能 用 这 两 只 杯 子 倒 出 4 升 水 来 吗? 这 一 题 有 两 个 参 数 water1 和 water2 water1 表 示 大 杯 子 中 目 前 的 水 量,water2 表 示 小 杯 子 中 目 前 的 水 量 water1 和 water2 的 初 值 都 是 0, 表 示 杯 子 中 没 有 水 我 们 首 先 考 虑 递 归 边 界 :water1 和 water2 满 足 什 么 条 件 时 我 们 可 以 直 接 给 出 答 案 而 不 用 进 行 递 归? 显 然,water1 和 water2 只 要 有 一 个 等 于 目 标 水 量 即 4, 那 么 我 们 就 有 了 这 么 多 水, 不 用 再 倒 来 到 去 了 递 归 假 设 是 只 要 water1 或 water2 比 原 值 更 接 近 目 标 水 量, 那 么 我 们 就 能 判 断 它 能 否 倒 出 那 么 多 水 递 归 推 导 要 分 为 八 种 情 况 考 虑 : 如 果 一 个 杯 子 不 满, 那 么 我 们 可 以 给 它 装 满 水 因 为 有 两 只 杯 子, 所 以 这 有 两 种 情 况 ; 如 果 一 个 杯 子 里 有 水, 那 么 我 们 可 以 把 它 倒 空, 这 也 有 两 种 情 况 ; 把 一 个 杯 子 里 的 水 全 部 倒 到 另 一 个 杯 子 里 去, 前 提 是 两 个 杯 子 中 的 水 的 总 量 小 于 等 于 后 者 的 容 量 从 而 不 会 让 后 者 漫 出 来 这 也 有 两 种 情 况 ; 把 一 个 杯 子 里 的 水 往 另 一 个 杯 子 里 倒, 把 后 者 装 满, 同 时 前 者 还 留 一 点 水, 前 提 是 两 个 杯 子 中 的 水 总 量 大 于 后 者 的 容 量 这 也 有 两 种 情 况 递 归 推 导 时 就 按 照 这 八 种 情 况 分 别 考 虑 就 可 以 了 错 误 的 递 归 我 们 首 先 给 出 主 程 序, 参 见 例 主 函 数 将 调 用 pourwater(c1, c2, g) 子 函 数 用 以 测 试 用 容 量 分 别 是 c1 和 c2 的 两 个 杯 子 是 否 能 够 倒 出 g 升 水 出 来 pourwater() 函 数 将 用 输 入 的 三 个 参 数 构 造 一 个 Water 对 象, 通 过 调 用 该 类 对 象 的 pour() 方 法 判 断 倒 水 是 否 成 功 例 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
32 第 三 章 递 归 程 序 设 计 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) 是 一 个 递 归 程 序, 见 例 注 意 : Water 类 中 有 三 个 成 员 变 量 保 留 两 个 杯 子 的 容 量 和 目 标 水 量, 因 为 这 三 个 值 相 对 于 函 数 pour() 的 每 次 调 用 来 说 是 不 变 的, 这 就 是 之 所 以 把 他 们 放 在 成 员 变 量 中 而 不 是 作 为 参 数 进 行 传 递 的 原 因 例 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
33 第 三 章 递 归 程 序 设 计 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
34 第 三 章 递 归 程 序 设 计 递 归 函 数 pour(water1, water2) 几 乎 是 完 全 按 照 上 一 小 节 的 讨 论 编 写 的, 但 这 个 解 对 吗? 一 旦 你 运 行 这 个 程 序 你 很 快 就 会 发 现 它 抛 出 了 StackOverflowError 这 意 味 着 递 归 没 有 中 止, 换 句 话 说, 递 归 边 界 (water1 == goal water2 == goal) 永 远 无 法 到 达 新 参 数 组 合 一 定 要 更 接 近 于 边 界 产 生 这 个 错 误 的 原 因 是 : 以 例 中 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) 总 是 在 不 断 地 减 一, 因 而 绝 对 不 会 出 现 参 数 重 复 保 存 状 态 法 如 果 你 无 法 保 证 新 参 数 组 合 更 接 近 于 边 界, 怎 么 办? 这 恰 恰 是 人 工 智 能 所 要 回 答 的 一 个 重 要 问 题, 即 : 当 状 态 出 现 重 复 时, 我 们 该 怎 么 办? 从 这 个 意 义 上 讲, 递 归 其 实 是 人 工 智 能 搜 索 方 法 的 一 个 特 例 ( 实 际 是 深 度 优 先 搜 索 的 一 个 特 例, 这 里 我 们 再 次 看 到 不 同 科 学 理 论 殊 路 同 归 的 性 质 ) 我 们 在 后 面 关 于 人 工 智 能 的 章 节 中 还 会 谈 到 这 个 问 题 现 在 我 们 有 一 个 简 单 的 方 法 解 决 这 个 问 题 如 果 出 现 参 数 重 复, 则 意 味 着 到 目 前 为 止 的 递 归 路 径 其 实 是 行 不 通 的, 注 定 要 回 到 原 点 重 新 再 来 所 以 我 们 可 以 把 参 数 组 合 保 存 下 来, 一 旦 递 归 过 程 中 发 现 当 前 参 数 组 合 与 保 存 的 某 个 参 数 组 合 相 同, 我 们 就 终 止 递 归 避 免 出 现 无 限 循 环 如 果 我 们 把 参 数 的 组 合 称 为 解 决 问 题 过 程 中 的 一 个 状 态, 则 我 们 把 这 种 保 存 参 数 组 合 的 方 法 称 为 保 存 状 态 法 根 据 这 个 思 路, 我 们 把 参 数 water1 和 water2 封 装 到 类 State 中, 然 后 在 递 归 函 数 中 增 加 一 个 参 数 visited 用 来 保 存 访 问 过 的 参 数 组 合 注 意, 为 了 能 够 判 断 两 个 状 态 是 否 相 等, 我 们 要 重 定 义 State 的 hashcode() 和 equals(object) 函 数 ( 这 个 问 题 我 们 以 后 还 会 谈 到 ) 这 样 我 们 的 程 序 就 被 改 成 : 例 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
35 第 三 章 递 归 程 序 设 计 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 = public int hashcode() { return (water1 << 16) 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
36 第 三 章 递 归 程 序 设 计 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; //
37 第 三 章 递 归 程 序 设 计 注 意,visited 集 合 仅 用 来 保 存 当 前 递 归 路 径 上 的 状 态 所 以 递 归 终 止 ( 即 return false) 之 前 应 该 把 当 前 状 态 从 集 合 中 删 除, 这 就 是 为 什 么 要 在 return false 之 前 执 行 visited.remove(state) 的 原 因 ( 参 见 例 中 用 //200 和 //210 标 记 的 行 ) 但 是 令 人 惊 讶 的 是, 例 中 用 //100 和 //110 标 记 的 行 在 return 语 句 之 前 并 没 有 删 除 当 前 状 态 state, 而 让 它 继 续 在 visited 集 合 中 保 持 存 在 这 是 因 为 如 果 我 们 把 state 从 visited 集 合 中 删 除, 则 下 次 如 果 再 遇 到 相 同 的 状 态, 程 序 还 是 会 对 它 递 归 求 解 这 样 我 们 不 但 避 免 无 限 循 环 的 递 归, 还 大 大 加 快 了 程 序 运 行 的 速 度 上 面 的 解 法 仅 仅 回 答 了 我 们 能 不 能 如 果 能 的 话, 怎 样 才 能 倒 出 那 么 多 水 呢? 以 及 如 何 用 最 少 的 次 数 倒 出 那 么 多 水 呢? 我 们 将 在 后 面 关 于 搜 索 的 章 节 中 回 答 这 两 个 问 题 3.3. 递 归 程 序 非 递 归 化 所 谓 递 归 程 序 的 非 递 归 化 是 指 用 非 递 归 ( 如 循 环 条 件 语 句 ) 的 方 法 实 现 递 归 思 想 至 少 有 以 下 几 个 理 由 促 使 我 们 讨 论 递 归 程 序 的 非 递 归 化 : 第 一, 递 归 的 奥 秘 是 什 么, 计 算 机 内 部 是 如 何 实 现 递 归 的? 第 二, 递 归 往 往 以 牺 牲 时 间 和 空 间 效 率 为 代 价 换 取 程 序 的 简 洁 和 高 可 读 性, 但 有 时 您 可 能 需 要 优 先 考 虑 时 空 效 率, 这 时 非 递 归 方 法 往 往 比 递 归 方 法 有 效 ; 第 三, 并 不 是 所 有 的 程 序 设 计 语 言 都 支 持 递 归, 比 如 Fortran77 就 不 支 持 如 何 用 这 样 的 语 言 开 发 递 归 思 想 的 程 序? 另 外, 你 不 想 知 道 Fortran 77 不 支 持 递 归 的 根 本 原 因 吗? 别 担 心 你 不 懂 Fortran 77, 它 的 语 法 与 一 般 高 级 语 言 没 有 什 么 大 的 差 异 更 重 要 的 是, Fortran 77 不 支 持 递 归 有 着 深 刻 的 原 因, 而 与 其 语 法 没 有 关 系 函 数 调 用 的 实 质 函 数 返 回 时 应 该 返 回 到 下 一 行 设 有 函 数 main() 调 用 m1(),m1() 调 用 m2(), 参 见 图 函 数 调 用 :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 图 main() 调 用 m1(),m1() 调 用 m2() 37
38 第 三 章 递 归 程 序 设 计 图 中 的 箭 头 指 明 程 序 运 行 的 流 程 比 如 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 行 继 续 执 行 综 上 所 述, 我 们 得 到 第 一 个 结 论 : 函 数 调 用 完 毕 之 后 应 该 返 回 到 调 用 语 句 的 下 一 行 继 续 执 行 用 堆 栈 来 保 存 返 回 地 址 请 看 上 节 的 函 数 调 用 示 例 :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) pop() 140 被 弹 出 pop() 50 被 弹 出 50 图 用 堆 栈 保 存 返 回 地 址 图 显 示 了 堆 栈 是 如 何 被 用 来 保 存 返 回 地 址 的 ( 这 个 堆 栈 常 常 被 称 为 运 行 堆 栈 ) 图 中 计 算 机 每 次 遇 到 Call 语 句, 都 把 下 一 句 的 地 址 作 为 返 回 地 址 压 入 堆 栈 ( 见 第 1 步 和 第 2 步 ) 每 次 遇 到 Return 语 句, 都 从 当 前 堆 栈 的 栈 顶 弹 出 一 个 数 据 作 为 返 回 地 址, 然 后 转 到 该 返 回 地 址 所 指 定 的 位 置 处 继 续 运 行 比 如 计 算 机 运 行 到 m2() 函 数 的 第 250 行 时 遇 到 Return 语 句, 堆 栈 发 生 一 次 pop 操 作 ( 见 第 3 步 ), 计 算 机 根 据 弹 出 的 返 回 地 38
39 第 三 章 递 归 程 序 设 计 址 140 转 到 第 140 行 ( 位 于 m1() 函 数 内 ) 运 行, 从 而 实 现 了 从 被 调 用 函 数 m2() 向 调 用 函 数 m1() 的 返 回 同 样 道 理, 计 算 机 运 行 到 m1() 函 数 第 160 行 时 遇 到 Return 语 句, 堆 栈 再 次 发 生 pop 操 作 ( 见 第 4 步 ), 使 计 算 机 从 m1() 返 回 到 main() 函 数 的 第 50 行 继 续 运 行 运 行 堆 栈 还 用 来 保 存 参 数 运 行 堆 栈 绝 不 仅 仅 用 来 保 存 返 回 地 址, 它 还 可 以 被 用 来 保 存 函 数 调 用 时 的 参 数 函 数 调 用 :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(); 图 用 运 行 堆 栈 保 存 返 回 地 址 和 参 数 图 显 示 了 用 运 行 堆 栈 保 存 返 回 地 址 和 参 数 时, 运 行 堆 栈 在 函 数 调 用 和 返 回 时 的 变 化 情 况 与 图 相 比, 两 者 有 以 下 不 同 图 遇 到 Call 语 句 时, 应 该 先 向 运 行 堆 栈 压 入 返 回 地 址, 然 后 压 入 参 数 设 有 n 个 参 数, 则 应 该 执 行 n+1 次 push 操 作 图 遇 到 Return 语 句 时, 应 该 首 先 把 参 数 全 部 弹 出, 设 有 n 个 参 数, 则 运 行 堆 栈 应 该 执 行 n 次 push 操 作 然 后 追 加 执 行 一 次 pop 操 作 以 便 弹 出 返 回 地 址, 并 根 据 返 回 地 址 决 定 计 算 机 应 该 跳 转 到 哪 里 继 续 执 行 返 回 地 址 入 栈 的 次 序 一 般 地, 返 回 地 址 应 该 比 参 数 先 入 栈, 这 样 我 们 就 可 以 通 过 栈 顶 直 接 计 算 参 数 的 位 置 了 如 果 返 回 地 址 比 参 数 后 入 栈, 则 该 返 回 地 址 位 于 栈 顶 位 置 那 么 计 算 参 数 地 址 的 时 候 就 需 要 首 先 减 去 返 回 地 址 所 占 据 的 空 间 这 会 影 响 到 函 数 调 用 的 效 率 在 特 别 情 况 下, 比 如 小 节 和 小 节 为 了 实 现 可 变 参 数, 返 回 地 址 也 可 以 39
40 第 三 章 递 归 程 序 设 计 后 入 栈 参 数 入 栈 的 次 序 与 可 变 参 数 如 果 仔 细 观 察 图 3.3-3, 你 会 发 现 对 同 一 次 函 数 调 用 来 说, 其 参 数 入 栈 的 次 序 似 乎 是 相 反 的 : 第 一 个 参 数 最 后 入 栈, 最 后 一 个 参 数 第 一 个 入 栈 也 就 是 说, 参 数 按 从 右 往 左 逆 序 入 栈 这 对 吗? 试 想 如 果 第 一 个 参 数 先 入 栈, 则 在 它 的 上 方 压 着 第 二 个 参 数, 在 第 二 个 参 数 的 上 方 压 着 第 三 个 参 数,, 以 此 类 推 最 后 一 个 参 数 则 位 于 当 前 栈 顶 ( 参 见 图 3.3-4) 也 就 是 说, 堆 栈 的 栈 顶 指 针 指 向 的 并 非 是 第 一 个 参 数, 而 是 最 后 一 个 参 数! 也 就 是 说 顺 序 入 栈 的 参 数 是 按 逆 序 搜 索 的 如 果 仅 仅 是 不 得 不 按 逆 序 搜 索 参 数 的 话, 也 许 不 足 以 说 服 你 接 受 参 数 应 该 逆 序 而 不 是 顺 序 入 栈 的 策 略 但 是 对 于 像 C 语 言 的 可 变 参 数 这 样 的 机 制 来 说, 参 数 逆 序 入 栈 则 是 不 得 不 接 受 的 选 择 Why? 这 是 因 为 所 谓 可 变 参 数 就 是 参 数 的 个 数 和 类 型 不 确 定, 如 果 参 数 按 顺 序 入 栈, 则 我 们 如 何 确 定 第 一 个 参 数 的 位 置? 别 忘 了 它 被 不 确 定 数 量 和 类 型 的 其 他 参 数 压 在 最 下 面 呢 如 果 参 数 逆 序 入 栈 的 话, 则 栈 顶 指 针 指 向 的 就 是 第 一 个 参 数, 其 位 置 是 确 定 的 有 了 第 一 个 参 数, 我 们 就 可 以 确 定 其 他 参 数 的 位 置 这 里 有 两 种 方 法 可 以 使 用 : 1) 可 以 根 据 第 一 个 参 数 中 的 信 息 确 定 所 有 其 他 参 数 的 类 型 和 长 度 从 而 计 算 出 它 们 的 位 置 ( 就 象 C 语 言 著 名 的 printf() 函 数 所 做 的 那 样 ) 或 者 2) 也 可 以 事 先 约 定 好 参 数 的 类 型, 比 如 第 一 个 参 数 是 int 型, 第 二 个 是 float 型,, 从 而 保 证 我 们 能 够 计 算 出 所 有 参 数 的 位 置 所 以 参 数 逆 序 入 栈 不 但 为 我 们 顺 序 搜 寻 参 数 带 来 便 利, 更 重 要 的 是, 它 是 实 现 可 变 参 数 的 关 键 Java 的 可 变 参 数 是 另 一 回 事 栈 顶 指 针 最 后 一 个 参 数 第 二 个 参 数 第 一 个 参 数 图 参 数 顺 序 入 栈 值 得 注 意 的 是,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
41 第 三 章 递 归 程 序 设 计 在 函 数 调 用 时 少 写 一 些 像 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 对 应 这 些 信 息 在 编 译 器 从 左 往 右 扫 描 整 个 参 数 列 表 时 很 容 易 获 得 控 制 运 行 堆 栈 的 代 码 应 该 放 在 哪 里? 运 行 堆 栈 上 的 操 作 主 要 有 两 个 :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() 调 用 端 被 调 用 函 数 图 pop() 操 作 位 于 被 调 用 函 数 内 push() 操 作 只 能 放 在 函 数 的 调 用 端 ( 参 见 图 3.3-5) 而 不 能 放 在 被 调 用 函 数 内 部, 因 为 被 调 用 函 数 不 可 能 知 道 应 该 往 堆 栈 中 压 入 哪 些 参 数 而 pop() 操 作 可 以 放 在 以 下 两 个 地 方 之 一 : 被 调 用 函 数 的 最 后 ( 参 见 图 3.3-5) 或 者 41
42 第 三 章 递 归 程 序 设 计 调 用 端 ( 参 见 图 3.3-6) 请 注 意, 在 上 述 两 种 方 法 里, 返 回 地 址 分 别 是 在 所 有 参 数 之 前 和 之 后 入 栈 的 ( 为 什 么?) 现 在 的 问 题 是, 上 述 两 种 方 法 有 什 么 区 别 吗? 如 果 pop() 操 作 位 于 调 用 端, 这 意 味 着 每 一 个 调 用 端 都 要 有 一 组 pop 操 作 如 果 被 调 用 函 数 是 一 个 经 常 被 调 用 的 函 数, 那 么 就 会 有 许 多 地 方 存 在 这 种 pop() 操 作 相 反, 如 果 pop() 操 作 位 于 被 调 用 函 数 内 部, 那 么 无 论 一 个 函 数 被 调 用 了 多 少 次, 调 用 端 都 不 必 执 行 pop() 操 作 既 然 这 样, 那 pop() 操 作 位 于 调 用 端 还 有 什 么 意 义 呢? 其 意 义 就 是 : 实 现 了 可 变 参 数 参 数 可 变, 意 味 着 调 用 端 压 入 运 行 堆 栈 的 参 数 个 数 不 确 定, 这 样 我 们 就 不 能 指 望 被 调 用 函 数 能 够 事 先 预 测 有 多 少 参 数 入 栈 于 是 就 只 能 由 调 用 端 来 执 行 pop() 操 作, 因 为 调 用 端 显 然 明 确 地 知 道 有 多 少 参 数 入 栈 所 以 总 结 起 来, 要 实 现 可 变 参 数, 必 须 满 足 以 下 条 件 : 1) 参 数 必 须 逆 序 入 栈 ; 2) 返 回 地 址 必 须 在 参 数 之 后 入 栈 ; 3) 出 栈 操 作 必 须 在 调 用 端 执 行 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:... 调 用 端 被 调 用 函 数 图 pop() 操 作 位 于 调 用 端 正 是 由 于 上 述 差 异,Visual C++ 中 约 定, 一 个 函 数 如 果 用 cdecl 申 明, 这 意 味 着 其 参 数 以 传 统 的 C 语 言 方 式 出 入 栈, 即 参 数 从 右 往 左 逆 序 入 栈 并 且 由 调 用 端 弹 出 这 样 做 是 为 了 保 证 可 变 参 数 的 实 现 如 果 用 pascal 申 明, 这 意 味 着 其 参 数 以 Pascal 语 言 方 式 出 入 栈 (Pascal 语 言 不 允 许 可 变 参 数 ), 即 参 数 从 左 往 右 顺 序 入 栈 并 且 由 被 调 用 函 数 负 责 弹 出 作 为 一 个 高 级 程 序 员, 你 应 该 明 白 其 中 的 差 异 和 各 自 的 优 缺 点, 知 道 该 在 什 么 情 况 下 选 用 哪 种 申 明 运 行 堆 栈 常 用 来 保 存 哪 些 数 据? 通 过 以 上 分 析, 我 们 知 道 运 行 堆 栈 常 用 来 保 存 返 回 地 址 和 参 数 另 外, 函 数 的 局 部 变 量 和 临 时 变 量 也 需 要 保 存 到 运 行 堆 栈 中 所 谓 临 时 变 量 是 指 计 算 机 内 部 为 了 计 算 程 序 的 运 行 结 果 而 临 时 设 置 的 变 量 比 如 为 了 计 算 a+b+c, 计 算 机 首 先 计 算 a+b 的 结 果, 并 把 结 果 保 存 到 一 个 临 时 变 量 里 面, 然 后 计 算 这 个 临 时 变 量 与 c 的 和 另 外, 对 于 Pascal 语 言 来 说, 为 了 使 程 序 员 能 够 在 函 数 和 过 程 内 定 义 子 函 数 或 子 过 程, 运 行 堆 栈 还 要 保 存 Display 表 不 明 白 什 么 是 Display 表 的 读 者 可 以 略 过 这 句 话 42
43 第 三 章 递 归 程 序 设 计 递 归 调 用 与 一 般 函 数 调 用 以 上 分 析 都 是 对 一 般 函 数 调 用 来 说 的 但 是 这 个 分 析 对 递 归 调 用 来 说 同 样 成 立 如 果 一 个 函 数 内 部 递 归 调 用 自 己, 那 么 与 一 般 函 数 调 用 一 样, 递 归 调 用 时 也 是 压 入 返 回 地 址 和 参 数, 然 后 跳 转 到 被 调 用 函 数 的 第 一 行 即 可 唯 一 不 同 的 是, 递 归 调 用 所 要 跳 转 的 目 的 地 就 是 当 前 调 用 函 数 的 第 一 行 所 谓 递 归 无 非 就 是 调 用 函 数 和 被 调 用 函 数 是 同 一 个 函 数 罢 了 所 以 计 算 机 内 部 其 实 并 不 区 分 递 归 还 是 非 递 归, 更 不 区 分 直 接 递 归 和 间 接 递 归 只 要 遇 到 函 数 调 用, 就 向 运 行 堆 栈 中 压 入 返 回 地 址 和 参 数, 然 后 跳 转 到 被 调 用 函 数 的 第 一 行 就 可 以 了! 原 来 递 归 和 一 般 函 数 调 用 并 没 有 多 大 差 异, 它 们 背 后 的 实 质 居 然 完 全 相 同 像 这 样 不 同 的 概 念 和 理 论 殊 路 同 归, 最 后 归 结 为 同 样 实 质 的 现 象 在 计 算 机 理 论 和 数 学 中 比 比 皆 是, 这 也 是 我 们 学 习 它 们 的 最 大 趣 味 来 源 之 一 现 在 为 了 证 实 我 们 的 理 论 ( 即 递 归 调 用 与 非 递 归 调 用 实 质 相 同 ), 我 们 考 察 二 叉 树 的 非 递 归 中 序 遍 历 算 法 非 递 归 中 序 遍 历 图 给 出 了 一 棵 二 叉 树 及 其 对 应 图 二 叉 树 的 中 序 遍 历 的 中 序 二 叉 树 中 序 遍 历 的 递 归 算 法 非 常 简 单 也 很 容 易 理 解, 参 见 例 例 则 给 出 了 二 叉 树 中 的 结 点 BianryNode 的 定 义 例 BinaryNode 的 定 义 package com.training.recursion; 中 序 :DBEAFCG public interface BinaryNode { Object getvalue(); BinaryNode getleft(); BinaryNode getright(); 例 二 叉 树 中 序 遍 历 的 递 归 算 法 package com.training.recursion; import java.util.stack; 43
44 第 三 章 递 归 程 序 设 计 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); 现 在 我 们 试 图 按 照 上 节 的 理 论 把 例 中 的 递 归 算 法 改 写 成 一 个 非 递 归 算 法 当 然, 很 多 教 材 已 经 给 出 了 二 叉 树 中 序 遍 历 的 非 递 归 算 法 的 例 子, 比 如 例 就 是 一 个 例 子 我 们 的 目 的 是 : 把 例 中 的 递 归 函 数 visitrim_recursively() 的 代 码 进 行 变 换, 最 后 得 到 一 个 与 例 中 非 递 归 函 数 visitrim_unrecursively() 的 代 码 一 模 一 样 的 程 序! 例 二 叉 树 中 序 遍 历 的 非 递 归 算 法 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
45 第 三 章 递 归 程 序 设 计 递 归 程 序 非 递 归 化 示 例 第 一 步 : 给 代 码 的 每 一 个 行 加 行 号 这 一 步 的 结 果 参 见 例 加 行 号 的 目 的 是 为 了 方 便 后 面 引 用 指 定 的 行 例 给 递 归 函 数 的 每 一 行 一 个 编 号 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()); 第 二 步 : 使 用 Stack, push(), pop() 和 goto 替 换 递 归 调 用 这 一 步 的 结 果 参 见 例 注 意, 原 递 归 函 数 中 没 有 用 到 局 部 变 量, 而 临 时 变 量 虽 然 有 用 到, 但 是 在 高 级 语 言 编 程 中 不 必 考 虑 所 以 运 行 堆 栈 中 只 需 压 入 返 回 地 址 和 唯 一 的 参 数 即 可 例 用 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
46 第 三 章 递 归 程 序 设 计 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: 第 三 步 : 用 while 替 换 if 和 goto if 打 头 goto 结 尾 的 一 组 语 句 可 以 用 一 个 while 循 环 代 替 结 果 参 见 例 例 用 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
47 第 三 章 递 归 程 序 设 计 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: 第 四 步 : 用 while 循 环 处 理 返 回 地 址 60 请 看 例 中 函 数 结 尾 的 switch 语 句, 当 返 回 地 址 是 60 时, 实 际 执 行 的 是 一 个 循 环 我 们 就 用 一 个 while 循 环 处 理 这 个 60, 结 果 参 见 例 例 用 while 循 环 处 理 返 回 地 址 60 public void visitrim_recursively(binarynode node) { 47
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; 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: 第 五 步 : 消 除 最 后 的 goto 30 语 句 方 法 是 把 例 中 第 行 的 代 码 统 统 移 到 后 面 并 加 上 一 个 goto 10 语 句 结 果 参 见 例 例 消 除 最 后 的 goto 30 语 句 public void visitrim_recursively(binarynode node) { 48
49 第 三 章 递 归 程 序 设 计 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; // 第 行 移 到 这 里 // 最 后 还 要 加 一 个 goto 语 句 70: 第 六 步 : 删 除 goto 10 第 一 个 goto 10 语 句 完 全 多 余, 可 以 直 接 删 除 第 二 个 goto 10 语 句 可 以 用 一 个 while(true) 死 循 环 代 替 结 果 参 见 例 例 删 除 goto 10 语 句 49
50 第 三 章 递 归 程 序 设 计 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: 第 七 步 : 用 30 取 代 返 回 地 址 70 如 果 运 行 堆 栈 中 的 当 前 返 回 地 址 是 70 时, 把 这 个 地 址 弹 出 堆 栈 之 后, 堆 栈 中 必 50
51 第 三 章 递 归 程 序 设 计 然 为 空 所 以 我 们 可 以 用 判 断 堆 栈 是 否 为 空 的 办 法 取 代 判 断 返 回 地 址 是 否 是 70 这 样 做 的 好 处 是 返 回 地 址 从 原 来 的 三 个 变 为 两 个 : 30 和 60 结 果 参 见 例 例 用 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 代 替 呢? 请 注 意 例 中 的 第 和 64 行, 在 判 断 堆 栈 是 否 为 空 之 前, 如 果 返 回 地 址 ( 即 addr) 是 60, 则 需 要 执 行 一 个 循 环, 所 以 用 60 是 不 合 适 的, 我 51
52 第 三 章 递 归 程 序 设 计 们 只 能 选 择 第 八 步 : 提 前 执 行 弹 出 操 作 请 看 例 第 63 行, 返 回 地 址 是 60 时, 堆 栈 总 会 执 行 一 个 pop() 操 作 而 不 会 执 行 其 他 操 作 所 以 我 们 可 以 在 压 入 60 之 前 就 执 行 这 个 pop() 操 作, 从 而 为 堆 栈 节 省 空 间 然 后 60 也 就 不 必 压 入 堆 栈 了 由 于 返 回 地 址 只 剩 下 唯 一 的 30 了, 所 以 改 为 压 入 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(); 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
53 第 三 章 递 归 程 序 设 计 70: 第 九 步 : 删 除 与 返 回 地 址 60 有 关 的 操 作 由 于 堆 栈 中 的 地 址 不 可 能 是 60, 所 以 所 有 与 之 有 关 的 语 句 都 可 以 删 除 了 结 果 参 见 例 例 删 除 与 返 回 地 址 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
54 第 三 章 递 归 程 序 设 计 70: 第 十 步 : 返 回 地 址 30 也 不 需 要 了 没 有 好 也 就 无 所 谓 坏, 没 有 阴 也 就 无 所 谓 阳 一 个 事 物 如 果 没 有 对 立 面 的 话, 那 它 就 没 有 存 在 的 理 由 了 作 为 唯 一 的 返 回 地 址, 30 本 身 也 不 再 被 需 要 我 们 删 除 所 有 压 入 返 回 地 址 30 的 操 作, 结 果 参 见 例 例 返 回 地 址 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
55 第 三 章 递 归 程 序 设 计 stack.push(node); 70: 第 十 一 步 : 消 除 node 与 stack 栈 顶 的 重 复 请 看 例 , 你 会 发 现 变 量 node 和 堆 栈 stack 的 栈 顶 元 素 是 重 复 的 这 就 提 示 了 我 们 可 以 删 除 这 个 栈 顶 元 素 从 而 为 堆 栈 再 节 省 一 个 单 位 空 间, 结 果 参 见 例 例 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
56 第 三 章 递 归 程 序 设 计 70: 比 较 例 与 例 3.3-3, 你 会 发 现 两 个 例 子 中 的 代 码 完 全 一 致 这 就 是 计 算 机 理 论 的 魅 力 3.4. 哑 元 与 不 可 递 归 性 什 么 是 哑 元 哑 元 (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) 当 然, 局 部 变 量 和 临 时 变 量 也 和 哑 元 一 样 放 在 内 存 中 相 对 固 定 位 置 处, 图 忽 略 了 它 们 以 图 为 例, 所 谓 哑 实 结 合 就 是 在 函 数 调 用 m(12, 25) 时, 把 实 元 和 返 回 地 址 分 别 放 入 内 存 10 号 20 号 和 30 号 位 置 处 那 这 与 参 数 有 什 么 区 别 呢? 头 部 函 数 体 图 哑 元 返 回 地 址 和 函 数 体 一 样, 都 是 放 在 内 存 中 相 对 固 定 的 位 置 处 56
57 第 三 章 递 归 程 序 设 计 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 次 递 归 调 用 hanoi() 函 数 后 的 状 态 哑 元 与 参 数 的 差 别 哑 元 与 参 数 的 最 大 差 异 是 : 哑 元 永 远 只 有 一 个 备 份 这 就 象 函 数 的 函 数 体 在 内 存 中 不 可 能 有 两 个 备 份 一 样 但 是 参 数 是 独 立 于 函 数 体 存 在 于 运 行 堆 栈 中 的, 对 同 一 个 函 数 m(x, y) 来 说, 它 的 参 数 x 和 y 在 运 行 堆 栈 中 可 以 有 多 个 备 份 以 递 归 函 数 hanoi(a, b, c, n) 为 例 ( 参 见 例 3.1-2), 假 设 主 程 序 调 用 hanoi( A, B, C, 5) 则 3 次 递 归 调 用 以 后, 运 行 堆 栈 的 状 态 如 图 所 示 运 行 堆 栈 中 出 现 了 3 个 返 回 地 址,3 个 参 数 a 参 数 b 和 参 数 c 正 是 由 于 每 次 递 归 调 用 时 计 算 机 都 会 向 运 行 堆 栈 压 入 参 数, 从 而 保 证 了 每 次 递 归 调 用 的 参 数 不 会 同 上 一 次 递 归 调 用 的 参 数 相 混 淆 而 哑 元 保 存 在 内 存 中 相 对 固 定 的 位 置, 同 一 个 哑 元 在 内 存 中 只 有 一 个 备 份, 因 而 对 同 一 个 哑 元 赋 值 将 导 致 该 哑 元 的 旧 值 被 覆 盖 所 以 哑 元 的 存 在 将 导 致 被 递 归 调 用 的 函 数 的 参 数 混 乱, 因 而 Fortran 77 约 定 函 数 的 递 归 调 用 是 不 允 许 的, 连 间 接 递 归 都 不 行! 那 么 哑 元 就 没 有 优 势 了 吗? 哑 元 以 不 允 许 递 归 为 代 价 换 来 的 好 处 是 : 哑 元 存 在 于 内 存 相 对 固 定 的 地 方, 而 参 数 是 放 在 堆 栈 里 的, 所 以 哑 元 的 定 位 比 较 直 接, 而 参 数 的 定 位 必 须 计 算 运 行 堆 栈 的 栈 顶 指 针 + 参 数 相 对 于 栈 顶 的 偏 移 所 以 参 数 的 定 位 要 多 计 算 一 次 加 法 ( 或 减 法, 取 决 于 堆 栈 开 口 是 向 下 还 是 向 上 ) 所 以 Fortran 77 程 序 相 对 于 其 它 使 用 参 数 的 高 级 语 言 速 度 要 快 由 于 科 学 计 算 往 往 计 算 量 巨 大, 对 程 序 的 运 行 速 度 要 求 较 高, 因 而 Fortran 77 是 高 级 语 言 中 特 别 适 合 编 写 科 学 计 算 程 序 的 语 言 而 递 归 提 高 了 程 序 的 简 洁 性 和 可 读 性, 但 是 运 行 速 度 就 受 到 了 一 定 限 制 所 以 后 来 的 Fortran 语 言 对 Fortran 77 进 行 了 改 进, 允 许 程 序 员 选 择 使 用 参 数 或 哑 元 57
58 第 三 章 递 归 程 序 设 计 作 为 一 个 高 级 程 序 员, 你 应 该 明 白 两 者 的 差 异 以 及 各 自 的 优 缺 点, 从 而 做 出 正 确 的 选 择 58
59 第 四 章 数 的 进 制 第 四 章 数 的 进 制 计 算 机 中 常 用 的 进 制 是 二 进 制, 我 们 日 常 生 活 中 常 用 的 是 十 进 制 您 可 能 会 觉 得 很 奇 怪 : 进 制 虽 然 重 要 但 并 不 很 复 杂 和 困 难, 它 有 必 要 成 为 一 本 专 门 面 向 高 级 程 序 员 的 教 材 中 单 独 的 一 章 吗? 为 了 回 答 这 个 问 题, 先 来 看 看 第 一 个 问 题 : 猜 姓 名 4.1. 猜 姓 名 问 题 90 年 代 初 的 一 天 我 在 上 海 浦 东 的 一 条 马 路 边 闲 逛 忽 然 看 见 有 一 群 人 聚 在 一 起 看 算 命 那 个 算 命 先 生 的 身 前 铺 有 七 张 纸, 每 张 纸 上 密 密 麻 麻 地 写 有 五 六 十 个 姓 氏 他 说 他 是 个 神 算 子, 只 要 告 诉 他 哪 几 张 纸 上 有 你 的 姓, 他 就 知 道 你 姓 什 么 有 这 等 怪 事? 旁 边 有 人 不 信, 拿 起 纸 来 试 了 试 结 果 百 发 百 中, 我 们 的 神 算 子 先 生 每 次 都 能 准 确 猜 出 对 方 的 姓 自 然 大 家 对 他 的 神 术 也 就 比 较 相 信 了, 有 不 少 人 掏 钱 请 他 算 了 命 当 然 这 位 神 算 子 是 个 大 骗 子, 你 能 独 立 看 出 他 的 骗 术 在 哪 里 吗? 神 算 子 的 秘 密 秘 密 就 在 那 七 张 纸 上 因 为 你 必 须 首 先 告 诉 人 家 你 的 姓 出 现 在 那 几 张 纸 上, 那 么 这 七 张 纸 的 排 列 组 合 可 以 表 示 多 少 姓 氏? 这 不 难 计 算, 答 案 是 即 127 个 姓 氏 所 以 把 百 家 姓 中 的 每 个 姓 用 七 位 的 二 进 制 进 行 编 码, 然 后 根 据 0 或 1 决 定 相 应 的 姓 氏 是 否 要 写 到 对 应 的 纸 上 即 可 比 如 百 家 姓 中 前 八 个 姓 的 编 码 如 下 : 表 姓 氏 的 二 进 制 编 码 及 其 所 属 纸 张 姓 氏 Page7 Page6 Page5 Page4 Page3 Page2 Page1 1. 赵 钱 孙 李 周 吴 郑 王 如 果 上 表 中 某 个 单 元 的 值 是 1, 则 其 横 向 对 应 的 姓 氏 就 应 该 写 到 纵 向 对 应 的 纸 上 比 如 第 一 张 纸 (Page1) 上 就 应 该 写 赵 孙 周 郑 等 姓 氏 吴 就 应 该 写 到 第 二 (Page2) 和 第 三 张 (Page3) 纸 上 现 在 你 就 可 以 表 演 神 算 子 了 比 如 有 人 告 诉 你 说 他 的 姓 氏 出 现 在 第 一 和 第 三 张 纸 上 这 意 味 着 他 的 姓 氏 的 编 码 是 , 即 第 5 个 姓, 所 以 他 姓 周! 神 算 子 程 序 现 在 我 们 编 一 个 程 序 模 拟 神 算 子 猜 名 字 的 过 程 这 个 程 序 一 旦 成 功, 大 家 就 可 以 上 59
60 第 四 章 数 的 进 制 街 骗 钱 了 如 有 收 获 务 必 记 住 给 本 书 作 者 方 博 士 分 一 半 红 如 被 警 察 或 城 管 抓 住 则 与 本 人 毫 无 关 系! 这 个 程 序 首 先 要 用 一 个 数 据 结 构 表 示 各 种 姓 氏 结 合 Java 的 实 际 情 况, 我 们 用 一 个 字 符 串 数 组 names 来 存 储 姓 氏 的 拼 音 姓 氏 在 这 个 字 符 串 数 组 中 的 下 标 就 是 它 的 编 码 问 题 是, 下 标 是 从 0 开 始 计 数 的, 而 我 们 只 能 从 1 开 始 编 码,0 是 不 能 用 的 解 决 这 个 问 题 的 办 法 有 两 个 :1) 在 进 行 下 标 和 编 码 之 间 的 转 换 时 进 行 加 1 或 减 1 操 作 ;2) 在 names 数 组 的 0 下 标 处 插 入 一 个 无 用 姓 氏 比 如 null 你 认 为 哪 个 方 法 更 好? 第 一 个 方 法 以 牺 牲 速 度 换 空 间 第 二 个 方 法 相 反, 以 多 用 一 个 单 位 空 间 换 来 下 标 和 编 码 之 间 的 直 接 对 应 他 们 之 间 还 有 一 个 更 重 要 的 差 别 : 前 者 的 代 码 要 比 后 者 复 杂 这 样 一 分 析, 你 知 道 该 使 用 哪 个 办 法 了 吧? 根 据 自 顶 向 下 的 程 序 设 计 原 则, 我 们 首 先 考 虑 主 程 序 主 程 序 首 先 调 用 getpages() 函 数 以 获 得 神 算 子 的 那 些 写 满 姓 氏 的 纸 张 然 后 循 环 执 行 playgame() 玩 这 个 游 戏 直 到 不 想 玩 为 止 主 程 序 形 如 : 例 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() 两 个 子 函 数 上 getpages() 函 数 getpages() 函 数 的 目 的 是 根 据 输 入 的 所 有 姓 氏 计 算 要 准 备 多 少 张 纸, 以 及 每 张 纸 上 应 该 写 哪 些 姓 氏 可 以 这 样 考 虑 : 把 姓 氏 的 二 进 制 编 码 从 右 到 左 分 别 称 为 第 0 位 第 1 位 60
61 第 四 章 数 的 进 制 第 2 位, 参 见 图 然 后 把 要 生 成 的 纸 张 按 第 0 张 第 1 张 第 2 张 的 次 序 排 序, 依 序 考 虑 图 姓 氏 二 进 制 编 码 的 每 一 位 对 于 第 i 张 (i=0, 1, 2, ) 纸, 凡 是 二 进 制 编 码 的 第 i 位 是 1 的 姓 氏 都 应 该 加 入 到 这 张 纸 中 如 果 没 有 一 个 姓 氏 加 入 到 某 张 纸 中, 则 意 味 着 这 张 纸 是 多 余 的 所 以 getpages() 函 数 可 以 这 样 编 写 : 例 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: 例 package com.training.numeralsystem; 61
62 第 四 章 数 的 进 制 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; playgame() 函 数 playgame(pages) 子 函 数 的 目 的 是 带 领 用 户 玩 一 次 游 戏 函 数 将 在 命 令 行 上 循 环 首 先 显 示 神 算 子 的 每 一 张 纸, 询 问 用 户 这 张 纸 上 是 否 有 他 的 姓 氏, 记 录 并 计 算 用 户 的 输 入 这 样 考 虑 未 必 是 最 优 的, 可 能 你 更 乐 意 通 过 一 个 GUI 界 面 跟 用 户 交 互 我 的 目 的 仅 仅 是 让 你 体 验 用 自 顶 向 下 的 方 法 如 何 理 清 你 自 己 头 脑 中 程 序 设 计 的 思 路 : 例 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
63 第 四 章 数 的 进 制 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."); 通 用 的 神 算 子 程 序 在 前 面 程 序 中, 为 了 保 证 汉 字 的 输 入 和 显 示 正 常, 我 们 用 拼 音 来 表 示 汉 字 所 以 我 们 需 要 用 一 个 字 符 串 数 组 String[] 来 存 储 所 有 姓 氏 的 拼 音 但 有 时 我 们 可 能 希 望 直 接 使 用 汉 字, 从 而 可 以 用 类 似 于 \u0000 赵 钱 孙 李 周 吴 郑 王 这 样 的 字 符 串 来 存 储 姓 氏 这 样 我 们 就 需 要 编 写 一 个 通 用 的 程 序 以 便 剥 离 姓 氏 等 具 体 业 务 信 息, 而 把 精 力 集 中 在 编 码 的 计 算 和 转 换 上 以 下 是 这 个 通 用 程 序 的 核 心 代 码 : 例 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
64 第 四 章 数 的 进 制 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 以 便 使 用 这 个 通 用 函 数 留 待 读 者 考 虑 瓶 药 水 有 100 瓶 药 水, 其 中 有 且 仅 有 一 瓶 是 变 质 的, 但 外 表 看 不 出 来 现 在 有 一 台 非 常 灵 敏 但 很 昂 贵 的 机 器 可 以 检 测 出 药 水 中 的 微 量 变 质 成 分 请 设 计 一 个 方 案 用 最 少 的 次 数 就 可 以 检 测 出 哪 瓶 药 水 是 变 质 的 相 同 的 解 法 这 一 题 与 上 一 节 中 的 猜 姓 名 的 解 法 完 全 相 同 即 把 每 瓶 药 水 从 1 到 100 编 码 凡 编 码 二 进 制 的 第 i 位 (i=0,1,2, ) 是 1 的, 从 这 瓶 药 水 中 取 一 滴 参 与 第 i 次 检 测 每 次 检 测 的 药 水 由 从 相 应 的 药 水 瓶 中 取 出 的 若 干 滴 混 合 而 成 检 测 时 若 发 现 被 检 测 的 混 合 药 水 变 质 就 记 一 个 二 进 制 1, 否 则 记 0 最 后 把 所 有 的 0 1 凑 在 一 起 构 成 一 个 二 进 制 码, 它 的 值 是 多 少 就 意 味 着 第 几 瓶 药 水 是 变 质 的 显 然, 一 共 只 需 要 7 次 检 测 就 可 以 确 定 变 质 的 药 水 是 哪 一 瓶 由 于 方 法 相 同, 这 里 不 再 给 出 程 序 二 分 法 如 果 你 认 为 上 述 二 进 制 编 码 法 理 解 起 来 有 那 么 一 点 点 困 难, 那 么 二 分 法 不 但 从 另 一 个 角 度 解 释 了 二 进 制 编 码 法, 而 且 更 容 易 理 解 : 把 所 有 药 水 分 为 两 组, 每 组 50 瓶 从 第 一 组 的 50 瓶 药 水 中 各 取 一 滴 混 合 起 来 然 后 做 第 一 次 检 测, 如 果 变 质, 则 意 味 着 变 质 药 水 在 第 一 组, 否 则 就 在 第 二 组 50 瓶 中 把 确 定 存 在 变 质 药 水 的 50 瓶 药 水 再 分 为 两 组, 每 组 25 瓶, 重 复 上 述 检 测 同 样 仅 需 要 经 过 7 次 检 测 也 可 以 确 定 变 质 的 药 水 是 哪 一 瓶 二 分 法 的 实 质 是 把 一 个 数 (100) 不 断 的 除 以 2 的 过 程 它 实 质 上 与 二 进 制 编 码 法 是 等 价 的 科 学 在 这 里 又 巧 妙 地 表 演 了 一 次 殊 路 同 归 4.3. 十 二 个 小 球 问 题 有 12 个 外 形 一 模 一 样 的 小 球 和 一 架 天 平 有 且 仅 有 一 个 小 球 的 重 量 与 其 他 小 球 不 同, 64
65 第 四 章 数 的 进 制 可 能 重 些 也 可 能 轻 些, 但 外 表 看 不 出 来 其 他 小 球 则 重 量 完 全 一 样 现 在 要 求 你 用 天 平 仅 称 三 次, 就 能 把 那 个 与 众 不 同 的 小 球 找 出 来 还 要 知 道 它 是 轻 的 还 是 重 的 如 果 你 是 第 一 次 接 触 这 道 题, 那 么 请 不 要 认 为 这 道 题 很 容 易 实 际 上 它 在 我 遇 到 的 所 有 智 力 题 中 几 乎 是 最 难 的 我 大 概 是 1990 年 第 一 次 遇 到 这 道 题, 至 今 近 20 年 了, 从 没 有 遇 到 一 个 人 独 立 解 决 这 道 题! 当 然 如 果 你 尝 试 之 后 觉 得 它 太 难 你 可 以 很 容 易 从 网 上 或 本 书 下 面 说 明 中 获 得 答 案 人 工 解 把 12 个 小 球 分 成 3 组, 每 组 4 个 先 用 天 平 称 第 一 组 和 第 二 组 第 一 组 在 左, 第 二 组 在 右 这 时 会 有 三 种 情 况 : 1) 左 边 重 右 边 轻, 参 见 图 这 意 味 着 坏 球 如 果 是 重 球 的 话 一 定 在 第 一 组 中, 如 果 是 轻 球 的 话 一 定 在 第 二 组 中 图 第 一 次 称 量 第 一 种 情 况 : 左 边 重 右 边 轻 现 在 从 第 二 组 中 任 意 取 出 3 个 放 到 一 边 ( 注 意, 这 3 个 球 中 存 在 可 能 的 轻 球 ), 留 下 1 个 仍 然 在 右 边 托 盘 上 再 从 左 边 第 一 组 中 任 取 出 3 个 放 到 天 平 右 边 托 盘 上 再 从 第 三 组 中 取 3 个 好 球 放 在 天 平 左 边 托 盘 上, 进 行 第 二 次 称 量 参 见 图
66 第 四 章 数 的 进 制 图 在 第 一 种 情 况 下 移 动 小 球 图 第 一 种 情 况 下 的 第 二 次 称 量 图 显 示 天 平 第 二 次 称 这 时 又 有 三 种 可 能 : 天 平 平 衡 这 意 味 着 放 到 旁 边 去 的 3 个 第 二 组 的 球 中 必 有 一 个 坏 球, 而 且 还 一 定 是 个 轻 球 从 中 任 取 两 个 放 到 天 平 两 端 作 第 三 次 称 量 : 若 平 衡, 则 确 定 唯 一 剩 下 的 那 个 第 二 组 的 球 是 坏 的 轻 球 ; 或 不 平 衡 则 轻 的 那 端 是 坏 球 左 边 轻 右 边 重, 即 与 图 相 反 这 意 味 着 刚 才 从 左 边 移 到 右 边 的 3 个 第 一 组 的 球 中 有 坏 球 并 且 是 个 重 球 从 中 任 取 两 个 放 到 天 平 两 端 作 第 三 次 称 量 : 若 平 衡, 则 确 定 唯 一 剩 下 的 那 个 第 一 组 的 球 是 坏 的 重 球 ; 或 不 平 衡 则 重 的 那 端 是 坏 球 左 边 重 右 边 轻, 即 与 图 相 同 这 意 味 着 如 果 坏 球 是 个 重 球 的 话 那 它 一 定 是 左 边 托 盘 里 唯 一 剩 下 的 那 个 第 一 组 的 球 ; 如 果 坏 球 是 个 轻 球 的 话 那 它 一 定 是 右 边 托 盘 里 唯 一 剩 下 的 那 个 第 二 组 的 球 我 们 拿 起 其 66
67 第 四 章 数 的 进 制 中 的 一 个 跟 一 个 好 球 称 一 称 就 行 了 2) 第 一 次 称 时 如 果 左 边 轻 右 边 重, 这 种 情 况 跟 图 所 示 的 情 况 是 对 称 的 按 照 上 文 的 讨 论 我 们 只 需 再 称 两 次 就 必 然 可 以 找 到 那 个 坏 球 还 知 道 轻 重 3) 最 后 一 种 情 况 就 是 第 一 次 称 时 两 边 平 衡 那 坏 球 一 定 在 第 三 组 中 我 们 从 中 任 取 3 个 和 1 个 好 球 一 起 如 图 所 示 那 样 进 行 第 二 次 称 量 计 算 机 解 图 第 一 次 称 量 平 衡 时 的 第 二 次 称 量 这 样 就 有 三 种 情 况 : 平 衡 则 唯 一 剩 下 的 那 个 第 三 组 的 球 是 坏 球, 我 们 再 用 天 平 把 它 和 一 个 好 球 称 一 下 就 知 道 它 是 轻 的 还 是 重 的 左 边 重 右 边 轻 这 意 味 着 如 果 坏 球 是 个 重 球 的 话, 那 它 就 是 左 边 托 盘 里 唯 一 的 那 个 第 三 组 的 球 ; 如 果 坏 球 是 个 轻 球 的 话, 那 它 一 定 是 右 边 托 盘 里 两 个 球 之 一 我 们 把 右 边 的 两 个 球 放 到 天 平 的 两 端 作 第 三 次 称 量 : 如 果 平 衡, 则 图 中 左 边 唯 一 一 个 第 三 组 的 球 是 坏 球, 并 且 是 个 重 球 ; 如 果 不 平 衡, 则 轻 的 那 端 是 坏 球 左 边 轻 右 边 重 这 种 情 况 跟 上 面 情 况 是 对 称 的, 把 上 面 文 字 中 轻 重 两 个 字 交 换 即 可 说 明 这 种 情 况 如 果 我 跟 你 说 12 个 小 球 问 题 可 以 编 一 个 程 序 来 解, 而 且 这 个 程 序 并 不 复 杂, 你 相 信 吗? 计 算 机 科 学 的 一 个 巨 大 魅 力 就 在 于 她 能 让 计 算 机 做 出 许 多 不 可 思 议 的 事 情, 包 括 解 这 个 用 人 脑 要 想 破 头 的 12 小 球 问 题 为 什 么 人 类 习 惯 使 用 十 进 制 呢? 因 为 人 的 两 只 手 恰 好 有 十 个 手 指 头, 计 数 方 便 如 果 外 星 人 有 八 个 手 指 头, 那 我 敢 肯 定 他 们 常 用 的 是 八 进 制 不 信 你 就 逮 一 个 外 星 人 给 我 看 看? 计 算 机 为 什 么 要 用 二 进 制 呢? 因 为 绝 大 多 数 电 子 元 器 件 的 状 态 有 两 种 : 接 通 或 关 闭 电 流 高 或 低 磁 性 有 或 无 如 果 外 星 人 的 元 器 件 的 状 态 主 要 有 三 种 的 话 我 相 信 他 们 的 计 算 机 会 使 用 三 进 制 所 以 二 进 制 也 好, 十 进 制 也 好, 八 进 制 也 好, 甚 至 三 进 制 也 好, 本 身 并 无 孰 优 孰 劣 计 数 的 能 力 也 是 相 同 的 ( 如 果 你 愿 意 甚 至 用 一 进 制 也 行 在 后 面 章 节 中 我 就 会 提 到 一 进 制 ) 差 别 仅 在 于 用 起 来 是 否 方 便 67
新・解きながら学ぶJava
481! 41, 74!= 40, 270 " 4 % 23, 25 %% 121 %c 425 %d 121 %o 121 %x 121 & 199 && 48 ' 81, 425 ( ) 14, 17 ( ) 128 ( ) 183 * 23 */ 3, 390 ++ 79 ++ 80 += 93 + 22 + 23 + 279 + 14 + 124 + 7, 148, 16 -- 79 --
More informationMicrosoft Word - 第3章.doc
Java C++ Pascal C# C# if if if for while do while foreach while do while C# 3.1.1 ; 3-1 ischeck Test() While ischeck while static bool ischeck = true; public static void Test() while (ischeck) ; ischeck
More informationuntitled
1 Outline 數 料 數 數 列 亂數 練 數 數 數 來 數 數 來 數 料 利 料 來 數 A-Z a-z _ () 不 數 0-9 數 不 數 SCHOOL School school 數 讀 school_name schoolname 易 不 C# my name 7_eleven B&Q new C# (1) public protected private params override
More information(TestFailure) JUnit Framework AssertionFailedError JUnit Composite TestSuite Test TestSuite run() run() JUnit
Tomcat Web JUnit Cactus JUnit Java Cactus JUnit 26.1 JUnit Java JUnit JUnit Java JSP Servlet JUnit Java Erich Gamma Kent Beck xunit JUnit boolean JUnit Java JUnit Java JUnit Java 26.1.1 JUnit JUnit How
More informationMicrosoft Word - 01.DOC
第 1 章 JavaScript 简 介 JavaScript 是 NetScape 公 司 为 Navigator 浏 览 器 开 发 的, 是 写 在 HTML 文 件 中 的 一 种 脚 本 语 言, 能 实 现 网 页 内 容 的 交 互 显 示 当 用 户 在 客 户 端 显 示 该 网 页 时, 浏 览 器 就 会 执 行 JavaScript 程 序, 用 户 通 过 交 互 式 的
More information1 4 1.1 4 1.2..4 2..4 2.1..4 3.4 3.1 Java.5 3.1.1..5 3.1.2 5 3.1.3 6 4.6 4.1 6 4.2.6 5 7 5.1..8 5.1.1 8 5.1.2..8 5.1.3..8 5.1.4..9 5.2..9 6.10 6.1.10
Java V1.0.1 2007 4 10 1 4 1.1 4 1.2..4 2..4 2.1..4 3.4 3.1 Java.5 3.1.1..5 3.1.2 5 3.1.3 6 4.6 4.1 6 4.2.6 5 7 5.1..8 5.1.1 8 5.1.2..8 5.1.3..8 5.1.4..9 5.2..9 6.10 6.1.10 6.2.10 6.3..10 6.4 11 7.12 7.1
More informationFY.DOC
高 职 高 专 21 世 纪 规 划 教 材 C++ 程 序 设 计 邓 振 杰 主 编 贾 振 华 孟 庆 敏 副 主 编 人 民 邮 电 出 版 社 内 容 提 要 本 书 系 统 地 介 绍 C++ 语 言 的 基 本 概 念 基 本 语 法 和 编 程 方 法, 深 入 浅 出 地 讲 述 C++ 语 言 面 向 对 象 的 重 要 特 征 : 类 和 对 象 抽 象 封 装 继 承 等 主
More informationCC213
: (Ken-Yi Lee), E-mail: feis.tw@gmail.com 49 [P.51] C/C++ [P.52] [P.53] [P.55] (int) [P.57] (float/double) [P.58] printf scanf [P.59] [P.61] ( / ) [P.62] (char) [P.65] : +-*/% [P.67] : = [P.68] : ,
More information新汉语水平考试
新 汉 语 水 平 考 试 HSK( 四 级 ) H41003 注 意 一 HSK( 四 级 ) 分 三 部 分 : 1. 听 力 (45 题, 约 30 分 钟 ) 2. 阅 读 (40 题,40 分 钟 ) 3. 书 写 (15 题,25 分 钟 ) 二 听 力 结 束 后, 有 5 分 钟 填 写 答 题 卡 三 全 部 考 试 约 105 分 钟 ( 含 考 生 填 写 个 人 信 息 时
More informationMicrosoft Word - HSK四级大纲_最新挖改3-5-10-11-14-15-33-34-35_.doc
新 汉 语 水 平 考 试 (HSK) 介 绍 为 使 汉 语 水 平 考 试 (HSK) 更 好 地 服 务 于 汉 语 学 习 者, 中 国 国 家 汉 办 组 织 中 外 汉 语 教 学 语 言 学 心 理 学 和 教 育 测 量 学 等 领 域 的 专 家, 在 充 分 调 查 了 解 海 外 汉 语 教 学 实 际 情 况 的 基 础 上, 吸 收 原 有 HSK 的 优 点, 借 鉴 近
More information使 用 Java 语 言 模 拟 保 险 箱 容 量 门 板 厚 度 箱 体 厚 度 属 性 锁 具 类 型 开 保 险 箱 关 保 险 箱 动 作 存 取 款
JAVA 程 序 设 计 ( 肆 ) 徐 东 / 数 学 系 使 用 Java 语 言 模 拟 保 险 箱 容 量 门 板 厚 度 箱 体 厚 度 属 性 锁 具 类 型 开 保 险 箱 关 保 险 箱 动 作 存 取 款 使 用 Java class 代 表 保 险 箱 public class SaveBox 类 名 类 类 体 实 现 封 装 性 使 用 class SaveBox 代 表 保
More information《大话设计模式》第一章
第 1 章 代 码 无 错 就 是 优? 简 单 工 厂 模 式 1.1 面 试 受 挫 小 菜 今 年 计 算 机 专 业 大 四 了, 学 了 不 少 软 件 开 发 方 面 的 东 西, 也 学 着 编 了 些 小 程 序, 踌 躇 满 志, 一 心 要 找 一 个 好 单 位 当 投 递 了 无 数 份 简 历 后, 终 于 收 到 了 一 个 单 位 的 面 试 通 知, 小 菜 欣 喜
More information3.1 num = 3 ch = 'C' 2
Java 1 3.1 num = 3 ch = 'C' 2 final 3.1 final : final final double PI=3.1415926; 3 3.2 4 int 3.2 (long int) (int) (short int) (byte) short sum; // sum 5 3.2 Java int long num=32967359818l; C:\java\app3_2.java:6:
More information新汉语水平考试
新 汉 语 水 平 考 试 HSK( 四 级 ) H41005 注 意 一 HSK( 四 级 ) 分 三 部 分 : 1. 听 力 (45 题, 约 30 分 钟 ) 2. 阅 读 (40 题,40 分 钟 ) 3. 书 写 (15 题,25 分 钟 ) 二 听 力 结 束 后, 有 5 分 钟 填 写 答 题 卡 三 全 部 考 试 约 105 分 钟 ( 含 考 生 填 写 个 人 信 息 时
More information新汉语水平考试
新 漢 語 水 平 考 試 HSK( 四 級 ) H41005 注 意 一 HSK( 四 級 ) 分 三 部 分 : 1. 聽 力 (45 題, 約 30 分 鐘 ) 2. 閱 讀 (40 題,40 分 鐘 ) 3. 書 寫 (15 題,25 分 鐘 ) 二 聽 力 結 束 後, 有 5 分 鐘 填 寫 答 題 卡 三 全 部 考 試 約 105 分 鐘 ( 含 考 生 填 寫 個 人 資 訊 時
More information全国计算机技术与软件专业技术资格(水平)考试
全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2008 年 上 半 年 程 序 员 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 试 题 一 ( 共 15 分 ) 阅 读 以 下 说 明 和 流 程 图, 填 补 流 程 图 中 的 空 缺 (1)~(9), 将 解 答 填 入 答 题 纸 的 对 应 栏 内 [ 说 明
More informationKillTest 质量更高 服务更好 学习资料 半年免费更新服务
KillTest 质量更高 服务更好 学习资料 http://www.killtest.cn 半年免费更新服务 Exam : 310-065Big5 Title : Sun Certified Programmer for the Java 2 Platform, SE 6.0 Version : Demo 1 / 14 1. 35. String #name = "Jane Doe"; 36. int
More informationjavaexample-02.pdf
n e w. s t a t i c s t a t i c 3 1 3 2 p u b l i c p r i v a t e p r o t e c t e d j a v a. l a n g. O b j e c t O b j e c t Rect R e c t x 1 y 1 x 2 y 2 R e c t t o S t r i n g ( ) j a v a. l a n g. O
More information第 期 熊 安 萍 等 *1$ 文 件 系 统 中 范 围 锁 机 制 的 应 用 研 究! 锁 命 名 空 间 '+'($($ 描 述 了 资 源 和 锁 的 集 合 它 同 时 在 客 户 节 点 和 服 务 节 点 存 在 不 同 之 处 只 是 利 用 一 个 数 据 标 识 来 有 效 区
第 卷 第 期 重 庆 邮 电 大 学 学 报 自 然 科 学 版 年 月!"#$" %$&'$ ''())$($*($'('+$$,-./0 1' 文 件 系 统 中 范 围 锁 机 制 的 应 用 研 究 熊 安 萍 葛 军 邹 洋 重 庆 邮 电 大 学 计 算 机 科 学 与 技 术 学 院 重 庆! 摘 要 分 布 式 锁 机 制 是 分 布 式 文 件 系 统 的 重 要 机 制 *1$
More informationCHAPTER VC#
1. 2. 3. 4. CHAPTER 2-1 2-2 2-3 2-4 VC# 2-5 2-6 2-7 2-8 Visual C# 2008 2-1 Visual C# 0~100 (-32768~+32767) 2 4 VC# (Overflow) 2-1 2-2 2-1 2-1.1 2-1 1 10 10!(1 10) 2-3 Visual C# 2008 10! 32767 short( )
More information中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!" 通 透 性 增 加 产 生 蛋 白 水 解 酶 促 进 血 管 内 皮 细 胞 有 丝 分 裂 内 皮 细 胞 从 基 底 膜 上 迁 移 到 血 管 周 围 间 隙 粘 附 聚 集 重 构 为 三 维 管 腔 并 与 周 围 血 管
中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!" 学 术 探 讨 冠 心 病 的 治 疗 性 血 管 新 生 与 活 血 化 瘀 段 练 熊 兴 江 王 阶 摘 要 治 疗 性 血 管 新 生 /) '0 1/ * ' 是 冠 状 动 脉 硬 化 性 心 脏 病 * '( '/) *! / * ) '/ ' + 治 疗 的 新 策 略 而 活 血 化 瘀 治 法 对 于 + 的 基 础
More informationuntitled
1 Outline 類别 欄 (1) 類 類 狀 更 易 類 理 若 類 利 來 利 using 來 namespace 類 ; (2) namespace IBM class Notebook namespace Compaq class Notebook 類别 類 來 類 列 欄 (field) (property) (method) (event) 類 例 立 來 車 類 類 立 車 欄 料
More informationuntitled
1 Outline 料 類 說 Tang, Shih-Hsuan 2006/07/26 ~ 2006/09/02 六 PM 7:00 ~ 9:30 聯 ives.net@gmail.com www.csie.ntu.edu.tw/~r93057/aspnet134 度 C# 力 度 C# Web SQL 料 DataGrid DataList 參 ASP.NET 1.0 C# 例 ASP.NET 立
More information. "#
. "# . / 0 1 234 54 "# ./0 "# ./0 12 32 42 56 /1/3 532273222 8749 0222 42:702:/132 /22 "" .. / 0.0/ 10. 122 01 122 340516 7 8 7 19 8 :09 5 7 8 7 8 5 "# . / / / 01222 3.222 4 0.222 3562 4 0772 34 0 3 822
More informationC 1
C homepage: xpzhangme 2018 5 30 C 1 C min(x, y) double C // min c # include # include double min ( double x, double y); int main ( int argc, char * argv []) { double x, y; if( argc!=
More informationOOP with Java 通知 Project 4: 4 月 19 日晚 9 点
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 4 月 19 日晚 9 点 复习 类的复用 组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double x) { d
More information! "#$ %$ $ 资 料 与 方 法 $ 调 查 对 象 全 国 东 北 华 北 华 东 西 北 西 南 和 中 南 六 个 大 区 个 省 自 治 区 直 辖 市 * 个 城 市 中 的 & 所 医 院 参 加 了 本 次 调 查 各 省 省 会 城 市 的 医 学 院 校 附 属 医 院 省
! "#$ %$ $ 临 床 研 究 中 国 住 院 新 生 儿 流 行 病 学 调 查 中 华 医 学 会 儿 科 学 分 会 新 生 儿 学 组 摘 要 目 的 通 过 全 国 范 围 内 城 市 医 院 住 院 新 生 儿 的 调 查 以 了 解 我 国 目 前 住 院 新 生 儿 的 疾 病 谱 及 转 归 方 法 抽 取 全 国 个 省 和 自 治 区 的 * 个 城 市 中 的 & 所
More informationC/C++ - 字符输入输出和字符确认
C/C++ Table of contents 1. 2. getchar() putchar() 3. (Buffer) 4. 5. 6. 7. 8. 1 2 3 1 // pseudo code 2 read a character 3 while there is more input 4 increment character count 5 if a line has been read,
More information内 容 简 介 本 书 是 一 本 关 于 语 言 程 序 设 计 的 教 材, 涵 盖 了 语 言 的 基 本 语 法 和 编 程 技 术, 其 中 包 含 了 作 者 对 语 言 多 年 开 发 经 验 的 总 结, 目 的 是 让 初 学 的 读 者 感 受 到 语 言 的 魅 力, 并 掌
语 言 程 序 设 计 郑 莉 胡 家 威 编 著 清 华 大 学 逸 夫 图 书 馆 北 京 内 容 简 介 本 书 是 一 本 关 于 语 言 程 序 设 计 的 教 材, 涵 盖 了 语 言 的 基 本 语 法 和 编 程 技 术, 其 中 包 含 了 作 者 对 语 言 多 年 开 发 经 验 的 总 结, 目 的 是 让 初 学 的 读 者 感 受 到 语 言 的 魅 力, 并 掌 握 语
More information[剑指offer] 面试题43:n个骰子的点数(Java),[剑指offer] 面试题42: 翻转单词顺序 VS左旋转字符串(Java),[剑指offer] 面试题41:和为s的两个数字VS和为s的连续序列
[ 剑 指 offer] 面 试 题 43:n 个 骰 子 的 点 数 (Java) 题 目 : 把 n 个 骰 子 扔 在 地 上, 所 有 骰 子 朝 上 一 面 的 点 数 之 和 为 S 输 入 n, 打 印 出 S 的 所 有 可 能 的 值 出 现 的 概 率 分 析 : 一 般 来 说 骰 子 只 有 6 面, 点 数 为 1~6, n 个 骰 故 子 的 最 小 和 为 n, 最 大
More information./ 0123 455
./ 0123 455 ./ 0/.1 0/2 0 3 0/2 3///41.///.3/ 56 1// 0 1 0/ 2/.///./ ./ 0/ 1/ 223.//. 4 5 6/3 7/3. 4 8 591././ 7 21 :1 01 5 5// :/3 " .. / 0. /.1. / 21. / 3 4.56. 788.947 80.8 81 ./ 0/ 1/ 234 5/4 6 5 0/4.24
More information4 中 南 大 学 学 报 医 学 版 摘 要 目 的 探 讨 早 发 性 精 神 分 裂 症 患 者 在 静 息 状 态 下 是 否 存 在 脑 功 能 连 接 异 常 以 及 异 常 区 域 的 定 位 方 法 采 用 第 版 美 国 精 神 障 碍 诊 断 与 统 计 手 册 ( * ) (
中 南 大 学 学 报 医 学 版 3! + )! + - + - %$ 58: 58:7& * 1:D * $%&' 1&! & )& "# ( &!& )#% & '& '#! & #& & " ( ) 5*( )/ + ( / + + 6') * )* ) ; + *6 / + * ) *+ ' 6') * )+ * ) 6 9, * : + * ) *+ ) /+( * ( / * ) (
More information中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!"# $! 症 状 在 诊 断 时 推 荐 应 用 $3 的 症 状 指 数 $!0 " 0 %!2 3% ". )./!0 ) 1/! 5 1! 0 %7$3 6 进 行 基 础 评 估 和 治 疗 监 测 心 理 状 况 的 评 估 可
专 家 共 识 慢 性 前 列 腺 炎 中 西 医 结 合 诊 疗 专 家 共 识 中 国 中 西 医 结 合 学 会 男 科 专 业 委 员 会 年 月 慢 性 前 列 腺 炎 )./!0 ) 1/! 是 指 前 列 腺 在 病 原 体 或 某 些 非 感 染 因 素 作 用 下 患 者 出 现 以 盆 腔 区 域 疼 痛 或 不 适 排 尿 异 常 等 症 状 为 特 征 的 疾 病 一 直 是
More informationChapter 9: Objects and Classes
Fortran Algol Pascal Modula-2 BCPL C Simula SmallTalk C++ Ada Java C# C Fortran 5.1 message A B 5.2 1 class Vehicle subclass Car object mycar public class Vehicle extends Object{ public int WheelNum
More information北魏山东佛教文化个案研究
北 魏 山 东 佛 教 文 化 个 案 研 究 一 北 魏 时 期 佛 教 在 山 东 的 传 播 与 发 展 以 滨 州 博 兴 龙 华 寺 为 代 表 社 会 背 景 北 魏 佛 教 的 发 展 是 伴 随 着 佛 教 的 中 国 化 即 汉 化 的 过 程 而 不 断 发 展 的, 同 时 也 带 有 北 魏 统 治 者 作 为 少 数 民 族 的 本 身 特 色 自 汉 通 西 域, 佛 教
More information附件1.FIT)
附 件 : 上 海 市 科 技 创 新 人 才 激 励 政 策 操 作 指 南 上 海 市 科 技 创 新 人 才 激 励 政 策 操 作 指 南 2011 年 1 月 国 有 企 业 科 技 创 新 激 励 操 作 指 南 附 件 : 上 海 市 科 技 创 新 人 才 激 励 政 策 操 作 指 南 目 录 1. 人 才 引 进 132 1.1 上 海 市 户 籍 及 居 住 证 132 1.2
More information23 10 18 5 1997 12 1 (1) (7) (16) (25) (35) (37) (44) (48) (51) (54) ( ) (58) (69) (74) (77) (89) (94) (98) (100) (107) (113) (117) (121) (126) " 37 38 ( ) ( ) ( ) ( ) 300 1 500 200 1938 1 30 15 8 1937
More information毛主席的猪
在 孔 孟 之 乡 掘 孔 孟 后 裔 的 坟, 在 生 产 队 的 田 里 放 毛 主 席 的 猪, 也 只 有 知 青 才 有 这 " 特 权 " 吟 了 < 血 色 黄 昏 >, 叹 了 < 蹉 跎 岁 月 >, 再 哼 一 哼 知 青 生 活 中 那 千 韵 百 律 的 曲 曲 小 调 儿, 也 别 有 一 番 滋 味 在 心 头 扒 坟 梁 平 扒 坟, 是 当 地 老 百 姓 的 叫 法
More informationMicrosoft Word - HERBRECIPES《中國藥膳》.doc
中 國 藥 膳 僅 供 參 考, 請 勿 亂 服 若 欲 服 用, 自 行 負 責 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 藥 膳 系 列 總 目 錄 第 一 章 總 論 第 一 節 簡 介 第 二 節 特 點 1. 注 重 整 體, 辯 證 施 食 2. 防 治 兼 宜, 效 果 顯 著 3. 良 藥 可 口, 服 食 方 便 第 三 節 藥 膳 內 容 與 分 類
More information循经指压疗法
循 经 指 压 疗 法 陈 玉 琴 0 自 序 我 没 有 进 过 医 学 院, 更 没 有 学 过 解 剖 学 我 是 一 个 自 学 中 医 的 人, 思 考 问 题 本 着 简 单 化 和 直 观 的 原 则 循 经 指 压 健 康 疗 法 就 是 我 二 十 年 实 践 的 心 得 体 会 愿 以 此 作 向 资 深 的 中 医 师 请 教, 尤 其 是 中 医 大 的 教 师, 如 果 你
More information从 因 人 设 事 谈 起 一 部 文 学 作 品 ( 尤 其 是 长 篇 小 说 ) 的 结 构 至 关 重 要, 因 为 它 是 文 本 整 体 的 组 织 方 式 和 内 部 构 造, 既 是 形 式 又 是 内 容 ; 乃 是 表 达 主 题 最 有 效 的 艺 术 手 段 元 代 戏 曲
凤 头 猪 肚 豹 尾 凤 头 猪 肚 豹 尾 谈 死 水 微 澜 的 结 构 艺 术 艾 芦 摘 要 : 论 文 从 死 水 微 澜 的 人 物 和 场 景 描 写 入 手, 具 体 地 分 析 了 这 部 长 篇 小 说 的 艺 术 结 构, 同 时 针 对 以 往 研 究 者 的 某 些 观 点 提 出 了 不 同 的 见 解 ; 认 为 作 品 以 精 粹 见 长, 以 少 胜 多, 由 小
More information2009年3月全国计算机等级考试二级Java语言程序设计笔试试题
2009 年 3 月 全 国 计 算 机 等 级 考 试 笔 试 试 卷 二 级 Java 语 言 程 序 设 计 ( 考 试 时 间 90 分 钟, 满 分 100 分 ) 一 选 择 题 ( 每 题 2 分, 共 70 分 ) 下 列 各 题 A) B) C) D) 四 个 选 项 中, 只 有 一 个 选 项 是 正 确 的 请 将 正 确 选 项 填 涂 在 答 题 卡 相 应 位 置 上,
More information辽 宁 时 代 万 恒 控 股 集 团 有 限 公 司 大 事 记 (2009 年 ) 集 团 办 公 室 编 辑 1 一 2009 年 组 织 沿 革 ( 一 ) 集 团 总 部 组 织 机 构 ( 部 门 设 置 ) 图 示 辽 宁 时 代 万 恒 控 股 集 团 有 限 公 司 监 事 会 董 事 会 党 委 董 事 会 秘 书 经 理 层 工 会 纪 委 信 办 企 审 财 国 党 监 息
More informationPowerPoint 演示文稿
目 录 1 为 什 么 要 投 资 定 增 基 金 2 基 金 拟 投 公 司 介 绍 3 基 金 募 集 概 要 掘 金 新 时 代 定 向 增 发 定 向 增 发, 即 定 增, 指 上 市 公 司 向 符 合 条 件 的 少 数 特 定 投 资 者 非 公 开 发 行 股 份 的 行 为 指 项 目 融 资 收 购 资 产 引 入 战 略 投 资 者 财 务 重 组 整 体 上 市 等 指
More information1 中 华 物 理 医 学 与 康 复 杂 志, - 年 月 第.0 卷 第 期 & + &# * & " (, - ".0 $ 代 康 复 理 念 更 强 调 患 者 主 动 参 与 因 此 笔 者 倾 向 于 采 用 球 囊 主 动 扩 张 术 即 治 疗 时 以 患 者 主 动 参 与 为 主
1 临 床 研 究 表 面 麻 醉 对 球 囊 扩 张 治 疗 鼻 咽 癌 放 疗 后 吞 咽 障 碍 疗 效 的 影 响 周 惠 嫦 张 盘 德 陈 丽 珊 梁 鹏 刘 景 辉 关 志 勇 摘 要 目 的 探 讨 表 面 麻 醉 对 球 囊 主 动 扩 张 治 疗 鼻 咽 癌 放 疗 后 吞 咽 障 碍 疗 效 的 影 响 方 法 选 取 - 例 鼻 咽 癌 放 射 出 现 吞 咽 障 碍 的 患
More information期 李 海 利 等 猪 接 触 传 染 性 胸 膜 肺 炎 放 线 杆 菌 血 清 型 分 子 鉴 定 及 药 敏 试 验 / 只 产 生 两 种,9: 毒 素 血 清 型 毒 力 的 强 弱 与,9: 毒 素 种 类 有 关 产,9: 和,9: 的 血 清 型 毒 力 最 强 本 研 究 对 临
中 国 畜 牧 兽 医 22! " # 猪 接 触 传 染 性 胸 膜 肺 炎 放 线 杆 菌 血 清 型 分 子 鉴 定 及 药 敏 试 验 李 海 利 徐 引 弟 宋 毓 民 朱 文 豪 张 青 娴 王 克 领 冯 亚 杰 候 自 花 河 南 省 农 业 科 学 院 畜 牧 兽 医 研 究 所 郑 州 山 东 省 临 沂 市 兰 山 区 畜 牧 兽 医 局 临 沂 摘 要 为 了 解 猪 接 触
More information!
! ! ! ! ! ! ! ! ! "! !! "! "! "! "! ! #" "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "!
More information新版 明解C++入門編
511!... 43, 85!=... 42 "... 118 " "... 337 " "... 8, 290 #... 71 #... 413 #define... 128, 236, 413 #endif... 412 #ifndef... 412 #if... 412 #include... 6, 337 #undef... 413 %... 23, 27 %=... 97 &... 243,
More information中共贺州市委员会
贺 州 市 加 强 宣 传 思 想 文 化 人 才 队 伍 建 设 签 约 制 暂 行 办 法 为 了 逐 步 解 决 当 前 贺 州 新 闻 写 作 播 音 主 持 记 者 编 辑 媒 体 运 营 文 艺 创 作 文 化 创 意 产 业 等 方 面 人 才 紧 缺 制 约 我 市 宣 传 思 想 文 化 工 作 和 文 化 产 业 发 展 滞 后 等 问 题, 根 据 自 治 区 党 委 自 治
More informationJava java.lang.math Java Java.util.Random : ArithmeticException int zero = 0; try { int i= 72 / zero ; }catch (ArithmeticException e ) { // } 0,
http://debut.cis.nctu.edu.tw/~chi Java java.lang.math Java Java.util.Random : ArithmeticException int zero = 0; try { int i= 72 / zero ; }catch (ArithmeticException e ) { // } 0, : POSITIVE_INFINITY NEGATIVE_INFINITY
More informationEJB-Programming-4-cn.doc
EJB (4) : (Entity Bean Value Object ) JBuilder EJB 2.x CMP EJB Relationships JBuilder EJB Test Client EJB EJB Seminar CMP Entity Beans Session Bean J2EE Session Façade Design Pattern Session Bean Session
More informationchp6.ppt
Java 软 件 设 计 基 础 6. 异 常 处 理 编 程 时 会 遇 到 如 下 三 种 错 误 : 语 法 错 误 (syntax error) 没 有 遵 循 语 言 的 规 则, 出 现 语 法 格 式 上 的 错 误, 可 被 编 译 器 发 现 并 易 于 纠 正 ; 逻 辑 错 误 (logic error) 即 我 们 常 说 的 bug, 意 指 编 写 的 代 码 在 执 行
More information2 34 2 41 2 39 37
2 34 2 41 2 39 37 1955 64 14 1957 4 2 1972 3 1 138 7 20 79 8 7 28 66 14 60 25 2 9 79 17 12 189 190 6 43 1 138 1 2 166 174 145 163 468 31 34 358 1118 131 132 513 514 865 58 292 37 21 1 142 232 244
More information气 候 与 环 境 研 究 卷 &!' 张 书 余 许 多 学 者 对 人 体 舒 适 度 进 行 了 研 究!!0!! " 对 欧 洲 不 同 国 家 的 城 市 热 舒 适 性 进 行 了 研 究 周 后 福 探 讨 了 气 候 变 化 对 人 体 健 康 的 影 响 吴 兑 ) 进 行 了 多
第 卷 第 期 年 月 气 候 与 环 境 研 究 &!'!' 靳 宁 景 元 书 武 永 利 南 京 市 区 不 同 下 垫 面 对 人 体 舒 适 度 的 影 响 分 析 气 候 与 环 境 研 究 * *.. D $% 4 D!. 5 $$!/ %" 0 $!/ /"" $!/ ".$ / "$! % 1!! /! %"!/ >. % "$" * * 南 京 市 区 不 同 下 垫 面 对 人
More information基于CDIO一体化理念的课程教学大纲设计
Java 语 言 程 序 设 计 课 程 教 学 大 纲 Java 语 言 程 序 设 计 课 程 教 学 大 纲 一 课 程 基 本 信 息 1. 课 程 代 码 :52001CC022 2. 课 程 名 称 :Java 语 言 程 序 设 计 3. 课 程 英 文 名 称 :Java Programming 4. 课 程 类 别 : 理 论 课 ( 含 实 验 上 机 或 实 践 ) 5. 授
More information新版 明解C言語入門編
328, 4, 110, 189, 103, 11... 318. 274 6 ; 10 ; 5? 48 & & 228! 61!= 42 ^= 66 _ 82 /= 66 /* 3 / 19 ~ 164 OR 53 OR 164 = 66 ( ) 115 ( ) 31 ^ OR 164 [] 89, 241 [] 324 + + 4, 19, 241 + + 22 ++ 67 ++ 73 += 66
More informationOOP with Java 通知 Project 4: 4 月 18 日晚 9 点 关于抄袭 没有分数
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 4 月 18 日晚 9 点 关于抄袭 没有分数 复习 类的复用 组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double
More information! # % % & # # % #!& % &# % &# % % % # %& ( (!& (! & & % % #!! ) %&! *& % %! % %!! # % %!! %*!& % &# % &# ) ) ( % # # ) % ( (!& (! (!! # % % #!! # ( &!
!#!#!%!&!& #!#!#!#!#!#!! #!% # ( )! & & % & ) % ( %! # )& ) &!) &!% )& )! )!!% & ( (!&!&!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! )! % * % * ( & )!! % & # %! %! )! % * % * ( & )!! % & # %! %! # )! % * % *
More information## $%& %& ## () #) (( * (+++ () #) #) (+ (+ #) #) ( #, - #)). #))- # ( / / / 0 1 2 0 / $ # ( *. 3. 3 *..# 4 #$ 3 ( 5 ) ### 4 $ # 5, $ ## # 4 $# 5 ( %
# # $ %& $ %# ( $ # ( # $ ( $ $ ( ( % ( $ ( $ ( ( % ( % $ ( $ ( ( $ ( ( ( & ( ( ( $ ( ( % %# ( ( $ ( %# % ## $%& %& ## () #) (( * (+++ () #) #) (+ (+ #) #) ( #, - #)). #))- # ( / / / 0 1 2 0 / $ # ( *.
More information《饲料和饲料添加剂管理条例》
"!"### $ %# %&& % " "" %# ( ) * +, -. -... /. -. - - - /. - -. / / - / -!,. - (! " "! " # # " $ % # # # " & # " #! " " " " " " " " "! " # # $ % " & $ % " " & $ % " & $ %! " # & #! )! " "! # $ %! & $ %!
More information4 00 4 4 .4 0 8 A 6 B 4 7 4 6 8 08 7 0 4 4 6 0 9 4 6 8 00 6 0 6 9 0 4 4. 8 6 0 8. 7 4 6 7 4 8 4 - = 0 ( ) = ( ) = ( ) = + +... + 97 99 + + +... + 4 99 00 + +... + 99 0 4 + +... + 4 4 7 00 0 7 = 7
More information1 Framework.NET Framework Microsoft Windows.NET Framework.NET Framework NOTE.NET NET Framework.NET Framework 2.0 ( 3 ).NET Framework 2.0.NET F
1 Framework.NET Framework Microsoft Windows.NET Framework.NET Framework NOTE.NET 2.0 2.0.NET Framework.NET Framework 2.0 ( 3).NET Framework 2.0.NET Framework ( System ) o o o o o o Boxing UnBoxing() o
More information1 4. ( 3 ) F A 5 0 2 5 0 的 氣 壓 缸 緩 衝 行 程 的 長 度, 依 工 業 規 格 的 建 議 為 1 2 0 ~ 3 0 2 2 5 ~ 4 0 3 1 5 ~ 20 410~ 15 mm 1 5. ( 4 ) 在 管 路 安 裝 中, 若 要 管 路 閉 止 時,
104 年 度 08000 氣 壓 乙 級 技 術 士 技 能 檢 定 學 科 測 試 試 題 本 試 卷 有 選 擇 題 80 題 單 選 選 擇 題 60 題, 每 題 1 分 ; 複 選 選 擇 題 20 題, 每 題 2 分, 測 試 時 間 為 100 分 鐘, 請 在 答 案 卡 上 作 答, 答 錯 不 倒 扣 ; 未 作 答 者, 不 予 計 分 准 考 證 號 碼 : 姓 名 :
More informationMicrosoft Word - ch04三校.doc
4-1 4-1-1 (Object) (State) (Behavior) ( ) ( ) ( method) ( properties) ( functions) 4-2 4-1-2 (Message) ( ) ( ) ( ) A B A ( ) ( ) ( YourCar) ( changegear) ( lowergear) 4-1-3 (Class) (Blueprint) 4-3 changegear
More information!$ 中 国 生 物 工 程 杂 志, 2 图 药 物 作 用 靶 点 及 靶 向 药 物!"! " #$% &' 丝 氨 酸 蛋 白 酶 抑 制 剂 2 34 丝 氨 酸 蛋 白 酶 是 目 前 研 究 最 多 的 抗 病 毒 靶 点 其 作 用 在 于 催 化 裂 解 +, 多 聚 蛋 白 前
中 国 生 物 工 程 杂 志!" 丙 型 肝 炎 病 毒 靶 向 药 物 及 抗 病 毒 药 物 筛 选 史 文 芳 冯 悦 魏 大 巧 夏 雪 山 昆 明 理 工 大 学 生 命 科 学 与 技 术 学 院 昆 明 $" 摘 要 丙 型 肝 炎 由 丙 型 肝 炎 病 毒 ()'*)+, 感 染 所 致 约 &- 感 染 者 可 发 展 成 慢 性 肝 炎 甚 至 肝 硬 化 和 肝 癌 目 前
More informationMicrosoft Word - 第三章第三節.doc
第 三 節 植 栽 及 建 物 環 境 敷 地 調 查 一 周 圍 環 境 調 查 臺 中 刑 務 所 典 獄 長 官 舍 及 浴 場 位 於 臺 中 市 西 區, 刑 務 所 演 武 場 之 後 方, 以 林 森 路 自 由 路 一 段 與 貴 和 街 為 界 圍 塑 出 之 區 域, 林 森 路 25 巷 與 自 由 路 一 段 89 巷 縱 橫 貫 穿 其 中 本 案 刑 務 所 典 獄 長
More information!!! "# $ " %!!
!!"#$%& ()*+,-./012!" #$$%! " # !!! "# $ " %!! !" #$$% #$$% #$$%!"#$%& ()*+,-./0(12 & #! ! "! " " " $ % #" # " % & " "!! !!" " "!"#" $%& ()!*+,! " #$ %$ &$ $ " # % & ( " " " "!"-" $%&./01*+, ) " ! #" #
More information北 风 网 讲 师 原 创 作 品 ---- 仅 供 学 员 内 部 交 流 使 用 前 言 吾 尝 终 日 而 思 矣, 不 如 须 臾 之 所 学 也 ; 吾 尝 跂 而 望 矣, 不 如 登 高 之 博 见 也 登 高 而 招, 臂 非 加 长 也, 而 见
北 风 网 讲 师 原 创 作 品 ---- 仅 供 www.ibeifeng.com 学 员 内 部 交 流 使 用 前 言 吾 尝 终 日 而 思 矣, 不 如 须 臾 之 所 学 也 ; 吾 尝 跂 而 望 矣, 不 如 登 高 之 博 见 也 登 高 而 招, 臂 非 加 长 也, 而 见 者 远 ; 顺 风 而 呼, 声 非 加 疾 也, 而 闻 者 彰 假 舆 马 者, 非 利 足 也,
More information国 际 政 治 研 究 年 第 期 一 中 国 国 名 渊 源 暨 中 外 交 流 中 中 国 的 称 谓 一 不 在 乎 国 名 的 王 朝 国 家 世 界 上 绝 大 多 数 国 家 的 国 名 是 在 历 史 上 逐 渐 形 成 的 国 名 具 有 排 他 性 宣 示 一 国 之 主 权 国
国 际 政 治 研 究 双 月 刊 年 第 期 未 完 成 的 国 家 中 国 国 名 的 形 成 与 近 代 民 族 主 义 的 构 建 李 扬 帆 内 容 提 要 国 名 对 于 民 族 国 家 的 身 份 认 同 具 有 强 烈 的 凝 聚 意 义 和 符 号 价 值 中 国 作 为 一 个 国 家 名 称 的 形 成 有 其 特 殊 的 历 史 背 景 在 以 天 下 观 念 为 核 心 的
More informationOOP with Java 通知 Project 4: 5 月 2 日晚 9 点
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 5 月 2 日晚 9 点 复习 类的复用 组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double x) { d =
More information《安徒生童话》(四)
! " # $ !"# $$$$$$$$$$$$$$$$$$$$!%" $$$$$$$$$$$$$$$$$$!& $$$$$$$$$$$$$$$$$$$$$!&" $$$$$$$$$$$$$$$$$$!&# $$$$$$$$$$$$$$$$$$$$$!&( $$$$$$$$$$$$!#) $$$$$$$$$$$$$$$$$$$!)" $$$$$$$$$$$$$$$$$$$$$!!" $$$$$$$$$$$$$$$$$!!!
More informationJAVA String常用APi
JAVA String 常 用API 2015 年 5 月13 日 星 期 三 ------------------------------------------ String 类 的 特 点 : 字 符 串 对 象 一 旦 被 初 始 化 就 不 会 被 改 变 abc 存 储 在 字 符 串 常 量 池 中 Java 的 核 心 类 包 是 java.lang eclipse:ctrl+ 方
More information附录J:Eclipse教程
附 录 J:Eclipse 教 程 By Y.Daniel Liang 该 帮 助 文 档 包 括 以 下 内 容 : Eclipse 入 门 选 择 透 视 图 创 建 项 目 创 建 Java 程 序 编 译 和 运 行 Java 程 序 从 命 令 行 运 行 Java Application 在 Eclipse 中 调 试 提 示 : 在 学 习 完 第 一 章 后 使 用 本 教 程 第
More information但 洋 糖 最 终 乘 船 溯 江 而 上, 再 加 上 民 国 初 年 至 抗 战 前 夕 二 十 余 年 间, 四 川 接 连 不 断 遭 受 水 灾 旱 灾 地 震, 平 均 每 月 爆 发 两 次 军 阀 混 战, 乡 村 遭 受 极 大 破 坏,( 赵 泉 民,2007) 农 村 经 济
原 载 黄 宗 智 主 编 : 中 国 乡 村 研 究 ( 第 八 辑 ), 福 州 : 福 建 教 育 出 版 社 2010 年 4 月 第 一 版, 第 196-241 页 北 京 联 合 大 学 李 安 平 抗 战 时 期 四 川 内 江 农 贷 个 案 研 究 摘 要 : 抗 日 战 争 时 期 四 川 内 江 蔗 农 在 承 受 高 利 贷 盘 剥 的 严 酷 境 遇 中, 利 用 中 国
More informationエスポラージュ株式会社 住所 : 東京都江東区大島 東急ドエルアルス大島 HP: ******************* * 关于 Java 测试试题 ******
******************* * 关于 Java 测试试题 ******************* 問 1 运行下面的程序, 选出一个正确的运行结果 public class Sample { public static void main(string[] args) { int[] test = { 1, 2, 3, 4, 5 ; for(int i = 1 ; i System.out.print(test[i]);
More information詞 彙 表 編 號 詞 彙 描 述 1 預 約 人 資 料 中 文 姓 名 英 文 姓 名 身 份 證 字 號 預 約 人 電 話 性 別 2 付 款 資 料 信 用 卡 別 信 用 卡 號 信 用 卡 有 效 日 期 3 住 房 條 件 入 住 日 期 退 房 日 期 人 數 房 間 數 量 入
100 年 特 種 考 試 地 方 政 府 公 務 人 員 考 試 試 題 等 別 : 三 等 考 試 類 科 : 資 訊 處 理 科 目 : 系 統 分 析 與 設 計 一 請 參 考 下 列 旅 館 管 理 系 統 的 使 用 案 例 圖 (Use Case Diagram) 撰 寫 預 約 房 間 的 使 用 案 例 規 格 書 (Use Case Specification), 繪 出 入
More informationC/C++语言 - C/C++数据
C/C++ C/C++ Table of contents 1. 2. 3. 4. char 5. 1 C = 5 (F 32). 9 F C 2 1 // fal2cel. c: Convert Fah temperature to Cel temperature 2 # include < stdio.h> 3 int main ( void ) 4 { 5 float fah, cel ;
More information<4D6963726F736F667420576F7264202D20CBD5D6DDBFC6BCBCD1A7D4BACCECC6BDD1A7D4BA32303135C4EAB1BEBFC6D5D0C9FAD7A8D2B5BDE9C9DC2E646F63>
苏 州 科 技 学 院 天 平 学 院 2015 年 本 科 招 生 专 业 介 绍 环 境 设 计 专 业 性 质 : 艺 术 ( 以 下 各 专 业 学 制 均 为 4 年 ) 本 专 业 培 养 适 应 社 会 主 义 建 设 需 要, 具 有 扎 实 的 理 论 基 础 较 高 艺 术 修 养 人 文 素 质 设 计 组 织 和 协 调 能 力 并 全 方 位 掌 握 环 境 设 计 专 业
More information$ $ $ %&!! ( )!"" " * ) " +! + ("$ + ) * "! ",! + " +! $, ( * " -. /. 0. 1.!!""! %! * " 2 & * 345! + " %! + )! %! + )!!! (!"" ( ) ( + ) * + * 2!( *!)
% % &% % % % & & "$! " ( ( " ( ) * "!! & " $ + " + & " "! $,% &!!!!! -% & "!!!!!.% "!!!!! /% & " " "$ % 0 & " % 0 " & + &! & 1! " ( + * ) " ) * "!! + " + & & " 2! $ & 2 "! $ & " / " %$& " % $" & + &!!!
More information投稿類別:電子工程類
投 稿 類 別 : 工 程 技 術 類 篇 名 : 井 字 生 死 戰 攻 略 作 者 : 陳 威 宇 國 立 臺 南 高 級 海 事 水 產 職 業 學 校 電 子 科 二 年 甲 班 邱 富 群 國 立 臺 南 高 級 海 事 水 產 職 業 學 校 電 子 科 二 年 甲 班 指 導 老 師 : 林 育 助 老 師 王 彥 盛 老 師 壹 前 言 家 喻 戶 曉 的 井 字 遊 戲 (Tic-Tac-Toe)
More information.' 6! "! 6 "'' 6 7% $! 7%/'& 人 类 非 洲 锥 虫 病 又 称 昏 睡 病 是 布 氏 锥 虫 冈 比 亚 亚 种!! 或 布 氏 锥 虫 罗 得 西 亚 种 "#$$ %! &'!!! 感 染 引 起 的 一 种 寄 生 虫 病 以 采 采 蝇! 为 传 播 ' 媒
) 文 章 编 号 '.')) 论 著!"#$%&' ' ' ' ' '!"# ' $%& ' ' '8 目 的 对 ' 例 输 入 性 非 洲 锥 虫 病 患 者 进 行 实 验 室 诊 断 与 病 原 体 鉴 定 方 法 收 集 患 者 的 临 床 发 病 与 流 行 病 学 调 查 资 料 采 集 血 样 脑 脊 液 瑞 氏 吉 氏 染 色 涂 片 后 镜 检 用 布 氏 锥 虫 表 达 位
More informationCHAPTER 1
CHAPTER 1 1-1 System Development Life Cycle; SDLC SDLC Waterfall Model Shelly 1995 1. Preliminary Investigation 2. System Analysis 3. System Design 4. System Development 5. System Implementation and Evaluation
More information議 程 前 發 言 冀 新 官 上 任 燒 好 三 把 火 用 好 三 盆 水 陳 明 金 2014 年 11 月 18 日 澳 門 特 區 政 府 即 將 換 屆, 各 種 傳 聞 令 廣 大 居 民 感 覺 到, 絕 大 部 份 主 要 官 員 都 會 換 人 雖 然 他 們 對 人 選 無 話
促 重 整 運 輸 部 門 冀 革 新 交 通 政 策 鄭 安 庭 議 員 議 程 前 發 言 2014 年 11 月 18 日 主 席 各 位 同 事 : 今 天 我 的 議 程 前 發 言 題 目 是 : 促 重 整 運 輸 部 門 冀 革 新 交 通 政 策 剛 剛 完 成 的 第 61 屆 澳 門 格 蘭 披 治 大 賽 車 令 到 遊 客 絡 繹 不 絕 的 澳 門 更 為 熱 烈, 關
More information一 耀 州 青 瓷 的 裝 飾 手 法 與 紋 飾 種 類 耀 州 窯 的 裝 飾 紋 樣, 豐 富 多 變, 而 且 題 材 內 容 廣 泛, 組 合 形 式 多 樣, 圖 案 形 象 優 美, 令 人 賞 心 悅 目, 並 且 反 映 了 當 時 社 會 的 審 美 趣 味 和 理 想 裝 飾
宋 代 耀 州 青 瓷 的 紋 飾 風 格 與 意 義 曾 肅 良 英 國 萊 斯 特 大 學 博 物 館 學 博 士 國 立 台 灣 師 範 大 學 美 術 研 究 所 助 理 教 授 摘 要 中 國 的 飲 茶 之 風, 興 於 唐 而 盛 於 宋, 特 別 是 宋 代 宮 廷 禁 苑 和 地 方 官 吏 文 人 學 士 的 尚 茶 崇 茶, 以 品 茶 為 雅 尚 的 觀 念 與 作 法, 使
More information前言 C# C# C# C C# C# C# C# C# microservices C# More Effective C# More Effective C# C# C# C# Effective C# 50 C# C# 7 Effective vii
前言 C# C# C# C C# C# C# C# C# microservices C# More Effective C# More Effective C# C# C# C# Effective C# 50 C# C# 7 Effective vii C# 7 More Effective C# C# C# C# C# C# Common Language Runtime CLR just-in-time
More information(\244j\257d\276\307\274\351_201508021-C.indd_70%.pdf)
1847-1852 1872 20 1 1896 8000 20 1896 1950 1 1896 1896 13 1900 1900 3 20 2 4 1910 1950 3 1911 1 2 3 4 1927 4 20 300 6 1906 1930 7 1911 5 1919 8 1914 9 1920 10 11 1902 200 6 12 1930 7 " # #! $! 14 15! "!
More informationMac Java import com.apple.mrj.*;... public class MyFirstApp extends JFrame implements ActionListener, MRJAboutHandler, MRJQuitHandler {... public MyFirstApp() {... MRJApplicationUtils.registerAboutHandler(this);
More informationC C
C C 2017 3 8 1. 2. 3. 4. char 5. 2/101 C 1. 3/101 C C = 5 (F 32). 9 F C 4/101 C 1 // fal2cel.c: Convert Fah temperature to Cel temperature 2 #include 3 int main(void) 4 { 5 float fah, cel; 6 printf("please
More informationJavaIO.PDF
O u t p u t S t ream j a v a. i o. O u t p u t S t r e a m w r i t e () f l u s h () c l o s e () public abstract void write(int b) throws IOException public void write(byte[] data) throws IOException
More information2007
2007 年 上 半 年 软 件 评 测 师 考 试 浅 析 作 者 : 陈 嘉 祥 方 耀 公 司 : 广 东 亿 迅 科 技 有 限 公 司 ( 质 量 管 理 部 ) 1 简 介 1.1 目 的 本 文 章 主 要 介 绍 软 件 评 测 师 考 试 的 范 围 内 容 以 及 其 重 要 性, 还 有 相 关 的 试 题 分 析 1.2 适 用 范 围 有 意 参 与 或 将 来 有 意 参
More information中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!"# $! )# 5! ) 3& &!" &"& & 4! (& )& * ) 55& " )! & 5 )!4 ( )&& & )&# 1-9,6 & 7! &) (& (& 5 ) & " 3!4 5! ) &"&!)! & ) " &
思 路 与 方 法 学 针 灸 治 疗 颈 源 性 头 痛 处 方 取 穴 规 律 现 代 文 献 研 究 张 凯 刘 宇 蒋 戈 利 摘 要 目 的 总 结 现 代 文 献 中 针 灸 治 疗 颈 源 性 头 痛 处 方 取 穴 规 律 方 法 通 过 计 算 机 检 索 中 国 生 物 医 学 文 献 数 据 库 / 0%0 年 中 国 知 网 $1 0%0 年 维 普 数 据 库 00 年 万
More informationuntitled
A, 3+A printf( ABCDEF ) 3+ printf( ABCDEF ) 2.1 C++ main main main) * ( ) ( ) [ ].* ->* ()[] [][] ** *& char (f)(int); ( ) (f) (f) f (int) f int char f char f(int) (f) char (*f)(int); (*f) (int) (
More information新・解きながら学ぶC言語
330!... 67!=... 42 "... 215 " "... 6, 77, 222 #define... 114, 194 #include... 145 %... 21 %... 21 %%... 21 %f... 26 %ld... 162 %lf... 26 %lu... 162 %o... 180 %p... 248 %s... 223, 224 %u... 162 %x... 180
More information内 容 提 要 将 JAVA 开 发 环 境 迁 移 到 Linux 系 统 上 是 现 在 很 多 公 司 的 现 实 想 法, 而 在 Linux 上 配 置 JAVA 开 发 环 境 是 步 入 Linux 下 JAVA 程 序 开 发 的 第 一 步, 本 文 图 文 并 茂 地 全 程 指
内 容 提 要 将 JAVA 开 发 环 境 迁 移 到 Linux 系 统 上 是 现 在 很 多 公 司 的 现 实 想 法, 而 在 Linux 上 配 置 JAVA 开 发 环 境 是 步 入 Linux 下 JAVA 程 序 开 发 的 第 一 步, 本 文 图 文 并 茂 地 全 程 指 导 你 搭 建 Linux 平 台 下 的 JAVA 开 发 环 境, 包 括 JDK 以 及 集
More information得 到 了 補 償. 對 於 武 姜 而 言, 莊 公 與 自 己 的 關 係 並 不 親 密, 而 共 叔 段 又 是 自 己 向 來 疼 愛 有 加 的 兒 子, 所 以, 對 莊 公 提 出 再 怎 麼 無 理 的 要 求, 武 姜 也 不 會 覺 得 有 什 麼 不 妥 之 處, 而 對 共
左 傳 - 鄭 伯 克 段 於 鄢 人 物 心 理 1021141 林 詩 倩 一. 緒 論 鄭 伯 克 段 於 鄢, 及 共 叔 段 之 亂, 是 魯 隱 公 元 年, 即 公 元 前 722 年, 春 秋 初 年 在 鄭 國 國 內 發 生 的 一 場 內 亂. 武 姜 成 為 武 公 夫 人 並 先 後 為 武 公 生 下 了 兩 個 兒 子, 長 子 莊 公 由 於 腳 先 出 來 造 成
More information期 戚 瑞 荣 等 单 克 隆 抗 体 在 水 产 无 脊 椎 动 物 血 淋 巴 细 胞 研 究 中 的 应 用 虾 体 之 后 细 胞 形 态 很 容 易 发 生 改 变 因 此 依 靠 传 统 的 光 镜 观 察 方 法 很 难 准 确 统 计 这 三 类 细 胞 单 克 隆 抗 体 用 单
中 国 农 业 科 技 导 报!"#!$!$% &$!' 单 克 隆 抗 体 在 水 产 无 脊 椎 动 物 血 淋 巴 细 胞 研 究 中 的 应 用 戚 瑞 荣 李 强 于 毅 李 华 / 大 连 海 洋 大 学 辽 宁 省 海 洋 生 物 资 源 与 生 物 修 复 重 点 实 验 室 辽 宁 大 连 / 北 京 市 水 产 技 术 推 广 站 北 京 摘 要 近 年 来 单 克 隆 抗 体
More information度 方 面 对 护 士 的 整 个 抢 救 过 程 进 行 评 价 医 生 对 护 士 抢 救 配 合 满 意 度 为 对 患 儿 首 次 评 估 的 正 确 表 & 快 捷 急 救 护 理 记 录 表 性 医 嘱 的 执 行 力 对 患 儿 抢 救 药 物 使 用 后 的 再 次 评 估 合 作
快 捷 急 救 护 理 记 录 表 在 小 儿 颅 脑 外 伤 急 诊 抢 救 护 理 中 的 应 用 体 会 黄 玉 芬 徐 燕 芬 倪 萍 俞 俊 春 浙 江 大 学 医 学 院 附 属 儿 童 医 院 浙 江 杭 州 摘 要 总 结 快 捷 急 救 护 理 记 录 表 在 例 小 儿 颅 脑 外 伤 急 诊 抢 救 护 理 中 的 应 用 体 会 自 行 设 计 快 捷 急 救 护 理 记 录
More information年 第 期 许 德 刚 基 于 遗 忘 因 子 -./ 算 法 的 自 适 应 直 达 波 对 消 技 术 * 达 站 周 围 的 环 境 可 能 比 较 复 杂 来 自 近 距 离 不 同 固 定 物 体 所 反 射 的 多 径 信 号 也 强 于 回 波 信 号 大 大 影 响 了 雷 达 的
第 期 年 月! " #$ %# &' # 工 程 与 应 用 # $$ # #( )*$### 基 于 遗 忘 因 子 算 法 的 自 适 应 直 达 波 对 消 技 术 许 德 刚 中 国 电 子 科 技 集 团 公 司 第 + 研 究 所 合 肥 ++ 摘 要 在 以 民 用 广 播 电 视 及 &, 等 信 号 为 照 射 源 的 无 源 雷 达 系 统 中 由 于 发 射 信 号 为 连
More information期 李 环 等 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞 功 能 影 响 1 )!# $ + $#'!!) #!%,$' $ 6. $#! +!! '!!' # $! 引 言 - # # 近 年 来 生 殖 健 康 问 题 日 益 突 出 % 不 孕 不 育 等 各
第 卷 第 期 年 月! "#$%&#% '% 李 环 张 洋 婷 刘 呈 惠 等 %% 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞 功 能 影 响 * % 环 境 科 学 学 报 1 1 2 3 4 5 2 3 %% )!#),$' $ #!' # $) # #)!! $ * %! 1 1 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞
More information