Hanoi函数解析.doc

C语言中的经典函数递归问题----Hanoi程序的解析

在谭浩强编写的《C程序设计（第三版）》中有这样一个经典递归（红框中）程序：
(程序运行环境：Visual Stdio 2008)
#include "stdafx.h"
#include<stdio.h>
void main()
{
void hanoi(int n,char one,char two,char three);
int m;
printf("input the number of diskes:");
scanf("%d",&m);
printf("The step to move %d diskes:\n",m);
hanoi(m,'A','B','C');
getchar();
getchar();
}
void hanoi(int n,char one,char two,char three)
{
void move(char x,char y);

if(n==1)
move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
很显然，这是著名的Hanoi问题的解答程序，“Hanoi问题是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图1.1所示）。有一个老和尚想把这64个盘子从A座移到C座，但每次只允许移动一个盘子，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座。”

A B C
图 1.1
一、首先 ，我们用数学知识来分析：
1、 逆向分析：要把n个盘从A移到C，先要把(n-1)个盘从A移到B，再把第n个盘从A移到C，最后把（n-1）个盘从B移到C；这里暂时把n个盘看作一个整体。
要把（n-1）个盘从A移到B，又必须先把（n-2）个盘从A移到C，再把第（n-1）个盘从A移到B，最后把（n-2）个盘从C移到B；这里暂时把（n-1）个盘看作一个整体。
…；如此循环，直到遇到第一个盘，这是终止递归的标志，又是层层解开递归的钥匙。

从上面的分析中，我们经过观察可以得到下面的结论：
①每次移动“整体”的最后一个盘时，都须要把上面所有的盘（大于一个盘，并且把它们也看作一个整体）移动两次，而层层递推到第一个盘时，第一个盘只需移动其本身1次，（更不需移动第0个盘2次）由此，移动次数的数学表达如下：
C（ n ） = C（n-1） × 2 ＋ 1这里所有的“1”指的是移动最后一个盘。
；
C（n-2） = C（n-3） × 2 ＋ 1；
∶
∶
C( 2 ) = C(1) × 2 ＋ 1；
C(1) = 1
这样，迭代求出：C（n）=。
②前后两次“整体”移动的方法基本是一样的（此时完全可以忽略底座的状态），这就只需在编程时控制好A、B、C座的位置，以便在函数执行相同动作时，可以得到不同的效果。

2、顺向分析：
①移动2个盘：AàB整体”1”第一次移动到B。
、AàC、BàC整体”1”第二次移动到C。

②移动3个盘：AàC、AàB、CàB整体”1、2”第一次移动到B。
、AàC、BàA、BàC、AàC整体”1、2”第二次移动到C。

这里经过观察，我们又可以得出结论：
Ⅰ、一种移动中，两次进行的“整体”移动仅仅是字母的相同方式的变更：把A换成B，把B换成C，把C换成A。
Ⅱ、在“移动3个盘”的过程中，2次运用到了“移动2个盘”的方法。
③同样地，在移动n个盘时，我们可以自信地说，通过两次连续、依次运用前面的步骤，中间再插入AàC，便完成了所有工序。下面是图解法：
移C
N
盘
移B
N-1
盘

移C
N-1
盘

移B
N-2
盘

移C
N-2
盘

移B
N-2
盘

移C
N-2
盘

…
…
…
…
…
…
…
…
{
{
{
{
{
{
∶
∶
{
{
{
{
{
{
{

限于表达空间，这里“移C N盘”指向C移动N个盘，且每次“最后一盘”的移动被省略。由以上同样可以看出移动的总次数为C（n）=。

二、 然后，我们再运用C语言的知识来分析：
要用C语言中的递归函数来分析，首先必须明白递归函数的运作原理，以上文
的递归函数的调用为例：第一次是main函数调用：hanoi(m,'A','B','C');此时，在运
行hanoi函数时，n值全赋为m的值,one值全赋为‘A’,two值全赋为‘B’，three
值全赋为‘C’，亦即，当函数头中的变量一旦取到值时，函数内所有的变量取值随
即确定下来，而不是函数运行到那一条语句才把该句中的变量值确定下来。
所以，第一次使用Hanoi是时，有
else
{
hanoi(2,A,C,B);这里对A、B、C重新分配了在下一个hanoi函数中的位置，目的是实现从A到B的调运。下同。

move(A,C); 这里是前两层与第3层之间的运作关系
hanoi(2,B,A,C);
}
hanoi函数首先运行 “hanoi(2,A,C,B);”语句(记为3-1，它的下面两条语句记为3-2、3-3)，把3-1展开如下：

else
{
hanoi(1,A,B,C);注意：运行到这一步时仍需再一次调用hanoi函数。

hanoi(2,A,C,B); move(A,B);
hanoi(1,C,A，B)；
}
接着hanoi函数又继续运行“hanoi(1,A,B,C);”语句（记为2-1，它的下面两条语句记为2-2、2-3），把2-1展开：

if(n==1)
hanoi(1,A,B,C); move(A,C); 记为1-1，而实际上，它一步就可以完成了！

然后反推到执行2-2：move(A，B); 再到2-3：hanoi(1,C,A，B);方法同2-1语句，上文已经分析过。

再返回执行：3-2：move（A，C）； 再到3-3：hanoi(2,B,A,C);方法同3-1语句。

当调用hanoi时，要注意变量（n,one,two,three）中值的不断更新及其更新方法，以2-1为例： hanoi( n-1, one, three, two );
1 A B C

void hanoi(int n, char one, char two, char three);
这里2-1语句中变量（或表达式）的具体值已经存在，分别为1、A、B、C，在上文中我直接以常量的形式写出，是为了更直观地表达这种更新方法。这有同于赋值，却与赋值有相当的差别！读者可以自己体会。

通过上面的C语言分析，以及细致观察，我们又可以得出一些有趣的结论:
Ⅰ、文章开头程序的红框中两条move（）语句是交替执行的！下面我们用事实来说话：
把if下的move()语句替换为：
printf("hidden\n");
看看运行结果:

再把else下的move（）语句替换为：printf("hidden\n");
看看运行结果：

结果正如我们所料！
Ⅱ、事实上，我们这里的变量（one，two,three）提供的仅仅是一个临时储存位置的功能，这里临时储存的是A、B、C三个座位，且三个座位可在one，two,three三变量中按我们的要求不断更换位置！记住one,two,three并非三个座位的固定住所。而实现盘子从A座调到C座是函数hanoi的功能。void hanoi( 位置位置是函数hanoi本身的。
1, 位置 2 , 位置 3 ,位置 4)，hanoi函数实现了把位置2上的盘子调到位置4，位置3是被借用的，这是编程者所赋予hanoi函数的属性，这个属性我们是可以更改的！现在我们指定hanoi函数实现把位置4的盘子（A座）调到位置1（C座），借助位置2.然后我们重新编一下程序，结果如下：

#include "stdafx.h"
#include<stdio.h>
void main()
{
void hanoi(char one,char two,int n,char three);
int m;
printf("input the number of diskes:");
scanf("%d",&m);
printf("The step to move %d diskes:\n",m);
hanoi('C','B',m,'A');
getchar();
getchar();
}
void hanoi(char one,char two,int n,char three)
{
void move(char x,char y);
if(n==1)
move(three,one); 取m=1为特例，确定这里应填写的变量。

else
{
hanoi(two,one,n-1,three);
move(three,one);
hanoi(one,three,n-1,two);
按第n层与上面（n-1）层的关系编写。
}
}
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}

读者也可以干脆把if语句该为如下，更便于理解：
if(n＞1)
{
hanoi(two,one,n-1,three);
move(three,one);
hanoi(one,three,n-1,two);
}

else
move(three,one);

再看一下运行结果：

运行结果也完全吻合！

Ⅲ、两个“move(three,one);”语句反映的是函数hanoi从位置4到位置1的调运功能。这里的three，one对应的是函数头void hanoi(char one,char two,int n,char three)中的three，one。
即保证了函数功能与输出结果的一致性。
同样地，在开头的程序中的move（one，three）是函数hanoi从位置2到位置4的运调功能，对应的是函数头void hanoi(int n,char one,char two,char three)中的one，three。

可以看到，递归函数与我们以前所学的while循环非常类似，同时仍然有很大区别。
1、不同点：
while循环每运行一次便有一个确定的结果，而递归函数运行过程中没有确定的结果，并沿着这个不确定性层层往下套，直到遇到一把终极钥匙，又返回去层层解开这些套，最终一路解出我们所要的结果。
2、相同点：
两种函数都需要时时判断是否符合条件，当不符合时（或当符合时）循环、递归才被终止。

到现在，可能有些读者仍未明白变量one、two、three的作用，我在这里再补充几点：一开始，one在hanoi函数变量声明中的位置1，three在位置4，它们正好落在了我们要求hanoi函数的“功能特区”上，当函数执行else中的hanoi()语句时，又按我们的想法，对A、B、C在下一个hanoi函数中的位置重新分配了一下，使A、B、C落在相应的“功能特区”。这时，one，three也在特区上，它们刚好承载了相应的字母。因此，此时的one，three（即两个move()中的one、three两个move函数中的one，three是都是直接从hanoi函数头中照搬过来的，这在hanoi函数头变量的更新方法中谈及。hanoi函数头的变量直接映射到函数体中的变量，只不过在映射到hanoi()中时，变量所占位置（指位置1、2、3、4）与此同时改变了，以此满足对A、B、C的要求。而move()函数不存在这个问题，因而move()函数总是相同的，从而move()也就对应输出了hanoi函数的功能性动作。
）不仅承载了字母，还显示着hanoi函数的特定功能，当A、B、C再次进行分配时，one，three便不再显示函数功能，因为它失去了原来的特定位置。如此循环。

现在可以告诉你，上面所说的什么hanoi函数的“功能位置”是不存在的，是在我们心中认定的。当你按自己的意志让变量在hanoi()中改变着位置时， hanoi函数的功能便按你的想法悄悄地实现，说这是one，three实现的功能也并不准确，不如说这是循环对应“循环”是由递归函数的特点提供的，“对应”是通过定期改变变量位置来实现的。
的功能。对应方式可以有两种方法产生：1、hanoi(m,'A','B','C');语句中的A、C位置已经决定，那么对应方式也随之确定下来，例如文章开头的程序；2、事先在hanoi函数中想好了对应方式，那么hanoi(m,'A','B','C');中的A、C位置也随之而定，例如上文第二个程序。当然，其中还有更多细节问题供读者自己去思考。

其实，当你揭开递归函数的“庐山真面目”时，可以发现递归函数并不那么神秘抽象，你甚至可以轻松地驾驭它，而它唯一留给我们的是C语言的无穷魅力！
7