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
