10 汉诺塔(递归)

汉诺塔问题都很熟悉，是一种典型的递归问题。

image.png

一般学习递归都会从这个例子学起，它的难度也不是特别大。

分析：

边界条件：
n = 1 时，直接把盘子从A盘移动到C盘即可。
状态转移方程：
定义 f(n, A, B, C) 表示将n个盘子从A盘移动到C盘（借助中间盘B）
则 f(n, A, B, C) = f(n - 1, A, C, B) + f(n - 1, B, A, C)
解释：直接把上面n-1个盘子当成整体先移动到中间盘B（中间盘C），然后剩下的一个盘子直接移动到C，然后再把B盘上当成整体的n-1个盘子移动到C（中间盘A）即可。

源码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

void hanota(int n, char a, char b, char c) {
    if (n == 1) {
        printf("%c->%c\n", a, c);
        return;
    }
    hanota(n - 1, a, c, b);
    printf("%c->%c\n", a, c);
    hanota(n - 1, b, a, c);
}

void solve(int n) {
    hanota(n, 'A', 'B', 'C');
}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}

运行结果：

image.png