汉诺塔递归算法求详解 （研究了5天了，没有理解，如果能教会我愿支付宝付现金20元）

#include
int main()
{
int hanoi(int n, char a, char b, char c);

int n;

printf("Please input the number of diskes:");
scanf("%d",&n);

hanoi(n, 'A', 'B', 'C');
}

int hanoi(int n, char a, char b, char c)
{

if(n==1)
{
printf("%c-->%c\n",a,c);
}
else
{
hanoi(n-1, a, c, b);
printf("%c-->%c\n",a,c); //这三步我道是怎么回事，就是不知道具体是怎么实现的 求解释，
hanoi(n-1, b, a, c);
}

return 0;
}
本人QQ：1451952033

首先要知道汉诺塔的基本思路.
汉诺塔有3根柱子. 为什么要有3根呢? 那是因为要直接使一个柱子上的碟片全部移动到另一根柱子是不行的,必须要通过第三根柱子来中转一下.
这种中转思路就是关键了.
具体来说,如果我们要把A柱子上的碟片移动到C柱子上,那么首先我们可以通过"某种方式"将A柱子上除了最底下的碟片以外的所有碟片移动到B柱子上去,也就是拿B柱子当中转. 然后下一步就可以直接把A柱子上最底层的那张碟片移动到C柱子上了. 最后,我们再以同样的方式,将B柱子上剩下的那堆碟片以同样的"某种方式"移动到C上. 总体来看,我们就完成了A->C的碟片移动操作.

那么剩下的问题就是,这"某种方式"是什么呢? 其实思考一下可以发现,在进行这"某种方式"的时候,除去A上最大的那个,其余碟片都是我们需要操作的, 这个时候由于A是最大,其他的碟片对他来说移动都没有限制的(都会比他小). 那么我们就可以暂时忽视这个最大的碟片.

以上面的例子来说,我们要移动A柱子上除了底层之外的所有碟片到B柱上,就可以暂时忽略掉A上最大的那个碟片. 发现没有, 这个时候我们的问题变成是: 将A上的所有碟片(因为已经忽视掉了最大的那个了)移动到B上,C可以作为转接(因为上面没有碟片).

这一步意味着我们把一个n个碟片的汉诺塔问题转化成了n-1个碟片的汉诺塔问题,从而这里面就包含了递归意义.

最后说回到你的程序. 函数hanoi(n,a,b,c)正是这样一个意味: 打印将a柱子上的n个碟片以b为中转移动到c上的操作步骤. 而可以看到,在执行这个函数的时候,如果n=1,那么由于只有一个碟片,可以直接打印a->c, 如果n>1,则先用hanoi(n-1,a,c,b), 以c为中转将a上的n-1个碟片先移动到b上,再打印a->c,即将a上剩下最大的那个碟片移动到c, 然后再调用hanoi(n-1,b,a,c), 以a为中转将b上的碟片移动到c上.
按如此的递归逻辑下去就可以得到全部的操作过程了.

搜一下：汉诺塔递归算法求详解 （研究了5天了，没有理解，如果能教会我愿支付宝付现金20元）