经典递归问题：汉诺塔【超详解】

前言：

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

问题解决：

举例：

当 n = 1 时：

只有一个盘子在a柱子上所以我们只需要将a柱子上的盘子直接移动到c柱子上，所以只需要一步；

-->

当 n = 2 时：

我们需要如下三步才可以将盘子全部移动到c柱子上面；

-->

-->

当 n = 3 时：

我们最少需要如下七步：

-->

-->

-->

-->

观察上面三个例子，我们可以类推到有n个盘子的时候

我们需要完成三大步骤：

（1）将a柱子上的n - 1个盘子借助c柱子移动到b柱子上；

（2）将a柱子上剩余的最后一个盘子移动到c柱子上；

（3）将b柱子上的n - 1个盘子借助a柱子移动到c柱子上；

-->

-->

移动步数分析：

假设移动n个盘子需要T(n)步骤，那么移动n-1个盘子就需要T(n - 1)步骤；

所以上面的三步分别对应的步骤为:

（1）将a柱子上的n - 1个盘子借助c柱子移动到b柱子上；   T(n - 1)

（2）将a柱子上剩余的最后一个盘子移动到c柱子上；           1

（3）将b柱子上的n - 1个盘子借助a柱子移动到c柱子上；     T(n - 1)

所以很容易得出T (n) = 2 * T(n - 1) + 1;

又因为T(1) = 1，所以很容易证明出：T (n) = 2 ^ n   -  1;

代码实现：

//汉诺塔问题
#include<stdio.h>
void move(char a, char c)
{
    printf("%c-->%c\n", a, c);
}
void han(int n, char a, char b, char c)
{
    if (n == 1)
        move(a, c);//只有一个盘子的时候直接从a移动到c
    else       //如果盘子数大于1就调用递归
    {
        han(n - 1, a, c, b);//借助c将a上的（n - 1）个盘子移动到b上
        move(a, c);   //在将最后一个最大的盘子挪到c上
        han(n - 1, b, a, c);//最后借助a将b上的（n - 1）个盘子挪动到c上
    }
}
int main()
{
    int n;
    char a = 'a', b = 'b', c = 'c';
    scanf_s("%d", &n);
    han(n, a, b, c);
    return 0;
}

如果内容帮到你，请点个赞吧！