hanoi塔的递归算法

A. 汉诺塔递归算法是什么

如下：

1、汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

2、抽象为数学问题：从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

算法分析（递归算法）：

实现这个算法可以简单分为三个步骤：把n-1个盘子由A 移到 B；把第n个盘子由 A移到 C；把n-1个盘子由B 移到 C。从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步。

1、中间的一步是把最大的一个盘子由A移到C上去。

2、中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上。

3、中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上。

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.代码如您写的。

C. C++ hanoi塔函数递归问题

程序就会按照你带的参数去继续调用void hanoi(int n, char one, char two, char three)函数了。这就是调用。以下是我曾经分析过的这个问题。供你参考。附上源程序。

//解决汉诺塔的核心概念：需要将大的在下小的在上的n个盘子从A借助B移动到C，
//全部还是按照大的在下小的在上的原则。
//可以分解为简单的3个过程，以实现递归
//过程0：A的N个盘子借助B移动到C； //move(n,a,b,c); //PS1//备注1
//过程1：A的N-1个盘子借助C移动到B； //move(n-1,a,c,b);
//过程2：A的最后一个盘子直接移动到C //printf("%c->%c\n",a,c); //简化
//过程3：B的N-1个盘子借助A移动到C； //move(n-1,b,a,c);
//过程3实际上回到了假定的过程0 //move(n-1,b,a,c);//和PS1相比:参数AB位置发生变化，n变为n-1
//于是，开始了新一轮的过程1、2、3，并以此实现递归
//本程序关键在于理解递归算法
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long count;
void move(int n,char a,char b,char c)
{
if(n==1)
{
printf("\t第%d次移动%c->%c\n",++count,a,c); //当n只有1个的时候直接从a移动到c
}
else
{
move(n-1,a,c,b); //第n-1个要从a通过c移动到b
printf("\t第%d次移动%c->%c\n",++count,a,c); //用于显示移动的每一步//上面一个函数运行后的最后一个盘的移动路线
move(n-1,b,a,c); //n-1个移动过来之后b变开始盘，b通过a移动到c，这边很难理解//
}
}

int main(void)
{
int n;
count=0;
printf("请输入要移动的圆盘数：");
scanf("%d",&n);
move(n,'a','b','c');
printf("%d个圆盘共需移动%d次\n",n,count);
return(0);
}
//本人也新学，供参考

D. 汉诺塔的算法

算法介绍：当盘子的个数为n时，移动的次数应等于2^n–1。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A、B、C；

若n为奇数，按顺时针方向依次摆放A、C、B。

所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

汉诺塔问题也是程序设计中的经典递归问题。

(4)hanoi塔的递归算法扩展阅读

由来：

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：18446744073709551615秒。

这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

E. (Hanoi)汉诺塔的递归问题

哈哈！正好我们上周实训也是做的汉诺塔演示程序，不过是C#。其实这里的循环问题你一定要用抽象思维，n就是一个变量，按盘子移动的规律设计代码的！主要是计算了盘子的起点和终点坐标，再用的递归算法。
不知道我这样讲，有没一点帮助哈！

F. 汉诺塔递归算法

1个只要1次2个碟子要3次3个要7次归纳法可以推得复杂度为2^n-1这个可以证明的，只是证明很复杂。

G. 求大神讲解一下C语言汉诺塔递归算法的简易理解

一开始我接触汉诺塔也是很不解，随着代码量的积累，现在很容易就看懂了，因此楼主主要还是对递归函数的理解不够深刻，建议你多写一些递归程序，熟练了自己就能理解。
圆盘逻辑移动过程+程序递归过程分析
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因此进入了递归的环节中。
<1>执行hanoi（1，a，c，b）：这里就是刚才的步骤（1），代表借助c柱子，将a柱子上的 1个圆盘（盘1）移动到b柱子，其实由于是n=1，此时c柱子并没被用到，而是直接移动了。
<2>执行hanoi（1，a，b，c）：这是步骤（2），借助b柱子，将a柱子上的一个圆盘（盘2）移动到c柱子上。这里由于也是n=1，也并没有真正借助b柱子，直接移动的。
<3>执行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因此进入了递归的环节中。
<1>执行hanoi(2,a,c,b):这里代表刚才的步骤（1），将两个盘子（盘1、盘2）从a移动到b，中间借助c。根据n=2的分析过程，必然是能够达到我们的目的。
<2>执行hanoi（1，a，b，c）：现在a上只有一个盘子（盘3），直接移动到c上面即可。
<3>执行hanoi（2，b，a，c）：此时对应步骤（3），剩下的目标就是将b上的两个盘子，借助a移动到c上。那么同样根据n=2的移动过程，必然能达到目的。

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

H. 如何理解汉诺塔的递归

递归就是一层套一层，函数自己调用自己，直到出现限制条件为止。函数自己调用自己，可以理解为sum = sum + M；给这个加一个循环 是不是就可以求出总和了；意思是一样的自己调自己，汉诺塔这个比较深，你可以用递归的方式去求所有数字的和，多学几遍你自然就会了。1. 汉诺塔可以理解为一个移动塔的游戏，把一个n层的塔从一个柱子移动到另一个柱子上2.这就是汉诺塔递归原型 hannuota（n, A,C）--n层的塔从A柱移动到C柱；每次必须回归到这个原型才算一次递归完成！<就像1-100的递归累加f(n)=f(n-1)+n； 此时f(n)是递归原型，回归到f(n-1)>3.中间需要借助一个柱子B，汉诺塔原型写成hunnuota(n,A,B,C)--n层塔从A柱借助B柱移动到C柱，这一步应该能够理解吧；4.递归都要求有一个出口，也即是控制条件，当n=1时直接把塔从A移动到C即可，这就是出口<如果n=2则需要移动两次才行，无法一次完成，不能出去>5.n>1时,这一步是理解汉诺塔递归的关键，必须形成n-1层往C柱移动的形式，分为三步：a. n层无法一次移动，那么可以理解为先把A上面的n-1层移动到B柱<hannuota(n-1,A,C,B)>-------b A柱剩下第n层的塔移动到C，C 然后形成B柱上的n-1层移动到C柱上--<hannuota（n-1,B,A,C）此时已经形成了递归的原型 不同的只是中间借助的柱子不同罢了,hanoi(n, a, b, c)这个函数的作用是：将n个金片从a移动到c（通过b）。递归完成

I. 证明hanoi塔问题的递归算法与非递归算法实际上是一回事

证明：设解决汉诺塔问题的函数为Hanoi（n，A，B，C）
用数学归纳法即可证明上述问题
当n=1和n=2时容易直接验证。设当k<=n-1时，递归算法和非递归算法产生完全相同的移动序列。考察k=n时的情形。
将移动分为顺时针移动（S），逆时针移动（N）和非最小圆盘塔间的移动（F）三种情况。
（1）当n为奇数时，顺时针非递归产生的移动序列为S,F,S,F,······S，逆时针非递归算法产生的序列为N,F,N,F,······N。
当n为偶数时，顺时针非递归产生的移动序列为N,F,N,F,······N，逆时针非递归算法产生的序列为S,F,S,F,······S。
（2）当n为奇数时，顺时针递归算法Hanoi（n，A，B，C）产生的移动序列为
Hanoi（n-1，A，C，B）产生的移动序列，F，Hanoi（n-1，C，B，A）产生的移动序列
其中，Hanoi（n-1，A，C，B）Hanoi（n-1，C，B，A）均为偶数圆盘逆时针移动问题。由数学归纳法知，它们产生的移动序列均为S,F,S,F,······S。因此Hanoi（n，A，B，C）产生的移动序列为S,F,S,F,······S。
当n为偶数时，顺时针递归算法Hanoi（n，A，B，C）产生的移动序列为
Hanoi（n-1，A，C，B）产生的移动序列，F，Hanoi（n-1，C，B，A）产生的移动序列
其中，Hanoi（n-1，A，C，B）Hanoi（n-1，C，B，A）均为奇数数圆盘逆时针移动问题。由数学归纳法知，它们产生的移动序列均为N,F,N,F,······N。因此Hanoi（n，A，B，C）产生的移动序列为N,F,N,F,······N。
当n为奇数和偶数时的逆时针递归算法也类似。
由数学归纳法可知，递归算法和非递归算法产生相同的移动序列。

J. 汉诺塔问题具体是怎么递归的

有a，b，c三个柱子
hanoit(n-1,a,c,b);//先借助c，把上面n-1个从a移动到b
move(a,c);//把第n个从a移动到c
hanoit(n-1,b,a,c);//把上面n-1个从b移动到c
移动第n个要先移动前n-1个。