递归典例---汉诺塔

https://ybt.ssoier.cn/problem_show.php?pid=1205

#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>using namespace std;
using ll = long long;void move(int n,char a,char b,char c) // n 个盘子，通过 b，从 a 移动到 c
{if(n==1) // 只有一个的时候，从 a 直接移动到 c{cout<<a<<"->1->"<<c<<endl; return ;}move(n-1,a,c,b); // 拆分子问题，将 n-1 个圆盘通过 c 从 a 移动到 bcout<<a<<"->"<<n<<"->"<<c<<endl; // 将第 n 个从 a 移动到 cmove(n-1,b,a,c); // 将剩下的 n-1 个通过 a 从 b 移动到 c，进入下一阶段return ;
}void solve()
{int n;char a,b,c;cin>>n>>a>>b>>c;move(n,a,c,b);
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; T=1;while(T--)solve();return 0;
}

总次数：回顾移动的过程，不难发现，对于 $n$ 个圆盘，移动经过以下步骤：

1. 将 n-1 个圆盘移动到从 a 移动到 b
2. 将最下面的圆盘从 a 移动到 c
3. 将 n-1 个圆盘从 b 移动到 c
   有 $f(n)=2\ast f(n-1)+1$，根据数列的相关知识，$f(n)=2^n-1$