汉诺塔问题——递归（时隔9个月，终于懂了）

程序员文章站 2024-03-05 15:39:07

...

记得我第一次做汉诺塔这道题时，是2017年11月。当时，我坐在山大青岛校区图书馆3楼，不知怎么地，看到了这个题。

然后，就思考了一整天，233

当然，悲剧就是，我当时花了一天的时间还是没有真正理解这道题递归的思路。

如今，我终于懂了，嘿嘿嘿。

关于递归：一定不要试图跟踪大型递归的过程！要写出递归，关键就是找出递归的递归方程式：也就是说，要完成最后一步，那么最后一步的前一步要做什么。

关于递归：

（1）在求f(n, other variables)的时候，你就默认f(n -1, other variables)已经被求出来了——至于怎么求的，这个是计算机通过回溯求出来的。

PS:这里用到了一种叫做栈(stack)的先进后出的数据结构，所以递归输出的答案一般是自下而上的。

（2）递归和二叉树是密切相关的。可以尝试通过二叉树的数据结构来理解递归是如何将一个问题拆分成若干子问题，求解再回溯的。这里可以参考以下快速排序(QuickSort)的过程（快速排序的核心思想是分治，分治即分而治之，通过递归将原问题分解为若干容易求解的子问题，再通过递归将这些子问题联系起来并向二叉树的上层回溯，最终求解出原问题）

递归的关键有两个：

（1）递归的结束条件（不写会死循环，TLE）

（2）递归最后一层和其他有关系的层的关系怎样用非递归函数来表达

比如：斐波纳契亚数列，（1）当n==1和n==2的时候f(n)=1，这就是递归的终止条件。给了终止条件，计算机才能进行求解子问题并回溯，最终求出f(n)

对于这个汉诺塔问题，在写递归时，我们只需要确定两个条件：

1.递归何时结束？

2.递归的核心公式是什么？即：

怎样将n个盘子全部移动到C柱上？

即：若使n个盘子全部移动到C柱上，上一步应该做什么？

下面正式进入该题：

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

下面我们来写递归函数。

首先，题目要求求的是如何操作，那么我们就必须写一个输出操作语句的函数。

这个操作语句必须说明：第几步将哪个盘子从哪个柱子移动到哪个柱子上（这样人类才知道怎样移动盘子嘛）

这里，我们定义这个函数的函数名为move。

接下来，我们来确定这个函数的参数列表。

显然，为了说明第几步将哪个盘子从哪个柱子移动到哪个柱子上，我们参数列表至少应该包含：

id，表示被移动的盘子的序号。

from，表示从哪个柱子上移动这个编号为id的盘子

to，表示移动到哪个柱子上

那么这个函数的函数头就确定了：

void move(int id, char from, char to) // 打印移动方式：编号，从哪个盘子移动到哪个盘子

那么函数体呢？

唯一的难点就是如何记录这是操作的第几步。

注意到，每次操作必须输出移动方式且仅能输出一次，那么显然，我们已经printf的当前总数不就是第几次操作了嘛

我们开一个全局变量用于记录printf的次数即可

所以函数体中就只有这一个语句：

printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);

合并起来就是：

void move(int id, char from, char to) // 打印移动方式：编号，从哪个盘子移动到哪个盘子
{
    printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
}

敲黑板：

递归函数怎么写呢?

我们先来想一下我们人类应该怎样操作吧。

我们每次操作都会这样问自己：我们需要将哪个柱子上的多少个盘子通过哪个柱子移动到哪个柱子上呢？

我们必须也只能用这么几个参数：

需要移动的盘子的总数，3个柱子。

所以函数头为：

void hanoi(int n, char x, char y, char z)

其中，n代表盘子总数，x，y，z代表柱子

hanoi(n, x, y, z)的意思就是：将n个在x柱子上的盘子通过y这个柱子移动到z这个柱子上。

那不就完了！

hanoi(n, 'A', 'B', 'C')就是这道问题的答案！

那么这一步的前一步是什么？

记住了，在求解f(n, other variables)的时候，我们直接默认f(n - 1, other variables)已经完了就可以了！这个在前面已经解释过了，在此不再鳌述。

我们将n-1个盘子当作一个整体：这就是类似于分治求解子问题的思想

那么，前一步也就是f(n - 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上，再将在A柱子上的编号为n的盘子移动到C柱上，再将B柱子上的n-1个盘子通过A柱移动到C柱上，over

C++代码如下：

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

汉诺塔完整代码：

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

int cnt;

void move(int id, char from, char to) // 打印移动方式：编号，从哪个盘子移动到哪个盘子
{
    printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    cnt = 0;
    scanf ("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

用户友好版：

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

int cnt;

void move(int id, char from, char to) // 打印移动方式：编号，从哪个盘子移动到哪个盘子
{
    ++cnt; // 记录走过的步数
    printf ("step %d: move %d from %c->%c\n", cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    printf("Please enter the number of the plates:");
    while (~scanf ("%d", &n) && n)
    {
        cnt = 0;
        printf ("The following are the steps for the question\n");
        hanoi(n, '1', '2', '3');
        printf ("There are %d steps in all.\nYou have solved the hanoi problems, congratulations!\n", cnt);
        printf ("Would you like to continue?(y/n)");
        char ch; scanf (" %c", &ch);
        if (ch == 'y' || ch == 'Y')
            printf("Please enter the number of the plates:\n");
        else
        {
            printf ("Here comes the end of the program. Bye\n");
            break;
        }
    }
    return 0;
}