汉诺塔递归问题
发布网友
发布时间：2022-05-20 19:40
共4个回答
热心网友
时间：2023-11-07 10:53
#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设的太大，不然容易死机！想想里面的循环次数就真令人咂舌了！
参考资料：原创
热心网友
时间：2023-11-07 10:54
从左到右 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 的过程.
热心网友
时间：2023-11-07 10:55
如果是三个盘，看成三层楼
编号1,2,3
n=3时，执行else，Hannoi(n-1,a,c,b);在这时调用自己，进入递归第二层 ，再执行else，Hannoi(n-1,a,c,b);这时调用自己，进入第三层，这时因为n=1,所以程序执行if，if(n==1) Move(1,a,c);编号1移动后，跳出递归第三层，回到第二层，这就意味着n=2在 Hannoi(n-1,a,c,b);这一步执行完毕，往下执行Move(n,a,c);移动后，执行Hannoi(n-1,b,a,c);接着调用n=1时，完成后第二层执行完成，跳出，执行n=3第一层的move,这样一直循环调用，直到move被执行2的n次方减1次，完成移动。
热心网友
时间：2023-11-07 10:55
VAR n,m:integer;
FUNCTION hanoi(n:integer;x,y,z:char):integer;
BEGIN
IF n=1 THEN
begin hanoi:=1;write(x,'->',z,' ') end
ELSE hanoi:=hanoi(n-1,x,z,y)+hanoi(1,x,y,z)+hanoi(n-1,y,x,z);
END;
BEGIN
write('n = ');read(n);
m:=hanoi(n,'A','B','C');
writeln(chr(13),chr(10),'hanoi(',n,')=',m)
END.
