荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Second (石开), 信区: Program
标 题: [合集]汉诺塔问题。
发信站: 荔园晨风BBS站 (Sun Oct 28 10:55:02 2001), 站内信件
lvyou (≈航之心≈) 于Wed Oct 24 16:16:26 2001提到:
| | |
■|■ | |
■■|■■ | |
■■■|■■■ | |
将第一根柱的三个盘通过第二根柱移到第三根柱,每次只能移动
一块盘,且始终保持小盘在大盘上面,最少要多少步?
若是有四个,五个,或者N个盘呢?又要怎么移?最少要移动几步?
IamBstone (Bstone) 于Wed Oct 24 16:25:55 2001提到:
自己看书去,少来这个!
用递归
tiny (土包子一个) 于Wed Oct 24 16:33:18 2001提到:
谭浩强的那本书有写呀,找2001的计算机的师弟借借吧
kaley (*_0) 于Wed Oct 24 16:34:27 2001提到:
7 次吧 ?
lvyou (≈航之心≈) 于Wed Oct 24 16:41:12 2001提到:
//hand
7次怎么移?
IamBstone (Bstone) 于Wed Oct 24 16:46:03 2001提到:
power(2,n)-1
//hand
7次怎么移?
lvyou (≈航之心≈) 于Wed Oct 24 16:50:24 2001提到:
若必须通过第二根柱移到第三根柱,7次应该不行吧?
我手工试过,偶最少也要26步。
IamBstone (Bstone) 于Wed Oct 24 17:34:49 2001提到:
正是笨笨
若必须通过第二根柱移到第三根柱,7次应该不行吧?
我手工试过,偶最少也要26步。
lvyou (≈航之心≈) 于Wed Oct 24 18:59:25 2001提到:
聪聪,你移给我看看。
Berry (紫杉) 于Wed Oct 24 19:14:49 2001提到:
嘿嘿,如果不是简单的从编程角度看的话,
这个也是“人工智能的状态空间的搜索策略问题”!
Begin (迷茫) 于Wed Oct 24 22:51:40 2001提到:
为什么必须通过第二根?你自己规定的?
IamBstone (Bstone) 于Wed Oct 24 23:23:00 2001提到:
是借助另外一更
lvyou (≈航之心≈) 于Wed Oct 24 23:33:02 2001提到:
是啊,可以批准吗?嘻嘻
pas (.......................................) 于Thu Oct 25 11:28:55 2001提到:
确实是7次就可以了啊,我手机上有这个游戏,
7次就可以了,我的最高记录是8秒钟
这个例子好像在很多C++的书上面都有的,我们的课本上也有
Mic (酷鱼) 于Thu Oct 25 13:00:38 2001提到:
你玩不了7步也不用在这里问阿,哈哈笨
lvyou (≈航之心≈) 于Thu Oct 25 13:26:34 2001提到:
f!SB!
我都说了要按新规则来移动咯,不能直接将第一根与第三根的盘
互移,必须经过第二根柱。
tang (独孤九剑) 于Thu Oct 25 15:21:56 2001提到:
汉诺威塔问题可以用4元组编码:(n,x,y,z),n是盘数,x,y,z为3个柱的编码
(如可离散地设为为A,B,C),4元组(n,x,y,z)表示把n个盘从x移到y,z为辅助。
(n,x,y,z) 的算法是:
1、(n-1,x,y,z) ;
2、把x上的一个盘从x搬到z;
3、(n-1,y,z,x)。
明显要用2^n - 1步,可用数学归纳法证明。
想直观理解,可以把问题规约到满二叉树的计数问题,算法中1相当于左子树,
2相当于父节点,3相当于右子树,n是树的高度,算法相当于满二叉树的中序
遍历,所需步数相当于满二叉树的节点数。由此另一证明:用数学归纳法证明
问题可以规约到求满二叉树的节点数问题,然后用公式直接得出答案。
看见大家讨论这么久都不到点子上,还为源程序犯愁,忍不住手!还是好好学
习,抓基本功重要。
lvyou (≈航之心≈) 于Thu Oct 25 17:40:20 2001提到:
THX。^_^
可是现在我说的这个应该已不是原来那个规则了,
按你说的,现在z就是桥,x,y就是两岸,盘无论从
x到y,还是从y到x都必须经过z,不能直接从x跳到
y或从y跳到x,又该如何呢?
tang (独孤九剑) 于Thu Oct 25 18:21:59 2001提到:
打错了,是(n,x,z,y)
再灌点:
搬运可以用二元组(x,z)编码,相应地,满二叉树上的每个结点都有一个这样的二
元组标记!如果要知道是那个盘被搬运,还可以把盘编号:汉诺威问题(n,x,y,z)
x上最大那个盘编号为n,那样搬运就用三元组编码(n,x,y),算法中2改为(n,x,y)。
仔细想想,但当n=1时是不需要用到辅助柱的。
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店