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

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

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

Microsoft Word - 01.DOC

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

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

FY.DOC

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

More information

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

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

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

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

《大话设计模式》第一章

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

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

JAVA String常用APi

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

More information

全国计算机技术与软件专业技术资格(水平)考试

全国计算机技术与软件专业技术资格(水平)考试 全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2008 年 上 半 年 程 序 员 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 试 题 一 ( 共 15 分 ) 阅 读 以 下 说 明 和 流 程 图, 填 补 流 程 图 中 的 空 缺 (1)~(9), 将 解 答 填 入 答 题 纸 的 对 应 栏 内 [ 说 明

More information

Microsoft PowerPoint - JavaÓïÑÔ»ù´¡.ppt

Microsoft PowerPoint - JavaÓïÑÔ»ù´¡.ppt Java2 lesson 本 Cycle 主 要 讲 Java 的 语 言 基 础 JAVA 程 序 设 计.2. The aim of this lesson is concept and method. 版 权 所 有 2001-2002 成 都 信 息 工 程 学 院 NIIT 信 息 技 术 学 院 赵 卓 宁 共 10 个 cycle 教 学 计 划 学 习 进 度 周 Java 课 程

More information

第 期 熊 安 萍 等 *1$ 文 件 系 统 中 范 围 锁 机 制 的 应 用 研 究! 锁 命 名 空 间 '+'($($ 描 述 了 资 源 和 锁 的 集 合 它 同 时 在 客 户 节 点 和 服 务 节 点 存 在 不 同 之 处 只 是 利 用 一 个 数 据 标 识 来 有 效 区

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

More information

中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!" 通 透 性 增 加 产 生 蛋 白 水 解 酶 促 进 血 管 内 皮 细 胞 有 丝 分 裂 内 皮 细 胞 从 基 底 膜 上 迁 移 到 血 管 周 围 间 隙 粘 附 聚 集 重 构 为 三 维 管 腔 并 与 周 围 血 管

中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期! 通 透 性 增 加 产 生 蛋 白 水 解 酶 促 进 血 管 内 皮 细 胞 有 丝 分 裂 内 皮 细 胞 从 基 底 膜 上 迁 移 到 血 管 周 围 间 隙 粘 附 聚 集 重 构 为 三 维 管 腔 并 与 周 围 血 管 中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!" 学 术 探 讨 冠 心 病 的 治 疗 性 血 管 新 生 与 活 血 化 瘀 段 练 熊 兴 江 王 阶 摘 要 治 疗 性 血 管 新 生 /) '0 1/ * ' 是 冠 状 动 脉 硬 化 性 心 脏 病 * '( '/) *! / * ) '/ ' + 治 疗 的 新 策 略 而 活 血 化 瘀 治 法 对 于 + 的 基 础

More information

内 容 简 介 本 书 是 一 本 关 于 语 言 程 序 设 计 的 教 材, 涵 盖 了 语 言 的 基 本 语 法 和 编 程 技 术, 其 中 包 含 了 作 者 对 语 言 多 年 开 发 经 验 的 总 结, 目 的 是 让 初 学 的 读 者 感 受 到 语 言 的 魅 力, 并 掌

内 容 简 介 本 书 是 一 本 关 于 语 言 程 序 设 计 的 教 材, 涵 盖 了 语 言 的 基 本 语 法 和 编 程 技 术, 其 中 包 含 了 作 者 对 语 言 多 年 开 发 经 验 的 总 结, 目 的 是 让 初 学 的 读 者 感 受 到 语 言 的 魅 力, 并 掌 语 言 程 序 设 计 郑 莉 胡 家 威 编 著 清 华 大 学 逸 夫 图 书 馆 北 京 内 容 简 介 本 书 是 一 本 关 于 语 言 程 序 设 计 的 教 材, 涵 盖 了 语 言 的 基 本 语 法 和 编 程 技 术, 其 中 包 含 了 作 者 对 语 言 多 年 开 发 经 验 的 总 结, 目 的 是 让 初 学 的 读 者 感 受 到 语 言 的 魅 力, 并 掌 握 语

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

尽 管 Java 语 言 是 在 C++ 语 言 基 础 上 发 展 起 来 的, 但 与 C++ 不 同,Java 是 一 种 纯 粹 的 面 向 对 象 语 言 (Object-oriented language) 在 Java 世 界 中, 所 有 事 物 都 是 Object 1. 通 过

尽 管 Java 语 言 是 在 C++ 语 言 基 础 上 发 展 起 来 的, 但 与 C++ 不 同,Java 是 一 种 纯 粹 的 面 向 对 象 语 言 (Object-oriented language) 在 Java 世 界 中, 所 有 事 物 都 是 Object 1. 通 过 玩 转 Object 不 理 解, 就 无 法 真 正 拥 有 歌 德 按 其 实 而 审 其 名, 以 求 其 情 ; 听 其 言 而 查 其 累, 无 使 放 悖 ( 根 据 实 际 明 辨 名 称, 以 便 求 得 真 实 情 况 ; 听 取 言 辞 后 弄 明 它 的 类 别, 不 让 它 混 淆 错 乱 ) 三 玩 转 Object 大 围 山 人 玩 转 Object...1 1. 通

More information

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

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

More information

Microsoft Word - 第6章.doc

Microsoft Word - 第6章.doc 100 第 6 章 继 承 第 6 章 继 承 继 承 是 面 向 对 象 编 程 的 重 要 特 征 之 一 顾 名 思 义, 继 承 就 是 在 现 有 类 的 基 础 上 构 建 新 类 以 满 足 新 的 要 求 在 继 承 过 程 中, 新 的 类 继 承 原 来 的 方 法 和 实 例 变 量, 并 且 能 添 加 自 己 的 方 法 和 实 例 变 量 在 本 章 中 主 要 讲 解

More information

! "#$ %$ $ 资 料 与 方 法 $ 调 查 对 象 全 国 东 北 华 北 华 东 西 北 西 南 和 中 南 六 个 大 区 个 省 自 治 区 直 辖 市 * 个 城 市 中 的 & 所 医 院 参 加 了 本 次 调 查 各 省 省 会 城 市 的 医 学 院 校 附 属 医 院 省

! #$ %$ $ 资 料 与 方 法 $ 调 查 对 象 全 国 东 北 华 北 华 东 西 北 西 南 和 中 南 六 个 大 区 个 省 自 治 区 直 辖 市 * 个 城 市 中 的 & 所 医 院 参 加 了 本 次 调 查 各 省 省 会 城 市 的 医 学 院 校 附 属 医 院 省 ! "#$ %$ $ 临 床 研 究 中 国 住 院 新 生 儿 流 行 病 学 调 查 中 华 医 学 会 儿 科 学 分 会 新 生 儿 学 组 摘 要 目 的 通 过 全 国 范 围 内 城 市 医 院 住 院 新 生 儿 的 调 查 以 了 解 我 国 目 前 住 院 新 生 儿 的 疾 病 谱 及 转 归 方 法 抽 取 全 国 个 省 和 自 治 区 的 * 个 城 市 中 的 & 所

More information

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

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

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

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

北魏山东佛教文化个案研究

北魏山东佛教文化个案研究 北 魏 山 东 佛 教 文 化 个 案 研 究 一 北 魏 时 期 佛 教 在 山 东 的 传 播 与 发 展 以 滨 州 博 兴 龙 华 寺 为 代 表 社 会 背 景 北 魏 佛 教 的 发 展 是 伴 随 着 佛 教 的 中 国 化 即 汉 化 的 过 程 而 不 断 发 展 的, 同 时 也 带 有 北 魏 统 治 者 作 为 少 数 民 族 的 本 身 特 色 自 汉 通 西 域, 佛 教

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

中 国 中 西 医 结 合 杂 志 年 月 第 卷 第 期!"# $! 症 状 在 诊 断 时 推 荐 应 用 $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

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

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

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

More information

PowerPoint 演示文稿

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

More information



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

More information

chp6.ppt

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

More information

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

4 中 南 大 学 学 报 医 学 版 摘 要 目 的 探 讨 早 发 性 精 神 分 裂 症 患 者 在 静 息 状 态 下 是 否 存 在 脑 功 能 连 接 异 常 以 及 异 常 区 域 的 定 位 方 法 采 用 第 版 美 国 精 神 障 碍 诊 断 与 统 计 手 册 ( * ) ( 中 南 大 学 学 报 医 学 版 3! + )! + - + - %$ 58: 58:7& * 1:D * $%&' 1&! & )& "# ( &!& )#% & '& '#! & #& & " ( ) 5*( )/ + ( / + + 6') * )* ) ; + *6 / + * ) *+ ' 6') * )+ * ) 6 9, * : + * ) *+ ) /+( * ( / * ) (

More information

中共贺州市委员会

中共贺州市委员会 贺 州 市 加 强 宣 传 思 想 文 化 人 才 队 伍 建 设 签 约 制 暂 行 办 法 为 了 逐 步 解 决 当 前 贺 州 新 闻 写 作 播 音 主 持 记 者 编 辑 媒 体 运 营 文 艺 创 作 文 化 创 意 产 业 等 方 面 人 才 紧 缺 制 约 我 市 宣 传 思 想 文 化 工 作 和 文 化 产 业 发 展 滞 后 等 问 题, 根 据 自 治 区 党 委 自 治

More information

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

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

More information

!

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

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

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

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

More information

附录J:Eclipse教程

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

More information

!!! "# $ " %!!

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

More information

! # % % & # # % #!& % &# % &# % % % # %& ( (!& (! & & % % #!! ) %&! *& % %! % %!! # % %!! %*!& % &# % &# ) ) ( % # # ) % ( (!& (! (!! # % % #!! # ( &!

! # % % & # # % #!& % &# % &# % % % # %& ( (!& (! & & % % #!! ) %&! *& % %! % %!! # % %!! %*!& % &# % &# ) ) ( % # # ) % ( (!& (! (!! # % % #!! # ( &! !#!#!%!&!& #!#!#!#!#!#!! #!% # ( )! & & % & ) % ( %! # )& ) &!) &!% )& )! )!!% & ( (!&!&!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! )! % * % * ( & )!! % & # %! %! )! % * % * ( & )!! % & # %! %! # )! % * % *

More information

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

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

More information

气 候 与 环 境 研 究 卷 &!' 张 书 余 许 多 学 者 对 人 体 舒 适 度 进 行 了 研 究!!0!! " 对 欧 洲 不 同 国 家 的 城 市 热 舒 适 性 进 行 了 研 究 周 后 福 探 讨 了 气 候 变 化 对 人 体 健 康 的 影 响 吴 兑 ) 进 行 了 多

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

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

全国计算机技术与软件专业技术资格(水平)考试

全国计算机技术与软件专业技术资格(水平)考试 全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2009 年 下 半 年 程 序 员 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 请 按 下 述 要 求 正 确 填 写 答 题 纸 1. 在 答 题 纸 的 指 定 位 置 填 写 你 所 在 的 省 自 治 区 直 辖 市 计 划 单 列 市 的 名 称 2. 在 答

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

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

2009年下半年软件设计师下午试题

2009年下半年软件设计师下午试题 全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 请 按 下 述 要 求 正 确 填 写 答 题 纸 1. 在 答 题 纸 的 指 定 位 置 填 写 你 所 在 的 省 自 治 区 直 辖 市 计 划 单 列 市 的 名 称 2.

More information

Microsoft Word - 第三章第三節.doc

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

More information

!$ 中 国 生 物 工 程 杂 志, 2 图 药 物 作 用 靶 点 及 靶 向 药 物!"! " #$% &' 丝 氨 酸 蛋 白 酶 抑 制 剂 2 34 丝 氨 酸 蛋 白 酶 是 目 前 研 究 最 多 的 抗 病 毒 靶 点 其 作 用 在 于 催 化 裂 解 +, 多 聚 蛋 白 前

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

More information

软件设计师

软件设计师 全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 请 按 下 述 要 求 正 确 填 写 答 题 纸 1. 在 答 题 纸 的 指 定 位 置 填 写 你 所 在 的 省 自 治 区 直 辖 市 计 划 单 列 市 的 名 称 2.

More information

投稿類別:電子工程類

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

More information

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

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

More information

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

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

More information

《安徒生童话》(四)

《安徒生童话》(四) ! " # $ !"# $$$$$$$$$$$$$$$$$$$$!%" $$$$$$$$$$$$$$$$$$!& $$$$$$$$$$$$$$$$$$$$$!&" $$$$$$$$$$$$$$$$$$!&# $$$$$$$$$$$$$$$$$$$$$!&( $$$$$$$$$$$$!#) $$$$$$$$$$$$$$$$$$$!)" $$$$$$$$$$$$$$$$$$$$$!!" $$$$$$$$$$$$$$$$$!!!

More information

2006 年 12 月 SUN 公 司 发 布 JDK6.0 目 前 主 流 的 JDK 是 Sun 公 司 发 布 的 JDK, 除 了 Sun 之 外, 还 有 很 多 公 司 和 组 织 都 开 发 了 自 己 的 JDK, 例 如 IBM 公 司 开 发 的 JDK,BEA 公 司 的 Jr

2006 年 12 月 SUN 公 司 发 布 JDK6.0 目 前 主 流 的 JDK 是 Sun 公 司 发 布 的 JDK, 除 了 Sun 之 外, 还 有 很 多 公 司 和 组 织 都 开 发 了 自 己 的 JDK, 例 如 IBM 公 司 开 发 的 JDK,BEA 公 司 的 Jr 1 Java 入 门 Java 是 一 门 很 优 秀 的 编 程 语 言, 具 有 面 向 对 象 与 平 台 无 关 安 全 稳 定 和 多 线 程 等 特 点, 是 目 前 软 件 设 计 中 极 为 健 壮 的 编 程 语 言 Java 不 仅 可 以 用 来 开 发 大 型 的 应 用 程 序, 而 且 特 别 适 合 于 Internet 的 应 用 开 发 Java 确 实 具 备 了

More information

<4D6963726F736F667420576F7264202D20CBD5D6DDBFC6BCBCD1A7D4BACCECC6BDD1A7D4BA32303135C4EAB1BEBFC6D5D0C9FAD7A8D2B5BDE9C9DC2E646F63>

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

More information

尽 管 Java 语 言 是 在 C++ 语 言 基 础 上 发 展 起 来 的, 但 是 有 别 于 C++,Java 是 一 种 纯 粹 的 面 向 对 象 语 言 (Object-oriented language) 在 像 Java 这 样 纯 粹 的 面 向 对 象 语 言 中, 所 有

尽 管 Java 语 言 是 在 C++ 语 言 基 础 上 发 展 起 来 的, 但 是 有 别 于 C++,Java 是 一 种 纯 粹 的 面 向 对 象 语 言 (Object-oriented language) 在 像 Java 这 样 纯 粹 的 面 向 对 象 语 言 中, 所 有 玩 转 Object 不 理 解, 就 无 法 真 正 拥 有 歌 德 按 其 实 而 审 其 名, 以 求 其 情 ; 听 其 言 而 查 其 累, 无 使 放 悖 ( 根 据 实 际 明 辨 名 称, 以 便 求 得 真 实 情 况 ; 听 取 言 辞 后 弄 明 它 的 类 别, 不 让 它 混 淆 错 乱 ) 三 玩 转 Object 大 围 山 人 玩 转 Object...1 1. 通

More information

詞 彙 表 編 號 詞 彙 描 述 1 預 約 人 資 料 中 文 姓 名 英 文 姓 名 身 份 證 字 號 預 約 人 電 話 性 別 2 付 款 資 料 信 用 卡 別 信 用 卡 號 信 用 卡 有 效 日 期 3 住 房 條 件 入 住 日 期 退 房 日 期 人 數 房 間 數 量 入

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

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

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

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

More information

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

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

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

Microsoft PowerPoint - course2.ppt

Microsoft PowerPoint - course2.ppt Java 程 式 設 計 基 礎 班 (2) 莊 坤 達 台 大 電 信 所 網 路 資 料 庫 研 究 室 Email: doug@arbor.ee.ntu.edu.tw Class 2 1 回 顧 Eclipse 使 用 入 門 Class 2 2 Lesson 2 Java 程 式 語 言 介 紹 Class 2 3 Java 基 本 知 識 介 紹 大 小 寫 有 差 (Case Sensitive)

More information

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

More information

議 程 前 發 言 冀 新 官 上 任 燒 好 三 把 火 用 好 三 盆 水 陳 明 金 2014 年 11 月 18 日 澳 門 特 區 政 府 即 將 換 屆, 各 種 傳 聞 令 廣 大 居 民 感 覺 到, 絕 大 部 份 主 要 官 員 都 會 換 人 雖 然 他 們 對 人 選 無 話

議 程 前 發 言 冀 新 官 上 任 燒 好 三 把 火 用 好 三 盆 水 陳 明 金 2014 年 11 月 18 日 澳 門 特 區 政 府 即 將 換 屆, 各 種 傳 聞 令 廣 大 居 民 感 覺 到, 絕 大 部 份 主 要 官 員 都 會 換 人 雖 然 他 們 對 人 選 無 話 促 重 整 運 輸 部 門 冀 革 新 交 通 政 策 鄭 安 庭 議 員 議 程 前 發 言 2014 年 11 月 18 日 主 席 各 位 同 事 : 今 天 我 的 議 程 前 發 言 題 目 是 : 促 重 整 運 輸 部 門 冀 革 新 交 通 政 策 剛 剛 完 成 的 第 61 屆 澳 門 格 蘭 披 治 大 賽 車 令 到 遊 客 絡 繹 不 絕 的 澳 門 更 為 熱 烈, 關

More information

一 耀 州 青 瓷 的 裝 飾 手 法 與 紋 飾 種 類 耀 州 窯 的 裝 飾 紋 樣, 豐 富 多 變, 而 且 題 材 內 容 廣 泛, 組 合 形 式 多 樣, 圖 案 形 象 優 美, 令 人 賞 心 悅 目, 並 且 反 映 了 當 時 社 會 的 審 美 趣 味 和 理 想 裝 飾

一 耀 州 青 瓷 的 裝 飾 手 法 與 紋 飾 種 類 耀 州 窯 的 裝 飾 紋 樣, 豐 富 多 變, 而 且 題 材 內 容 廣 泛, 組 合 形 式 多 樣, 圖 案 形 象 優 美, 令 人 賞 心 悅 目, 並 且 反 映 了 當 時 社 會 的 審 美 趣 味 和 理 想 裝 飾 宋 代 耀 州 青 瓷 的 紋 飾 風 格 與 意 義 曾 肅 良 英 國 萊 斯 特 大 學 博 物 館 學 博 士 國 立 台 灣 師 範 大 學 美 術 研 究 所 助 理 教 授 摘 要 中 國 的 飲 茶 之 風, 興 於 唐 而 盛 於 宋, 特 別 是 宋 代 宮 廷 禁 苑 和 地 方 官 吏 文 人 學 士 的 尚 茶 崇 茶, 以 品 茶 為 雅 尚 的 觀 念 與 作 法, 使

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

一、注意事项

一、注意事项 2014 年 天 津 市 公 务 员 考 试 行 测 真 题 及 答 案 解 析 第 一 部 分 数 量 关 系 ( 共 15 题 参 考 时 限 15 分 钟 ) 1 6, 11, 17, ( ), 45 A.30 B.28 C.25 D.22 2 2, 3, 6, 15, ( ) A.25 B.36 C.42 D.64 3 1, 2, 9, 64, 625, ( ) A.1728 B.3456

More information

Microsoft Word - 2-2排列與組合.doc

Microsoft Word - 2-2排列與組合.doc 2 2 排 列 與 組 合 ( 甲 ) 直 線 排 列 引 入 直 線 排 列 : 例 子 : 從 建 中 高 一 某 班 5 個 同 學 中, 選 出 3 人 排 成 一 列, 有 幾 種 排 法? 解 法 : A 5 個 同 學 以 ABCDE 表 示, 選 出 3 人 排 成 一 列, 我 們 將 這 個 過 程, 分 成 3 個 步 驟, 配 合 樹 狀 圖, 可 得 排 法 共 有 5 4

More information

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

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

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

1 已 賺 得 並 已 收 到 現 金 2 已 經 收 到 現 金, 但 仍 未 賺 得 3 尚 未 賺 得, 或 收 到 現 金 4 已 經 賺 得, 但 尚 未 收 到 現 金 (2)9. 下 列 何 種 報 表 係 表 達 一 公 司 在 某 一 時 點 之 財 務 狀 況? 1 綜 合 損

1 已 賺 得 並 已 收 到 現 金 2 已 經 收 到 現 金, 但 仍 未 賺 得 3 尚 未 賺 得, 或 收 到 現 金 4 已 經 賺 得, 但 尚 未 收 到 現 金 (2)9. 下 列 何 種 報 表 係 表 達 一 公 司 在 某 一 時 點 之 財 務 狀 況? 1 綜 合 損 Chapter 1 基 本 概 念 一 選 擇 題 (4)1. 所 謂 自 然 營 業 年 度 是 指 : 1 自 購 貨 製 造 銷 貨 至 應 收 帳 款 收 現 為 止 的 一 個 期 間 2 自 每 年 1 月 1 日 至 12 月 31 日 的 會 計 期 間 3 企 業 管 理 當 局 所 訂 定 賒 銷 收 帳 的 最 長 期 限 4 以 企 業 之 營 業 淡 季 為 起 迄 分 界

More information

社 会 妇 也 有 到 夫 家 守 志 的 情 况 目 前 各 地 现 存 的 大 量 贞 节 牌 坊 和 史 书 中 连 篇 累 牍 的 节 妇 传 就 是 当 时 历 史 的 真 实 反 映 但 是 在 历 史 上, 现 实 生 活 中 的 寡 妇 守 志 并 非 一 件 易 事 很 多 寡 妇

社 会 妇 也 有 到 夫 家 守 志 的 情 况 目 前 各 地 现 存 的 大 量 贞 节 牌 坊 和 史 书 中 连 篇 累 牍 的 节 妇 传 就 是 当 时 历 史 的 真 实 反 映 但 是 在 历 史 上, 现 实 生 活 中 的 寡 妇 守 志 并 非 一 件 易 事 很 多 寡 妇 社 会 总 第 期 高 永 平,! "#" " "# $ %&$ ' & " # $ # $ #,$ & $! & & $, & ' $! "#" # ($ $ ), ' ( *," # ' & & $* & & * # & "#" + $ & # $! " + ' $$ & *# $!! * ** $! "#" $#! & &# $,$ & & & $#, & # $ "& & # & $ ##$

More information

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

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

More information

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

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

More information

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

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

More information

《无事生非》

《无事生非》 !!!! " #! " # $ $ ! !! " # $ " % # " & # " # " $ " # $ " # # # % # " # " # # &! "! # $! $ $ % $ " $ #! $ "! $ $! $ $ # $ $! $ " " $ $ $! $ $ #! $! $ # $! $! # ! " # " $$ % " # % % # " " % & " " # " " "

More information

1911 年 武 汉 起 义, 广 东 独 立 胡 汉 民 任 总 督, 陈 任 广 东 军 政 府 外 交 部 副 部 长 陈 不 愿 做 官, 几 个 月 后 即 辞 职 1915 年 与 李 煜 堂 设 立 上 海 保 险 公 司, 陈 任 主 席 1921 年 孙 中 山 就 任 非 常 大

1911 年 武 汉 起 义, 广 东 独 立 胡 汉 民 任 总 督, 陈 任 广 东 军 政 府 外 交 部 副 部 长 陈 不 愿 做 官, 几 个 月 后 即 辞 职 1915 年 与 李 煜 堂 设 立 上 海 保 险 公 司, 陈 任 主 席 1921 年 孙 中 山 就 任 非 常 大 近 代 新 会 名 人 事 迹 张 云 田 : 新 会 县 双 水 区 人, 中 国 同 盟 会 员 华 侨 镇 南 关 起 义 烈 士 张 云 田 少 年 受 其 父 教 育, 精 通 文 翰, 其 时 深 受 外 国 嘲 笑 中 华 民 族 为 东 亚 病 夫 之 辱, 因 而 弃 文 就 武, 中 武 秀 才 中 年 时 结 交 三 合 会 兄 弟, 立 志 革 清 兴 华, 参 加 孙 中

More information

2014~2015 年度全国 1 卷考前模拟冲刺 语 文 满分 150 分考试时间 150 分钟 第Ⅰ卷 阅读题 甲 必考题 一尧 现代文阅读 渊9 分 每小题 3 分冤 阅读下面的文字完成 1-3 题 在教育领域 数据是描述事实的符号序列 是信息载体 教育数据大致可以分为三类 包括结构化尧 半结构

2014~2015 年度全国 1 卷考前模拟冲刺 语 文 满分 150 分考试时间 150 分钟 第Ⅰ卷 阅读题 甲 必考题 一尧 现代文阅读 渊9 分 每小题 3 分冤 阅读下面的文字完成 1-3 题 在教育领域 数据是描述事实的符号序列 是信息载体 教育数据大致可以分为三类 包括结构化尧 半结构 目 录 一 全 国 各 省 ( 市 ) 模 拟 卷 精 选 1. 河 南 河 北 山 西 三 省 2015 届 高 考 考 前 模 拟 冲 刺 2. 河 南 河 北 山 西 三 省 2015 届 高 三 高 考 考 前 质 量 监 测 ( 二 ) 3. 河 南 省 2015 届 高 三 高 考 适 应 性 模 拟 练 习 (5 月 ) 4. 江 西 省 2015 届 高 三 5 月 大 联 考 5.

More information

泰康附加意外住院津贴收入保障保险条款

泰康附加意外住院津贴收入保障保险条款 泰 康 养 老 [2011] 医 疗 保 险 058 号 泰 康 附 加 新 生 活 少 儿 意 外 津 贴 医 疗 保 险 条 款 阅 读 指 引 请 扫 描 以 查 询 验 证 条 款 本 阅 读 指 引 有 助 于 您 理 解 条 款, 对 本 附 加 合 同 内 容 的 解 释... 凡 条 款 已 有 约 定 的, 以 条 款 约 定 为 准... 您 拥 有 的 重 要 权 益 本 附

More information

6 22 22 23 23 24 24 1., 2., 3., 24 26 26 28 30 31 31 31 32 32 34 34 1. 2., 3.,, 34 37 37 39 40 43 44 2

6 22 22 23 23 24 24 1., 2., 3., 24 26 26 28 30 31 31 31 32 32 34 34 1. 2., 3.,, 34 37 37 39 40 43 44 2 1 1 1., 2.,, 3., 1 3 3 5 7 9 11 11 12 12 13 13 1., 2.,, 3., 13 15 15 18 19 21 1 6 22 22 23 23 24 24 1., 2., 3., 24 26 26 28 30 31 31 31 32 32 34 34 1. 2., 3.,, 34 37 37 39 40 43 44 2 44 45 45 47 1., 2.

More information

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

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

More information

Microsoft Word - 把时间当作朋友(2011第3版)3.0.b.07.doc

Microsoft Word - 把时间当作朋友(2011第3版)3.0.b.07.doc 2 5 8 11 0 1. 13 2. 15 3. 18 1 1. 22 2. 25 3. 27 2 1. 35 2. 38 3. 41 4. 43 5. 48 6. 50 3 1. 56 2. 59 3. 63 4. 65 5. 69 13 22 35 56 6. 74 7. 82 8. 84 9. 87 10. 97 11. 102 12. 107 13. 111 4 114 1. 114 2.

More information

为 进 一 步 推 进 教 育 教 学 改 革, 满 足 学 生 个 性 化 学 习 需 求, 培 养 学 生 实 践 能 力 和 创 新 创 业 素 质, 在 编 制 2016 级 专 业 人 才 培 养 方 案 指 导 意 见 中, 对 原 有 文 件 关 于 印 发 <2015 级 人 才 培

为 进 一 步 推 进 教 育 教 学 改 革, 满 足 学 生 个 性 化 学 习 需 求, 培 养 学 生 实 践 能 力 和 创 新 创 业 素 质, 在 编 制 2016 级 专 业 人 才 培 养 方 案 指 导 意 见 中, 对 原 有 文 件 关 于 印 发 <2015 级 人 才 培 教 务 2016 28 号 本 学 期, 在 学 校 深 入 开 展 两 学 一 做 学 习 教 育 活 动 的 指 引 下, 教 务 处 全 面 贯 彻 和 落 实 关 于 印 发 学 校 2016 年 十 项 重 点 工 作 责 任 分 解 表 的 通 知 ( 漳 职 院 办 2015 14 号 ) 和 漳 州 职 业 技 术 学 院 办 公 室 关 于 开 展 追 问 题 破 难 题 促 发

More information

<4D6963726F736F667420576F7264202D20B5F8C4B1A55CAFE0B5FBA6F4ACF6BFFDAAED2E646F63>

<4D6963726F736F667420576F7264202D20B5F8C4B1A55CAFE0B5FBA6F4ACF6BFFDAAED2E646F63> 南 區 身 心 障 礙 者 職 業 輔 導 評 量 資 源 中 心 - 功 能 性 視 覺 評 估 記 錄 表 * 由 專 業 人 員 施 測 並 填 寫, 施 測 者 與 填 寫 者 須 為 同 一 人 * 此 表 改 編 自 謝 曼 莉 與 張 千 惠 所 製 之 功 能 性 視 覺 評 估 表, 並 由 張 千 惠 再 次 校 對 姓 名 性 別 出 生 日 期 年 月 日 年 齡 障 礙 類

More information

目 录 1 国 务 院 中 央 军 委 关 于 建 立 和 完 善 军 民 结 合 寓 军 于 民 武 器 装 备 科 研 生 产 体 系 的 若 干 意 见 2 国 务 院 关 于 鼓 励 和 引 导 民 间 投 资 健 康 发 展 的 若 干 意 见 >>....... 11 3 国 防 科 工

目 录 1 国 务 院 中 央 军 委 关 于 建 立 和 完 善 军 民 结 合 寓 军 于 民 武 器 装 备 科 研 生 产 体 系 的 若 干 意 见 2 国 务 院 关 于 鼓 励 和 引 导 民 间 投 资 健 康 发 展 的 若 干 意 见 >>....... 11 3 国 防 科 工 军 民 融 合 相 关 政 策 法 规 汇 编 广 东 省 国 防 科 学 技 术 工 业 办 公 室 2015 年 5 月 25 日 目 录 1 国 务 院 中 央 军 委 关 于 建 立 和 完 善 军 民 结 合 寓 军 于 民 武 器 装 备 科 研 生 产 体 系 的 若 干 意 见 2 国 务 院 关 于 鼓 励 和 引 导 民 间 投 资 健 康 发 展 的 若 干 意 见 >>.......

More information

<4D6963726F736F667420576F7264202D20B9D8D3DA32303135C4EAC9EAB1A8D7A8D2B5BCBCCAF5C8FDBCB6B8DACEBBB5C4CDA8D6AA2E646F63>

<4D6963726F736F667420576F7264202D20B9D8D3DA32303135C4EAC9EAB1A8D7A8D2B5BCBCCAF5C8FDBCB6B8DACEBBB5C4CDA8D6AA2E646F63> 贵 州 大 学 文 件 贵 大 发 2015 40 号 贵 州 大 学 关 于 2015 年 申 报 专 业 技 术 三 级 岗 位 的 通 知 各 学 院 校 直 各 单 位 : 根 据 省 教 育 厅 省 人 力 资 源 和 社 会 保 障 厅 关 于 做 好 2015 年 省 属 高 等 学 校 专 业 技 术 三 级 岗 位 聘 用 评 议 工 作 的 通 知 ( 黔 教 师 发 2015

More information

食 用 蘑 菇 尤 其 是 在 上 流 社 会 非 常 流 行 据 传 古 罗 马 的 凯 撒 大 帝 在 食 用 蘑 菇 膳 肴 前 有 专 门 的 侍 者 先 行 鉴 尝 蘑 菇 是 否 有 毒 以 确 保 食 用 安 全 在 世 界 其 他 地 方 如 墨 西 哥 俄 罗 斯 以 及 一 些

食 用 蘑 菇 尤 其 是 在 上 流 社 会 非 常 流 行 据 传 古 罗 马 的 凯 撒 大 帝 在 食 用 蘑 菇 膳 肴 前 有 专 门 的 侍 者 先 行 鉴 尝 蘑 菇 是 否 有 毒 以 确 保 食 用 安 全 在 世 界 其 他 地 方 如 墨 西 哥 俄 罗 斯 以 及 一 些 第 一 章 国 内 外 食 用 菌 产 业 发 展 现 状 在 过 去 的 半 个 世 纪 里 食 用 菌 栽 培 技 术 已 传 至 全 球 五 大 洲 商 业 栽 培 食 用 菌 已 成 为 一 个 全 球 性 的 行 业 世 界 各 国 的 食 用 菌 生 产 随 着 栽 培 技 术 的 进 步 都 取 得 了 飞 跃 式 的 发 展 食 用 菌 的 精 深 加 工 业 也 发 展 迅 速 整

More information

# # # # # # # # # % # & # & # # # () # (( # * * (( # (+ # ( (# # (# # (# # ( # ( +) (

# # # # # # # # # % # & # & # # # () # (( # * * (( # (+ # ( (# # (# # (# # ( # ( +) ( # # # # # # # # # % # & # & # # # () # (( # * * (( # (+ # ( (# # (# # (# # ( # ( +) ( # +) # +( # ++ # + + # + # +# # + # +% +& # +& # + # + # ) ( # ( # + # # # # # # ) ( # + # # # # + # # # # # # #

More information

/ 第 卷 (!(" $& $% $%% $$/,!. $"($ ) 0 %'&.(!.' (!' 0 %$ $'#78#/8# 8#$/!),% 3 -+ /! ", $ % +'!)%+%$" $ %'+(("& +'!) "'$,'(% -' (!' 0 %$ $'18 #88 #88!)(!

/ 第 卷 (!( $& $% $%% $$/,!. $($ ) 0 %'&.(!.' (!' 0 %$ $'#78#/8# 8#$/!),% 3 -+ /! , $ % +'!)%+%$ $ %'+((& +'!) '$,'(% -' (!' 0 %$ $'18 #88 #88!)(! 第 卷 第 期 年 月!"#!# $%# 7 三 峡 库 区 万 州 段 农 村 环 境 卫 生 现 状 与 健 康 潜 在 危 害 因 素 研 究 罗 超 冉 贞 卫 周 新 颜 朝 阳 张 学 建 王 军 程 永 红 刘 纯 华 重 庆 市 万 州 区 疾 病 预 防 控 制 中 心 万 州 摘 要 目 的 了 解 万 州 区 农 村 居 民 环 境 卫 生 现 状 与 人 群 健 康 主 要

More information