汉诺塔 | Wpz's Blog

起源

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象为数学问题

如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

调用方法的栈机制（先进后出）

从主线程开始调用方法（函数）进行不停的压栈和出栈操作，函数的调用就是将函数压如栈中，函数的结束就是函数出栈的过程，这样就保证了方法调用的顺序流，即当函数出现多层嵌套时，需要从外到内一层层把函数压入栈中，最后栈顶的函数先执行结束（最内层的函数先执行结束）后出栈，再倒数第二层的函数执行结束出栈，到最后，第一个进栈的函数调用结束后从栈中弹出回到主线程，并且结束。

算法分析（递归算法）

我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是通过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。

实现这个算法可以简单分为三个步骤：

把 n-1 个盘子由 A 移到 B；
把第 n 个盘子由 A 移到 C；
把 n-1 个盘子由 B 移到 C；

从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：

中间的一步是把最大的一个盘子由 A 移到 C 上去；
中间一步之上可以看成把 A 上 n-1 个盘子通过借助辅助塔（C塔）移到了 B 上，
中间一步之下可以看成把 B 上 n-1 个盘子通过借助辅助塔（A塔）移到了 C 上；

代码实现

Java

Java 实现

import java.util.Scanner;

public class Hannota {

    public static void hannota(int n, char A, char B, char C) {
        if (n == 1) {
            move(n, A, C);
        } else {
            hannota(n - 1, A, C, B);
            move(n, A, C);
            hannota(n - 1, B, A, C);
        }
    }

    public static void move(int n, char from, char to) {
        System.out.printf("将编号为%d的盘子从柱子%c移动到柱子%c\n", n, from, to);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        hannota(n, 'A', 'B', 'C');
        scanner.close();
    }
}

Python

Python 实现

def hannota(n, A, B, C):
    if n == 1:
        move(n, A, C)
    else:
        hannota(n - 1, A, C, B)
        move(n, A, C)
        hannota(n - 1, B, A, C)


def move(n, f, to):
    print('将编号为%d的盘子从柱子%c移动到柱子%c' % (n, f, to))


if __name__ == '__main__':
    n = input()
    hannota(int(n), 'A', 'B', 'C')

Go

Go 实现

package main

import "fmt"

func Hannota(n int, A, B, C byte) {
    if n == 1 {
        Move(n, A, C) // 只有一个盘子，直接从 A 移动到 C
    } else {
        Hannota(n-1, A, C, B) // 先将 n-1 这个盘子从 A 借助 C 移动到 B
        Move(n, A, C)         // 经过上面的递归，n-1 这个盘子已经移动到了 B，现在将最后一个盘子 n 直接从 A 移动到 C
        Hannota(n-1, B, A, C) // 最后将 n-1 这个盘子从 B 借助 A 移动到 C
    }
}

func Move(n int, from, to byte) {
    fmt.Printf("将编号为%d的盘子从柱子%c移动到柱子%c\n", n, from, to)
}

func main() {
    var n int
    fmt.Scanf("%d", &n)
    Hannota(n, 'A', 'B', 'C')
}

参考文章

汉诺塔的图解递归算法