Java 大师之路

Size: px
Start display at page:

Download "Java 大师之路"

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

新・解きながら学ぶ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 information

Microsoft Word - 第3章.doc

Microsoft 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 information

untitled

untitled 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

(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 information

Microsoft Word - 01.DOC

Microsoft Word - 01.DOC 第 1 章 JavaScript 简 介 JavaScript 是 NetScape 公 司 为 Navigator 浏 览 器 开 发 的, 是 写 在 HTML 文 件 中 的 一 种 脚 本 语 言, 能 实 现 网 页 内 容 的 交 互 显 示 当 用 户 在 客 户 端 显 示 该 网 页 时, 浏 览 器 就 会 执 行 JavaScript 程 序, 用 户 通 过 交 互 式 的

More information

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

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 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 information

FY.DOC

FY.DOC 高 职 高 专 21 世 纪 规 划 教 材 C++ 程 序 设 计 邓 振 杰 主 编 贾 振 华 孟 庆 敏 副 主 编 人 民 邮 电 出 版 社 内 容 提 要 本 书 系 统 地 介 绍 C++ 语 言 的 基 本 概 念 基 本 语 法 和 编 程 方 法, 深 入 浅 出 地 讲 述 C++ 语 言 面 向 对 象 的 重 要 特 征 : 类 和 对 象 抽 象 封 装 继 承 等 主

More information

CC213

CC213 : (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 information

Microsoft Word - HSK四级大纲_最新挖改3-5-10-11-14-15-33-34-35_.doc

Microsoft Word - HSK四级大纲_最新挖改3-5-10-11-14-15-33-34-35_.doc 新 汉 语 水 平 考 试 (HSK) 介 绍 为 使 汉 语 水 平 考 试 (HSK) 更 好 地 服 务 于 汉 语 学 习 者, 中 国 国 家 汉 办 组 织 中 外 汉 语 教 学 语 言 学 心 理 学 和 教 育 测 量 学 等 领 域 的 专 家, 在 充 分 调 查 了 解 海 外 汉 语 教 学 实 际 情 况 的 基 础 上, 吸 收 原 有 HSK 的 优 点, 借 鉴 近

More information

使 用 Java 语 言 模 拟 保 险 箱 容 量 门 板 厚 度 箱 体 厚 度 属 性 锁 具 类 型 开 保 险 箱 关 保 险 箱 动 作 存 取 款

使 用 Java 语 言 模 拟 保 险 箱 容 量 门 板 厚 度 箱 体 厚 度 属 性 锁 具 类 型 开 保 险 箱 关 保 险 箱 动 作 存 取 款 JAVA 程 序 设 计 ( 肆 ) 徐 东 / 数 学 系 使 用 Java 语 言 模 拟 保 险 箱 容 量 门 板 厚 度 箱 体 厚 度 属 性 锁 具 类 型 开 保 险 箱 关 保 险 箱 动 作 存 取 款 使 用 Java class 代 表 保 险 箱 public class SaveBox 类 名 类 类 体 实 现 封 装 性 使 用 class SaveBox 代 表 保

More information

《大话设计模式》第一章

《大话设计模式》第一章 第 1 章 代 码 无 错 就 是 优? 简 单 工 厂 模 式 1.1 面 试 受 挫 小 菜 今 年 计 算 机 专 业 大 四 了, 学 了 不 少 软 件 开 发 方 面 的 东 西, 也 学 着 编 了 些 小 程 序, 踌 躇 满 志, 一 心 要 找 一 个 好 单 位 当 投 递 了 无 数 份 简 历 后, 终 于 收 到 了 一 个 单 位 的 面 试 通 知, 小 菜 欣 喜

More information

3.1 num = 3 ch = 'C' 2

3.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 information

KillTest 质量更高 服务更好 学习资料 半年免费更新服务

KillTest 质量更高 服务更好 学习资料   半年免费更新服务 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 information

javaexample-02.pdf

javaexample-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$ 文 件 系 统 中 范 围 锁 机 制 的 应 用 研 究! 锁 命 名 空 间 '+'($($ 描 述 了 资 源 和 锁 的 集 合 它 同 时 在 客 户 节 点 和 服 务 节 点 存 在 不 同 之 处 只 是 利 用 一 个 数 据 标 识 来 有 效 区

第 期 熊 安 萍 等 *1$ 文 件 系 统 中 范 围 锁 机 制 的 应 用 研 究! 锁 命 名 空 间 '+'($($ 描 述 了 资 源 和 锁 的 集 合 它 同 时 在 客 户 节 点 和 服 务 节 点 存 在 不 同 之 处 只 是 利 用 一 个 数 据 标 识 来 有 效 区 第 卷 第 期 重 庆 邮 电 大 学 学 报 自 然 科 学 版 年 月!"#$" %$&'$ ''())$($*($'('+$$,-./0 1' 文 件 系 统 中 范 围 锁 机 制 的 应 用 研 究 熊 安 萍 葛 军 邹 洋 重 庆 邮 电 大 学 计 算 机 科 学 与 技 术 学 院 重 庆! 摘 要 分 布 式 锁 机 制 是 分 布 式 文 件 系 统 的 重 要 机 制 *1$

More information

CHAPTER VC#

CHAPTER 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 information

untitled

untitled 1 Outline 類别 欄 (1) 類 類 狀 更 易 類 理 若 類 利 來 利 using 來 namespace 類 ; (2) namespace IBM class Notebook namespace Compaq class Notebook 類别 類 來 類 列 欄 (field) (property) (method) (event) 類 例 立 來 車 類 類 立 車 欄 料

More information

untitled

untitled 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 information

C 1

C 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 information

OOP with Java 通知 Project 4: 4 月 19 日晚 9 点

OOP 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 information

C/C++ - 字符输入输出和字符确认

C/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),[剑指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 ./ 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 information

4 中 南 大 学 学 报 医 学 版 摘 要 目 的 探 讨 早 发 性 精 神 分 裂 症 患 者 在 静 息 状 态 下 是 否 存 在 脑 功 能 连 接 异 常 以 及 异 常 区 域 的 定 位 方 法 采 用 第 版 美 国 精 神 障 碍 诊 断 与 统 计 手 册 ( * ) (

4 中 南 大 学 学 报 医 学 版 摘 要 目 的 探 讨 早 发 性 精 神 分 裂 症 患 者 在 静 息 状 态 下 是 否 存 在 脑 功 能 连 接 异 常 以 及 异 常 区 域 的 定 位 方 法 采 用 第 版 美 国 精 神 障 碍 诊 断 与 统 计 手 册 ( * ) ( 中 南 大 学 学 报 医 学 版 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 进 行 基 础 评 估 和 治 疗 监 测 心 理 状 况 的 评 估 可

中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!# $! 症 状 在 诊 断 时 推 荐 应 用 $3 的 症 状 指 数 $!0  0 %!2 3% . )./!0 ) 1/! 5 1! 0 %7$3 6 进 行 基 础 评 估 和 治 疗 监 测 心 理 状 况 的 评 估 可 专 家 共 识 慢 性 前 列 腺 炎 中 西 医 结 合 诊 疗 专 家 共 识 中 国 中 西 医 结 合 学 会 男 科 专 业 委 员 会 年 月 慢 性 前 列 腺 炎 )./!0 ) 1/! 是 指 前 列 腺 在 病 原 体 或 某 些 非 感 染 因 素 作 用 下 患 者 出 现 以 盆 腔 区 域 疼 痛 或 不 适 排 尿 异 常 等 症 状 为 特 征 的 疾 病 一 直 是

More information

Chapter 9: Objects and Classes

Chapter 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)

附件1.FIT) 附 件 : 上 海 市 科 技 创 新 人 才 激 励 政 策 操 作 指 南 上 海 市 科 技 创 新 人 才 激 励 政 策 操 作 指 南 2011 年 1 月 国 有 企 业 科 技 创 新 激 励 操 作 指 南 附 件 : 上 海 市 科 技 创 新 人 才 激 励 政 策 操 作 指 南 目 录 1. 人 才 引 进 132 1.1 上 海 市 户 籍 及 居 住 证 132 1.2

More information

23 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 information

Microsoft Word - HERBRECIPES《中國藥膳》.doc

Microsoft Word - HERBRECIPES《中國藥膳》.doc 中 國 藥 膳 僅 供 參 考, 請 勿 亂 服 若 欲 服 用, 自 行 負 責 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 藥 膳 系 列 總 目 錄 第 一 章 總 論 第 一 節 簡 介 第 二 節 特 點 1. 注 重 整 體, 辯 證 施 食 2. 防 治 兼 宜, 效 果 顯 著 3. 良 藥 可 口, 服 食 方 便 第 三 節 藥 膳 內 容 與 分 類

More information

循经指压疗法

循经指压疗法 循 经 指 压 疗 法 陈 玉 琴 0 自 序 我 没 有 进 过 医 学 院, 更 没 有 学 过 解 剖 学 我 是 一 个 自 学 中 医 的 人, 思 考 问 题 本 着 简 单 化 和 直 观 的 原 则 循 经 指 压 健 康 疗 法 就 是 我 二 十 年 实 践 的 心 得 体 会 愿 以 此 作 向 资 深 的 中 医 师 请 教, 尤 其 是 中 医 大 的 教 师, 如 果 你

More information

从 因 人 设 事 谈 起 一 部 文 学 作 品 ( 尤 其 是 长 篇 小 说 ) 的 结 构 至 关 重 要, 因 为 它 是 文 本 整 体 的 组 织 方 式 和 内 部 构 造, 既 是 形 式 又 是 内 容 ; 乃 是 表 达 主 题 最 有 效 的 艺 术 手 段 元 代 戏 曲

从 因 人 设 事 谈 起 一 部 文 学 作 品 ( 尤 其 是 长 篇 小 说 ) 的 结 构 至 关 重 要, 因 为 它 是 文 本 整 体 的 组 织 方 式 和 内 部 构 造, 既 是 形 式 又 是 内 容 ; 乃 是 表 达 主 题 最 有 效 的 艺 术 手 段 元 代 戏 曲 凤 头 猪 肚 豹 尾 凤 头 猪 肚 豹 尾 谈 死 水 微 澜 的 结 构 艺 术 艾 芦 摘 要 : 论 文 从 死 水 微 澜 的 人 物 和 场 景 描 写 入 手, 具 体 地 分 析 了 这 部 长 篇 小 说 的 艺 术 结 构, 同 时 针 对 以 往 研 究 者 的 某 些 观 点 提 出 了 不 同 的 见 解 ; 认 为 作 品 以 精 粹 见 长, 以 少 胜 多, 由 小

More information

2009年3月全国计算机等级考试二级Java语言程序设计笔试试题

2009年3月全国计算机等级考试二级Java语言程序设计笔试试题 2009 年 3 月 全 国 计 算 机 等 级 考 试 笔 试 试 卷 二 级 Java 语 言 程 序 设 计 ( 考 试 时 间 90 分 钟, 满 分 100 分 ) 一 选 择 题 ( 每 题 2 分, 共 70 分 ) 下 列 各 题 A) B) C) D) 四 个 选 项 中, 只 有 一 个 选 项 是 正 确 的 请 将 正 确 选 项 填 涂 在 答 题 卡 相 应 位 置 上,

More information



 辽 宁 时 代 万 恒 控 股 集 团 有 限 公 司 大 事 记 (2009 年 ) 集 团 办 公 室 编 辑 1 一 2009 年 组 织 沿 革 ( 一 ) 集 团 总 部 组 织 机 构 ( 部 门 设 置 ) 图 示 辽 宁 时 代 万 恒 控 股 集 团 有 限 公 司 监 事 会 董 事 会 党 委 董 事 会 秘 书 经 理 层 工 会 纪 委 信 办 企 审 财 国 党 监 息

More information

PowerPoint 演示文稿

PowerPoint 演示文稿 目 录 1 为 什 么 要 投 资 定 增 基 金 2 基 金 拟 投 公 司 介 绍 3 基 金 募 集 概 要 掘 金 新 时 代 定 向 增 发 定 向 增 发, 即 定 增, 指 上 市 公 司 向 符 合 条 件 的 少 数 特 定 投 资 者 非 公 开 发 行 股 份 的 行 为 指 项 目 融 资 收 购 资 产 引 入 战 略 投 资 者 财 务 重 组 整 体 上 市 等 指

More information

1 中 华 物 理 医 学 与 康 复 杂 志, - 年 月 第.0 卷 第 期 & + &# * & " (, - ".0 $ 代 康 复 理 念 更 强 调 患 者 主 动 参 与 因 此 笔 者 倾 向 于 采 用 球 囊 主 动 扩 张 术 即 治 疗 时 以 患 者 主 动 参 与 为 主

1 中 华 物 理 医 学 与 康 复 杂 志, - 年 月 第.0 卷 第 期 & + &# * &  (, - .0 $ 代 康 复 理 念 更 强 调 患 者 主 动 参 与 因 此 笔 者 倾 向 于 采 用 球 囊 主 动 扩 张 术 即 治 疗 时 以 患 者 主 动 参 与 为 主 1 临 床 研 究 表 面 麻 醉 对 球 囊 扩 张 治 疗 鼻 咽 癌 放 疗 后 吞 咽 障 碍 疗 效 的 影 响 周 惠 嫦 张 盘 德 陈 丽 珊 梁 鹏 刘 景 辉 关 志 勇 摘 要 目 的 探 讨 表 面 麻 醉 对 球 囊 主 动 扩 张 治 疗 鼻 咽 癌 放 疗 后 吞 咽 障 碍 疗 效 的 影 响 方 法 选 取 - 例 鼻 咽 癌 放 射 出 现 吞 咽 障 碍 的 患

More information

期 李 海 利 等 猪 接 触 传 染 性 胸 膜 肺 炎 放 线 杆 菌 血 清 型 分 子 鉴 定 及 药 敏 试 验 / 只 产 生 两 种,9: 毒 素 血 清 型 毒 力 的 强 弱 与,9: 毒 素 种 类 有 关 产,9: 和,9: 的 血 清 型 毒 力 最 强 本 研 究 对 临

期 李 海 利 等 猪 接 触 传 染 性 胸 膜 肺 炎 放 线 杆 菌 血 清 型 分 子 鉴 定 及 药 敏 试 验 / 只 产 生 两 种,9: 毒 素 血 清 型 毒 力 的 强 弱 与,9: 毒 素 种 类 有 关 产,9: 和,9: 的 血 清 型 毒 力 最 强 本 研 究 对 临 中 国 畜 牧 兽 医 22! " # 猪 接 触 传 染 性 胸 膜 肺 炎 放 线 杆 菌 血 清 型 分 子 鉴 定 及 药 敏 试 验 李 海 利 徐 引 弟 宋 毓 民 朱 文 豪 张 青 娴 王 克 领 冯 亚 杰 候 自 花 河 南 省 农 业 科 学 院 畜 牧 兽 医 研 究 所 郑 州 山 东 省 临 沂 市 兰 山 区 畜 牧 兽 医 局 临 沂 摘 要 为 了 解 猪 接 触

More information

!

! ! ! ! ! ! ! ! ! ! "! !! "! "! "! "! ! #" "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "! "! "! "! "! "! "! !! "! "! "! "!

More information

新版 明解C++入門編

新版 明解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 information

Java java.lang.math Java Java.util.Random : ArithmeticException int zero = 0; try { int i= 72 / zero ; }catch (ArithmeticException e ) { // } 0,

Java 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 information

EJB-Programming-4-cn.doc

EJB-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 information

chp6.ppt

chp6.ppt Java 软 件 设 计 基 础 6. 异 常 处 理 编 程 时 会 遇 到 如 下 三 种 错 误 : 语 法 错 误 (syntax error) 没 有 遵 循 语 言 的 规 则, 出 现 语 法 格 式 上 的 错 误, 可 被 编 译 器 发 现 并 易 于 纠 正 ; 逻 辑 错 误 (logic error) 即 我 们 常 说 的 bug, 意 指 编 写 的 代 码 在 执 行

More information

2 34 2 41 2 39 37

2 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!! " 对 欧 洲 不 同 国 家 的 城 市 热 舒 适 性 进 行 了 研 究 周 后 福 探 讨 了 气 候 变 化 对 人 体 健 康 的 影 响 吴 兑 ) 进 行 了 多

气 候 与 环 境 研 究 卷 &!' 张 书 余 许 多 学 者 对 人 体 舒 适 度 进 行 了 研 究!!0!!  对 欧 洲 不 同 国 家 的 城 市 热 舒 适 性 进 行 了 研 究 周 后 福 探 讨 了 气 候 变 化 对 人 体 健 康 的 影 响 吴 兑 ) 进 行 了 多 第 卷 第 期 年 月 气 候 与 环 境 研 究 &!'!' 靳 宁 景 元 书 武 永 利 南 京 市 区 不 同 下 垫 面 对 人 体 舒 适 度 的 影 响 分 析 气 候 与 环 境 研 究 * *.. D $% 4 D!. 5 $$!/ %" 0 $!/ /"" $!/ ".$ / "$! % 1!! /! %"!/ >. % "$" * * 南 京 市 区 不 同 下 垫 面 对 人

More information

基于CDIO一体化理念的课程教学大纲设计

基于CDIO一体化理念的课程教学大纲设计 Java 语 言 程 序 设 计 课 程 教 学 大 纲 Java 语 言 程 序 设 计 课 程 教 学 大 纲 一 课 程 基 本 信 息 1. 课 程 代 码 :52001CC022 2. 课 程 名 称 :Java 语 言 程 序 设 计 3. 课 程 英 文 名 称 :Java Programming 4. 课 程 类 别 : 理 论 课 ( 含 实 验 上 机 或 实 践 ) 5. 授

More information

新版 明解C言語入門編

新版 明解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 information

OOP with Java 通知 Project 4: 4 月 18 日晚 9 点 关于抄袭 没有分数

OOP 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 / $ # ( *. 3. 3 *..# 4 #$ 3 ( 5 ) ### 4 $ # 5, $ ## # 4 $# 5 ( % # # $ %& $ %# ( $ # ( # $ ( $ $ ( ( % ( $ ( $ ( ( % ( % $ ( $ ( ( $ ( ( ( & ( ( ( $ ( ( % %# ( ( $ ( %# % ## $%& %& ## () #) (( * (+++ () #) #) (+ (+ #) #) ( #, - #)). #))- # ( / / / 0 1 2 0 / $ # ( *.

More information

《饲料和饲料添加剂管理条例》

《饲料和饲料添加剂管理条例》 "!"### $ %# %&& % " "" %# ( ) * +, -. -... /. -. - - - /. - -. / / - / -!,. - (! " "! " # # " $ % # # # " & # " #! " " " " " " " " "! " # # $ % " & $ % " " & $ % " & $ %! " # & #! )! " "! # $ %! & $ %!

More information

4 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 information

1 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 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 information

1 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 ) 在 管 路 安 裝 中, 若 要 管 路 閉 止 時,

1 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 information

Microsoft Word - ch04三校.doc

Microsoft 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 丝 氨 酸 蛋 白 酶 是 目 前 研 究 最 多 的 抗 病 毒 靶 点 其 作 用 在 于 催 化 裂 解 +, 多 聚 蛋 白 前

!$ 中 国 生 物 工 程 杂 志, 2 图 药 物 作 用 靶 点 及 靶 向 药 物!!  #$% &' 丝 氨 酸 蛋 白 酶 抑 制 剂 2 34 丝 氨 酸 蛋 白 酶 是 目 前 研 究 最 多 的 抗 病 毒 靶 点 其 作 用 在 于 催 化 裂 解 +, 多 聚 蛋 白 前 中 国 生 物 工 程 杂 志!" 丙 型 肝 炎 病 毒 靶 向 药 物 及 抗 病 毒 药 物 筛 选 史 文 芳 冯 悦 魏 大 巧 夏 雪 山 昆 明 理 工 大 学 生 命 科 学 与 技 术 学 院 昆 明 $" 摘 要 丙 型 肝 炎 由 丙 型 肝 炎 病 毒 ()'*)+, 感 染 所 致 约 &- 感 染 者 可 发 展 成 慢 性 肝 炎 甚 至 肝 硬 化 和 肝 癌 目 前

More information

Microsoft Word - 第三章第三節.doc

Microsoft Word - 第三章第三節.doc 第 三 節 植 栽 及 建 物 環 境 敷 地 調 查 一 周 圍 環 境 調 查 臺 中 刑 務 所 典 獄 長 官 舍 及 浴 場 位 於 臺 中 市 西 區, 刑 務 所 演 武 場 之 後 方, 以 林 森 路 自 由 路 一 段 與 貴 和 街 為 界 圍 塑 出 之 區 域, 林 森 路 25 巷 與 自 由 路 一 段 89 巷 縱 橫 貫 穿 其 中 本 案 刑 務 所 典 獄 長

More information

!!! "# $ " %!!

!!! # $  %!! !!"#$%& ()*+,-./012!" #$$%! " # !!! "# $ " %!! !" #$$% #$$% #$$%!"#$%& ()*+,-./0(12 & #! ! "! " " " $ % #" # " % & " "!! !!" " "!"#" $%& ()!*+,! " #$ %$ &$ $ " # % & ( " " " "!"-" $%&./01*+, ) " ! #" #

More information

北 风 网 讲 师 原 创 作 品 ---- 仅 供 学 员 内 部 交 流 使 用 前 言 吾 尝 终 日 而 思 矣, 不 如 须 臾 之 所 学 也 ; 吾 尝 跂 而 望 矣, 不 如 登 高 之 博 见 也 登 高 而 招, 臂 非 加 长 也, 而 见

北 风 网 讲 师 原 创 作 品 ---- 仅 供  学 员 内 部 交 流 使 用 前 言 吾 尝 终 日 而 思 矣, 不 如 须 臾 之 所 学 也 ; 吾 尝 跂 而 望 矣, 不 如 登 高 之 博 见 也 登 高 而 招, 臂 非 加 长 也, 而 见 北 风 网 讲 师 原 创 作 品 ---- 仅 供 www.ibeifeng.com 学 员 内 部 交 流 使 用 前 言 吾 尝 终 日 而 思 矣, 不 如 须 臾 之 所 学 也 ; 吾 尝 跂 而 望 矣, 不 如 登 高 之 博 见 也 登 高 而 招, 臂 非 加 长 也, 而 见 者 远 ; 顺 风 而 呼, 声 非 加 疾 也, 而 闻 者 彰 假 舆 马 者, 非 利 足 也,

More information

国 际 政 治 研 究 年 第 期 一 中 国 国 名 渊 源 暨 中 外 交 流 中 中 国 的 称 谓 一 不 在 乎 国 名 的 王 朝 国 家 世 界 上 绝 大 多 数 国 家 的 国 名 是 在 历 史 上 逐 渐 形 成 的 国 名 具 有 排 他 性 宣 示 一 国 之 主 权 国

国 际 政 治 研 究 年 第 期 一 中 国 国 名 渊 源 暨 中 外 交 流 中 中 国 的 称 谓 一 不 在 乎 国 名 的 王 朝 国 家 世 界 上 绝 大 多 数 国 家 的 国 名 是 在 历 史 上 逐 渐 形 成 的 国 名 具 有 排 他 性 宣 示 一 国 之 主 权 国 国 际 政 治 研 究 双 月 刊 年 第 期 未 完 成 的 国 家 中 国 国 名 的 形 成 与 近 代 民 族 主 义 的 构 建 李 扬 帆 内 容 提 要 国 名 对 于 民 族 国 家 的 身 份 认 同 具 有 强 烈 的 凝 聚 意 义 和 符 号 价 值 中 国 作 为 一 个 国 家 名 称 的 形 成 有 其 特 殊 的 历 史 背 景 在 以 天 下 观 念 为 核 心 的

More information

OOP with Java 通知 Project 4: 5 月 2 日晚 9 点

OOP 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 information

JAVA String常用APi

JAVA String常用APi JAVA String 常 用API 2015 年 5 月13 日 星 期 三 ------------------------------------------ String 类 的 特 点 : 字 符 串 对 象 一 旦 被 初 始 化 就 不 会 被 改 变 abc 存 储 在 字 符 串 常 量 池 中 Java 的 核 心 类 包 是 java.lang eclipse:ctrl+ 方

More information

附录J:Eclipse教程

附录J:Eclipse教程 附 录 J:Eclipse 教 程 By Y.Daniel Liang 该 帮 助 文 档 包 括 以 下 内 容 : Eclipse 入 门 选 择 透 视 图 创 建 项 目 创 建 Java 程 序 编 译 和 运 行 Java 程 序 从 命 令 行 运 行 Java Application 在 Eclipse 中 调 试 提 示 : 在 学 习 完 第 一 章 后 使 用 本 教 程 第

More information

但 洋 糖 最 终 乘 船 溯 江 而 上, 再 加 上 民 国 初 年 至 抗 战 前 夕 二 十 余 年 间, 四 川 接 连 不 断 遭 受 水 灾 旱 灾 地 震, 平 均 每 月 爆 发 两 次 军 阀 混 战, 乡 村 遭 受 极 大 破 坏,( 赵 泉 民,2007) 农 村 经 济

但 洋 糖 最 终 乘 船 溯 江 而 上, 再 加 上 民 国 初 年 至 抗 战 前 夕 二 十 余 年 间, 四 川 接 连 不 断 遭 受 水 灾 旱 灾 地 震, 平 均 每 月 爆 发 两 次 军 阀 混 战, 乡 村 遭 受 极 大 破 坏,( 赵 泉 民,2007) 农 村 经 济 原 载 黄 宗 智 主 编 : 中 国 乡 村 研 究 ( 第 八 辑 ), 福 州 : 福 建 教 育 出 版 社 2010 年 4 月 第 一 版, 第 196-241 页 北 京 联 合 大 学 李 安 平 抗 战 时 期 四 川 内 江 农 贷 个 案 研 究 摘 要 : 抗 日 战 争 时 期 四 川 内 江 蔗 农 在 承 受 高 利 贷 盘 剥 的 严 酷 境 遇 中, 利 用 中 国

More information

エスポラージュ株式会社 住所 : 東京都江東区大島 東急ドエルアルス大島 HP: ******************* * 关于 Java 测试试题 ******

エスポラージュ株式会社 住所 : 東京都江東区大島 東急ドエルアルス大島 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 住 房 條 件 入 住 日 期 退 房 日 期 人 數 房 間 數 量 入

詞 彙 表 編 號 詞 彙 描 述 1 預 約 人 資 料 中 文 姓 名 英 文 姓 名 身 份 證 字 號 預 約 人 電 話 性 別 2 付 款 資 料 信 用 卡 別 信 用 卡 號 信 用 卡 有 效 日 期 3 住 房 條 件 入 住 日 期 退 房 日 期 人 數 房 間 數 量 入 100 年 特 種 考 試 地 方 政 府 公 務 人 員 考 試 試 題 等 別 : 三 等 考 試 類 科 : 資 訊 處 理 科 目 : 系 統 分 析 與 設 計 一 請 參 考 下 列 旅 館 管 理 系 統 的 使 用 案 例 圖 (Use Case Diagram) 撰 寫 預 約 房 間 的 使 用 案 例 規 格 書 (Use Case Specification), 繪 出 入

More information

C/C++语言 - C/C++数据

C/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>

<4D6963726F736F667420576F7264202D20CBD5D6DDBFC6BCBCD1A7D4BACCECC6BDD1A7D4BA32303135C4EAB1BEBFC6D5D0C9FAD7A8D2B5BDE9C9DC2E646F63> 苏 州 科 技 学 院 天 平 学 院 2015 年 本 科 招 生 专 业 介 绍 环 境 设 计 专 业 性 质 : 艺 术 ( 以 下 各 专 业 学 制 均 为 4 年 ) 本 专 业 培 养 适 应 社 会 主 义 建 设 需 要, 具 有 扎 实 的 理 论 基 础 较 高 艺 术 修 养 人 文 素 质 设 计 组 织 和 协 调 能 力 并 全 方 位 掌 握 环 境 设 计 专 业

More information

$ $ $ %&!! ( )!"" " * ) " +! + ("$ + ) * "! ",! + " +! $, ( * " -. /. 0. 1.!!""! %! * " 2 & * 345! + " %! + )! %! + )!!! (!"" ( ) ( + ) * + * 2!( *!)

$ $ $ %&!! ( )!  * )  +! + ($ + ) * ! ,! +  +! $, ( *  -. /. 0. 1.!!! %! *  2 & * 345! +  %! + )! %! + )!!! (! ( ) ( + ) * + * 2!( *!) % % &% % % % & & "$! " ( ( " ( ) * "!! & " $ + " + & " "! $,% &!!!!! -% & "!!!!!.% "!!!!! /% & " " "$ % 0 & " % 0 " & + &! & 1! " ( + * ) " ) * "!! + " + & & " 2! $ & 2 "! $ & " / " %$& " % $" & + &!!!

More information

投稿類別:電子工程類

投稿類別:電子工程類 投 稿 類 別 : 工 程 技 術 類 篇 名 : 井 字 生 死 戰 攻 略 作 者 : 陳 威 宇 國 立 臺 南 高 級 海 事 水 產 職 業 學 校 電 子 科 二 年 甲 班 邱 富 群 國 立 臺 南 高 級 海 事 水 產 職 業 學 校 電 子 科 二 年 甲 班 指 導 老 師 : 林 育 助 老 師 王 彥 盛 老 師 壹 前 言 家 喻 戶 曉 的 井 字 遊 戲 (Tic-Tac-Toe)

More information

.' 6! "! 6 "'' 6 7% $! 7%/'& 人 类 非 洲 锥 虫 病 又 称 昏 睡 病 是 布 氏 锥 虫 冈 比 亚 亚 种!! 或 布 氏 锥 虫 罗 得 西 亚 种 "#$$ %! &'!!! 感 染 引 起 的 一 种 寄 生 虫 病 以 采 采 蝇! 为 传 播 ' 媒

.' 6! ! 6 '' 6 7% $! 7%/'& 人 类 非 洲 锥 虫 病 又 称 昏 睡 病 是 布 氏 锥 虫 冈 比 亚 亚 种!! 或 布 氏 锥 虫 罗 得 西 亚 种 #$$ %! &'!!! 感 染 引 起 的 一 种 寄 生 虫 病 以 采 采 蝇! 为 传 播 ' 媒 ) 文 章 编 号 '.')) 论 著!"#$%&' ' ' ' ' '!"# ' $%& ' ' '8 目 的 对 ' 例 输 入 性 非 洲 锥 虫 病 患 者 进 行 实 验 室 诊 断 与 病 原 体 鉴 定 方 法 收 集 患 者 的 临 床 发 病 与 流 行 病 学 调 查 资 料 采 集 血 样 脑 脊 液 瑞 氏 吉 氏 染 色 涂 片 后 镜 检 用 布 氏 锥 虫 表 达 位

More information

CHAPTER 1

CHAPTER 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 日 澳 門 特 區 政 府 即 將 換 屆, 各 種 傳 聞 令 廣 大 居 民 感 覺 到, 絕 大 部 份 主 要 官 員 都 會 換 人 雖 然 他 們 對 人 選 無 話 促 重 整 運 輸 部 門 冀 革 新 交 通 政 策 鄭 安 庭 議 員 議 程 前 發 言 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# 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)

(\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 information

Mac Java import com.apple.mrj.*;... public class MyFirstApp extends JFrame implements ActionListener, MRJAboutHandler, MRJQuitHandler {... public MyFirstApp() {... MRJApplicationUtils.registerAboutHandler(this);

More information

C C

C 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 information

JavaIO.PDF

JavaIO.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 information

2007

2007 2007 年 上 半 年 软 件 评 测 师 考 试 浅 析 作 者 : 陈 嘉 祥 方 耀 公 司 : 广 东 亿 迅 科 技 有 限 公 司 ( 质 量 管 理 部 ) 1 简 介 1.1 目 的 本 文 章 主 要 介 绍 软 件 评 测 师 考 试 的 范 围 内 容 以 及 其 重 要 性, 还 有 相 关 的 试 题 分 析 1.2 适 用 范 围 有 意 参 与 或 将 来 有 意 参

More information

中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!"# $! )# 5! ) 3& &!" &"& & 4! (& )& * ) 55& " )! & 5 )!4 ( )&& & )&# 1-9,6 & 7! &) (& (& 5 ) & " 3!4 5! ) &"&!)! & ) " &

中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!# $! )# 5! ) 3& &! && & 4! (& )& * ) 55&  )! & 5 )!4 ( )&& & )&# 1-9,6 & 7! &) (& (& 5 ) &  3!4 5! ) &&!)! & )  & 思 路 与 方 法 学 针 灸 治 疗 颈 源 性 头 痛 处 方 取 穴 规 律 现 代 文 献 研 究 张 凯 刘 宇 蒋 戈 利 摘 要 目 的 总 结 现 代 文 献 中 针 灸 治 疗 颈 源 性 头 痛 处 方 取 穴 规 律 方 法 通 过 计 算 机 检 索 中 国 生 物 医 学 文 献 数 据 库 / 0%0 年 中 国 知 网 $1 0%0 年 维 普 数 据 库 00 年 万

More information

untitled

untitled 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言語

新・解きながら学ぶ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 程 序 开 发 的 第 一 步, 本 文 图 文 并 茂 地 全 程 指 内 容 提 要 将 JAVA 开 发 环 境 迁 移 到 Linux 系 统 上 是 现 在 很 多 公 司 的 现 实 想 法, 而 在 Linux 上 配 置 JAVA 开 发 环 境 是 步 入 Linux 下 JAVA 程 序 开 发 的 第 一 步, 本 文 图 文 并 茂 地 全 程 指 导 你 搭 建 Linux 平 台 下 的 JAVA 开 发 环 境, 包 括 JDK 以 及 集

More information

c_cpp

c_cpp C C++ C C++ C++ (object oriented) C C++.cpp C C++ C C++ : for (int i=0;i

More information

得 到 了 補 償. 對 於 武 姜 而 言, 莊 公 與 自 己 的 關 係 並 不 親 密, 而 共 叔 段 又 是 自 己 向 來 疼 愛 有 加 的 兒 子, 所 以, 對 莊 公 提 出 再 怎 麼 無 理 的 要 求, 武 姜 也 不 會 覺 得 有 什 麼 不 妥 之 處, 而 對 共

得 到 了 補 償. 對 於 武 姜 而 言, 莊 公 與 自 己 的 關 係 並 不 親 密, 而 共 叔 段 又 是 自 己 向 來 疼 愛 有 加 的 兒 子, 所 以, 對 莊 公 提 出 再 怎 麼 無 理 的 要 求, 武 姜 也 不 會 覺 得 有 什 麼 不 妥 之 處, 而 對 共 左 傳 - 鄭 伯 克 段 於 鄢 人 物 心 理 1021141 林 詩 倩 一. 緒 論 鄭 伯 克 段 於 鄢, 及 共 叔 段 之 亂, 是 魯 隱 公 元 年, 即 公 元 前 722 年, 春 秋 初 年 在 鄭 國 國 內 發 生 的 一 場 內 亂. 武 姜 成 為 武 公 夫 人 並 先 後 為 武 公 生 下 了 兩 個 兒 子, 長 子 莊 公 由 於 腳 先 出 來 造 成

More information

期 戚 瑞 荣 等 单 克 隆 抗 体 在 水 产 无 脊 椎 动 物 血 淋 巴 细 胞 研 究 中 的 应 用 虾 体 之 后 细 胞 形 态 很 容 易 发 生 改 变 因 此 依 靠 传 统 的 光 镜 观 察 方 法 很 难 准 确 统 计 这 三 类 细 胞 单 克 隆 抗 体 用 单

期 戚 瑞 荣 等 单 克 隆 抗 体 在 水 产 无 脊 椎 动 物 血 淋 巴 细 胞 研 究 中 的 应 用 虾 体 之 后 细 胞 形 态 很 容 易 发 生 改 变 因 此 依 靠 传 统 的 光 镜 观 察 方 法 很 难 准 确 统 计 这 三 类 细 胞 单 克 隆 抗 体 用 单 中 国 农 业 科 技 导 报!"#!$!$% &$!' 单 克 隆 抗 体 在 水 产 无 脊 椎 动 物 血 淋 巴 细 胞 研 究 中 的 应 用 戚 瑞 荣 李 强 于 毅 李 华 / 大 连 海 洋 大 学 辽 宁 省 海 洋 生 物 资 源 与 生 物 修 复 重 点 实 验 室 辽 宁 大 连 / 北 京 市 水 产 技 术 推 广 站 北 京 摘 要 近 年 来 单 克 隆 抗 体

More information

度 方 面 对 护 士 的 整 个 抢 救 过 程 进 行 评 价 医 生 对 护 士 抢 救 配 合 满 意 度 为 对 患 儿 首 次 评 估 的 正 确 表 & 快 捷 急 救 护 理 记 录 表 性 医 嘱 的 执 行 力 对 患 儿 抢 救 药 物 使 用 后 的 再 次 评 估 合 作

度 方 面 对 护 士 的 整 个 抢 救 过 程 进 行 评 价 医 生 对 护 士 抢 救 配 合 满 意 度 为 对 患 儿 首 次 评 估 的 正 确 表 & 快 捷 急 救 护 理 记 录 表 性 医 嘱 的 执 行 力 对 患 儿 抢 救 药 物 使 用 后 的 再 次 评 估 合 作 快 捷 急 救 护 理 记 录 表 在 小 儿 颅 脑 外 伤 急 诊 抢 救 护 理 中 的 应 用 体 会 黄 玉 芬 徐 燕 芬 倪 萍 俞 俊 春 浙 江 大 学 医 学 院 附 属 儿 童 医 院 浙 江 杭 州 摘 要 总 结 快 捷 急 救 护 理 记 录 表 在 例 小 儿 颅 脑 外 伤 急 诊 抢 救 护 理 中 的 应 用 体 会 自 行 设 计 快 捷 急 救 护 理 记 录

More information

年 第 期 许 德 刚 基 于 遗 忘 因 子 -./ 算 法 的 自 适 应 直 达 波 对 消 技 术 * 达 站 周 围 的 环 境 可 能 比 较 复 杂 来 自 近 距 离 不 同 固 定 物 体 所 反 射 的 多 径 信 号 也 强 于 回 波 信 号 大 大 影 响 了 雷 达 的

年 第 期 许 德 刚 基 于 遗 忘 因 子 -./ 算 法 的 自 适 应 直 达 波 对 消 技 术 * 达 站 周 围 的 环 境 可 能 比 较 复 杂 来 自 近 距 离 不 同 固 定 物 体 所 反 射 的 多 径 信 号 也 强 于 回 波 信 号 大 大 影 响 了 雷 达 的 第 期 年 月! " #$ %# &' # 工 程 与 应 用 # $$ # #( )*$### 基 于 遗 忘 因 子 算 法 的 自 适 应 直 达 波 对 消 技 术 许 德 刚 中 国 电 子 科 技 集 团 公 司 第 + 研 究 所 合 肥 ++ 摘 要 在 以 民 用 广 播 电 视 及 &, 等 信 号 为 照 射 源 的 无 源 雷 达 系 统 中 由 于 发 射 信 号 为 连

More information

期 李 环 等 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞 功 能 影 响 1 )!# $ + $#'!!) #!%,$' $ 6. $#! +!! '!!' # $! 引 言 - # # 近 年 来 生 殖 健 康 问 题 日 益 突 出 % 不 孕 不 育 等 各

期 李 环 等 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞 功 能 影 响 1 )!# $ + $#'!!) #!%,$' $ 6. $#! +!! '!!' # $! 引 言 - # # 近 年 来 生 殖 健 康 问 题 日 益 突 出 % 不 孕 不 育 等 各 第 卷 第 期 年 月! "#$%&#% '% 李 环 张 洋 婷 刘 呈 惠 等 %% 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞 功 能 影 响 * % 环 境 科 学 学 报 1 1 2 3 4 5 2 3 %% )!#),$' $ #!' # $) # #)!! $ * %! 1 1 邻 苯 二 甲 酸 二 丁 酯 暴 露 对 雄 性 大 鼠 生 精 细 胞

More information