桌子移碟问题

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的关系又是如何？

美景

不行！我看题看的迷糊了！

515761153

X=N吧。。。
第2问没看

515761153

X=mN






(是题目弱还是我弱）

Cielo

前两问就是汉诺塔吧！很久以前在文曲星上玩过的

第二问用递归很容易解决的，X = 2 ^ N - 1

第三问就有点麻烦了，我再想想吧……

ggglgq

　　
　　
  
    这些问题可以编程求解，比如 四塔问题
  
            四塔问题.rar (226.99 KB, 下载次数: 9)

2009-3-9 06:53:46 上传

下载次数: 9

  
  
  
    这是我以前编的程序（现在无音响效果），大家可以参考一下。　　
　　
　　　　
　　
　　　　

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

Cielo

原帖由 lulijie 于 2009-3-9 12:03 发表
那么对于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(4,K) 和 2^(K/2) 同一数量级，乘以2之后仍远远小于 X(3,K)，所以我猜 K = N - 2 时应该是最小了！

juventus66

很复杂,学习了

骰迷

是何奈塔的問題嗎?網上的解答很全喔,就是第三問沒答案