经典递归问题——汉诺塔

                                                                汉诺塔

汉诺塔问题第一次接触时就感觉非常有趣，但是由于当时知识有限不能深刻地理解递归的含义，所以没能继续深究，现在来谈一谈吧。

题目描述：汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘，只能移动在最顶端的圆盘。

思路：假设有A,B,C三个柱子，当A上只有一个盘子时直接将该盘子移到另一柱子上；当A上有两个盘子时，先借助B将第一个移到B上，其次将最后一个移到C上，然后再将第一个盘子移到C上；当有三个盘子时，先将前两个借助C移到B，其次将最后一个移到C，然后再将B上的借助A移到C；当有n个盘子时，先将前n-1个借助C移到B，其次将最后一个移到C，然后再将B上的借助A移到C。

具体实现代码为C++如下：

#include<iostream>
using namespace std;
int count;
void move(char A,char C){
     cout<<++count<<','<< A<<"->"<<C<<endl;
}
void hanoi(int n,char A,char B,char C){   //将n个盘子借助B移到C
     if(n==1)   move(A,C);
        else{
           hanoi(n-1,A,C,B);   //先将n-1个从A借助C移到B
           move(A,C);           //其次将最后一个从A移到C
           hanoi(n-1,B,A,C);     //然后将n-1个从B借助A移到C
        };
}
int main(){
    int i;
    char A,B,C,b,c;
    cout<<"请输入总盘子数:";
    cin>>i;
    hanoi(i,'A','B','C');
    cout<<"一共"<<count<<"次";
    return 0;
}