数学研发论坛

 找回密码
 欢迎注册
查看: 18038|回复: 60

[擂台] 四柱汉诺塔升级版

[复制链接]
发表于 2008-6-22 09:41:17 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
转自:http://tieba.baidu.com/f?ct=3356 ... FD%D1%A7#4079132505

四根柱子的汉诺塔变种问题:
有四个排成一行的柱子和n个大小不同的盘子,每次可以将一个盘子移动到相邻的柱子上,但是大盘子不能放在小盘子上面。
请用最小的步数将n个盘子从第一个柱子全部移到第4个盘子。

这个问题在n不大(比如不超过10)时用计算机应该不难,但是n大一些就很难了。
看谁能够计算到最大的n.
还有对于比较大的n,比如n=20和n=30,计算最优的移动方案很难,所以我们还可以比赛对于n=20和n=30,看谁可以用最小的步数完成移动过程
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 10:45:15 | 显示全部楼层


按照汉诺塔的原则
先移动到2,再移动到3,再移动到4

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 10:51:38 | 显示全部楼层
我变形下题目

有四个堆栈1,2,3,4
堆栈1按顺序压入n, n-1, ..., 1
2,3,4为空
允许操作
       从堆栈弹出一个数字压到相邻堆栈
       但弹出的数字必须小于要压栈的栈顶或者要压栈的是空栈

请问,最少要多少操作,使得堆栈4呈现初始堆栈1
的状态
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 10:59:18 | 显示全部楼层
n = 1  3次
n = 2 10次
[2 1]
[ ]
[ ]
[ ]

[2]
[1]
[ ]
[ ]

[2]
[ ]
[1]
[ ]

[ ]
[2]
[1]
[ ]

[ ]
[ 2 1]
[ ]
[ ]

[1]
[2]
[ ]
[ ]

[1]
[ ]
[2]
[ ]

[1]
[ ]
[ ]
[2]

[ ]
[1]
[ ]
[2]

[ ]
[ ]
[1]
[2]

[ ]
[ ]
[ ]
[ 2 1]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 11:03:25 | 显示全部楼层
n = 3  19步
n = 4  34步
最小移动步数是????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-22 14:51:07 | 显示全部楼层
不错,$n<=4$和百度贴吧里面找到最优结果相同
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-22 14:54:44 | 显示全部楼层
要不然将你移动方案也都贴出来。
当然像你上面那样贴太麻烦了。实际上每次移动我们只要说明从哪根柱子移动到哪根就是了。
有三个从左向右移动方案和三个从右向左移动方案,分别为:
$1->2,2->3,3->4,4->3,3->2,2->1$
我们可以用字母$A,B,C,c,b,a$分别表示这些移动方案,那么每个结果可以用一个字母串表示了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 15:08:44 | 显示全部楼层
3的我差点错了,中间被我省略了一步,后来发现了
3的
ABACBcAbaCBcbCBCABC   19步
4的
ABACBAbaBABAbcabaCBcbCBCABAbaBCABC  34步

[ 本帖最后由 无心人 于 2008-6-22 15:50 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 15:14:45 | 显示全部楼层
说些我的思路
如果有堆栈为空,称安全状态,或者顶不是1,称次安全状态

则,总会有一个,栈2是空,小于某数k的所有数字分布在3,4栈,而其他数字按顺序在栈1的状态
此状态可得到最终解

所以问题可简化为,得到各k对应的中间状态,然后就能推出各k状态的转换步骤的次数
而得到最后的步骤数

[ 本帖最后由 无心人 于 2008-6-22 15:17 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-22 15:40:25 | 显示全部楼层
比如n=5
ABCAB得到
543//2/1状态
则可证明3能安全的转移到右边
然后
AcbaCBcAB
得到
54//321/
AbaCbABCaBAB
得到
5//43/21
然后
AcbabcbCBABaCbacbaCBcbCBC
得到
321///54
ABAbaBABCAbaBcbCBCABcbCBC
得到结果

76步
似乎多些

[ 本帖最后由 无心人 于 2008-6-22 15:42 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-6-1 23:32 , Processed in 0.062736 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表