类比思想在解题中的应用.DOC

1、Comment Tenx1: Page: 1作者：张力 1999.12.5 类比思想在解题中的应用 第 1 页 共 13页类 比 思 想 在 解 题 中 的 应 用【 关 键 字 】 思 想 ； 类 比 ； 相 似 性 ； 对 应 。【 摘 要 】 ：类 比 ， 是 一 种 试 图 建 立 未 知 的 问 题 与 已 知 的 问 题 之 间的 联 系 ， 从 而 利 用 已 知 的 解 题 方 法 去 解 决 新 的 问 题 的 思 路 。本 文 首 先 通 过 分 析 具 体 的 例 子 ， 指 出 类 比 解 题 不 仅 仅 是 注意 到 了 表 面 上 的 相 似 性 ， 更 是 建 立

2、 了 已 知 问 题 和 未 知 问 题之 间 的 对 应 关 系 。 然 后 ， 本 文 将 通 过 另 一 个 例 子 ， 论 述 表面 相 似 性 与 内 在 的 对 应 之 间 的 关 系 ， 并 且 指 出 利 用 类 比 解题 的 过 程 是 从 表 面 相 似 性 上 升 到 一 一 对 应 的 过 程 。引 ： 解 题 ， 从 熟 悉 的 地 方 开 始面 对 一 个 新 的 问 题 应 该 如 何 着 手 去 分 析 解 决 呢 ？从 熟 悉 的 地 方 开 始 着 手 。 这 是 生 活 中 人 们 常 常 采 用 的 方 法 ： 希 望面 对 的 难 题 与 以 前 解

3、决 过 的 某 个 问 题 是 相 同 的 ， 或 者 至 少 类 似 的 ； 由 此就 可 以 获 得 值 得 借 鉴 的 经 验 。 面 对 一 个 陌 生 的 问 题 ， 试 图 把 它 和 某 个 熟悉 的 问 题 联 系 起 来 ， 借 助 熟 悉 的 知 识 和 熟 悉 的 方 法 来 解 决 新 问 题 ， 是 自然 的 想 法 。这 种 寻 找 未 知 问 题 和 已 知 问 题 之 间 联 系 的 思 想 ， 可 以 称 为 类 比 。更 确 切 的 说 ， “如 果 两 个 系 统 的 各 自 的 各 部 分 之 间 ， 存 在 某 种 一 致 的 关系 的 话 ， 则 称

4、 两 个 系 统 是 可 以 类 比 的 。 ”1如 何 理 解 定 义 中 所 说 的 “一 致 的 关 系 ”呢 ？如 果 只 简 单 的 把 “存 在 某 种 一 致 的 关 系 ”理 解 成 一 种 含 糊 的 相 似性 。 那 么 类 比 就 完 全 归 结 为 人 的 主 观 的 感 觉 ， 这 种 主 观 上 的 “似 曾相 识 ”是 不 能 够 作 为 分 析 问 题 、 解 决 问 题 的 依 据 的 。 然 而 类 比 的 思 想 的确 被 广 泛 的 应 用 于 解 决 各 种 问 题 ， 说 明 类 比 的 本 质 是 另 一 种 比 表 面 上 的相 似 性 更 可

5、靠 和 更 有 说 服 力 的 “一 致 关 系 ”。 事 实 上 ， 类 比 是 建 立 在两 个 问 题 之 间 的 一 种 一 一 对 应 的 映 射 关 系 。 本 文 的 第 一 部 分 ， 正 是 试 图阐 述 这 一 本 质 上 的 “一 致 关 系 ”。然 而 两 个 问 题 之 间 的 本 质 联 系 并 不 是 那 么 容 易 得 到 的 。 人 们 在 对 问题 的 最 初 的 分 析 中 ， 注 意 到 的 往 往 还 是 表 面 上 （ 甚 至 只 是 文 字 上 ） 的 相1 引自参考书目 i（数学与猜想）第二章。作者：张力 1999.12.5 类比思想在解题中的应

6、用 第 2 页 共 13 页似 性 。 希 望 直 接 得 到 两 个 问 题 之 间 相 互 对 应 和 相 互 转 化 的 关 系 是 不 现 实的 。 因 此 ， 最 初 观 察 到 的 表 面 上 的 相 似 性 虽 然 有 些 不 可 靠 ， 但 是 至 少 它能 够 为 分 析 问 题 指 出 方 向 ， 由 此 尝 试 着 建 立 问 题 之 间 的 对 应 关 系 。 正 如本 文 第 二 部 分 将 要 阐 述 的 ， 利 用 类 比 解 题 的 过 程 是 从 模 糊 到 清 晰 ， 从 表面 到 本 质 的 分 析 过 程 。接 下 来 的 两 个 部 分 ， 就 将 探

7、 讨 类 比 过 程 中 ， 表 面 的 相 似 和 本 质 的 对应 之 间 的 关 系 。类 比 的 本 质 ， 一 一 对 应 的 关 系类 比 作 为 一 种 分 析 问 题 的 思 想 方 法 ， 目 的 是 希 望 将 不 熟 悉 的 知 识 转化 为 熟 悉 的 知 识 ， 将 未 知 的 问 题 转 化 为 已 知 的 问 题 。如 何 实 现 这 一 转 化 ， 取 决 于 如 何 对 两 个 问 题 进 行 类 比 。 如 果 仅 考 虑到 两 个 问 题 表 面 上 的 相 似 性 ， 那 么 很 可 能 会 机 械 的 模 仿 已 知 问 题 的 解 决方 法 ， 来

8、解 决 新 问 题 。 这 种 想 法 缺 乏 严 谨 可 靠 的 支 持 ， 难 以 保 证 在 实 际解 题 中 能 够 成 功 。 即 使 成 功 了 ， 也 是 知 其 然 而 不 知 其 所 以 然 ， 没 有 发 现问 题 之 间 本 质 的 联 系 ， 往 往 得 不 到 最 好 的 解 决 方 法 。 而 当 类 比 过 程 中 两个 问 题 之 间 存 在 一 种 对 应 关 系 ， 未 知 问 题 中 的 所 有 描 述 对 象 和 操 作 ， 在已 知 问 题 中 都 有 与 之 一 一 对 应 的 内 容 ， 那 么 整 个 未 知 的 问 题 就 可 以 通 过这 种

9、 一 一 对 应 的 映 射 关 系 ， 转 化 为 已 知 的 问 题 ， 也 就 可 以 应 用 已 知 问 题的 解 决 方 法 来 解 决 它 。下 面 的 例 子 就 是 如 此 。【 “整 数 拆 分 ”与 “因 数 分 解 ”】整 数 拆 分 ： 将 一 个 正 整 数 n， 拆 分 为 一 组 小 于 n 的 正 整 数 的 和（ 不 考 虑 这 组 正 整 数 排 列 的 先 后 次 序 ） 。 求 总 共 有 多 少 组 可 能 的 拆 分 。 1这 是 一 道 众 所 周 知 的 组 合 计 数 问 题 。 解 决 的 方 法 有 两 种 ： 利 用 递 归 的 枚 举

10、解 题 模 型 。 (对 应 程 序 名 DIVIDE1.PAS)将 问 题 描 述 为 ： 求 满 足 等 式 12321 naaan mm的 所 有 正 整 数 组 （ a1， a2， a3， a4， am） 的 总 数 。 为 此 ， 可 以 采 用递 归 枚 举 的 方 法 逐 个 确 定 每 一 个 ai 从 而 求 出 所 有 的 解 ， 并 统 计 总 数 。设 D(k,n)为 将 n 拆 分 成 一 组 不 小 于 k 的 正 整 数 的 和 的 解 的 数 目 。例 如 ， a1 可 以 选 取 1n/2之 间 的 任 意 整 数 ， 剩 下 的 n-a1 可 以 拆分 成

11、不 小 于 a1 的 若 干 个 整 数 的 和 。 于 是 对 于 a1， 有；2/1),(),(n而 对 a2， 有21),(),(2/) 212 个 数若 只 拆 分 成 个 以 上 的 数若 拆 分 成anaD由 此 不 难 得 出 问 题 的 递 归 求 解 式1 问题来自参考书目 ii（算法设计）4.2.4。作者：张力 1999.12.5 类比思想在解题中的应用 第 3 页 共 13 页; 1),(),(2/nikiD问 题 的 解 等 价 于 ( 减 一 以 除 去 n = n 的 拆 分 方 案 )。由 于 原 问 题 只 要 给 出 解 的 总 数 ， 而 这 一 算 法 在

12、 计 算 过 程 中 求 出 了 所有 的 解 ， 所 以 枚 举 算 法 的 效 率 在 n 较 大 的 时 候 是 很 低 的 。 母 函 数 解 题 模 型 。 (对 应 程 序 名 DIVIDE2.PAS)设 拆 分 的 这 组 正 整 数 中 1 出 现 的 次 数 为 x1， 2 出 现 的 次 数 为x2， 等 等 ， 那 么 问 题 可 以 描 述 为 ： 求 不 定 方 程)0(*21 inkxx的 整 数 解 的 总 数 。 于 是 就 可 以 利 用 构 造 母 函 数 ， 来 求 不 定 方 程 的 整 数 解的 个 数 。 方 法 如 下 ： 1拆 分 中 不 选 取

13、 1 可 以 表 示 为 x0=1， 取 一 个 1 表 示 为 x， 取 两 个1 为 x*x=x2， 取 k 个 1 为 xk。 由 加 法 原 理 得 到 选 取 1 的 所 有 方 案 为 ；n3不 选 取 2 可 以 表 示 为 1， 取 一 个 2 表 示 为 x2， 取 两 个 2 为x2*x2=x4， 取 k 个 为 x2k， 由 加 法 原 理 得 到 选 取 2 的 所 有 方 案 为 ；/n同 理 ， 对 于 正 整 数 r， 选 取 k 个 表 示 为 xk*r， 由 加 法 原 理 得 到 选取 r 的 所 有 方 案 为 ；nrr /*21再 由 乘 法 原 理 ，

14、 同 时 选 取 1,2,n-1 的 方 案 可 以 表 示 为)1( )() */*23363 2/423n rnrkrnkxxxxg 由 于 要 使 最 后 的 和 等 于 n， 所 以 g(x)展 开 式 中 的 系 数 ， 就 是 问n题 的 解 。 对 于 这 类 母 函 数 ， 无 法 直 接 用 通 项 公 式 计 算 其 展 开 式 的 系 数 ，但 是 可 以 通 过 逐 次 进 行 的 多 项 式 的 乘 法 求 解 展 开 式 。 这 在 程 序 实 现 中 相当 于 一 个 线 性 表 的 归 并 算 法 ， 而 计 算 过 程 中 也 不 必 求 出 方 程 实 际

15、的 解 ，速 度 较 上 一 种 方 法 快 得 多 。 （ 程 序 和 运 行 效 率 的 比 较 ， 请 见 附 录 ）因 数 分 解 ： 将 一 个 正 整 数 n， 分 解 为 除 1 和 它 本 身 的 因 数 的 乘 积的 形 式 ， 不 考 虑 因 数 的 先 后 顺 序 ， 求 所 有 可 能 的 分 解 方 案 的 总 数 。将 一 个 正 整 数 分 成 若 干 个 正 整 数 ， 这 种 表 述 是 熟 悉 的 。 事 实 上 ， 这和 整 数 拆 分 中 的 表 述 是 相 似 的 。 虽 然 两 个 问 题 之 间 的 区 别 是 显 然 的 ： 一个 是 拆 成 乘

16、 积 的 形 式 ； 一 个 是 拆 成 和 的 形 式 。 但 是 两 个 问 题 都 是 计 算 一个 整 数 分 成 若 干 个 整 数 的 方 案 数 目 。于 是 ， 在 注 意 到 了 两 个 问 题 表 面 上 的 相 似 后 ， 确 定 “因 数 分 解 ”的 问 题 也 可 以 用 枚 举 法 来 解 决 。 不 妨 着 手 模 仿 整 数 拆 分 的 解 题 模 型 ， 将 问 题 描 述 为 ： 求 满 足 等 式 )2(*321321 naaaan mm 1 利用母函数计算不定方程整数解的总数的一般方法，请参见参考书目 iii（组合数学及其在计算机科学中的应用）。作者：

17、张力 1999.12.5 类比思想在解题中的应用 第 4 页 共 13 页的 所 有 正 整 数 组 （ a1， a2， a3， a4， am） 的 总 数 。 可 以 发 现 ， 两 个问 题 的 描 述 是 非 常 相 似 的 ， 只 是 把 加 号 换 成 了 乘 号 。 可 以 直 接 做 这 样 的变 换 而 不 改 动 其 它 内 容 的 关 键 在 于 ： 加 法 和 乘 法 都 满 足 交 换 律 和 结 合 律 。它 们 是 两 种 非 常 相 似 的 运 算 。 由 以 上 的 描 述 出 发 ， 模 仿 “整 数 拆 分 ”的 D(k,n)， 同 样 可 以 定 义 F(

18、k,n)为 将 n 分 解 成 一 组 不 小 于 k 的 正 整 数的 积 的 解 的 数 目 ，则 容 易 推 导 出 ; 1)/,(,|niik且而 F(2,n)-1 就 是 问 题 的 解 。由 于 采 用 的 是 枚 举 法 ， 在 n 的 因 子 很 多 时 ， 程 序 的 速 度 是 非 常 慢的 。 (对 应 程 序 名 P1.PAS)以 上 的 解 题 模 型 和 “整 数 拆 分 ”的 方 法 是 出 奇 的 类 似 的 。 然 而 ，机 械 的 模 仿 所 能 做 到 的 也 只 有 这 些 了 。 它 无 法 解 释 两 个 问 题 为 什 么 如 此类 似 。然 而

19、， 有 一 点 已 经 被 提 了 出 来 ： 两 者 之 所 以 是 相 似 的 ， 关 键 在 于 加法 和 乘 法 是 相 似 的 。 那 么 加 法 和 乘 法 之 间 ， 究 竟 是 怎 样 的 关 系 呢 ？为 了 回 答 这 个 问 题 ， 要 引 入 同 构 的 定 义 ：设 有 两 个 集 合 A， B， “ ”和 “ ”为 分 别 定 义 在 两 个 集 合 上 的（ 二 元 ） 运 算 。 那 么 称 A 和 运 算 “ ”构 成 一 个 代 数 系 统 A， ，B 和 运 算 “ ”构 成 代 数 系 统 B， 。如 果 存 在 一 个 一 一 对 应 的 映 射 ，

20、使 得 对 于 所 有 的BAxf:)(x A， y A， 都 有 ， 则 称 代 数 系 统 A， )(yyxf和 B， 是 同 构 的 。如 果 两 个 代 数 系 统 是 同 构 的 ， 那 么 显 然 其 中 一 个 系 统 中 的 问 题 总 可以 转 化 为 另 一 个 系 统 中 的 问 题 。现 在 借 助 简 单 的 中 学 知 识 ， 就 可 以 知 道 R， + 与 R+， * 是同 构 的 ：设 ， 则 有 恒 有 成 立 。)0()ln(xxf )()*(bfabf对 数 函 数 ln(x)就 是 把 乘 法 转 化 为 加 法 的 工 具 。有 了 这 些 作 为

21、基 础 ， 我 们 就 可 以 很 有 信 心 的 利 用 母 函 数 解 决 因 数 分解 问 题 。首 先 假 设 整 数 n 有 除 1 和 n 以 外 因 数 共 m 个 ， 为p1、 p2、 p3pm， 而 设 每 个 因 数 pi 在 分 解 的 式 子 中 出 现 次 数 分 别 为xi， 那 么 问 题 可 以 描 述 成 ： 求 方 程mxxx 321的 非 负 整 数 解 的 数 目 。 接 着 ， 利 用 ln(x)把 乘 法 转 化 为 加 法 ， 对 等 式 两边 取 对 数 ， 就 得 到 对 应 的 线 性 方 程；pppmlnlln321 欲 求 它 的 非 负

22、 整 数 解 的 个 数 ， 利 用 加 法 原 理 和 乘 法 原 理 构 造 母 函 数 （ 推导 过 程 参 见 “整 数 拆 分 ”的 相 应 段 落 ） ，作者：张力 1999.12.5 类比思想在解题中的应用 第 5 页 共 13 页)1( )() *lnl/ln3ln2ln *ln/lln3ln2ln n322 1111 mmmm kkkk pppp pppp xxxxxxg 则 g(x)展 开 式 的 项 的 系 数 就 是 问 题 的 解 。 与 整 数 拆 分 的 求 解 方法 类 似 的 ， 利 用 线 性 表 的 归 并 算 法 ， 就 可 以 求 出 解 来 。 (对

23、 应 程 序名 P2.PAS)与 递 归 枚 举 算 法 相 比 ， 算 法 的 效 率 同 样 也 大 大 的 提 高 了 。 （ 程 序 和 运行 效 率 的 比 较 ， 请 见 附 录 ）如 果 仅 仅 凭 借 表 面 上 观 察 到 的 相 似 性 ， 而 不 清 楚 乘 法 和 加 法 代 数 系 统之 间 存 在 着 同 构 的 关 系 ， 是 不 容 易 得 出 利 用 母 函 数 的 解 题 模 型 的 。这 个 例 子 中 最 有 启 发 性 的 ， 莫 过 于 同 构 概 念 的 引 入 。 为 了 说 明 两 个 同构 的 代 数 系 统 之 间 的 关 系 ， 借 助

24、了 一 个 一 一 映 射 ， 这 个 映BAxf:)(射 使 两 个 系 统 的 不 同 运 算 之 间 产 生 了 一 种 对 应 关 系 ：；)(yfxfByxA集 合 中 的对 应 于集 合 中 的这 样 A 集 合 中 关 于 运 算 的 每 一 个 问 题 ， 都 与 B 集 合 中 关 于运 算 的 一 个 问 题 相 对 应 。 于 是 可 以 把 A， 中 的 问 题 转 化 为 B， 中 的 问 题 来 解 决 。实 现 这 种 转 化 正 是 利 用 类 比 思 想 解 题 的 目 的 ， 而 寻 找 这 种 一 一 对 应 的关 系 则 是 类 比 的 实 质 。 只

25、要 发 现 了 这 种 一 一 对 应 的 关 系 ， 就 能 够 应 用 解决 已 知 问 题 的 方 法 去 解 决 新 问 题 。同 构 只 是 代 数 系 统 中 的 概 念 ， 然 而 对 应 的 关 系 可 以 应 用 到 其 它 问 题 中 ，因 此 用 类 比 解 题 是 不 局 限 于 代 数 系 统 之 内 的 。 下 面 的 例 子 就 属 于 另 一 个不 同 方 面 。 目 的 是 在 进 一 步 说 明 类 比 的 表 象 和 它 的 本 质 之 间 的 关 系 。从 表 面 的 相 似 到 内 在 的 对 应类 比 的 本 质 是 揭 示 已 知 问 题 与 未

26、知 问 题 之 间 一 一 对 应 的 关 系 。 但 是 ，正 如 引 言 中 说 的 ， 本 质 往 往 不 容 易 被 发 现 ， 而 表 面 的 相 似 性 却 首 先 被 观察 到 。 所 以 ， 不 应 该 忽 视 表 面 的 相 似 性 ； 相 反 ， 应 该 沿 着 相 似 性 所 指 出的 方 向 开 始 分 析 ， 尝 试 发 现 问 题 之 间 的 本 质 联 系 。在 分 析 下 面 这 个 例 子 的 过 程 中 ， 将 着 重 说 明 这 一 点 。【 平 面 分 割 空 间 问 题 】一 个 平 面 把 空 间 分 成 独 立 的 两 个 部 分 ， 两 个 平

27、面 把 空 间 分 成 4个 部 分 。 n 个 平 面 ， 最 多 能 把 整 个 空 间 分 割 成 多 少 个 部 分 。 1立 体 空 间 的 情 况 是 陌 生 的 ， 而 且 不 容 易 描 述 。 虽 然 同 样 是 “分割 ”问 题 。 但 是 正 常 情 况 下 ， 不 会 把 它 和 “整 数 拆 分 ”联 系 起 来 ， 因为 两 者 处 理 的 对 象 （ 整 数 和 空 间 平 面 ） 是 完 全 不 同 的 。 那 么 ， 究 竟 如 何把 这 个 问 题 和 已 知 的 知 识 联 系 起 来 呢 ？ 这 个 时 候 ， 即 使 是 表 面 的 相 似 性 ，1

28、问题来自参考书目 i（数学与猜想）第三章。作者：张力 1999.12.5 类比思想在解题中的应用 第 6 页 共 13 页也 能 够 为 解 题 提 供 一 条 线 索 。类 比 的 目 的 是 将 未 知 的 、 复 杂 的 东 西 化 为 已 知 的 、 简 单 的 东 西 。 空间 上 的 问 题 是 复 杂 的 ， 而 平 面 上 的 问 题 则 是 简 单 的 。 而 且 空 间 和 平 面 的关 系 ， 与 平 面 和 直 线 的 关 系 ， 是 相 似 的 。 平 面 把 空 间 分 割 成 两 个 部 分 ，直 线 也 把 平 面 分 割 成 两 个 部 分 。于 是 得 到

29、了 另 一 个 与 例 题 相 类 似 的 问 题 ： n 条 直 线 ， 最 多 能 把 整个 平 面 分 割 成 多 少 个 部 分 。 1这 道 题 容 易 解 决 得 多 。 它 的 解 决 方 法 是 利 用 数 学 归 纳 法 （ 如 图 ） ：一 条 直 线 ， 把 平 面 分割 为 两 个 部 分 （ A 和B） ；增 加 一 条 直 线 ， 它 与第 一 条 直 线 相 交 ， 被 分为 两 段 射 线 ， 每 一 段 射线 又 把 所 在 的 区 域 （ 例如 A） 分 成 两 部 分（ A1 和 A2） ； 因 此 增加 了 2 个 部 分 ； 共 有2+2=4 个 部

30、分 。再 增 加 一 条 直 线 ，它 与 前 两 条 直 线 相 交 ，被 分 为 三 段 ， 每 一 段 又把 所 在 区 域 （ 例 如 B1） 分 成 两 部 分 (B11 和 B12)； 总 共 增 加 了 3 个部 分 ； 共 有 4+3=7 个 部 分 ；由 此 类 推 ， 设 前 k-1 条 直 线 共 把 平 面 分 为 Ak-1 个 部 分 。 加 入 第k 条 直 线 ， 与 前 k-1 条 直 线 相 交 ， 被 分 为 k 段 ， 每 一 段 把 所 在 区 域 分为 两 部 分 ； 总 共 增 加 了 k 部 分 ； 总 共 有 Ak-1+k 个 部 分 。于 是

31、得 到 了 递 推 关 系 A1=2； Ak=Ak-1+k；由 此 不 难 计 算 出 通 项 公 式 ：；2)(1Ak于 是 直 线 分 割 平 面 的 问 题 就 解 决 了 。解 决 这 一 问 题 对 “平 面 分 割 空 间 问 题 ”有 何 帮 助 ？ 既 然 空 间 和 平面 ， 与 平 面 和 直 线 的 关 系 相 似 ， 那 么 直 接 把 平 面 换 成 空 面 ， 把 直 线 换 成平 面 ， 就 可 以 直 接 用 以 上 的 过 程 来 证 明 未 知 的 问 题 了 吗 ？ 显 然 是 不 可 以的 。 这 仅 仅 是 根 据 主 观 的 相 似 得 出 的 机

32、械 的 模 仿 ， 是 错 误 的 。但 是 如 果 仔 细 分 析 一 下 错 误 的 原 因 ， 将 会 发 现 问 题 的 关 键 ： 线 线 相交 得 到 的 是 交 点 ， 面 面 相 交 得 到 的 是 直 线 ， k 个 点 把 直 线 分 成 k+1个 部 分 ， 而 k 条 直 线 则 不 是 简 单 的 把 平 面 分 成 k+1 个 部 分 。事 实 上 ， k 条 直 线 最 多 把 平 面 分 成 Ak 个 部 分 ！因 此 两 个 问 题 真 正 的 相 似 之 处 在 于 ， 一 个 为 了 计 算 直 线 把 平 面 分 割成 几 部 分 ， 先 计 算 这 条

33、 直 线 被 点 （ 线 线 交 点 ） 分 割 成 几 部 分 ， 把 二 维 的问 题 化 为 一 维 的 问 题 ； 另 一 个 要 计 算 平 面 把 空 间 分 割 成 几 部 分 ， 先 计 算1 这实际上是本届（第五届）分区联赛初赛的一道填空题。作者：张力 1999.12.5 类比思想在解题中的应用 第 7 页 共 13 页这 个 平 面 被 线 （ 面 面 交 线 ） 分 割 成 几 部 分 ， 把 三 维 的 问 题 化 为 二 维 的 问题 。 而 二 维 的 问 题 是 已 经 被 解 决 了 的 ； 于 是 反 过 来 ， 三 维 的 问 题 也 解 决了 。同 样 是

34、 利 用 数 学 归 纳 法 ：一 个 平 面 把 空 间 分 割 成 两 部 分 ；设 前 k-1 个 平 面 共 把 空 间 分 割 成 Bk-1 个 部 分 。 加 入 第 k 个 平 面后 ， 与 前 k-1 个 平 面 相 交 ， 共 有 k-1 条 交 线 。 k-1 条 交 线 把 这 个 平 面 被分 为 几 个 块 呢 ？ 这 实 际 上 就 是 刚 刚 解 决 过 的 问 题 ： k-1 条 直 线 ， 把 平面 分 割 成 部 分 。 这 块 平 面 ， 分 别 把 所 在 原 来 空 间 一2)1(kkA2)(分 为 二 ， 总 共 增 加 了 个 部 分 ； 于 是

35、， k 个 平 面 总 共 把 空 间 分 割)(k成 个 部 分 。)(1Bk于 是 得 到 了 递 推 关 系 B1=2； ；2)1(1k利 用 这 一 递 推 关 系 来 编 写 程 序 ， 不 难 求 出 Bn， 而 且 即 便 对 很 大 的n， 程 序 的 运 算 速 度 仍 然 是 很 快 的 。（ 当 然 ， 也 可 以 计 算 出 Bn 的 通 项 公 式 ， 这 实 际 上 是 一 个 二 阶 等 差 数列 的 和 ：）6)2(12)(1nBn在 这 个 例 子 中 的 一 一 对 应 的 关 系 ， 虽 然 不 如 同 构 的 概 念 中 那 么 容 易地 用 式 子 表

36、 达 出 来 ， 但 还 是 很 清 楚 的 ： n 个 平 面 中 的 任 意 一 个 平 面 ，截 其 它 n-1 个 平 面 得 到 的 所 有 n-1 条 交 线 ， 把 这 个 平 面 分 成 An-1 部 分 ，而 这 正 对 应 于 是 第 n 个 平 面 分 割 空 间 得 到 的 增 量 。 或 者 说 ，；1AB在 这 个 例 子 中 ， 最 初 找 不 到 什 么 熟 悉 的 类 似 问 题 ， 但 是 从 简 单 和 便于 分 析 的 角 度 着 手 ， 构 造 了 一 个 平 面 上 的 与 之 相 似 的 问 题 。 此 时 ， 相 似性 可 以 说 是 “立 体

37、”和 “平 面 ”的 类 比 ， 这 是 非 常 模 糊 的 。 因 为 几 乎 没有 确 切 的 理 由 ， 能 表 明 这 样 的 类 比 可 以 使 问 题 相 互 转 化 ； 这 种 相 似 性 主要 依 据 的 是 以 往 解 决 问 题 的 经 验 （ 化 空 间 问 题 为 平 面 问 题 ， 在 中 学 的 立体 几 何 中 是 经 常 用 到 的 手 法 ） ， 另 一 个 原 因 则 是 为 了 简 化 问 题 。接 着 ， 在 解 决 平 面 的 问 题 之 后 ， 面 对 的 困 难 是 ： 如 何 把 解 决 平 面 上问 题 的 经 验 应 用 到 空 间 的 问

38、题 中 。 如 果 仅 仅 根 据 表 面 的 相 似 性 ， 机 械 的模 仿 将 导 出 一 种 错 误 的 方 法 。 然 而 这 种 尝 试 却 不 是 没 有 价 值 的 。 通 过 比较 正 确 的 论 证 和 错 误 的 论 证 之 间 的 差 别 ， 原 来 的 简 单 而 模 糊 的 类 比 得 到了 完 善 和 澄 清 ： 把 “三 维 降 低 到 二 维 的 过 程 ”和 “二 维 降 低 到 一 维 的过 程 ”做 类 比 。 由 此 ， 两 个 问 题 之 间 的 联 系 变 得 很 清 楚 ， 于 是 得 出 了 完整 的 推 算 过 程 。事 实 上 ， 这 道

39、例 题 的 解 决 ， 和 近 年 来 不 少 三 维 的 计 数 问 题 的 思 考 方法 是 非 常 类 似 的 ： 先 考 虑 把 二 维 化 为 一 维 的 情 况 ； 再 用 相 同 的 方 法 （ 类比 ） ， 把 三 维 的 问 题 化 为 二 维 的 问 题 来 解 决 。 这 种 策 略 被 形 象 的 称 为“降 维 ”的 策 略 。 11 CTSC99 的论文隐蔽化、多维化、开放化（石润婷）中做了十分详细的分析。作者：张力 1999.12.5 类比思想在解题中的应用 第 8 页 共 13 页以 上 “因 数 分 解 ”和 “平 面 分 割 空 间 问 题 ”的 例 子 ，

40、 都 是 借 助 类比 解 决 的 。 而 且 在 最 初 ， 都 把 探 究 问 题 之 间 的 某 种 相 似 性 作 为 分 析 问 题的 线 索 ， 这 样 做 的 目 的 是 希 望 能 够 把 未 知 的 问 题 和 熟 悉 的 知 识 联 系 起 来 ，以 提 供 我 们 解 决 问 题 的 可 能 性 。 然 而 正 如 在 这 两 个 例 子 中 见 到 的 ， 这 种从 问 题 的 表 面 上 得 出 的 相 似 性 ， 往 往 不 是 本 质 的 ， 并 且 可 能 是 有 缺 陷 的 。所 以 ， 这 种 表 面 现 象 上 的 类 比 只 是 为 解 题 指 出 了

41、可 行 的 方 向 。 为 了 最 终能 够 把 未 知 的 问 题 转 化 为 已 知 的 问 题 ， 需 要 揭 示 两 个 问 题 之 间 更 深 层 的类 比 ， 即 建 立 从 一 个 问 题 到 另 一 个 问 题 的 对 应 关 系 。在 利 用 类 比 解 题 的 整 个 过 程 中 ， 表 面 的 相 似 和 内 在 的 对 应 是 紧 密 的联 系 在 一 起 的 。 相 似 性 在 浅 层 ， 对 应 关 系 在 深 层 。 对 应 关 系 是 解 决 问 题的 关 键 ， 而 发 现 对 应 关 系 的 途 径 是 从 表 面 的 相 似 性 出 发 的 。总 结信 息

42、 学 竞 赛 涉 及 到 大 量 的 不 同 算 法 ， 对 于 每 一 种 算 法 的 特 点 和 应 用技 巧 ， 老 师 和 前 辈 们 都 已 经 进 行 了 大 量 的 分 析 和 研 究 ， 并 且 总 结 出 了 许多 完 整 的 理 论 。 那 么 ， 在 分 析 问 题 和 解 决 问 题 的 思 路 方 面 ， 是 否 也 有 一定 的 规 律 和 方 法 呢 ？ 出 于 这 样 的 考 虑 ， 本 文 没 有 就 某 种 具 体 的 算 法 进 行分 析 ， 而 是 希 望 能 够 在 分 析 问 题 的 思 想 方 法 上 有 所 探 讨 。 在 这 方 面 ，许 多

43、数 学 上 的 技 巧 （ 例 如 构 造 、 化 归 、 归 纳 法 ） 都 是 值 得 借 鉴 的 ， 本 文所 主 要 分 析 的 类 比 思 想 ， 也 是 其 中 之 一 。本 文 的 第 一 部 分 ， 通 过 利 用 类 比 解 题 的 例 子 ， 首 先 指 出 仅 仅 表 面 的相 似 性 并 不 能 真 正 体 现 两 个 问 题 之 间 的 实 质 性 联 系 ； 然 后 ， 从 代 数 系 统的 同 构 的 定 义 中 提 取 出 类 比 的 本 质 ， 即 两 个 系 统 的 各 个 部 分 之 间 一 一 对应 的 关 系 。 这 种 一 一 对 应 的 关 系 ，

44、 使 一 个 系 统 中 的 一 个 操 作 （ 运 算 ） 对应 于 另 一 个 系 统 中 的 另 一 个 操 作 （ 运 算 ） 。 由 此 ， 可 以 把 关 于 一 个 陌 生的 系 统 中 的 新 问 题 ， 转 化 为 熟 悉 的 问 题 来 解 决 。一 一 对 应 的 关 系 是 类 比 本 质 的 一 面 ， 而 主 观 上 的 相 似 性 则 是 类 比 的表 象 。 同 时 ， 正 如 在 本 文 的 第 二 部 分 所 阐 述 的 ， 这 两 者 不 是 完 全 对 立 ，而 是 互 相 联 系 的 。 没 有 主 观 的 相 似 性 的 引 导 ， 类 比 的 本

45、质 很 难 被 发 现 。整 个 类 比 的 过 程 ， 从 含 糊 （ 主 观 上 的 ） 的 相 似 到 清 晰 的 （ 概 念 上 的 ） 对应 关 系 ， 把 已 知 的 问 题 与 未 知 问 题 逐 渐 联 系 起 来 ， 最 后 使 两 个 问 题 之 间能 够 互 相 转 化 ， 从 而 把 已 知 问 题 的 解 题 模 型 应 用 到 未 知 问 题 的 解 决 中 去 。利 用 类 比 解 题 并 不 是 某 种 固 定 的 算 法 ， 而 是 分 析 问 题 时 的 一 种 思 考方 法 ， 因 此 没 有 什 么 定 式 ， 但 也 有 规 律 可 循 。 类 比 的

46、 目 的 ， 是 希 望 化 复杂 的 问 题 为 简 单 的 问 题 ， 化 陌 生 的 问 题 为 熟 悉 的 问 题 。 为 了 实 现 这 一 转化 ， 最 初 ， 可 能 是 按 照 某 种 相 似 性 ， 把 两 个 不 同 的 问 题 联 系 起 来 ， 并 尝试 着 模 仿 解 决 已 知 问 题 的 方 法 ， 来 解 决 新 问 题 。 在 这 一 模 仿 的 过 程 中 ，如 果 能 够 明 晰 两 个 问 题 之 间 存 在 的 对 应 关 系 ， 就 能 够 实 现 两 个 问 题 之 间的 转 化 ； 否 则 ， 如 果 仅 仅 是 机 械 的 模 仿 ， 往 往

47、是 难 以 解 决 问 题 的 。类 比 ， 是 一 种 把 已 知 的 种 种 信 息 和 知 识 ， 与 陌 生 的 问 题 联 系 起 来 的作者：张力 1999.12.5 类比思想在解题中的应用 第 9 页 共 13 页思 路 。 这 既 依 靠 选 手 解 题 时 发 散 思 维 的 能 力 ， 又 取 决 于 选 手 在 平 时 的 学习 和 训 练 中 所 接 触 知 识 的 深 度 和 广 度 ； 而 类 比 解 题 的 基 础 也 要 求 选 手 拥有 与 未 知 问 题 相 类 似 的 知 识 ， 这 就 需 要 选 手 在 平 时 的 学 习 和 训 练 中 既 有扎 实

48、 的 基 本 功 ， 又 有 广 泛 的 知 识 面 。因 此 ， 类 比 这 种 解 题 思 路 ， 对 选 手 的 要 求 正 是 “能 力 ”+“基 本功 ”。参 考 书 目i. 数 学 与 猜 想 ( Mathematics and plausible reasoning )，GPolya 著 ， 李 心 灿 、 王 日 爽 、 李 志 尧 译 ， 科 学 出 版 社 ，1984。ii. 算 法 设 计 ， 蒋 新 儿 著 ， 全 国 青 少 年 计 算 机 课 外 活 动 辅 导 员 培 训教 材 编 委 会 ， 1996。iii. 组 合 数 学 及 其 在 计 算 机 科 学 中 的 应 用 ， 庄 心 谷 ， 西 安 电 子 科技 大 学 出 版 社 ， 1989。附 录“整 数 拆 分 ”问 题 利 用 不 同 算 法 的 程 序 的 效 率 比 较 ：N 问 题 的 解 递 归 枚 举 算法(divide1.pas)的 耗 时 (秒 )利 用 母 函 数 的 多 项式 乘 法 算 法(divide2.pas)的 耗 时(秒 )5 7 0.00 0.0010 42 0.00 0.0050 204226 0.05