web127 / 算法 / 递归算法 Hanoi(汉诺)塔问题

分享

   

递归算法 Hanoi(汉诺)塔问题

2014-06-08  web127

Hanoi(汉诺)塔问题。这是一个古典的数学问题,是一个用递归方法解题的典型例子。问题是这样的:古代有一个梵塔,塔内有3 个座A、B、C,开始时A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个老和尚想把这64个盘子从A座移到C座,但每次只允许移动一个盘,且在移动过程中在3个座上都始终保持大盘在下,小盘在上。在移动过程中可以引用B座,要求编程序输出移动的步骤。
读者是不大可能直接写出移动盘子的每一个具体步骤的,请读者实验一下按上面的规律将5个盘子从A座移到C座,能否直接写出每一步骤?
老和尚自然会这样想:加入有另外一个和尚能有办法将63个盘子从一个座移到另一座。那么,问题就解决了。此时老和尚只需这样做:
(1)命令第2个和尚将63个盘子从A座移到B座;
(2)自己将1个盘子(最底下的,最大的盘子)从A座移到C座;
(3)再命令第2个和尚将63个盘子从B座移到C座。
至此,全部任务完成了。这就是递归方法。但是,有一个问题实际上未解决:第2个和尚怎样才能将63个盘子从A座移到B座?
为了解决将63个盘子从A座移到B座,第2个和尚又想:如果有人能将62个盘子从一个座移到另一座,我就能将63个盘子从A座移到B座,他是这样做的:
(1)命令第3个和尚将62个盘子从A座移到C座;
(2)自己将1个盘子从A座移到B座;
(3)再命令第3个和尚将62个盘子从C座移到B座。
再进行一次递归。如此“层层不放”,直到后来找到第63个和尚,让他完成将2个盘子从一个座移到另一座,进行到此,问题就接近解决了。最后找到第64个和尚,让他完成将1个盘子从一个座移到另一座,至此,全部工作都已落实,都是可以执行的。
可以看出,递归的结束条件是最后一个和尚只需移一个盘子;否则递归还要继续进行下去。
应当说明,只有第64个和尚的任务完成后,第63个和尚的任务才能完成。只有第2个到第64个和尚任务完成后,第1个和尚的任务才能完成。只是一个典型的递归的问题。
为便于理解,先分析讲A做上3个盘子移到C座上的过程:
(1)将A座上2个盘子移到B座上(借助C);
(2)将A座上1个盘子移到C座上;
(3)将B座上2个盘子移到C座上(借助A)。
其中第(2)步可以直接实现。第(1)步又可用递归方法分解为:
1.1 将A上1个盘子从A移到C;
1.2 将A上1个盘子从A移到B;
1.3 将C上1个盘子从C移到B。
第(3)不可以分解为:
3.1 将B上1个盘子从B移到A上;
3.2 将B上1个盘子从B移到C上;
3.3 将A上1个盘子从A移到C上。
将以上综合起来,可得到移动3个盘子的步骤为:
A→C,A→B,C→B,A→C,B→A,B→C,A→C。
共经历7步。由此可推出:移动n个盘子熬经历2n-1步。如移4个盘子经历15步,移5个盘子经历31步,移64个盘子经历264-1步。
由上面的分析可知:将n个盘子从A座移到C座可以分解为以下3个步骤:
(1)将A上n-1个盘借助C座先移到B座上;
(2)把A座上剩下的一个盘移到C座上;
(3)将n-1个盘从B座借助于A座移到C座上。
上面第(1)步和第(3)步,都是把n-1个盘从一个座移到另一个座上,采取的办法是一样的,只是座的名字不同而已。为使之一般化可以将第(1)步和第(3)步表示为:
将"one"座上n-1个盘移到"two”座(借助"three”座)。只是在第(1)步和第(3)步中,one、two、three和A、B、 C的对应关系不同。对第(1)步,对应关系是one对应A,two对应B,three对应C。对第(3)步,是:one对应B,two对应C,three 对应A。

因此,可以把上面3个步骤分成两类操作:
(1)将n-1个盘从一个座移到另一个座上(n>1)。这就是大和尚让小和尚做的工作,它是一个递归的过程,即和尚将任务层层下放,直到第64个和尚为止。
(2)将1个盘子从一个座上移到另一个座上。这是打和尚自己做的工作。
下面编写程序。分别用两个函数实现以上的两类操作,用hanio函数实现上面第1类操作(即模拟小和尚的任务),用move函数实现上面第2类操作(模拟 大和尚自己移盘),函数调用hanio(n,one,two,three)表示将n个盘子从"one”座移到"three”座的过程(借助 “two”座)。函数调用move(x,y)表示将1个盘子从x座移到y座的过程。x和y是代表A,B,C座之一,根据每次不同情况分别取A、B、C代 入。
程序如下:

#include <iostream>
using namespace std;

void move(char x,char y)
{
 cout<<x<<"-->"<<y<<endl;
}

void hanoi(int n,char one,char two,char three)
{
 if(n==1) move(one,three);
 else
 {
  hanoi(n-1,one,three,two);
  move(one,three);
  hanoi(n-1,two,one,three);
 }
}

int main()
{
 int m;
 cout<<"请输入盘子数:";
 cin>>m;
 cout<<"移动盘子的步骤为:"<<endl;
 hanoi(m,'A','B','C');
 return 0;
}

(若你觉得本文很好,请顶一下hanoi(汉诺)塔问题C++的递归实现,谢谢啦。hanoi(汉诺)塔问题C++的递归实现hanoi(汉诺)塔问题C++的递归实现

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    来自: web127 > 《算法》

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>