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 n n 個圓盤,移動經過以下步驟:
- 將 n-1 個圓盤移動到從 a 移動到 b
- 將最下面的圓盤從 a 移動到 c
- 將 n-1 個圓盤從 b 移動到 c
有 f ( n ) = 2 ? f ( n ? 1 ) + 1 f(n)=2*f(n-1)+1 f(n)=2?f(n?1)+1,根據數列的相關知識, f ( n ) = 2 n ? 1 f(n)=2^n-1 f(n)=2n?1