汉诺塔的递归与非递归实现

汉诺塔（Tower of Hanoi）是根据一个传说形成的数学问题： 有三根杆子A，B，C。 A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。 问：如何移？最少要移动多少次？ 递归版本： #include <iostream> #include <time.h> int count = 0; using namespace std; void hanio(int n, char a, char c, char b) { if(n == 1) { cout<<a<<" -> "<<b<<endl; count++; } else { hanio(n - 1, a, b, c); cout<<a<<" -> "<<b<<endl; count++; hanio(n - 1, c, a, b); } } int main() { int n; cin>>n; clock_t time_start = clock(); hanio(n, 'a', 'b', 'c'); clock_t time_end = clock(); cout<<"The program takes "<<(time_end - time_start)/1.0/1000<<" milliseconds"<<endl; return 0; } 非递归版本： #include <iostream> #include <memory.h> #include <math.h> #include <time.h> using namespace std; int max_k(int i) { if(i==0) return 0; int k = 0; while(i%2==0) { i/=2; k++; } return k; } int main() { int n, k; cin>>n; clock_t time_start = clock(); char* a = new char[n]; memset(a, 'a', n); if(n%2==0) { for(int i=1;i<=pow(2,n)-1;i++) { k = max_k(i); if((k+1)%2) { char now = a[k];//k+1号盘子现在在哪根柱子上 char next = (a[k]=='c')?'a':(a[k]+1);//k+1号盘子要移动到哪根柱子上 cout<<now<<" -> "<<next<<endl; a[k] = next; } else { char now = a[k];//k+1号盘子现在在哪根柱子上 char next = (a[k]=='a')?'c':(a[k]-1);//k+1号盘子要移动到哪根柱子上 cout<<now<<" -> "<<next<<endl; a[k] = next; } } } else { for(int i=1;i<=pow(2,n)-1;i++) { k = max_k(i); if((k+1)%2) { char now = a[k];//k+1号盘子现在在哪根柱子上 char next = (a[k]=='a')?'c':(a[k]-1);//k+1号盘子要移动到哪根柱子上 cout<<now<<" -> "<<next<<endl; a[k] = next; } else { char now = a[k];//k+1号盘子现在在哪根柱子上 char next = (a[k]=='c')?'a':(a[k]+1);//k+1号盘子要移动到哪根柱子上 cout<<now<<" -> "<<next<<endl; a[k] = next; } } } clock_t time_end = clock(); cout<<"The program takes "<<(time_end - time_start)/1.0/1000<<" seconds"<<endl; return 0; } 最后还输出计算时间，n较小时两者差不多，n大了之后明显非递归更快