汉诺塔递归

汉诺塔递归问题应该是最简单的递归问题了吧，纠结了快半小时才纠结出来。。。好失败啊。。。

大致思路（来自王民利的博客，其实和课本上写的基本一样）：

现在要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。

1、此时老和尚（后面我们叫他第1个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第2个和尚）（呵呵，倚老卖老），命令：

① 你把前63个盘子移动到第二柱子上

② 在我自己把第64个盘子一道第三个柱子上后

③ 你把前63个盘子移动到第三柱子上

2、第2个和尚接了任务，也觉得很难，所以他也和第1个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第3和尚）（呵呵，又倚老卖老），命令：

① 你把前62个盘子移动到第三柱子上

② 在我自己把第63个盘子一道第二个柱子上后

③ 你把前62个盘子移动到第二柱子上

3、第3个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第4个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。

4、到此任务下交完成，到各司其职完成的时候了。

完成回推了：

第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分

配的第2个盘子。第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。

从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚—第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。

现在我们以有3个盘子来分析：

第1个和尚命令：

㈠ 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）

㈡第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。

㈢第2个和尚你把前2个盘子从第二柱子移动到第三柱子。

很显然，第㈡步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）

其中第㈠步。第2个和尚他有2个盘子，他就命令：

① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）

② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。

③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。

同样，第步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）

第㈢步可以分解为，第2个和尚还是有2个盘子，命令：

①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。

② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。

③第3个和尚你把第一柱子上的盘子移动到第三柱子。

分析组合起来就是：1→3   1→2    3→2    1→3   2→1  2→3   1→3共需要七步。如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n个盘子需要（2的n次方）–1步。

从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：

（1）把1座上（n-1）个盘子借助3座移到2座。

（2）把1座上第n个盘子移动3座。

（3）把2座上（n-1）个盘子借助1座移动3座。

自己写的代码：

#include <iostream>
using namespace std;
void move(int pNum,int zFrom,int zTo) //显示移动的方法
{
    cout << "将第" << pNum << "个盘子从第" << zFrom << "个柱子移动到第" << zTo << "个柱子" <<endl;
}
void Hanoi(int pNum,int One,int Two,int Three) //把第pNum个盘子通过柱子Two从柱子One移动到柱子Three
{
    if (pNum==1) move(1,One,Three); //只有一个盘子了直接移动
    else
    {
        Hanoi(pNum-1,One,Three,Two);//先把柱子One上面的pNum-1个盘子通过柱子Three移动到柱子Two
        move(pNum,One,Three);       //显示操作方法，把第pNum个盘子移动到柱子Three（也就是目标柱子）
        Hanoi(pNum-1,Two,One,Three);//把柱子Two上剩下的pNum-1个盘子通过柱子One移动到柱子Three完成全部操作
    }
}
int main()
{
    int Num;
    cout << "请输入要移动的盘数：";
    cin >> Num;
    Hanoi(Num,1,2,3);
    return 0;
}

运行结果

请输入要移动的盘数：3
将第1个盘子从第1个柱子移动到第3个柱子
将第2个盘子从第1个柱子移动到第2个柱子
将第1个盘子从第3个柱子移动到第2个柱子
将第3个盘子从第1个柱子移动到第3个柱子
将第1个盘子从第2个柱子移动到第1个柱子
将第2个盘子从第2个柱子移动到第3个柱子
将第1个盘子从第1个柱子移动到第3个柱子

无论如何算是搞定啦。。。万事开头难慢慢来。