2038 - 汉诺塔
汉诺塔是根据一个传说形成的一个问题：
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
1.每次只能移动一个圆盘；
2.大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移，最少要移动多少次？
MiaoWu玩三根杆子移动圆盘玩腻了。于是，它从寝室偷了m-3根杆子，想用这m根杆子来移动盘子，问n个盘子从起始盘移动到目标盘，至少需要移动多少步？
Input
输入m,n到文件末尾结束（3<=m<=20 , 0<=n<=1000）
Output
输出最小移动步数
Examples
Input
3 3 3 4 3 5 4 1 4 12
Output
7 15 31 1 81
Hint
Big numbers are required.
Solution C++
#include<stdio.h> #include<string.h> #include<ctime> #include<vector> #include<algorithm> using namespace std; #define N 1000000000 inline vector<int> change(int val) { vector<int>ans; while(val) { ans.push_back(val%N); val/=N; } return ans; } inline vector<int> equ(vector<int> a) { vector<int>ans; for(int i=0;i<a.size();i++) ans.push_back(a[i]); return ans; } inline vector<int> Min(vector<int> a,vector<int> b) { if(a.size()>b.size()) return b; else if(a.size()<b.size()) return a; else { for(int i=a.size()-1;i>=0;i--) { if(a[i]<b[i]) return a; else if(a[i]>b[i]) return b; } return a; } } inline vector<int> add(vector<int>a,vector<int>b) { vector<int>ans; int l1=a.size(),l2=b.size(),l=0; int m=0; while(l<min(l1,l2)) { int p=a[l]+b[l]+m; m=p/N; ans.push_back(p%N); l++; } while(l<l1) { int p=a[l]+m; m=p/N; ans.push_back(p%N); l++; } while(l<l2) { int p=b[l]+m; m=p/N; ans.push_back(p%N); l++; } if(m!=0) ans.push_back(m); return ans; } inline void Print(vector<int> a) { for(int i=a.size()-1;i>=0;i--) { printf("%d",a[i]); } printf("\n"); } vector<int>dp[21][1001]; inline void init() { for(int i=3;i<=20;i++) dp[i][1].push_back(1); for(int i=3;i<=20;i++) dp[i][2].push_back(3); for(int i=3;i<=1000;i++) { dp[3][i]=add(dp[3][1],add(dp[3][i-1],dp[3][i-1]));//dp[3][1]); } for(int i=4;i<=20;i++) for(int j=3;j<=1000;j++) { dp[i][j]=add(dp[i-1][1],add(dp[i][j-1],dp[i][j-1]));//,dp[i-1][1]); for(int k=2;k<=j;k++) { dp[i][j]=Min(dp[i][j],add(dp[i-1][k],add(dp[i][j-k],dp[i][j-k])));//dp[i-1][k])); } } } int main() { int m,n; init(); //printf("zz\n"); while(~scanf("%d%d",&m,&n)) { if(n==0) printf("0\n"); else Print(dp[m][n]); } }
Hint
Big numbers are required.