三、四柱汉诺塔问题
3 、四塔问题：设有 A ， B ， C ， D 四个柱子 ( 有时称塔 ) ，在 A 柱上有由小到大堆放的 n 个盘子，如图所示。

今将 A 柱上的盘子移动到 D 柱上去。可以利用 B ， C 柱作为工作栈用，移动的规则如下 :
 ① 每次只能移动一个盘子。
② 在移动的过程中，小盘子只能放到大盘子的上面。
设计并实现一个求解四塔问题的动态规划算法，并分析时间和空间复杂性。
 
■   算法思想:
用如下算法移动盘子(记为FourPegsHanoi):
1) 、将A柱上n个盘子划分为上下两部分，下方部分共有k(1≤k≤n)个盘子，上方部分共有n - k个盘子。
2) 、将A柱上面部分n–k个盘子使用FourPegsHanoi算法经过C、D柱移至B柱。
3) 、将A柱剩余的k个盘子使用ThreePegsHanoi算法经过C柱移至D柱。
4) 、将B柱上的n–k个盘子使用FourPegsHanoi算法经过A、C柱移至D柱。
 
ThreePegsHanoi 算法如下(设三个柱子分别为A、B、C，A柱上共有k个盘子):
1) 、将A柱上方k-1个盘子使用ThreePegsHanoi算法经过B柱移至C柱。
2) 、将C柱上最后一个盘子直接移至C盘。
3) 、将B柱上k-1个盘子使用ThreePegsHanoi算法经过A柱移至C柱。
 
 
 
■   算法步骤：
根据动态规划的四个步骤，求解如下 :
1) 、最优子结构性质:
    四柱汉诺塔问题的最优解是用最少的移动次数将A柱上的盘子全部移到D柱上。当盘子总数为i时，我们不妨设使用FourPegsHanoi的最少移动次数为f(i)。相应的ThreePegsHanoi 算法移动次数为g(k)，由于g(k)=2g(k-1)+1= 2k  -1, 当k确定时，g(k)也是不变的。
   f(i) 为最优解时，其子问题f(i-k)也必为最优解。如果f(i-k)不是最优解，那么存在f’(i-k) < f(i-k)。用f’(i-k)替换f(i-k)将产生一个比f(i)更优的解。这与f(i)为最优解是矛盾的。所以本问题具有最优子结构性质。
 
2) 、递归地定义问题的最优解:
根据上述FourPegsHanoi算法得到最少移动次数f(i):
3) 、自底向上地计算最优解的值 : ( 相应的 Java 源程序在 Hanoi.java 中。 )
f(i) 对应算法中的 m[i , s[i]] 。
-----------------------------------------------------------------------------------------
求四柱汉诺塔最小移动次数伪代码：
数 组下标从 0 开始，数组 m,s 大小为 n+1 。 数组 m 存储计算最小移动次数的中间值。数组 s 存储每步最小移动次数所对应的分割值 k 。
MinMovements ( n ):
      m[0,0] ← s[0] ← 0  ▹为了方便计算增加了 f(0) = m[0,s[0]] = 0   
      for i ← 1 to n
           do min ←  ∞
                 for k ← 1 to i
                      do m[i , k] ← 2 * m[i – k , s[i – k]] + 2k – 1
                            if m[i , k] < min
                                  then min ← m[i , k]
                                        s[i] = k
      return m[n , s[n]] & s
4) 、根据计算信息构造最优解 :
MinMovements 求出的数组 s 中， s[i] 是 f(i) 所对应的最优分割位置。根据数组 s 来构造移动盘子的最佳序列，伪代码如下 :
-----------------------------------------------------------------------------------------
FourPegsHanoi (i , src, temp1, temp2, dest):
if i = 1
then move(src , dest)
else FourPegsHanoi(i – s[i] , src , temp2 , dest , temp1)
ThreePegsHanoi(s[i] , src , temp2 , dest)
                  FourPegsHanoi(i – s[i] , temp1 , src , temp2 , dest)
----------------------------------------------------------------------------------------
ThreePegsHanoi(k , src , temp, dest):
           if k = 1
then move(src , dest)
                 else ThreePegsHanoi(k - 1, src , dest , temp)
                        move(src , dest)
                        ThreePegsHanoi(k - 1, temp , src , dest)
-----------------------------------------------------------------------------------------
■    时间空间复杂度分析 :
1 、时间复杂度
MinMovements 算法的时间复杂度为 :
T(n) = 1 + 2 + ... + n = n(n+1)/2 = O(n2)
2 、空间复杂度
MinMovements 算法占用的空间为 m  和  s 数组的大小 :
即  (n+1)2 + (n+1) = O(n2)
通过分析 m 数组中记录了一些与结果不相关的数据 , 所以通过对 MinMovements 进行改进 , 可使占用空间减小为 O(n) 。
MinMovements ( n ):
      m[0] ← s[0] ← 0      
      for i ← 1 to n
           do m[i] ←  ∞
                 for k ← 1 to i
                      do q ← 2 * m[i – k] + 2k – 1
                            if q < m[i]
                                  then m[i] ← q
                                        s[i] ← k
      return m[n] & s

■    算法测试
当 n=10 时，最小移动次数 49 。   移动序列如下 :
1    A->D
2    A->B
3    A->C
4    B->C
5    D->C
6    A->B
7    A->D
8    B->D
9    A->B
 
10  D->A
11  D->B
12  A->B
13  C->A
14  C->D
15  C->B
16  D->B
17  A->B
18  A->C
19  A->D
 
20  C->D
21  A->C
22  D->A
23  D->C
24  A->C
25  A->D
26  C->D
27  C->A
28  D->A
29  C->D
 
30  A->C
31  A->D
32  C->D
33  B->C
34  B->D
35  B->A
36  D->A
37  C->A
38  B->D
39  B->C
40  D->C
41  B->D
42  C->B
43  C->D
44  B->D
45  A->B
46  A->C
47  A->D
48  C->D
49  B->D
 
当 n=15 时，最小移动次数 129 。移动序列如下 :
1    A->B
2    A->C
3    A->D
4    C->D
5    B->D
6    A->C
7    A->B
8    C->B
9    A->C
10  B->A
11  B->C
12  A->C
13  D->A
14  D->B
15  D->C
16  B->C
17  A->C
18  A->D
19  A->B
20  D->B
21  A->D
22  B->A
23  B->D
24  A->D
25  A->B
26  D->B
 
27  D->A
28  B->A
29  D->B
30  A->D
31  A->B
32  D->B
33  C->D
34  C->B
35  C->A
36  B->A
37  D->A
38  C->B
39  C->D
40  B->D
41  C->B
42  D->C
43  D->B
44  C->B
45  A->C
46  A->D
47  A->B
48  D->B
49  C->B
50  A->D
51  A->C
52  D->C
 
53  A->D
54  C->A
55  C->D
56  A->D
57  A->C
58  D->C
59  D->A
60  C->A
61  D->C
62  A->D
63  A->C
64  D->C
65  A->D
66  C->A
67  C->D
68  A->D
69  C->A
70  D->C
71  D->A
72  C->A
73  C->D
74  A->D
75  A->C
76  D->C
77  A->D
78  C->A
 
79  C->D
80  A->D
81  B->D
82  B->A
83  B->C
84  A->C
85  D->C
86  B->A
87  B->D
88  A->D
89  B->A
90  D->B
91  D->A
92  B->A
93  C->B
94  C->D
95  C->A
96  D->A
97  B->A
98  B->C
99  B->D
100C->D
101B->C
102D->B
103D->C
104B->C
 
105      B->D
106      C->D
107      C->B
108      D->B
109      C->D
110    B->C
111   B->D
112    C->D
113    A->C
114    A->D
115    A->B
116    D->B
117   C->B
118    A->D
119    A->C
120      D->C
121      A->D
122      C->A
123      C->D
124      A->D
125      B->A
126      B->C
127      B->D
128      C->D
129      A->D