Hanoi雙塔問題
題目描述
?
給定A,B,C三根足夠長的細柱，在A柱上放有2n個中間有空的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區分的(下圖為n=3的情形）。現要將 這些國盤移到C柱上，在移動過程中可放在B柱上暫存。要求:
?
?
(1)每次只能移動一個圓盤；
?
(2) A、B、C三根細柱上的圓盤都要保持上小下大的順序；
?
任務:設An為2n個圓盤完成上述任務所需的最少移動次數，對于輸入的n，輸出An。
?
?
輸入
?
輸入文件hanoi.in為一個正整數n，表示在A柱上放有2n個圓盤。
?
輸出
?
輸出文件hanoi.out僅一行，包含一個正整數，為完成上述任務所需的最少移動次數An。
?
樣例輸入
1
樣例輸出
2
提示
?對于50%的數據，?1<=n<=25
對于100%?數據，?1<=n<=200
?
設法建立An與An-1的遞推關系式。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int f[1000],n; 4 void Hanoi() 5 { 6 int i; 7 for(i=1;i<=f[0];i++) f[i]*=2; //按位乘2 8 f[1]+=2; 9 for(int i=1;i<=f[0];i++) //處理進位 10 { 11 f[i+1]+=f[i]/10; 12 f[i]%=10; 13 } 14 if(f[f[0]+1]!=0) f[0]++; //確定位數 15 } 16 int main() 17 { 18 cin>>n; 19 memset(f,0,sizeof(f)); 20 f[0]=1;f[1]=2; 21 for(int i=2;i<=n;i++) 22 { 23 Hanoi(); 24 } 25 for(int i=f[0];i>=1;i--) 26 cout<<f[i]; 27 cout<<endl; 28 return 0; 29 }
?
)
)
