所属类别：开发技术

文章作者：wintys

特别推荐：免费发布信息 承包关键词~~抢爆了！^HOT!

版权声明：原创作品，允许转载，转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。http://wintys.blog.51cto.com/425414/100703三、四柱汉诺塔问题3、四塔问题：设有A，B，C，D四个柱子(有时称塔)，在A柱上有由小到大堆放的n个盘子，如图所示。今将A柱上的盘子移动到D柱上去。可以利用B，C柱作为工作栈用，移动的规则如下:①每次只能移动一个盘子。②在移动的过程中，小盘子只能放到大盘子的上面。设计并实现一个求解四塔问题的动态规划算法，并分析时间和空间复杂性。■ 算法思想:用如下算法移动盘子(记为FourPegsHanoi):1)、将A柱上n个盘子划分为上下两部分，下方部分共有k(1≤k≤n)个盘子，上方部分共有n - k个盘子。2)、将A柱上面部分nCk个盘子使用FourPegsHanoi算法经过C、D柱移至B柱。3)、将A柱剩余的k个盘子使用ThreePegsHanoi算法经过C柱移至D柱。4)、将B柱上的nCk个盘子使用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 C k , s[i C k]] + 2k C 1 if m[i , k] < min then min ← m[i , k] s[i] = k return m[n , s[n]] & s4)、根据计算信息构造最优解:MinMovements求出的数组s中，s[i]是f(i)所对应的最优分割位置。根据数组s来构造移动盘子的最佳序列，伪代码如下:-----------------------------------------------------------------------------------------FourPegsHanoi (i , src, temp1, temp2, dest):if i = 1then move(src , dest)else FourPegsHanoi(i C s[i] , src , temp2 , dest , temp1)ThreePegsHanoi(s[i] , src , temp2 , dest) FourPegsHanoi(i C s[i] , temp1 , src , temp2 , dest)----------------------------------------------------------------------------------------ThreePegsHanoi(k , src , temp, dest): if k = 1then 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 C k] + 2k C 1 if q < m[i] then m[i] ← q s[i] ← k return m[n] & s ■ 算法测试当n=10时，最小移动次数49。 移动序列如下:1 A->D2 A->B3 A->C4 B->C5 D->C6 A->B7 A->D8 B->D9 A->B10 D->A11 D->B12 A->B13 C->A14 C->D15 C->B16 D->B17 A->B18 A->C19 A->D20 C->D21 A->C22 D->A23 D->C24 A->C25 A->D26 C->D27 C->A28 D->A29 C->D30 A->C31 A->D32 C->D33 B->C34 B->D35 B->A36 D->A37 C->A38 B->D39 B->C40 D->C41 B->D42 C->B43 C->D44 B->D45 A->B46 A->C47 A->D48 C->D49 B->D当n=15时，最小移动次数129。移动序列如下:1 A->B2 A->C3 A->D4 C->D5 B->D6 A->C7 A->B8 C->B9 A->C10 B->A11 B->C12 A->C13 D->A14 D->B15 D->C16 B->C17 A->C18 A->D19 A->B20 D->B21 A->D22 B->A23 B->D24 A->D25 A->B26 D->B27 D->A28 B->A29 D->B30 A->D31 A->B32 D->B33 C->D34 C->B35 C->A36 B->A37 D->A38 C->B39 C->D40 B->D41 C->B42 D->C43 D->B44 C->B45 A->C46 A->D47 A->B48 D->B49 C->B50 A->D51 A->C52 D->C53 A->D54 C->A55 C->D56 A->D57 A->C58 D->C59 D->A60 C->A61 D->C62 A->D63 A->C64 D->C65 A->D66 C->A67 C->D68 A->D69 C->A70 D->C71 D->A72 C->A73 C->D74 A->D75 A->C76 D->C77 A->D78 C->A79 C->D80 A->D81 B->D82 B->A83 B->C84 A->C85 D->C86 B->A87 B->D88 A->D89 B->A90 D->B91 D->A92 B->A93 C->B94 C->D95 C->A96 D->A97 B->A98 B->C99 B->D100C->D101B->C102D->B103D->C104B->C105 B->D106 C->D107 C->B108 D->B109 C->D110 B->C111 B->D112 C->D113 A->C114 A->D115 A->B116 D->B117 C->B118 A->D119 A->C120 D->C121 A->D122 C->A123 C->D124 A->D125 B->A126 B->C127 B->D128 C->D129 A->D本文出自 “露水阑珊” 博客，请务必保留此出处http://wintys.blog.51cto.com/425414/100703本文出自 51CTO.COM技术博客

....