具体数学--2007概要.ppt

教 材 课 本 《Concrete Mathematics 》 Second Edition 《具体数学》 第2版 作者： R. L. Graham D. E. Knuth O. Patashnik 机械工业出版社, 2002.8 评 分 原 则 平时：40 % 作业：20 % 学习报告：20 % 期未考试：60 % 书面考试，开卷。 第一章 递归问题 在这一章中，通过研究三个例子来得到对递归问题的感性认识。它们有两个共同的特点： 它们都是数学家们一直反复研究的问题； 它们的解都使用了递归的概念，即将问题求解转化为相同问题的更小实例的求解。 1.1 汉诺塔 首先让我们看一个称为“汉诺塔”的智力问题。该问题是法国数学家Edouard Lucas在1883年提出的。给定一个由八个大小不同的圆盘组成的塔，最初圆盘按尺寸递减的次序自底而上地堆放到三根杆中的一根上： 汉诺塔--目标和求解 目标是把整个塔移到另一根杆上，其过程要求一次只能移动一个圆盘，而且在移动过程中大的盘子不能移到比它小的盘子上面。 很难一下子看出这个问题有解，但是稍加思索之后（或者是以前曾经见过这个问题）可以确信它有一个解。现在的问题是：怎样做才最好？也就是说，为了完成这个任务，多少次移动是必要而且充分的？ 处理这类问题的最好方法是把它一般化一点。婆罗门塔有64个圆盘，而汉诺塔只有8个；我们可以考虑任意 n 个圆盘的情况。 汉诺塔—小规模情况 一般化的一个好处是可以把问题的规模大大降低，而实际上先注意小规模的情况是有利于问题求解 。 很容易看出如何转移一个仅包含一个或者两个圆盘的塔，而且用少量实验就能说明如何转移包含三个圆盘的塔。 设Tn 为在 Lucas规则下将 n 个盘子从一根杆转移到另一根杆的最小移动次数。 很明显， T0=0，T1=1，T2 = 3。 汉诺塔— n个盘子情形 转移n个盘子的一般思路： 先把 n－1个小的盘子转移到一根不同的杆上(需要Tn－1次移动)， 然后移动最大的盘(要求一次移动)，最后再把n－1个盘转移到最大的盘上(也需要Tn－1次移动)。因此，最多移动 2Tn－1+1 次就能转移 n 个盘（其中n 0）。 上述公式没有使用‘＝’，而使用了‘≤’,因为上述构造方法仅仅能证明 2Tn－1 ＋1 次移动是充分的，并没有说明 2 Tn－1＋1次移动是必要的。 汉诺塔— n个盘子情形(续) 转移n个盘子的一般思路(续)： 有更好的方法吗？实际上没有。 必须在某个时刻移动最大的盘，当移动最大盘时，n－1 个最小的盘一定在一根杆上，而且至少用了Tn－1次移动来把这些盘子放到那根杆上。 如果不太注意的话，移动最大盘的次数可能会大于一次。但是在最后一次移动最大盘之后，还必须把n－1个最小盘(一定还在一根杆上)转移回最大盘上，这同样需要 Tn－1 次移动。 汉诺塔—递归方程 将前面两个不等式和 n=0 的平凡情况结合在一起，可得： (1.1) 类似于式(1.1)的等式称为一个递归方程。它给出了一个边界值以及根据前面的值来表示一般值的一个方程。 严格来说，递归方程需要有边界值才算是完整的，有时也把单独一个方程称为一个递归方程。 汉诺塔—递归方程求解 可以通过递归方程来计算任何 n 值下的 Tn。但是当 n 比较大的时候，没有人真正愿意用递归方程来计算，因为耗时太长。 递归方程仅仅给出了间接的“局部”信息，而递归方程的解会让我们满意得多。也就是说，我们希望有 Tn 的一个简洁良好的“闭形式”，即使是在 n 很大的情况下，也能迅速地计算出它的值。通过闭形式，能够了解 Tn 的真正意义。 如何求解递归方程呢？一种方法是猜测正确的解，然后证明猜想是正确的。最有希望猜测出解的方法就是观察数目小的情况。 汉诺塔—递归方程求解(续) 因此我们接连计算出T3 = 2·3 + 1 = 7；T4 = 2·7 + 1 = 15；T5 = 2·15 + 1 = 31；T6 = 2·31 + 1 = 63。啊哈！解好像应该是这样的： (1.2)