经典问题之——汉诺塔 - 数据结构 - 机器学习
数据结构 - 机器学习
深度学习
当前位置：首页 » 数据结构精品文章 » 正文
经典问题之——汉诺塔
1308 人参与 2018年09月03日 22:55 分类 : 数据结构精品文章 评论
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。汉诺塔的大概起源就是这样，众僧们耗尽毕生精力也不可能完成金片的移动，因为通过计算，发现移动圆片的次数为18446744073709551615，这基本上是一个不可能完成的任务。
汉诺塔规则：后来，这个传说就演变为下面的规则:
1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片。
比如，3阶汉诺塔可以这样移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C。
此外，汉诺塔问题也是程序设计中的经典递归问题。
算法思路：通过程序，可以借助计算机的快速处理速度来解决这个问题，方法如下：
1.如果只有一个金片，则把该金片从源移动到目标棒，结束。
2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒.
3.单纯对于有N个金片要挪动的步数求出, 可以使用递推方法,满足递推方程f(i) = f(i - 1) * 2 + 1.
C语言版本的Hanoi塔问题：
一块板上有三根针，A，B，C。A针上套有64个大小不等的圆盘，大的在下，小的在上。如图5.4所示。要把这64个圆盘从A针移动C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。本题算法分析如下：
设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。显然这是一个递归过程，据此算法可编程如下：
move(int n,int x,int y,int z)
{
if(n==1)
printf("%c-->%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c-->%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{ int h;
printf("\ninput number:\n");
scanf("%d",&h);
printf("the step to moving %2d diskes:\n",h);
move(h,'a','b','c');
}来源：我是码农，转载请保留出处和链接！
本文链接：http://www.54manong.com/?id=204
微信号：qq444848023 QQ号：444848023
加入【我是码农】QQ群：864689844（加群验证：我是码农）
- 数据结构之栈和队列-基本概念和术语汇总2018-08-18 08:59
- 数据结构相关基本概念2018-09-03 22:30
- 树与二叉树的表示和基本操作2018-09-03 22:40
- 稀疏矩阵的基本运算2018-09-03 22:58
网站分类
- 数据结构
- 数据结构视频教程
- 数据结构练习题
- 数据结构试卷
- 数据结构习题解析
- 数据结构电子书
- 数据结构精品文章
- 区块链
- 区块链精品文章
- 区块链电子书
- 大数据
- 大数据精品文章
- 大数据电子书
- 机器学习
- 机器学习精品文章
- 机器学习电子书
- 面试笔试
- 物联网/云计算
标签列表
- 数据结构 (39)
- 数据结构电子书 (20)
- 数据结构习题解析 (8)
- 数据结构试卷 (10)
- 区块链是什么 (261)
- 数据结构视频教程 (31)
- 大数据技术与应用 (12)
- 百面机器学习 (14)
- 机器学电子书 (29)
- 大数据电子书 (37)
- 程序员面试 (10)
- RFID (21)
最近发表
- 找出数组中有3个出现一次的数字
- 《百面机器学习》电子书下载
- 区块链精品电子书《深度探索区块链：Hyperledger技术与应用_区块链技术丛书》张增骏
- 区块链精品电子书《比特币：一个虚幻而真实的金融世界》
- 区块链精品电子书《图说区块链》-徐明星 & 田颖 & 李霁月
- 区块链精品电子书《是非区块链：技术、投机与泡沫》-英国《金融时报》
- 区块链精品电子书《商业区块链：开启加密经济新时代》-威廉·穆贾雅
- 区块链精品电子书《人工智能时代，一本书读懂区块链金融 (互联网_时代企业管理实战系列)》-马兆林
-
(function(){
var bp = document.createElement('script');
var curProtocol = window.location.protocol.split(':')[0];
if (curProtocol === 'https'){
bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
}
else{
bp.src = 'http://push.zhanzhang.baidu.com/push.js';
}
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(bp, s);
})();
全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试
var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！
评论专区