不懂汉诺塔还能继续学编程吗 关于汉诺塔问题C语言

写在前面：我是菜鸡，文章都是主观的我认为，不保证正确性，我是菜鸡，求轻喷

汉诺塔问题：相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

好，然后很显然嘛，我是菜鸡，解决不了这个问题。那么去搜答案嘛。一搜就出来了，一大堆，按着几个推送在前面的进去……培训班广告。行嘛，继续再往下找。一个看起来就很厉害的老师开始分析：同学们，看看汉诺塔问题。刚才我们已经进行了递归的学习，相信同学们已经熟练掌握了技巧，我们可以把这个问题简化为三个步骤。

(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；

(2)将A杆中剩下的第n号盘移至C杆；

(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。

说完然后就开始写代码了，然后就写完了，然后就是牛逼牛逼！看的我是一脸懵逼。我接着去搜好几个，讲法完全雷同，但并没有人仔细讲解到底是怎么实现的，具体递归的步骤演示，就是强调上面三个步骤，然后代码就出来了。我的感受，就是仿佛人类从原始社会一跃到了登上火星。以前有人调侃说，数学课上弯腰捡起来一支笔，从此一个学期的数学课都在坐飞机——我当时的内心就是这样，区别是我连腰都没有弯，一直死盯着黑板。

void Move(char pos1, char pos2){printf("%c->%c ", pos1, pos2);}

void Hanoi(int n, char pos1, char pos2, char pos3){if (1 == n){Move(pos1, pos3);}else{Hanoi(n - 1, pos1, pos3, pos2);Move(pos1, pos3);Hanoi(n - 1, pos2, pos1, pos3);}}

int main(){int n = 0;char pos1 = 'A';char pos2 = 'B';char pos3 = 'C';Hanoi(1, pos1, pos2, pos3);Hanoi(2, pos1, pos2, pos3);printf("\n");Hanoi(3, pos1, pos2, pos3);printf("\n");Hanoi(4, pos1, pos2, pos3);printf("\n");return 0;}把源码贴上来，为什么贴，大家懂得都懂哈。不知道直接复制粘贴好不好用。

然后我研究这玩意研究了半天，当然我最后研究得应该可以说是七七八八了。天才就略过我吧，可能我是真的蠢。我研究的结论是，你能搜到的一大半对这个问题的解读是属于，老手不用听一点就会，新手听不懂一脸茫然。起码我就是这么觉得：我前几次看这代码，连递归从哪里进，从哪里出来都不知道。

言归正传（首先你接受我比较蠢的这个设定，接下来就好看多了）：

在开始之前，理解一下大家都强调的那三个步骤。我觉得那个我还是能理解的，就是把塔分成两块嘛，一块移到B，最下层移到C，再把B的移到C。那么我遇到的第一个问题，抛开递归步骤不谈——我确实未能领会，按照别人说的，只是单纯重复强调的那三个步骤。那开头或者结尾，不论算的塔有几层，都该有一步是完全一样的，开头都应该是A->B,结束都该是A->C。但代码随便跑一下显然不是这么回事：

你发现是交错着的。这个要解释起来很简单，你一块的时候，直接从A柱就移动到C柱了，而你两块的时候必须经过B柱的周转。有些人可能会说，三块也从B柱周转就行啊，三块的时候若你最上面一块，移动到B柱，那同样的步数，你最下面一块只能放在B柱，而不是C柱上。也就是说，塔层为单数的时候第一步是A到C，最后一步也是A到C；而双数的时候，第一步是A到B,必以B到C收尾。而代码也是在Hanoi(n - 1, pos1, pos3, pos2)这一步在反复递归中，不停地交换位置，实现这一点的。

我不知道为什么没人提这点，可能大家都默认知道？但是我比较笨，不太理解。第一个写出代码的人，应该是考虑过这个问题的，而不是单纯按着那三个步骤，然后就哗哗哗流畅地写出来了。很巧妙！

第二个问题就是怎么递归的，说得再通俗一点，就是程序运行的顺序是怎么样的？这个简单，逐语句调试，一条条跑。以及它为什么是这个顺序。在我没看到下面这张图，和另外一篇很角落才现的文章前，我不理解，它的递归为什么是这么一个运行逻辑。

三块的示例

下⾯我们以n=3为例来详细地解释⼀遍，这⾥我们需要⽤到⼀点栈的概念，简单说就是每⼀次递归之前程序都会将现在的数据储存在栈中（从下往上存储），递归结束后会依次从上往下调出数据，之后程序就会返回到这个数据存储的地⽅向后继续执⾏，此时栈中的这⼀条数据也会消失。当程序执⾏到第⼀个hanoi函数时，显然n！=1，执⾏else的部分，此时hanoi函数中的变量值为hanoi（3,A,B,C），在执⾏第8⾏语句之前，⾸先要将其存放到栈中。经过下⼀⾏的递归后，四个值变为hanoi（2，A，C，B）。此时栈中的数据为

第⼀次 hanoi(2,A,C,B)上面初始 hanoi(3,A,B,C)下面

再运行一次，n为1，执行printf的语句。再调用hanoi2执行完消失，然后再是hanoi1执行完结束。也就是有的人解释说“跳回”，这里为什么跳回的原因。

我再用n=4一步步来走一遍，主函数开始就不用看了，直接从hanoi开始，主要介绍n值的变化以及程序跑的顺序：

这里进去的是n=4，if判断非，执行else第一步的hanoi，执行完后这里n=3，再回去if判断，再回第一步hanoi，n=2，再判断，回来这时候n=1，执行Move：

move就上边那玩意，move执行完之后，第一步的hanoi语句就暂告结束，但它还储存着n=2、3、4的值。按顺序，先从n=2开始。一二三步那里，就继续往下走，执行第二步的move。第三步，也就是第二次的hanoi，此时n值变为1，执行if的是，也就是move。储存是第一步的hanoi储存的（if判断是非，按顺序下来就是第一句hanoi而不是第二句），那么每次还得回到第一步hanoi结束的位置。这时候n=2的已经弄完了，排除出栈，继续n=3。执行move，再来到第二条hanoi，n值变为2，判断失败再回来，变为1，执行判断成功后的语句。因为上边还有一条n值变为2，没有处理，因此再回到第一条hanoi的时候，首先调用它，也就是n值仍然为2。接着move，再走n就变为1，执行if成功。

最复杂的n=4的时候。首先还是跳回取n=4执行move，紧随其后遍历第二条hanoi直至n为1，执行if成功。n=2再次出现在第一句hanoi完成之后，执行move，执行第三步后，n变为1，执行if成功后。 n=3再次出现在第一句hanoi完成之后，执行move，执行第三步后，n变为2，再判断一次后，执行一次hanoi第一句就if成功。再来一次从第一句hanoi结束后的n=2，因为你上一步n=3第一次变为2的时候if是失败的，它是栈里的最后一个。

叙述可能很复杂繁琐，但胜在一步步地说。反正我写完是印象深刻了。目的也达到了，希望能帮到人，哪怕一两个也好。

最后说下递归，当你发现问题能从一个大问题不断拆分成两个时，而拆分的办法又有迹可循，就是如此。