求汉诺塔C递归算法详细解答

求C语言汉诺塔源码（递归和非递归都要）~

递归算法是我前些天写的，非递归是刚才找的，里面含递归和非递归。\x0d\x0a递归算法：\x0d\x0a#include \x0d\x0a//递归求汉诺塔问题\x0d\x0avoid hanoi(int n, char A, char B, char C, int *time)\x0d\x0a{\x0d\x0aif (n>=1)\x0d\x0a{\x0d\x0a hanoi(n-1, A, C, B, time);\x0d\x0a move(A, C);\x0d\x0a (*time)++;\x0d\x0a hanoi(n-1, B, A, C, time);\x0d\x0a }\x0d\x0a}\x0d\x0a//打印出每一步的路径\x0d\x0avoid move(char a, char c)\x0d\x0a{\x0d\x0aprintf(" %c-->%c
", a, c);\x0d\x0a}\x0d\x0a\x0d\x0aint main(void)\x0d\x0a{\x0d\x0aint n, time = 0;;\x0d\x0aprintf("请输入汉诺塔的盘数:");\x0d\x0ascanf("%d", &n);\x0d\x0aprintf("%d个盘的汉诺塔移动方法是：", n);\x0d\x0aprintf("
");\x0d\x0ahanoi(n, 'A', 'B', 'C', &time);\x0d\x0aprintf("移动了%d次
", time);\x0d\x0asystem("pause");\x0d\x0areturn 0;\x0d\x0a}\x0d\x0a\x0d\x0a非递归算法：\x0d\x0a#include \x0d\x0a\x0d\x0a#define MAXSTACK 10 /* 栈的最大深度 */\x0d\x0a\x0d\x0aint c = 1; /* 一个全局变量，表示目前移动的步数 */\x0d\x0a\x0d\x0astruct hanoi { /* 存储汉诺塔的结构，包括盘的数目和三个盘的名称 */\x0d\x0aint n;\x0d\x0achar x, y, z;\x0d\x0a};\x0d\x0a\x0d\x0avoid move(char x, int n, char y) /* 移动函数，表示把某个盘从某根针移动到另一根针 */\x0d\x0a{\x0d\x0aprintf("%d-> %d from %c -> %c
", c++, n, x, y);\x0d\x0a}\x0d\x0a\x0d\x0avoid hanoi(int n, char x, char y, char z) /* 汉诺塔的递归算法 */\x0d\x0a{\x0d\x0aif (1 == n)\x0d\x0amove(x, 1, z);\x0d\x0aelse {\x0d\x0ahanoi(n - 1, x, z, y);\x0d\x0amove(x, n, z);\x0d\x0ahanoi(n - 1, y, x, z);\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0avoid push(struct hanoi *p, int top, char x, char y, char z,int n)\x0d\x0a{\x0d\x0ap[top+1].n = n - 1;\x0d\x0ap[top+1].x = x;\x0d\x0ap[top+1].y = y;\x0d\x0ap[top+1].z = z;\x0d\x0a}\x0d\x0a\x0d\x0avoid unreverse_hanoi(struct hanoi *p) /* 汉诺塔的非递归算法 */\x0d\x0a{\x0d\x0aint top = 0;\x0d\x0a\x0d\x0awhile (top >= 0) {\x0d\x0awhile (p[top].n > 1) { /* 向左走到尽头 */\x0d\x0a push(p, top, p[top].x, p[top].z, p[top].y, p[top].n);\x0d\x0a top++;\x0d\x0a}\x0d\x0aif (p[top].n == 1) { /* 叶子结点 */\x0d\x0a move(p[top].x, 1, p[top].z);\x0d\x0a top--;\x0d\x0a}\x0d\x0aif (top >= 0) { /* 向右走一步 */\x0d\x0a move(p[top].x, p[top].n, p[top].z);\x0d\x0a top--;\x0d\x0a push(p, top, p[top+1].y, p[top+1].x, p[top+1].z, p[top+1].n);\x0d\x0a top++;\x0d\x0a}\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0aint main(void)\x0d\x0a{\x0d\x0aint i;\x0d\x0aprintf("递归:
");\x0d\x0ahanoi(3, 'x', 'y', 'z');\x0d\x0aprintf("非递归:
");\x0d\x0astruct hanoi p[MAXSTACK];\x0d\x0ac = 1;\x0d\x0ap[0].n = 3;\x0d\x0ap[0].x = 'x', p[0].y = 'y', p[0].z = 'z';\x0d\x0aunreverse_hanoi(p);\x0d\x0a\x0d\x0areturn 0;\x0d\x0a}

一开始我接触汉诺塔也是很不解，随着代码量的积累，现在很容易就看懂了，因此楼主主要还是对递归函数的理解不够深刻，建议你多写一些递归程序，熟练了自己就能理解。
圆盘逻辑移动过程+程序递归过程分析
hanoi塔问题, 算法分析如下，设a上有n个盘子，为了便于理解我将n个盘子从上到下编号1-n，标记为盘子1，盘子2......盘子n。
如果n=1，则将“ 圆盘1 ” 从 a 直接移动到 c。
如果n=2，则：
（1）将a上的n-1（等于1）个圆盘移到b上，也就是把盘1移动到b上；
（2）再将a上 “盘2” 移到c上；
（3）最后将b上的n-1（等于1）个圆盘移到c上，也就是第（1）步中放在b上的盘1移动到c上。
注意：在这里由于超过了1个盘子，因此不能直接把盘子从a移动到c上，要借助b，那
么 hanoi（n，one，two，three）的含义就是由n个盘子，从one移动到three，如果n>2
那么就进行递归，如果n=1，那么就直接移动。
具体流程：
hanoi（2，a，b，c）；由于2>1因此进入了递归的环节中。
执行hanoi（1，a，c，b）：这里就是刚才的步骤（1），代表借助c柱子，将a柱子上的 1个圆盘（盘1）移动到b柱子，其实由于是n=1，此时c柱子并没被用到，而是直接移动了。
执行hanoi（1，a，b，c）：这是步骤（2），借助b柱子，将a柱子上的一个圆盘（盘2）移动到c柱子上。这里由于也是n=1，也并没有真正借助b柱子，直接移动的。
执行hanoi（1，b，a，c）：这是步骤（3），将b上的一个盘子（盘1）移动到c
函数中由于每次调用hanoi的n值都是1，那么都不会进入递归中，都是直接执行了mov移动函数。
如果n=3，则：（倒着想会想明白）移动的倒数第二部，必然是下面的情况
（1）将a上的n`-1（等于2）个圆盘移到c上，也就是将盘1、盘2 此时都在b柱子上，只有这样才能移动最下面的盘子（盘3）。那么由于现在我们先忽略的最大的盘子（盘3），那么我们现在的目标就是，将两个盘子（盘1、盘2）从a柱子上，借助c柱 子，移动到b柱子上来，这个过程是上面n=2的时候的移动过程，n=2的移动过程是“2 个盘子，从柱子a，借助柱子b，移动到柱子c”。现在是“2个盘子，从柱子a，借助柱子 c，移动到柱子b上”。因此移动过程直接调用n=2的移动过程就能实现。
（2）将a上的一个圆盘（盘3）移到c。
（3）到这一步，由于已经将最大的盘子（盘3）移动到了目的地，此时无论后面怎么移动都不需要在用到最大的那个盘子（盘3），我们就先忽略他，剩下的目标就是将b上面的n-1个盘子（盘1、盘2）移动到c上，由于a上没有盘子了，此时要完成上面的目标，就要借助a盘子。最终达到的目标就是将b上的2个盘子，借助a移动到c上，这个过程就是当n=2时分析的过程了，仅仅是最开始的柱子（b柱子）和被借助的柱子（a柱子）不同了。所以直接调用n=2时候的过程就能股实现了。
具体执行过程：
hanoi（3，a，b，c）；由于3>1因此进入了递归的环节中。
执行hanoi(2,a,c,b):这里代表刚才的步骤（1），将两个盘子（盘1、盘2）从a移动到b，中间借助c。根据n=2的分析过程，必然是能够达到我们的目的。
执行hanoi（1，a，b，c）：现在a上只有一个盘子（盘3），直接移动到c上面即可。
执行hanoi（2，b，a，c）：此时对应步骤（3），剩下的目标就是将b上的两个盘子，借助a移动到c上。那么同样根据n=2的移动过程，必然能达到目的。

最终实现了3个盘子从a，借助b移动到了c。

Hanoi塔问题, 算法分析如下，设A上有n个盘子。
如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
（1）将A上的n-1（等于1）个圆盘移到B上；
（2）再将A上的一个圆盘移到C上；
（3）最后将B上的n-1（等于1）个圆盘移到C上。
如果n=3，则：
A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：
（1）将A上的n`-1（等于1）个圆盘移到C上。
（2）将A上的一个圆盘移到B。
（3）将C上的n`-1（等于1）个圆盘移到B。
B）将A上的一个圆盘移到C。
C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：
（1）将B上的n`-1（等于1）个圆盘移到A。
（2）将B上的一个盘子移到C。
（3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。

从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。

Hanoi塔问题中函数调用时系统所做工作

一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：

①将所有的实参、返回地址等信息传递给被调用函数保存。

②为被调用函数的局部变量分配存储区；

③将控制转移到被调用函数的入口。

从被调用函数返回调用函数前，系统也应完成3件事：

①保存被调用函数的结果；

②释放被调用函数的数据区；

③依照被调用函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。

一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i＋1层。反之，退出第i层递归应返回至上一层，即i－1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
P.S.代码如您写的。

我有 你可以把你的邮箱给我 我发给你

假设要解决的汉诺塔共有N个圆盘，对A塔上的全部N个圆盘从小到大顺序编号，最小的圆盘为1号，次之为2号，依次类推，则最下面的圆盘的编号为N。

第一步：若A塔上只有一个圆盘，即汉诺塔只有一层，则只需将这个盘从A塔上移到B塔上即可；

第二步：对于一个有N（N＞1）个圆盘的汉诺塔，将N个圆盘分成两部分：上面的N－1个圆盘和最下面的N号圆盘。解决N个圆盘的汉诺塔，可以按下面的方式进行操作：

1、将A塔上面的N－1个圆盘，借助B塔，移到C塔上；

2、将A塔上剩余的N号盘子移到B塔上；

3、将C塔上的N－1个盘子，借助A塔，移到B塔上。

如果你有 谭爷爷 de C教程 ，可以看看162页（第二版）有详解，如果没有再讲吧！

用VB来写较简单

---

乌兰察布市18699022737： 求C汉诺塔递归详细过程 - ？
迟许斯诺： 解决汉诺塔的基本思想是先把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子(初始柱子)移动到中间那个柱子上(辅助柱子),然后把最下面的盘子移动到最后一根柱子上(目标柱子).最后把剩下的盘子移动到目标柱子上.这样,...

乌兰察布市18699022737： 求汉诺塔C递归算法详细解答 - ？
迟许斯诺： Hanoi塔问题, 算法分析如下,设A上有n个盘子.如果n=1,则将圆盘从A直接移动到C.如果n=2,则:(1)将A上的n-1(等于1)个圆盘移到B上;(2)再将A上的一个圆盘移到C上;(3)最后将B上的n-1(等于1)个圆盘移到C上.如果n=...

乌兰察布市18699022737： 求真正理解汉诺塔问题的电脑大神给我解答一下,当n=3时,求用c语言编写的汉诺塔递归调用代码的详细执 - ？
迟许斯诺： 一开始我接触汉诺塔也是很不解,随着代码量的积累,现在很容易就看懂了,因此楼主主要还是对递归函数的理解不够深刻,建议你多写一些递归程序,熟练了自己就能理解.圆盘逻辑移动过程+程序递归过程分析 hanoi塔问题, 算法分析如下...

乌兰察布市18699022737： 谁给提供汉诺塔的C语言递归解法详细说明啊? - ？
迟许斯诺： //********************************************************* //比书上更好理解的汉诺塔递归算法 //********************************************************* #include <stdio.h> #include <stdlib.h> long step=1;//步数计数 /////////////////////////////////////////////// void HanNuo(long...

乌兰察布市18699022737： 求大神讲解一下C语言汉诺塔递归算法的简易理解 - ？
迟许斯诺： 第一,把a上的n-1个盘通过c移动到b.第二,把a上的最下面的盘移到c.第三,因为n-1个盘全在b上了,所以把b当做a重复以上步骤就好了.

乌兰察布市18699022737： 谁能告诉我关于汉诺塔递归算法的详细运行步骤(c\c++)? - ？
迟许斯诺： 汉诺塔的规则是把N个盘子从A柱挪到C柱(假设是这样) 那末,我们要做的就是把N-1个盘子从A柱挪到B柱,再把1个盘子从A柱挪到C柱,再把N-1个盘子从B柱挪到C柱. 当运行到N-1的时候,N就代表N-1,这时再把N-2个盘子从开始柱挪到临时柱,再把1个主子从开始柱挪到结束柱,再把n-2个柱子从临时柱挪到结束柱.不停的调用自身,直到调用的程序的N=1的时候…… 说了这些,不知道阁下懂不懂.

乌兰察布市18699022737： 【100财富求讲解达人】C语言递归汉诺塔求讲解 - ？
迟许斯诺： 递归法是一种很方便的算法,你不要太过于纠结过程 hannoi这个函数4个变量,分别是要处理的塔的层数n,和塔a,b,c;a表示原塔,b是目标塔,c是中间的塔;当n=1时,只有一层,直接移动;其余情况:先讲上面的(n-1)层塔移到c上,此处可看做原问题的子问题,即hanoi(n-1,a,c,b); 再将最底层移到b,即可.至于程序,楼上的已经改的很好了, 我就不多说了 不知这样,够明白不?

乌兰察布市18699022737： 求真正理解汉诺塔问题的编程大神回答一下,当n=3时,用c语言编写的汉诺塔递归调用代码的详细执行过程 - ？
迟许斯诺： /* 汉诺塔 hannota.c */#include<stdio.h>/* 解法:如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘子,就将B当作辅助柱.如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,...

乌兰察布市18699022737： 谁给个C语言汉诺塔递归算法及其详细注释 - ？
迟许斯诺： 源代码: #include void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle); int i=0; int main() { unsigned n; printf(＂please en...

乌兰察布市18699022737： 汉诺塔分治递归算法解释! - ？
迟许斯诺： hanoi中的参数:从A(源)通过B(中转)移动到C(目的) 先把n-1个从A通过C移动到B:hanoi(n-1,A,C,B,time); 再把最后那个从A移到C:move(A,C); 然后把那n-1个从B通过A移到C:hanoi(n-1,B,A,C,time) 注意每一步的目的是什么