四柱汉诺塔升级版

mathe

转自：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，看谁可以用最小的步数完成移动过程

无心人

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

无心人

我变形下题目

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

请问，最少要多少操作，使得堆栈4呈现初始堆栈1
的状态

无心人

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]

无心人

n = 3  19步
n = 4  34步
最小移动步数是？？？？

mathe

不错，$n<=4$和百度贴吧里面找到最优结果相同

mathe

要不然将你移动方案也都贴出来。
当然像你上面那样贴太麻烦了。实际上每次移动我们只要说明从哪根柱子移动到哪根就是了。
有三个从左向右移动方案和三个从右向左移动方案，分别为:
$1->2,2->3,3->4,4->3,3->2,2->1$
我们可以用字母$A,B,C,c,b,a$分别表示这些移动方案，那么每个结果可以用一个字母串表示了。

无心人

3的我差点错了，中间被我省略了一步，后来发现了
3的
ABACBcAbaCBcbCBCABC   19步
4的
ABACBAbaBABAbcabaCBcbCBCABAbaBCABC  34步

[ 本帖最后由 无心人 于 2008-6-22 15:50 编辑 ]

无心人

说些我的思路
如果有堆栈为空，称安全状态，或者顶不是1，称次安全状态

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

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

[ 本帖最后由 无心人 于 2008-6-22 15:17 编辑 ]

无心人

比如n=5
ABCAB得到
543//2/1状态
则可证明3能安全的转移到右边
然后
AcbaCBcAB
得到
54//321/
AbaCbABCaBAB
得到
5//43/21
然后
AcbabcbCBABaCbacbaCBcbCBC
得到
321///54
ABAbaBABCAbaBcbCBCABcbCBC
得到结果

76步
似乎多些

[ 本帖最后由 无心人 于 2008-6-22 15:42 编辑 ]