汉诺塔递归算法(汉诺塔规律总结口诀)
求大神讲解一下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，如果n2
那么就进行递归，如果n=1，那么就直接移动。
具体流程：
hanoi（2，a，b，c）；由于21因此进入了递归的环节中。
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）；由于31因此进入了递归的环节中。
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。
汉诺塔递归算法求详解 （研究了5天了，没有理解，如果能教会我愿支付宝付现金20元）
首先要知道汉诺塔的基本思路.
汉诺塔有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, 如果n1,则先用hanoi(n-1,a,c,b), 以c为中转将a上的n-1个碟片先移动到b上,再打印a-c,即将a上剩下最大的那个碟片移动到c, 然后再调用hanoi(n-1,b,a,c), 以a为中转将b上的碟片移动到c上.
按如此的递归逻辑下去就可以得到全部的操作过程了.
汉诺塔递归算法
hanot (n-1,b,a,c);（解释：在把B塔上的(n-1))个借助A塔移动到C塔）
这样就对了
汉诺塔递归问题
汉诺塔的递归算法与解析
从左到右 A B C 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则: 大盘子只能在小盘子的下面.
如果有3个盘子, 大中小号, 越小的越在上面, 从上面给盘子按顺序编号 1(小),2(中),3(大), 后面的原理解析引用这里的编号.
递归算法简单来说就是方法内部自己调用自己, 同时也一定有一个结束点. 如果对方法调用栈了解的话,其实是很容易理解方法的调用过程的, 就是从主线程开始调用方法进行不停的压栈和出栈操作. 方法的调入就是将方法压入栈中, 方法的结束就是方法出栈的过程, 这样保证了方法调用的顺序流. 如果跟踪递归的调用情况会发现也是如此, 到最后一定是这个方法最后从栈中弹出回到主线程, 并且结束.
栈的特点:先进后出。 比如一个方法 A 自己调用自己, 我用编号区分一下进栈过程:
A - A(1) - A(2) - A(3)
在A(3)时满足某种条件得以退出, 回到 A(2), A(2)结束回到A(1), 再回到A, 出栈过程:
A(3) - A(2) - A(1) - A
对于递归,还有一个形象的认识,就是我小时候家里有一个柜子, 柜子两端都是玻璃, 头伸进柜子看一面镜子,会看到镜子里还有镜子, 然后镜子里还有镜子, 但和递归的特点不同的是这镜子的反射是没有尽头的, 只要眼睛一直能看到底的话.
了解完递归后, 再回头来看如何用递归的方式解决汉诺塔的问题.
案例 1 - 假设只有一个盘子的时候, 盘子数量 N=1
只有一个步骤 将第1个盘子从A移动到C, 为了对比方便我这样来描述这个步骤：
步骤 盘子编号 从柱子移动 移动到柱子
1 1 A C
案例 2 - 如果有两个盘子, 盘子数量 N = 2
步骤 盘子编号 从柱子移动 移动到柱子
1 1 A B
2 2 A C
3 1 B C
案例 3 - 如果有三个盘子, 盘子数量 N = 3
步骤 盘子编号 从柱子移动 移动到柱子
1 1 A C
2 2 A B
3 1 C B
4 3 A C
5 1 B A
6 2 B C
7 1 A C
如何找出盘子移动的规律 ？
我们要做的最重要的一件事情就是永远要把最底下的一个盘子从 A 移动到 C
看看上面从1个盘子的移动到3个盘子的移动, 在移动记录中,当盘子的编号和盘子数量相同的时候他们的步骤都是从A移动到C (看加粗的部分),其它的步骤对等.
再观察第3个案例中的第 1-3 步 和 第 5-7步
第 1-3 步 目的是从 A 移动到 B 如果我们把 B 当作终点, 那么这里的第 1-3 步理解起来和 第2个案例的三个步骤完全相同, 都是通过一个柱子来移动,和第2个案例比起来在后面加括号来表示
1 1 A C ( A - B)
2 2 A B ( A - C)
3 1 C B ( B - C)
总结：将盘子B变成C即可.
第 5-7 步 目的是从 B 移动到 C 如果我们把 C 当作终点, 那么这里的 5-7 步理解起来和上面也是一样的, 和第2个案例的三个步骤也完全相同.和第2个案例比起来就是:
5 1 B A ( A - B)
6 2 B C ( A- C)
7 1 A C ( B - C)
总结: 将盘子B变成A即可
根据这个演示可以明确几点规律:
1. 当盘子只有一个的时候,只有一个动作 从 A 移动到 C 即结束.
2. 当有N个盘子的时候, 中间的动作都是从 A 移动到 C, 那么表示最下面的第N个盘子移动完毕
3. 中间动作之上都可以认为是: 从 A 移动到 B
4. 中间动作之下都可以认为是: 从 B 移动到 C
2，3，4 可以表示为
1 1 A B
2 2 A C
3 1 B C
这种结构一直在重复进行,C#不太熟悉,试着写写,就有了以下代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
class HanoiTower
{
public void MoveDisk(int DiskQuantity,string PositionA, string PositionB, string PositionC)
{
// If there's only one disk, then end.
if (DiskQuantity == 1)
{
Console.WriteLine("Move disk from position {0} to {1}.", PositionA, PositionC);
// Must return
return;
}
else
{
// Step 1 - Change B to C (A -- B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
// Step 2 - No changes (A -- C)
MoveDisk(1, PositionA, PositionB, PositionC);
// Step 3 - Change B to A (A -- C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
}
}
static void Main(string[] args)
{
HanoiTower hanoi = new HanoiTower();
Console.WriteLine("Please input Disk Quantity:");
int DiskQuantity = Convert.ToInt32(Console.ReadLine());
hanoi.MoveDisk(DiskQuantity, "A", "B", "C");
Console.ReadKey();
}
}
}
结合上面的分析,最重要的就是这里的3步交换动作, 中间从 A到C的动作是最底层盘子的最终操作.
//Step 1 - Change B to C (A -- B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
//Step 2 - No changes (A -- C)
MoveDisk(1, PositionA, PositionB, PositionC);
//Step 3 - Change B to A (A -- C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
至于第1个参数为什么是DiskQuantity - 1,或者1 大家再回到上面看看是不是所有的步骤都是.. 1. 1,2,1. 1,2,1,3,1,2,1 这种以盘子数对称的结构,而它前后都是重复1,2,1 的过程.
汉诺塔递归算法是什么？
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，不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
以上内容参考：百度百科-递归公式