最近毕业设计基本完成，又重拾了数据结构的学习，正好学到了递归的一个教学案例——汉诺塔游戏，感觉非常地有趣，而且学习过程颇有曲折，于是记录一下。
熟悉汉诺塔的背景的请跳过下面一段：
据说，1884年，法国数学家卢卡斯，发明了休闲数学上的一种游戏，名为汉诺塔，取自印度的某些神话传说。

汉诺塔游戏背景故事:
在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

汉诺塔抛开其神话色彩之外，其实是一个很有趣的数学问题，既然是数学问题，那么我就可以通过建模实现用程序进行解答，从而求出所需要的步骤以及每一步具体的移动轨迹。

汉诺塔游戏规则大概意思是有A、B、C三根柱子，A柱子有n个大小不一的圆盘按照从上到下逐渐变大的顺序套在上面，现在要求把所有的圆盘从A柱子按照原顺序挪到C柱子。
要求一：一次只能移动一个圆盘
要求二：在整个游戏过程中，小圆盘永远不能位于大圆盘上方

咋一看，非常地抽象难懂，那么怎么解决呢？其实是依靠一种递归的思想。

举例：现有ABC三根柱子，n个大小不一的圆盘套在A柱子，按照汉诺塔规则把A柱子的圆盘挪到C柱子上。

image.png

其核心解决步骤可抽象为三步：

1、把A柱子上除了最底下那个最大的圆盘外的其它所有圆盘想办法挪到B柱子。
（此时A柱子只剩下一个最大的圆盘，B柱子有n-1个圆盘，C柱子没有圆盘）

image.png

2、把A的圆盘柱子先挪到C柱子上

image.png

3、把B柱子上的n-1个圆盘想办法挪到C柱子

image.png

这样就完成了最初的目标：把A上的圆盘挪到C上。

但是，你是否有注意到一点：这三步中有一个很模糊的词语：想办法。
怎么想办法呢？就算是n-1个，要挪动也很困难啊，一会左挪一会右挪完全无法找到规律啊，其实，你想不到办法，那你可以叫别人想办法呀。

现在假设有这样的情景：我叫你想办法把A柱子上的n-1个盘子挪到B柱子，因为你挪完了我才可以把最下面那个圆盘挪到C柱子，等我挪到C柱子后，你还要负责把B柱子上的n-1个圆盘挪到C柱子重新压在我那个圆盘上，至于你怎么挪，我不管。

然后我这边由于你还没有把圆盘挪到B柱子上，所以我一直在等，而你一转身，拉了另外一个人过来说，你给我把除了最下面两个圆盘，其它的圆盘挪到C柱子，因为你挪完了，我才可以把次下面那个圆盘先放到B柱子，等我挪到B柱子后，你还要负责把C柱子上那n-2个圆盘重新挪回到B柱子上压在我那个圆盘上，至于你怎么挪，我不管（你心想，只要那个人把任务完成了，你不也就可以完成我交给你的任务了吗）

然后就是无尽的循环，一个人拉另外一个人。。。

直到柱子上只剩下最上面那个圆盘没人可以推脱了，于是他啪一下就跳过去了，跳过去之后，紧接着它下面的圆盘也想跳到它那根柱子，通过一番挪移，成功了，然后又是一个个跳，跳到最后发现，所有的圆盘都已经从A柱子来到了C柱子。

讲的有点啰嗦了，其实是想尽可能地把东西表达清楚。

接下来话不多说，直接上代码。
在这里我采用的是递归来实现（似乎还可以通过堆栈来实现？)

void move(int n,char from,char buffer,char to){
        //如果是最上面的盘子，可以直接挪动
    if(n == 1){
        printf("将第%d个盘子，从%c柱移动到%c柱\n",n,from,to);
    }else{
                //如果不是最上面的盘子，要挪动就要叫人
        move(n-1,from,to,buffer);
        printf("将第%d个盘子，从%c柱移动到%c柱\n",n,from,to);
        move(n-1,buffer,from,to);
    }   
}

int main(void){
    int n = 6;
    char from = 'A';
    char buffer = 'B';
    char to = 'C';
    move(n,from,buffer,to);

    return 0;
}

结果如下：

image.png