首页 > 代码库 > 《具体数学》1.1递归(一)

《具体数学》1.1递归(一)

《具体数学》通过三个例子来讲递归,分别是:Hanoi Tower(汉诺塔)、Lines in the Plane(平行中的直线)、Josephus Circle(约瑟夫环问题)

这三个例子一直被数学家们反复研究;已知解法都使用递归,大问题化为小问题;都可以用计算机程序来求解;
我最近因为考试忙的其实也没看几页,就先把看的写出来吧;

1.1 汉诺塔

首先来看被称为“汉诺塔”(Hanoi Tower)的智力问题。该问题是法国数学家Edouard Lucas在1883年提出的。给定一个由八个大小不同的圆盘组成的塔,最初圆盘按尺寸递减的次序自底而上地堆放到三根杆中的一根上。类似的问题是婆罗门塔(64个盘子,一直挪到世界末日……,后面我们有相关的分析)

目标:把整个塔从一根杆移到另一根杆上。
规则:
(1)One time, one disk;
(2)No larger disks on smaller ones, Anytime.
直观上很难看出这个问题的解法,但是我们以前在C语言的递归部分已经遇到过,可以确信它有一个解.(结尾会给出c语言的代码片段)

书上写的解法其实已经很清楚了,目的是让我们求Tn是在Lucas规则下n个盘从一根杆移到另一根杆的最小移动次数,当n=1时显然T1=1,T2=3,这些都是小的问题,我们也可以通过小的问题去考虑大的,我们如何能转移一个大的塔?3个盘的实验表明要想获胜就是把顶上的2个移到中间,然后移第3个盘,再把另外的2个盘放上去,再扩展到n个盘一般移动的思路:首先把n-1个最小的盘转移到一个不同的杆(Tn-1次移动),然后移动最大的盘(一次移动),最后再把n-1个最小盘上的转移回最大的盘上(Tn-1次移动),所以,至多用2Tn-1+1次移动能转移n个盘(n>0)

Tn<=2Tn-1+1(n>0)

注意红色的部分,此公式用了‘<=‘而不是‘=‘,这本书真的是很严谨啊,因为我们的构造仅证明2Tn-1+1次移动是充分的,并未证明2Tn-1+1次移动是必要的。其实,没有很好的方法去证明它是必要的.在某个时刻我们一定要移动最大的盘,当我们移动最大盘时,n-1个最小的盘一定在一根杆上,且至少用Tn-1次移动把它们放到那里,我们假如不注意,则移动最大盘等等次数可能大于一次。但最后一次移动最大盘之后,我们一定要把n-1个最小盘转移回最大盘上,还要Tn-1次移动。因此Tn>=2Tn-1+1(n>0)

所以汉诺塔递归公式为:

T0=0

Tn=2Tn-1+1(n>0)

它给定一个边界值以及根据较早值表达一般值一个方程。我们有时把这个一般方程单独称为一个递归,但其实还是要一个边界值。

怎么去理解 递归呢,先去猜测一个正确的解,然后由这个解推出通解,找出规律,最后去证明规律的普遍性,数学归纳法是证明某个命题关于(对所有n>=n0)成立的一种一般方法,其实数学归纳法完美为递归作了准备。书上有一段是真的很重要的,在各种应用提出的许多问题中,汉诺塔的递归具有典型性,在找出像Tn那样表达式,我们经历三个阶段:

1:看看小的情形,这能使我们更深入的了解问题

2:求出和证明关心量的一个数学表达式,它使我们能就给定的量来计算任何n的Tn

3:求出和证明我们的数学表达式的一个闭形式

其实根据我们高中所学的知识,我们可以对Tn进行简化的:

T0+1=1;

Tn+1=2Tn-1+2,Un=2Un-1;

等比数列

汉诺塔C语言程序片段:#include <stdio.h>
int hanoiSolver(int peg1, int peg2, int peg3, int dCount)
{
   int mCount = 0;
   if (dCount > 1) {
       mCount += hanoiSolver(peg1, peg3, peg2, dCount - 1);
       printf("Move the top disk : peg %d -> peg %d\n", peg1, peg3);
       mCount += hanoiSolver(peg2, peg1, peg3, dCount - 1);
   } else {
       printf("Move the top disk : peg %d -> peg %d\n", peg1, peg3);
   }
   return ++mCount;
}
下一篇估计得有段时间去写了,天天考试,下一篇是打算写Lines in the Plane(平行中的直线)问题
总结:由于最近一直忙于复习考试,看的很少,但已经看完第一章了,课后习题还没写(感觉是在被教怎么做人了),真的写的很精彩,对于有些问题感到很神奇,对于很多解题思路很方法感觉还是有点吃力去理解,页边的涂鸦也很嗨啊,大师的公式推导,绝妙方法,真的让我醉了,醉的不行了,最后附上我在微博上看到的一句,我觉得很有道理:

算法和汇编,这才是计算机科学。低头制造垃圾简直暴殄天物。。。。。