《CM》1.1 The Tower Of Hanoi

1.1 The Tower Of Hanoi 汉诺塔问题

汉诺塔问题:3根柱子,n个尺寸不同的盘子从小到大的堆放在一根柱子上。现在要把这堆盘子移到另一根柱子上,求最少移动的次数。移动规则:一次移动一个盘,始终保持每个盘下面没有比它更小的盘。

用Tn代表n个盘子时所需要的最少移动次数。考虑这样的移盘方案:我们首先移动上面的n-1个盘到第二根的柱子上,这至少需要Tn-1次,然后把底下的第n个盘移动到第三根柱子上,这需要1次,最后把第二根柱子上的盘全都移动到第3根柱子上,这又需要Tn-1次。于是我们移动了2Tn-1 + 1次完成目标,这意味着Tn <= 2Tn-1 + 1。然而,在移动底下最大的那个盘之前,必须先把上面n-1个盘子先移动到一根柱子上,然后在移动它到另一根空的柱子上,之后还要把那n-1个盘移到最大盘所在的柱子,这表明Tn >= 2Tn-1 + 1。所以有

T0 = 0;
Tn = 2Tn-1 + 1,   for n>0.

类似以上形式的式子就是递归式,解递归式就是要求出递归式的"closed form",所谓"closed form",粗略的讲是指用独立于n的固定次的一些标准操作,如+-*/等来计算的式子形式,大概就是通常所说的“公式”,“通式”之类的东西。

打表,找规律,猜想,证明,这往往是解一个递归式的最基本最先想到的思路。其中,证明往往采用数学归纳法。

用这种方法解上述递归式非常容易。然而,如果我们把它稍微做点变化:

T0 + 1 = 1;
Tn + 1 = 2Tn-1 + 2,   for n>0.

令Un = Tn + 1,得到:

U0 = 1;
Un = 2Un-1,   for n>0.

显然,Un = 2n,因此,Tn = 2n - 1,   for n≥0。

打表找规律的方法有相当的局限性,虽然它可以解决一些递归问题,尤其是在算法分析中出现的递归式。然而,更多数的递归式是找不出规律的,这就需要仔细观察递归式,用一些技巧来变换、化简等。CM一书的一个目的就是要培养这种思维能力,当然,这是通过平时的思考,训练等日积月累的过程。



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*