递归:汉诺塔详解

昨天有的同学问到我关于汉诺塔的问题,说是无法理解。且不说汉诺塔这是个经典递归算法问题,光是中学的数学课,我们应该就见过不只一次这个问题。

首先我们来回顾一下中学的数学问题:现在有一个汉诺塔,上面有nn个盘子,请问要几步才能完成这个汉诺塔的移动?

我们假设最终要ana_n步。那么,我们先来试试看:

  1. n=1n=1

    这个时候想要完成任务,只需要把这个盘子从XX移动到ZZ就可以了。

    于是,a1=1a_1=1

  2. n=2n=2

    这个时候,我们需要把最小的先放入中转站,然后把大的移动到ZZ,最后再把中转站的也移到ZZ

    于是,a2=3a_2=3

  3. n=3n=3

    现在盘子越来越多,不着急。我们先把上面的两个按照n=2n=2的方法来移动到中转站。

    然后将最大的移动到ZZ,然后再将中转站上的所有移动到ZZ

    于是,a3=7a_3=7

然后我们再回顾下,会发现,除了第一次,其他的不论多少个盘子,都是将除了最大的以外所有盘子先移动到中转站,然后把最大的移动到ZZ,最后再把中转站上的所有盘子移到ZZ上。

因此,ana_n我们都可以通过它的上一次的移动来推出。每一次的移动,都要把其中n1n-1个从XXYY,然后从YYZZ,相当于an1a_{n-1}两遍,最大的那个从XXZZ移动一次。

an=2an1+1a_n=2a_{n-1}+1

是不是越听越像递归了?

好,那我们现在来从程序的角度理解下。

首先,只有一个盘子的时候,不需要用到中转站,直接X --> Z即可。

两个以上盘子的时候,我们需要引入一个中转站Y,首先让n-1个执行X --> Y(中转缓存),然后让最大的执行X --> Z,最后让那n-1个执行Y --> Z(清空缓存)。

至于这n-1个盘子怎么操作,递归就好了。

原理知道了,那我们来创建一个函数:

hanoi(盘子数, 起点, 中转站, 终点)

这里的起点,中转站和终点,在每一轮里是不一样的,比如,执行中转缓存的时候,本质上是X --> Y,那么起点就是X,终点就是Y,中转站当然就是Z了。

只有一个盘子的时候,直接:

print(X,'-->',Z)

多个盘子的时候:

hanoi(n-1, X, Z, Y) # 把除了最大的都移动到Y,此时Z是中转站(中转缓存)
print(X,'-->',Z) # 把最大的那个从A移动到Z
hanoi(n-1, Y, X, Z) # 把除了最大的那些从Y移动到Z,此时X是中转站(清空缓存)

说到这里应该都明白了。下面是代码示例:

C语言:

void hanoi(int n, char X, char Y, char Z)
{
    if (n == 1)
    {
        printf("%c --> %c\n", X, Z);
    }
    else
    {
        hanoi(n-1, X, Z, Y);
        printf("%c --> %c\n", X, Z);
        hanoi(n-1, Y, X, Z);
    }
}

Java:

public void hanoi(int n, String X, String Y, String Z) {
    if (n == 1) {
        System.out.println(X + "-->" + Z);
    }
    else {
        hanoi(n-1, X, Z, Y);
        System.out.println(X + "-->" + Z);
        hanoi(n-1, Y, X, Z);
    }
}

Python:

def hanoi(n:int, X:str, Y:str, Z:str):
    if n == 1:
        print(f"{X} --> {Z}")
    else:
        hanoi(n-1, X, Z, Y)
        print(f"{X} --> {Z}")
        hanoi(n-1, Y, X, Z)

Go:

func hanoi(n int, X string, Y string, Z string) {
    if (n == 1) {
        fmt.Println(X + "-->" + Z)
    } else {
        hanoi(n-1, X, Z, Y)
        fmt.Println(X + "-->" + Z)
        hanoi(n-1, Y, X, Z)
    }
}