b161 - NOIP2007 4.Hanoi双塔问题
題目描述
題目要求計算將 2n 個圓盤從 A 柱移動到 C 柱，允許使用 B 柱暫存，且每次只能移動一個圓盤，並保持柱上圓盤大小順序的最小移動次數 An。
解題思路
本題可以透過觀察和數學歸納法來找到遞迴關係式。
當 n=1 時，有兩個圓盤，需要 2 步移動。
當 n=2 時，有四個圓盤，需要 6 步移動。
當 n=3 時，有六個圓盤，需要 14 步移動。
可以發現 An = 2 * An-1 + 2。
程式碼中，ans[i] 儲存了 n=i 時的最小移動次數。
程式碼使用動態規劃的方式預先計算出 ans[1] 到 ans[200] 的值，然後根據輸入的 n 值直接輸出 ans[n]。
add 函數用於大數加法，因為移動次數可能會超出整數範圍。
複雜度分析
- 時間複雜度: O(N) (預計算
ans陣列) + O(1) (查詢) = O(N) - 空間複雜度: O(N) (儲存
ans陣列)
程式碼
#include <iostream>
using namespace std;
int n;
string ans[251]={"0"};
inline string add(string a,string b){
int tmp[10001]={0},al=a.length(),bl=b.length();
string c;
for(int i=0;i<al;++i)tmp[al-i-1]+=a[i]-'0';
for(int i=0;i<bl;++i)tmp[bl-i-1]+=b[i]-'0';
for(int i=0;i<10000;++i)
if(tmp[i]>9){
++tmp[i+1];
tmp[i]-=10;
}
for(int i=10000;i>=0;--i)
if(tmp[i]){
al=i;
break;
}
for(int i=al;i>=0;--i)c+=tmp[i]+'0';
return c;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=0;i<250;++i)
ans[i+1]=add(add(ans[i],ans[i]),"2");
while(cin >> n)
cout << ans[n] << "\n";
}