四柱汉诺塔升级版

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 编辑 ]