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

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

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

传说

解答

解法

解法的基本思想是递归。假设有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。