深入浅出『汉诺塔』

0.前言

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。一次只移动一片，不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

1.游戏规则

条件： 有A、B、C三根柱子，A柱子按照上小下大放置圆盘。

规则： 每次只能移动1个圆盘，圆盘可在A、B、C三根柱子间任意移动，并且始终保持小盘在大盘上。

目标： 圆盘全部从A柱移动到C柱上，并且圆盘顺序不变，依旧是上小下大。

2.汉诺塔1-3层详解

汉诺塔是一道非常经典的递归问题，对于递归问题的求解，最重要的是找到递归公式，下面我们先通过观察1-3层汉诺塔移动方法，看看能不能找到一些规律。

🍑(1)一层汉诺塔

一层汉诺塔移动方法显然是：

移动第1个圆盘: A -> C

🍑(2)二层汉诺塔

二层汉诺塔移动方法：

移动第1个圆盘: A -> B

移动第2个圆盘: A -> C

移动第1个圆盘: B -> C

🍑(3)三层汉诺塔

动图演示：

三层汉诺塔移动方法：

移动第1个圆盘: A -> C

移动第2个圆盘: A -> B

移动第1个圆盘: C -> B

移动第3个圆盘: A -> C

移动第1个圆盘: B -> A

移动第2个圆盘: B -> C

移动第1个圆盘: A -> C

3.汉诺塔求解思路

观察过上面1-3层的汉诺塔的移动，你有没有找到一些规律呢？经过简单的归纳总结，我们大体可以得到这样的规律：

当汉诺塔层数n为1时：

• 将A柱上的1个圆盘直接挪到C柱上

当汉诺塔层数n为2时：

• 步骤1：先将A柱上第1个圆盘移动到B柱上
• 步骤2：再将A柱上剩下的1个圆盘直接移动到C柱上
• 步骤3：最后将B柱上的圆盘移动到C柱上

当汉诺塔层数n为3时：

• 步骤1：先将A柱上前2个圆盘移动到B柱上
• 步骤2：再将A柱上剩下的1个圆盘直接移动到C柱上
• 步骤3：最后将B柱上的圆盘移动到C柱上

那么当n=4的时候呢？

我们按照上述过程，可以想到这样的思路：

• 步骤1：先将前4-1个圆盘，从A柱借助C柱挪到B柱
• 步骤2：再将A柱上剩下的1个圆盘，从A柱直接挪到C柱
• 步骤3：最后将B柱上的4-1个圆盘，从B柱借助A柱挪到C柱

通过对上述过程的归纳，当为n层汉诺塔的时候，我们将其分为三步：

• 步骤1：先将前n-1个圆盘，从A柱借助C柱挪到B柱
• 步骤2：再将A柱上剩下的1个圆盘，从A柱直接挪到C柱
• 步骤3：最后将B柱上的n-1个圆盘，从B柱借助A柱挪到C柱

4.汉诺塔语言实现

有了以上的递归逻辑，我们就可以借助任意的语言工具将其实现，由于笔者目前只学过C语言和Java，那么下面就使用这两种语言实现汉诺塔。

🍑(1)C语言实现代码

/*
n 盘子的数目
origin 源柱
assist 辅助柱
destination 目的柱
*/

#include<stdio.h>

//创建一个计数器
int count;//全局变量默认初始化为0

void move(int n, char origin, char destination)
{
    count++;
    printf("第%-2d次移动圆盘%d：%c->%c\n",count,n,origin,destination);
}

void hanoi(int n,char origin,char assist,char destination)
{
    if (n == 1)
    {
      //递归终止条件:当递归到柱上只有1个盘子的时
        move(n, origin, destination);
    }
    else
    {
      //将n-1个盘子：origin->(destination)->assist
        hanoi(n-1,origin,destination,assist);
        //将origin柱上剩下的盘子：origin->destination
        move(n, origin, destination);
        //将辅助柱上的n-1个盘子：assist->(origin)->destination
        hanoi(n - 1, assist, origin, destination);
    }
}

int main()
{
    int n = 0;
    printf("汉诺塔的层数:");
    scanf(" %d", &n);

    hanoi(n,'A','B','C');
    return 0;
}

测试结果：

🍑(2)Java实现代码

import java.util.Scanner;

public class Hanoi {
    /**
     *
     * @param n 盘子的数目
     * @param origin 源柱
     * @param assist 辅助柱
     * @param destination 目的柱
     */
    public static void hanoi(int n,char origin,char assist,char destination){
        if(n==1) {
            move(n,origin,destination);
        } else {
            hanoi(n-1,origin,destination,assist);
            move(n,origin,destination);
            hanoi(n-1,assist,origin,destination);
        }
    }

    public static void move(int n,char origin,char destination) {
        System.out.println("移动第"+n+"个圆盘: "+origin+" -> "+destination);
    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        System.out.print("汉诺塔的层数:");
        int n= scan.nextInt();

        hanoi(n,'A','B','C');
    }
}

测试结果：

🍑由汉诺塔引申出对递归问题的求解

对于递归问题的求解，核心是如何找到递推公式，而不是关心每一层递归执行的具体细节。就比如汉诺塔问题，当我们用具体的语言工具实现之后，如果让我们写出每一层的执行细节，当n=3时就变得非常复杂了，更不用说n=4、5……所以说，对于递归的实现，我们需要注重的是它的逻辑，而不是执行细节，对于细节的处理只要程序的逻辑没有问题，再复杂的执行计算机都可以帮你处理，这方面你可以永远相信计算机！

总结

最后我们在回到汉诺塔问题，移动64块金片，在不出错的情况下至少要移动264-1次，假设1秒移动一次就需要18,446,744,073,709,551,615秒，大约是5800亿年，可想当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界恐怕就要在一声霹雳中消灭了。