四柱汉诺塔升级版
有趣且有难度转自：http://tieba.baidu.com/f?ct=335675392&tn=baiduPostBrowser&sc=4079132505&z=318545067&pn=0&rn=50&lm=0&word=%CA%FD%D1%A7#4079132505四根柱子的汉诺塔变种问题:
有四个排成一行的柱子和n个大小不同的盘子，每次可以将一个盘子移动到相邻的柱子上，但是大盘子不能放在小盘子上面。
请用最小的步数将n个盘子从第一个柱子全部移到第4个盘子。
这个问题在n不大（比如不超过10）时用计算机应该不难，但是n大一些就很难了。
看谁能够计算到最大的n.
还有对于比较大的n,比如n=20和n=30,计算最优的移动方案很难，所以我们还可以比赛对于n=20和n=30，看谁可以用最小的步数完成移动过程 :)
按照汉诺塔的原则
先移动到2，再移动到3，再移动到4
:lol 我变形下题目
有四个堆栈1，2，3，4
堆栈1按顺序压入n, n-1, ..., 1
2，3，4为空
允许操作
从堆栈弹出一个数字压到相邻堆栈
但弹出的数字必须小于要压栈的栈顶或者要压栈的是空栈
请问，最少要多少操作，使得堆栈4呈现初始堆栈1
的状态 n = 13次
n = 2 10次
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ 2 1]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ 2 1] n = 319步
n = 434步
最小移动步数是？？？？ 不错，$n<=4$和百度贴吧里面找到最优结果相同 要不然将你移动方案也都贴出来。
当然像你上面那样贴太麻烦了。实际上每次移动我们只要说明从哪根柱子移动到哪根就是了。
有三个从左向右移动方案和三个从右向左移动方案，分别为:
$1->2,2->3,3->4,4->3,3->2,2->1$
我们可以用字母$A,B,C,c,b,a$分别表示这些移动方案，那么每个结果可以用一个字母串表示了。 3的我差点错了，中间被我省略了一步，后来发现了
3的
ABACBcAbaCBcbCBCABC 19步
4的
ABACBAbaBABAbcabaCBcbCBCABAbaBCABC34步
[ 本帖最后由 无心人 于 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 编辑 ]