共计 781 个字符，预计需要花费 2 分钟才能阅读完成。
递归算法三：汉诺塔
问题描述
移动规则：
每次只能移动一个圆盘；
圆盘可以插在 A、B 和 C 中的任何一个塔座上；
任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
分析
边界条件
只有一个圆环时，只需将圆环从第一座塔移到第三座塔
递归条件
1、从第一座塔把 n - 1 个圆环移到第二座塔，用第三座塔做辅助
2、从第一座塔把第 n 个圆环移到第三座塔
3、从第二座塔把 n - 1 个圆环移到第三座塔，用第一座塔做辅助
代码
简单汉诺塔递归实现
#include<iostream>
using namespace std;
void move(char from, char to){cout<<"Move"<<from<<"to"<<to<<endl;}
void hanoi(int n, char first, char second, char third){if(n==1){move(first, third);
}else{hanoi(n-1, first, third, second);
move(first, third);
hanoi(n-1, second, first, third);
}
}
int main(){
int m;
cout<<"the number of diskes:";
cin>>m;
cout<<"move"<<m<<"diskes:\n";
hanoi(m,'A','B','C');
return 0;
}汉诺塔递推实现
#include<iostream>
using namespace std;
int main(){
int m;
cin>>m;
long long p = 0;
for(int i=0; i<m; i++){p=2*p+1;}
cout<<2*p<<endl;
return 0;
}递推和递归都可以实现汉诺塔 但无法完美通过 openjudge 上的问题，可能是因为当数据很大时，数据溢出，可能需要通过自己编写大整数运算的算法来解决问题。这个下一篇文章单独写出。
正文完
