桌子移碟问题

lulijie

第一问：
有3张桌子，A桌、B桌和C桌，A桌上放着3个盘子，每个盘子上都编有号码，分别为1号、2号和3号，三个盘子上下叠放在一起，号码大的在下面。现在要求将A桌上的3个盘子移到B桌上，移动规则如下：
   1.  每次只能移动一个盘子，且只能移最上面的盘子。
   2.  若盘子要放的桌子上已经有盘子，只能叠放在盘子的最上面。
   3.  号码大的盘子不能放在号码小的盘子上面。
那么最少移动步数是多少？

第二问：
若A桌上的盘子总数为N，初始也是号码大的在下面全部叠放在一起，那么将A桌上的这N个盘子移到B桌上，移动规则一样，假设最少步数是X，那么X与N的关系是什么？

第三问：
若一共有m张桌子，其他初始条件，移动目标，移动规则都一样，
那么最少移动步数X与盘子总数N和桌子数m的关系又是如何？

lulijie

对于4塔问题，m=4，
假设X(N)表示移动N个碟子的最少步数，
那么   可以先把N-2个移到一个辅助桌子，步数为X(N-2)，剩下的2个碟子移动目的桌子的步数是3，再把辅助桌子上的N-2个碟子移动目标桌子，步数是X(N-2)。
所以可以用递推公式  X(N)=2*X(N-2)+3    用这个公式解出的值，保证可以完成任务。但该公式解出的步数是不是就是最少步数，还需要证明。
我们设X（m，N）表示 X与m，N的关系。
4塔问题可以表示成 X（4，N）
3塔问题可以表示成 X（3，N）

那么对于4塔，我们可以先把K个碟子移动辅助桌子，步数为X（4，k）
然后把剩下的N-K个碟子，移动目标桌子，由于1个辅助桌子已经被占用，所以只要3个桌子可用（即3塔问题），步数是X（3，N-K）。所以递推公式为：    X（4，N）=2*X（4，k）+ X（3，N-K）
当K取N-2时，就是上述红字的公式。是不是K取N-2时， X（4，N）的值最小  需要证明。
-----------------------------------------------------------------------------------------------------------
对于X（m，N）的情况，同理可以推出 递推公式：    X（m，N）=2 * X（m，k）+ X（m-1 ，N-K）
是不是K=N-m+2时，  X（m，N）步数最少，也需要证明。
只有证明了K=N-m+2时，  X（m，N）步数最少，才能用上述的递推公式求出通项，得出X与m、N的关系。

[ 本帖最后由 lulijie 于 2009-3-9 12:05 编辑 ]

lulijie

根据    X（4，N）=2*X（4，k）+ X（3，N-K）   计算了以下值：
X(2,1)=1
X(3,1)=1  X(3,2)=3   X(3,3)=7  X(3,4)=15  X(3,5)=31  X(3,6)=63  X(3,7)=127  X(3,8)=255  X(3,9)=511  X(3,10)=1023
X(4,1)=1  X(4,2)=3   X(4,3)=5  X(4,4)=9   X(4,5)=13   X(4,6)=17  X(4,7)=25   X(4,8)=33   X(4,9)=41      X(4,10)=49  X(4,11)=65  X(4,12)=81  X(4,13)=97  X(4,14)=113  X(4,15)=129   (4,16)=161
---------------------------------------------------------------------------------------------------
最少步数并不是都是  K取N-2。
以上的猜测都是错误的。
观察  X（4，N）的变化规律，好像是：
第1项是1，后面2项各递加2 (=2^1)，再后面3项各递加4 (=2^2)，再后面4项各递加8 (=2^3)，再后面5项各递加16 (=2^4)，
递推公式，可写成       X(4,N)=X(4,N-1)+2^(p-1)      （整数p满足  p(p-1)/2 <N< =     p(p+1)/2）。
不知是否正确。

lulijie

X(m，N) 表示m张桌子，N个碟子的最少移动步数。
m=4 (即4塔问题)，前100项：
1，3，5，9，13，17，25，33，41，49，65，81，97，113，129，161，193，225，257，289，321，385，449，513，577，641，705，769，897，1025，1153，1281，1409，1537，1665，1793，2049，2305，2561，2817，3073，3329，3585，3841，4097，4609，5121，5633，6145，6657，7169，7681，8193，8705，9217，10241，11265，12289，13313，14337，15361，16385，17409，18433，19457，20481，22529，24577，26625，28673，30721，32769，34817，36865，38913，40961，43009，45057，49153，53249，57345，61441，65537，69633，73729，77825，81921，86017，90113，94209，98305，106497，114689，122881，131073，139265，147457，155649，163841，172033，
m=5，前100项：
1，3，5，7，11，15，19，23，27，31，39，47，55，63，71，79，87，95，103，111，127，143，159，175，191，207，223，239，255，271，287，303，319，335，351，383，415，447，479，511，543，575，607，639，671，703，735，767，799，831，863，895，927，959，991，1023，1087，1151，1215，1279，1343，1407，1471，1535，1599，1663，1727，1791，1855，1919，1983，2047，2111，2175，2239，2303，2367，2431，2495，2559，2623，2687，2751，2815，2943，3071，3199，3327，3455，3583，3711，3839，3967，4095，4223，4351，4479，4607，4735，4863，
m=6，前100项：
1，3，5，7，9，13，17，21，25，29，33，37，41，45，49，57，65，73，81，89，97，105，113，121，129，137，145，153，161，169，177，185，193，201，209，225，241，257，273，289，305，321，337，353，369，385，401，417，433，449，465，481，497，513，529，545，561，577，593，609，625，641，657，673，689，705，721，737，753，769，801，833，865，897，929，961，993，1025，1057，1089，1121，1153，1185，1217，1249，1281，1313，1345，1377，1409，1441，1473，1505，1537，1569，1601，1633，1665，1697，1729，
m=7，前100项：
1，3，5，7，9，11，15，19，23，27，31，35，39，43，47，51，55，59，63，67，71，79，87，95，103，111，119，127，135，143，151，159，167，175，183，191，199，207，215，223，231，239，247，255，263，271，279，287，295，303，311，319，327，335，343，351，367，383，399，415，431，447，463，479，495，511，527，543，559，575，591，607，623，639，655，671，687，703，719，735，751，767，783，799，815，831，847，863，879，895，911，927，943，959，975，991，1007，1023，1039，1055，
m=8，前100项：
1，3，5，7，9，11，13，17，21，25，29，33，37，41，45，49，53，57，61，65，69，73，77，81，85，89，93，97，105，113，121，129，137，145，153，161，169，177，185，193，201，209，217，225，233，241，249，257，265，273，281，289，297，305，313，321，329，337，345，353，361，369，377，385，393，401，409，417，425，433，441，449，457，465，473，481，489，497，505，513，521，529，537，545，561，577，593，609，625，641，657，673，689，705，721，737，753，769，785，801，
m=9，前100项：
1，3，5，7，9，11，13，15，19，23，27，31，35，39，43，47，51，55，59，63，67，71，75，79，83，87，91，95，99，103，107，111，115，119，123，127，135，143，151，159，167，175，183，191，199，207，215，223，231，239，247，255，263，271，279，287，295，303，311，319，327，335，343，351，359，367，375，383，391，399，407，415，423，431，439，447，455，463，471，479，487，495，503，511，519，527，535，543，551，559，567，575，583，591，599，607，615，623，631，639，
m=10，前100项：
1，3，5，7，9，11，13，15，17，21，25，29，33，37，41，45，49，53，57，61，65，69，73，77，81，85，89，93，97，101，105，109，113，117，121，125，129，133，137，141，145，149，153，157，161，169，177，185，193，201，209，217，225，233，241，249，257，265，273，281，289，297，305，313，321，329，337，345，353，361，369，377，385，393，401，409，417，425，433，441，449，457，465，473，481，489，497，505，513，521，529，537，545，553，561，569，577，585，593，601，
-----------------------------------------------------------------------------------------
3塔问题即汉诺塔问题，盘子总数64个，假设一步移动花费1秒钟，那么，完成任务要花几千亿年的时间。
而增加了1个辅助塔，即4塔，完成移动64个盘子只要5个小时余。
只差1个塔，咋就差距这么大内。
这说明住房空间狭窄，对人的压抑有多大！稍微增加一点空间，马上就会有豁然开朗、得心应手的感觉。
向全世界的无房者致敬。
提议今天为全世界无房者日。