算法之路（四）----汉诺塔（又称河内之塔）

汉诺塔是很简单也很经典的算法之一。
汉诺塔是根据一个传说形成的数学问题：
有三根杆子A，B，C 。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

• 1 每次只能移动一个圆盘；
• 2 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可以将A杆移除的圆盘重新移动回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？

3个圆盘的汉诺塔移动 4个圆盘的汉诺塔移动

传说

最早发明这个问题的人是法国数学家爱德华*卢卡斯。
传说印度某间寺院有三根柱子，上串64个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要2⁶⁴− 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5849亿年才能完成。整个宇宙现在也不过137亿年。
这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。
佛教中确实有“浮屠”（塔）这种建筑；有些浮屠亦遵守上述规则而建。“河内塔”一名可能是由中南半岛在殖民时期传入欧洲的。

解答

如取N=64，最少需移动2⁶⁴− 1次。即如果一秒钟能移动一块圆盘，仍将需5849.42亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。
在真实玩具中，一般N=8；最少需移动255次。如果N=10，最少需移动1023次。如果N=15，最少需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他最多仅能移动15块。如果N=20，最少需移动1048575次，即超过了一百万次。

解法

解法的基本思想是递归。假设有A、B、C 三个塔，A塔有N块盘，目标是把这些盘全部移动到C塔。那么先把塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移动到C，最后把B塔的N-1块盘移动到C。
每次移动多于一块盘时，则再次使用上述算法来移动。

怎么来理解呢？
我们可以倒着理解，要将A塔上的所有圆盘移动到C塔，且所有圆盘是下大上小。那么必定有一个过程是最大的圆盘（也就是第N个圆盘）从A移动到C。那么必须保证上面的N-1个圆盘全在B塔，且圆盘满足上面小，下面大。当第N个圆盘从A移动到C之后，又得把N-1个圆盘从B塔移动到C塔，这样工作就完成了。
但是怎么把A塔上的N-1个圆盘移动到B塔呢？
这里需要一点想象力，可以想象成只有N-1个圆盘，从A塔移动到B塔（此时的B塔其实就相当于上面的C塔），我们称A塔为A1塔，B塔为C1塔，C塔为B1塔，那么问题就变成了如何将N-1个盘从A1塔移动到C1塔？
同样的需要将上面的N-2个圆盘从A1塔移动到B1塔，然后将第N-1个圆盘从A1塔移动到C1塔，然后再将B1塔上的N-2个圆盘移动到C1塔。
同理，递推第N-2个塔.....。

将 B塔上的 N-1个盘，移动到C塔的过程与上面原理一样。

递归解

以Objective-C语言实现：

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view from its nib.
    int n = 9;
    [self hannoi:n from:@"A" buffer:@"B" to:@"C"];
    NSLog(@"一共 %d 步",count);
}

- (void)hannoi:(int)n from:(NSString *)from buffer:(NSString *)buffer to:(NSString *)to
{
    if (n == 1) {
        NSLog(@"Move disk %d from %@ to %@", n, from, to);
    } else {
        [self hannoi:n-1 from:from buffer:to to:buffer];
        NSLog(@"Move disk %d from %@ to %@", n, from, to);
        [self hannoi:n-1 from:buffer buffer:from to:to];
    }
}

console : 一共 511 步

以C++语言实现：

using namespace std;
#include <iostream>
#include <cstdio>

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 1) {
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
    } else {
        hannoi (n-1, from, to, buffer);
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
        hannoi (n-1, buffer, from, to);
    }
}

int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}

通过以上递归过程可知hannoi(n) = 2 * hannoi(n-1) + 1 ，hannoi(n) = 2^n-1 + 2^n-2 + 2^n-3+ ...... + 2² + 2 +1。
对等比数列求和得出hannoi(n) = 2ⁿ -1。