递归算法汉诺塔

⑴ 求大神讲解一下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。

⑵ 汉诺塔递归算法

汉诺塔
递归算法
Hanoi(int
n,char
Start,Middle,End)
begin
if
n=1
then
输出Start->End
else
begin
Hanoi(n-1,Start,End,Middle);
//要把Start的盘子借助middle移动到End
先把n-1个盘子由start移到middle
//这步做完后
Start上
n-1个盘子移到中转盘
Middle上
输出
Start->End;
//把Start上最后一个盘子移到End
Hanoi(n-1,Middle,Start,End);
end
end

⑶ 用递归法求汉诺塔问题 求解

c1、c2都是临时变量，分别代表从A移到B时移动了几次，以及从B移动到C时移动了几次，两者相加再加1，就是从A移动到C的移动次数。
它们的赋值就是通过递归调用得到啊，c1 = move( n-1, A, C, B )...

⑷ 汉诺塔递归算法是什么

hanot (n-1,b,a,c);（解释：在把B塔上的(n-1))个借助A塔移动到C塔）

为了实现 n个盘从 借助c 从a 移动到 b

思路如下：

首先考虑极限当只有一个盘的时候，盘直接从 a -> b即可。

当有2个盘的时候，把1号盘从a -> c 然后 把2号盘 a->b 再 把 2好盘从 c - > b。

当有n个盘的时候，把 n-1个 盘 借助 b 移动到 c 然后将 n号盘从 a -> b。

这时候只要将 n-1想办法从c移动到 b 借助 a 那么就可以先把 n-2个盘借助b移动到a。

递归，就是在运行的过程中调用自己。

构成递归需具备的条件：

1，子问题须与原始问题为同样的事，且更为简单；

2，不能无限制地调用本身，须有个出口，化简为非递归状况处理。

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

以上内容参考：网络-递归公式

⑸ 汉诺塔递归问题

#include <fstream>
#include <iostream>
using namespace std;
ofstream fout("out.txt");
void Move(int n,char x,char y)
{
fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}
int main()
{
fout<<"以下是7层汉诺塔的解法:"<<endl;
Hannoi(7,'a','b','c'); //调用
fout.close();
cout<<"输出完毕！"<<endl;
return 0;

汉诺塔使用递归的方法来实现的
可能你对递归还没理解透，反正记住，程序总是一步一步的按顺序执行，有调用函数就先在调用的地方设个断点，转入函数执行，执行完了又返回断点，万变不离其宗！

程序执行的顺序
Hannoi(7,'a','b','c');这里调用函数，转入函数执行并传入参数n=7

第一步，执行判断语句，根据n的值进入else执行
第二步，执行Hannoi(n-1,a,c,b);这时是调用函数本身，也就是所谓的递归了，你看传入的值n-1，相当于传入n=6，还有a,c,b,的值，这个要注意顺序，在调用的时候a,c,b的值是第一次传入的值
第三步，执行Hannoi(int n,char a,char b,char c)函数，这点能理解吧，这次传入的值n=6了，但是a,b,c,的值相对于第一次的值有改变了哦，可以理解成，a(2)=a(1),b(2)=c(1),c(2)=b(1),这里括号里代表函数调用的次数，其实这里最容易弄混的就是，a,b,c的值，自己用本子把每次传入的值的a,b,c按传入顺序列出来，会容易理解些
同样，执行判断，n>1进入else,按顺序执行，先执行Hannoi(n-1,a,c,b);然后又是调用本身，注意传入的值，是a(2),c(2),b(2),又转入去执行Hannoi(int n,char a,char b,char c)函数,这时接收的值a(3)=a(2),b(3)=c(2),c(3)=b(2)，就像在兜圈子是吧，没错。后面你自己做张表来理一下。
这样兜圈子直到n=1。你看Hannoi(n-1,a,c,b);每次n都是减了1的，所以n-1次递归的时候，就直接执行if(n==1)里面的了，终于有所改变了是吧，他执行的是Move(1,a,c); 也就是输出函数，执行完Move(int n,char x,char y) 返回原来的调用的那个断点。继续向后。没有语句了，就返回上次调用的函数，上次调用Hannoi(int n,char a,char b,char c)是谁呢，就是n-2次的Hannoi(int n,char a,char b,char c)中的Hannoi(n-1,a,c,b);调用的他啊，返回到这里，继续向后又遇到Move(n,a,c); 这里不用讲解了吧，输出后返回来，继续向后执行Hannoi(n-1,b,a,c); 新的递归开始了，看你再列个新的表理一下呢，注意传入的值和他的顺序，还有n的值这时是多少。

其实我的讲解你可能看的也不是很清楚，关键是要理解到递归他无非就是调用自己，调用完返回就是返回上次调用的地方，也是他自己，只是俩次的函数使用中的值是不一样的，这个值呢，最好拿笔记下来，并写个次数才容易理解和分析。

这递归程序很经典，值得研究，你会发现他是如此的巧妙，太棒了！建议测试的时候不要把n设的太大，不然容易死机！想想里面的循环次数就真令人咂舌了！

⑹ 汉诺塔问题的递归算法流程图

关键是第一步移法，奇数层的说，3层在第一柱，后两根柱数数：123。所以，第一块应放在第二根柱，4层，第一块放第三柱。...........奇数层第一块放第二柱，偶数层第一块放第三柱。

⑺ 汉诺塔递归算法是什么

汉诺塔递归算法是：f（n）=2^n-1。

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

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

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的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亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

⑻ 汉诺塔递归算法是什么

如下：

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上。

⑼ 递归算法 汉诺塔 演示

整理分析结果：把第1步中化简问题的条件作为递归 结束条件，将第3步分析得到的算法作为递归算法。
定义函数movedisc( n，fromneedle，toneedle，usingneedle)。将 fromneedle 杆上的 N 个圆盘，借助 usingneedle 杆，移动到 toneedle 杆上。
移动N个圆盘的递归算法描述如下：
movedisc ( n，fromneedle，toneedle，usingneedle )
{ if ( n==1 ) 将 n 号圆盘从 fromneedle 上移到 toneedle;
else {
① movedisc ( n-1，fromneedle，usingneedle，toneedle )
② 将 n 号圆盘从 fromneedle 上移到 toneedle;
③ movedisc ( n-1，usingneedle，toneedle，fromneedle )
}
}

下面是程序
int i=0; /* 移动圆盘数量计数器 */
main( )
{ unsigned n;
scanf ("%d", &n);
movedisc ( n,’a’,’b’,’c’); /* 将A上的N个圆盘借助C将移动到B上 */
printf( "\t Total: %d\n", i );
}
movedisc ( n, fromneedle, toneedle, usingneedle )
unsigned n;
char fromneedle, toneedle, usingneedle;
{ if ( n == 1 )
printf("%2d-(%2d): %c ==> %c\n",++i, n,fromneedle,toneedle);
else {
movedisc ( n-1, fromneedle, usingneedle, toneedle );
printf("%2d-(%2d): %c ==> %c\n",++i, n,fromneedle,toneedle);
movedisc ( n-1, usingneedle, toneedle, fromneedle );
}
}

⑽ 关于汉诺塔问题的递归算法 算法如图 嗯 我看不懂if语句以后的算法 if(n){hanoi(n-1

递归方法最重要的清楚递归逻辑，也就是func(n)函数的含义。
汉诺塔的逻辑就是，先想办法把上面n-1个块挪到中间，再挪最底下那个到右侧，最后再把n-1个块挪到右侧。hanoi(n,x,y,z)的含义，就是把n个块从x挪到z上，可以利用中间柱子y。
使用递归的时候，看清楚最上层逻辑就好，不要纠结递归走到下一层的具体步骤。