具体数学--2007.ppt

具体数学 Concrete Mathematics 主 讲: 顾 乃 杰 教授 单 位: 计算机科学技术系 时 间: 2007 (秋) 中国科学技术大学-计算机科学技术系 Date1 Department of Computer Science & Technology 教 材 课 本 《Concrete Mathematics 》 Second Edition 《具体数学》 第2版 作者： R. L. Graham D. E. Knuth O. Patashnik 机械工业出版社, 2002.8 Date2 Department of Computer Science & Technology 评 分 原 则 n平时：40 % 作业：20 % 学习报告：20 % n期未考试：60 % 书面考试，开卷 Date3 Department of Computer Science & Technology 第一章 递归问题 在这一章中，通过研究三个例子来得到对递归问题的感 性认识它们有两个共同的特点： n它们都是数学家们一直反复研究的问题； n它们的解都使用了递归的概念，即将问题求解转化为相同 问题的更小实例的求解。

Date4 Department of Computer Science & Technology 1.1 汉诺塔 首先让我们看一个称为“汉诺塔”的智力问题该问 题是法国数学家Edouard Lucas在1883年提出的给定一个 由八个大小不同的圆盘组成的塔，最初圆盘按尺寸递减的 次序自底而上地堆放到三根杆中的一根上： Date5 Department of Computer Science & Technology 汉诺塔--目标和求解 n目标是把整个塔移到另一根杆上，其过程要求一次只能移 动一个圆盘，而且在移动过程中大的盘子不能移到比它小 的盘子上面 n很难一下子看出这个问题有解，但是稍加思索之后（或者 是以前曾经见过这个问题）可以确信它有一个解现在的 问题是：怎样做才最好？也就是说，为了完成这个任务， 多少次移动是必要而且充分的？ n处理这类问题的最好方法是把它一般化一点婆罗门塔有 64个圆盘，而汉诺塔只有8个；我们可以考虑任意 n 个圆盘 的情况 Date6 Department of Computer Science & Technology 汉诺塔—小规模情况 n一般化的一个好处是可以把问题的规模大大降低，而实际 上先注意小规模的情况是有利于问题求解 。

n很容易看出如何转移一个仅包含一个或者两个圆盘的塔， 而且用少量实验就能说明如何转移包含三个圆盘的塔 n设Tn 为在 Lucas规则下将 n 个盘子从一根杆转移到另一根 杆的最小移动次数 n很明显， T0=0，T1=1，T2 = 3 Date7 Department of Computer Science & Technology 汉诺塔— n个盘子情形 n转移n个盘子的一般思路： n先把 n－1个小的盘子转移到一根不同的杆上(需要Tn－1 次移动)， n然后移动最大的盘(要求一次移动)，最后再把n－1个盘 转移到最大的盘上(也需要Tn－1次移动)因此，最多移 动 2Tn－1+1 次就能转移 n 个盘（其中n 0） n n上述公式没有使用‘＝’，而使用了‘≤’,因为上述构造方法 仅仅能证明 2Tn－1 ＋1 次移动是充分的，并没有说明 2 Tn－1＋1次移动是必要的 Date8 Department of Computer Science & Technology 汉诺塔— n个盘子情形(续) n转移n个盘子的一般思路(续)： n有更好的方法吗？实际上没有 n必须在某个时刻移动最大的盘，当移动最大盘时，n－1 个最小的盘一定在一根杆上，而且至少用了Tn－1次移动 来把这些盘子放到那根杆上。

n如果不太注意的话，移动最大盘的次数可能会大于一次 但是在最后一次移动最大盘之后，还必须把n－1个最 小盘(一定还在一根杆上)转移回最大盘上，这同样需要 Tn－1 次移动 n Date9 Department of Computer Science & Technology 汉诺塔—递归方程 n将前面两个不等式和 n=0 的平凡情况结合在一起，可得： (1.1) n类似于式(1.1)的等式称为一个递归方程它给出了一个边 界值以及根据前面的值来表示一般值的一个方程 n严格来说，递归方程需要有边界值才算是完整的，有时也 把单独一个方程称为一个递归方程 Date10 Department of Computer Science & Technology 汉诺塔—递归方程求解 n可以通过递归方程来计算任何 n 值下的 Tn但是当 n 比较 大的时候，没有人真正愿意用递归方程来计算，因为耗时 太长 n递归方程仅仅给出了间接的“局部”信息，而递归方程的解 会让我们满意得多也就是说，我们希望有 Tn 的一个简洁 良好的“闭形式”，即使是在 n 很大的情况下，也能迅速地 计算出它的值通过闭形式，能够了解 Tn 的真正意义。

n如何求解递归方程呢？一种方法是猜测正确的解，然后证 明猜想是正确的最有希望猜测出解的方法就是观察数目 小的情况 Date11 Department of Computer Science & Technology 汉诺塔—递归方程求解(续) n因此我们接连计算出T3 = 2·3 + 1 = 7；T4 = 2·7 + 1 = 15；T5 = 2·15 + 1 = 31；T6 = 2·31 + 1 = 63啊 哈！解好像应该是这样的： (1.2) n至少这个公式对于n≤6都是成立的 Date12 Department of Computer Science & Technology 汉诺塔—递归方程求解(续) n数学归纳法是用来证明某个命题对于所有大于等 于 的整数n都成立的一般方法首先我们证明 了当n为最小值 时命题成立，这称为归纳基础 然后我们假设对于包含在 和n–1之间的所有 值，命题均成立，在此假设上证明命题对于满足 n 的整数n成立这种方法称为归纳法这种证 明方法仅用有限的步骤就能产生无限多结果 Date13 Department of Computer Science & Technology 汉诺塔—递归方程求解(续) n递归方程是数学归纳法的理想应用。

例如在我们讨论的情 况中，很容易从式（1.1）得到式（1.2）：因为 ，所以基础是平凡的若假设用n – 1来代 替n时式（1.2）成立，且对于n＞0的情况归纳如下： 因此对于n，式（1.2）同样成立好！我们成功得到了 Date14 Department of Computer Science & Technology 汉诺塔—递归方程求解(续) n在各种应用中出现的许多问题中，汉诺塔递归问题具 有代表性在寻找像 这个有趣结果的闭形式的表达 式的过程中，我们经历了三个阶段： 1. 观察数目小的情况这样能让我们深入了解问题 ，并在第二和第三阶段帮助我们 2.寻找并证明重要变量的数学表达式对于汉诺塔， 就是递归方程（1.1），通过它，我们可以根据给定 的方式来计算对于任何n值的 3.寻找并证明我们的数学表达式的闭形式对于汉诺 塔，就是递归方程的解（1.2） Date15 Department of Computer Science & Technology 汉诺塔—递归方程求解(续) n我们对于汉诺塔的分析得到了正确的答案，但是它要 求“归纳跳跃”，我们依赖于对于答案的侥幸猜中 本书的主要目的之一就是说明在不依赖对答案敏锐的 洞察力时，如何解决递归问题。

例如，我们将看到递 归式（1.1）能通过在方程两边都加上1来进行简化： 如果令 ，我们得到 (1.3) 发现这个递归方程的解是 ，因此 Date16 Department of Computer Science & Technology 1.2 平面中的直线 n我们的第二个例题有几何味道：平面中的n条直线确定的最 大区域数Ln是多少？瑞士数学家Jacob Steiner[338]在 1826年首先解决了这个问题 n我们还是先来观察小的情况，记住从最小的情况开始没 有直线的平面具有一个区域；有一条直线的平面具有两个 区域；而有两条直线的平面具有四个区域（每条直线都在 两个方向上无限延伸）： Date17 Department of Computer Science & Technology 平面中的直线-目标和求解 n我们当然可以认为 = 2n，也就是每次添加一条新的直线只是让 区域数目加倍但很不幸，这是错误的如果第n条直线把每个 原来的区域切割成两个，那么整个区域数目会加倍；因为每个原 来的区域都是凸的，因此第n条直线能把原来的区域切割成两部 分。

一条直线至多能把一个凸区域切割为两个新区域，新区域 也是凸的但是当我们添加第三条直线的时候，我们马上发现 ，无论如何放置前两条直线，第三条直线都至多能切割到三个原 来的区域 Date18 Department of Computer Science & Technology 平面中的直线-目标和求解 n经过思考，我们适当地进行一般化当且仅当第n条直线（ n 0）切割了k个原来的区域时，增加的区域数目才为k 而当且仅当第n条直线在k – 1个不同的位置与原先的直线 相交，它才能切割k个原来的区域两条直线最多相交到一 点因此新的直线最多与n – 1 条原来的直线相交于n – 1个不同点，而且一定有k≤n，这样我们就得到了上界 Date19 Department of Computer Science & Technology 平面中的直线-目标和求解 n此外，用归纳法很容易取到这个公式中的等式我们 只要使第n条直线不平行于任何一条其他的直线（因此 它和每条直线都相交），而且让它不经过任何已经存 在的交点（因此它和其他任何直线都相交于不同的位 置）这种情况下的递归方程为： (1.4) n已知值 ， 和 都完全符合这个递归方程，因此我 们接受这个方程。

Date20 Department of Computer Science & Technology 平面中的直线-递归方程求解 n现在我们需要闭形式的解我们可以再做一次猜测，但是 我们并不熟悉1，2，4，7，11，16，…中的规律，所以让 我们改变一下策略我们通常把递归式“展开”或者“摊 开”到底来了解它，如下所示： n换句话说， 是前n个正整数的和 加上1 Date21 Department of Computer Science & Technology 平面中的直线-递归方程求解 n量Sn经常会出现，所以值得把它的小值做成一个表这样 下一次我们遇到这些数的时候，就能更容易地分辨出来 n这些值也被称为三角形数，因为Sn是n行三角形阵中圆孔的 个数譬如普通的四行阵 有 = 10个圆孔 Date22 Department of Computer Science & Technology 平面中的直线-递归方程求解 n为了计算Sn，我们可以利用据说是Gauss在1786年提出的技 巧，也就是在他九岁的时候[88]（也可以参考Euler[114， 第1部分，§415]）： n我们仅仅需要把 和自身颠倒相加，这样右边n列的每一列 之和的值都为n＋1。

化简得到： (1.5) Date23 Department of Computer Science & Technology 平面中的直线-递归方程求解 n这样就得到了结果： (1.6) n根据经验，我们可能满足于这个推导，并且认为这就是证 明，尽管在进行展开和考虑的时候我们不够严格。