荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: 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软件 网络书店