主元素、嵌套箱、四柱汉诺塔问题的算法设计与分析.pdf

《主元素、嵌套箱、四柱汉诺塔问题的算法设计与分析.pdf》由会员分享，可在线阅读，更多相关《主元素、嵌套箱、四柱汉诺塔问题的算法设计与分析.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 算法设计与分析 算法设计与分析 算法设计与分析 算法设计与分析 课程 课程 课程 课程大作业 大作业 大作业 大作业 题 题 题 题 目 目 目 目:主元素、嵌套箱、汉诺塔问题 作 作 作 作 者 者 者 者:天堂露珠(网名)邮 邮 邮 邮 箱 箱 箱 箱:完成时间 完成时间 完成时间 完成时间:2008-08-25 仅供学习参考 仅供学习参考 仅供学习参考 仅供学习参考 摘 摘 摘 摘 要 要 要 要 分析了主元素、嵌套 d 维箱与四柱汉诺塔问题。分别使用分治法、贪心法和动态规划的算法设计技术。使用伪代码实现描述了关键算法，同时也用 Java 语言实现了伪代码(源程序未附入文中)。关键字：

2、算法设计与分析，主元素，嵌套箱，汉诺塔 目 目 目 目 录 录 录 录 一、主元素问题1 基于分治法的线性时间求主元素算法1 无序关系时求主元素的 O(nlgn)的算法.2 无序关系时求主元素的 O(n)算法.4 算法测试.5 二、嵌套箱问题.6 箱嵌套关系的传递性.6 d 维箱的嵌套关系.6 最长嵌套箱序列8 三、四柱汉诺塔问题.11 四、参考文献.15-1-一 一 一 一、主元素问题 主元素问题 主元素问题 主元素问题 1、设 T0.n-1是 n 个元素的数组。对任一元素 x，设 S(x)=i|Ti=x。当|S(x)|n/2 时，称 x 为 T的主元素。1)如果 T中元素存在序关系，按分治

3、策略设计并实现一个线性时间算法，确定 T0.n-1是否有一个主元素。2)若 T中元素不存在序关系，只能测试任意两个元素是否相等，试设计并实现一个 O(nlogn)有效算法，确定 T是否有一个主元素。进一步，能找到一个线性时间算法吗？注：实现的算法要求列出足够的实验结果。1)基于分治法的线性时间求主元素算法 基于分治法的线性时间求主元素算法 基于分治法的线性时间求主元素算法 基于分治法的线性时间求主元素算法 算法思想 中位数：数列排序后位于最中间的那个数。如果一个数列有主元素,那么必然是其中位数。求一个数列有没有主元素，只要看中位数是不是主元素。找中位数的方法:选择一个元素作为划分起点，然后用快

4、速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为 k。如果 kn/2，那么继续用同样的方法在左边部分找；如果 k n/2 then print 主元素:+median+出现次数:+cnt else print 无主元素-2-找一个序列中第 k大的数伪代码 randomizedSelect(A,p,q,k):r randomizedPartition(p,q)找出划分元素 r if r=k then return Ar else if r k then randomizedSelect(A,p,r 1,k)else randomizedS

5、elect(A,r+1,q,k)-实现随机划分的伪代码:randomizedPartition(A,p,q):rand random(p,q)exchange Arand Aq return partition(p,q)-基于快速排序思想的划分伪代码:partition(A,p,q):pivot Aq i p 1 for j p to q 1 do if Aj=pivot then i i+1 exchange Ai Aj exchange Ai+1 Aq return i+1-时间复杂度分析 master()中求中位数可以在平均时间复杂度为 O(n)的时间内完成,检查中位数是否是主元素耗时

6、O(n),所以时间复杂度为 O(n)。2)2)2)2)无序关系时求主元素的 无序关系时求主元素的 无序关系时求主元素的 无序关系时求主元素的 O(nlgn)的算法 的算法 的算法 的算法 算法思想 若 T 中存在主元素，则将 T 分为两部分后，T 的主元素也必为两部分中至少一部分的主元素，因此可用分治法。将元素划分为两部分，递归地检查两部分有无主元素。算法如下：a.若 T 只含一个元素，则此元素就是主元素，返回此数。b.将 T 分为两部分 T1 和 T2（二者元素个数相等或只差一个），分别递归调用此方法求其主元素 m1 和 m2。c.若 m1 和 m2 都存在且相等，则这个数就是 T 的主元素

7、，返回-3-此数。d.若 m1 和 m2 都存在且不等，则分别检查这两个数是否为 T 的主元素，若有则返回此数，若无则返回空值。e.若 m1 和 m2 只有一个存在，则检查这个数是否为 T 的主元素，若是则返回此数，若否就返回空值。f.若 m1 和 m2 都不存在，则 T 无主元素，返回空值。算法实现 相应的 Java程序在 MasterElement.java中-O(nlgn)的算法伪代码:求 Tp.q中的主元素。返回主元素及其出现次数或空(表示无主元素)CheckMaster(T,p,q):if p q then return Tp and 1 len q p+1 r p+len/2 a

8、and numa CheckMaster(T,p,r 1)b and numb CheckMaster(T,r,q)if a=NIL and b=NIL then return NIL if a=NIL and b NIL then return CheckAnotherPart(T,len,p,r 1,b,numb)if a NIL and b=NIL then return CheckAnotherPart(T,len,r,q,a,numa)if a NIL and b NIL then if a=b then numa numa+numb return a and numa else r

9、e CheckAnotherPart(T,len,p,r 1,b,numb)if re NIL then return re else return CheckAnotherPart(T,len,r,q,a,numa)-检查候选主元素是否是主元素 CheckAnotherPart(T,len,p,q,c,numc):numc CheckNum(T,p,q,c)+numc if num len/2 then return c and numc else return NIL-4-计算 Tp.q中 element出现的次数 CheckNum(T,p,q,element):cnt 0 for i p

10、 to q do if Ti=element then cnt cnt+1 return cnt-时间复杂度分析 T(n)=2T(n/2)+n 所以时间复杂度为 O(nlgn)3)3)3)3)无序关系时求主元素的 无序关系时求主元素的 无序关系时求主元素的 无序关系时求主元素的 O(n)算法 算法 算法 算法 算法思想 在一个集合中，删除两个不同的数，则集合的主元素保持不变。根据这个原理，可以很快求出主元素。算法实现-相应的 Java程序在 MainElement.java中 master(A):n lengthA count 1 seed A0 找候选主元素 for i 1 to n 1 d

11、o if Ai=seed then count count+1 else if count 0 then count count 1 else seed Ai 查找候选主元素是否是主元素 count 0 for i 0 to n 1 do if Ai=seed then count count+1 if count n/2 then return seed and count else return NIL-5-时间复杂度分析 时间复杂度为 O(n)4)4)4)4)算法 算法 算法 算法测试 测试 测试 测试 对前面三个求主元素算法，使用测试数据进行测试:测试数组 结果 0,0,1,1,0,8

12、,1,1,1 主元素:1 出现次数:5 13,17,26,3,5,2,17,3 无主元素 1,2,3,4,5,6,7,8 无主元素 1,0,0,1,0,2,0 主元素:0 出现次数:4 1,3,4,1,2,1,1,4,0,1,1,1 主元素:1 出现次数:7 0,1,1 主元素:1 出现次数:2 13,17,26,3,5,2,17,3,3,3,3,3,3 主元素:3 出现次数:7 100,58 无主元素 597 主元素:597 出现次数:1 6,1,2,2,2,3,5 无主元素 7,7,7,7,7,7 主元素 7 出现次数:6 5,9,45,96,77,28,13 无主元素-6-二 二 二 二

13、、嵌套箱问题 嵌套箱问题 嵌套箱问题 嵌套箱问题 2、一个 d 维箱(x1,x2,.,xn)嵌入另一个 d 维箱(y1,y2,.,yn)是指存在1,2,d 的一个排列，使得x(1)y1,x(2)y2,.,x(d)yd。1)证明上述箱嵌套关系具有传递性；2)试设计并实现一个贪心算法，用于确定一个 d 维箱是否可嵌入另一个d维箱；3)给定由 n 个 d 维箱组成的集合 B1,B2,B3,.,Bn，试设计并实现一个贪心算法找出这n 个d维箱中的一个最长嵌套箱序列，并用n 和d 描述算法的计算时间复杂性。1)箱嵌套关系的传递性 箱嵌套关系的传递性 箱嵌套关系的传递性 箱嵌套关系的传递性 证明：设有 3

14、 个 d 维箱 B1(x1,x2,xd)，B2(y1,y2,yd)，B3(z1,z2,zd)，B1可嵌入 B2，B2可嵌入 B3。B1可嵌入 B2，则存在排列使得：x(1)y1，x(2)y2，x(d)yd 1 B2可嵌入 B3，则存在排列使得：y(1)z1，y(2)z2，y(d)zd 2 由1式可得：x(1)y(1)，x(2)y(2)，x(d)y(d)3 由23可得：存在排列=使得：x(1)z1，x(2)z2，x(d)zd 根据 d 维箱的定义可得，B1可嵌入 B3。因此，嵌套箱关系具有传递性。2)d 维箱的嵌套关系 维箱的嵌套关系 维箱的嵌套关系 维箱的嵌套关系 贪心选择性质:对于d 维箱X

15、(x1,x2,xd),Y(y1,y2,yd),排列、是分别使 X、Y非递减有序的排列，有如下结论:XY(表示X 可嵌入Y)的充要条件是，对任意1id 有x(i)y(i)。证明:a.充分性:当对任意1id有x(i)y(i)时，令=-1,那么 x(i)=x(-1(i)y(-1(i)=yi，即存在一个排列使得对于任意1i-7-d，x(i)yi，所以XY。b.必要性:用数学归纳法证明。当维数为1 时,XY 可得 x1 y1，那么x(1)y(1)成立。假设维数为 d 时，结论成立，即:当XY 时，对于任意1id，有x(i)y(i)。那么当维数为 d+1 时，对于任意1id+1，XY，则存在 使得:x(1

16、)y1，x(2)y2，x(d)yd，x(d+1)yd+1 1 先观察1式前 d 项,x(1)y1，x(2)y2，x(d)yd。由假设可知，对任意1id，有存在排列、使得x(i)y(i)，即:x(1)x(2)x(d)2 y(1)y(2)y(d)3 x(1)y(1)，x(2)y(2)，x(d)y(d)4 此时，、只对1式前 d 项进行排列，并不包含 x(d+1)和 yd+1。可以将 x(d+1)按大小顺序插入到2式(设插入位置为 j)，从而有新的排列使得 xi(1id+1)非递减有序。同理，也有使得 yd+1按大小顺序插入到3式后(设插入位置为k)，yi(1id+1)非递减有序。因为 x(d+1)

17、yd+1，易知 jk。当 j=k 时，因为xm、ym(1md+1)的对应位置都没有变，显然x(i)y(i)(1id+1)，所证结论成立。当 jk 时，x1y1，x2y2，xjxj+1yj，xj+1xj+2 yj+1，xk-1xk yk-1，xkyk-1 yk，xk+1y k+1，xd+1 y d+1。即,对任意1id+1 x(i)y(i)，所证结论成立。命题得证。算法实现 由上面所得结论，对两个 d维箱进行排序后，只要判断排序后两个 d 维箱的嵌套关系就可以得出结果。-求两个箱子的嵌套关系的伪代码:返回 1 表示 X嵌套 Y(即 YX)返回1 表示 Y嵌套 X(即 XY)返回 0 表示 X和

18、Y之间无嵌套关系 NEST(X,Y,d):-8-Sort(X)对数组所表示的 d维箱 X、Y进行排序 Sort(Y)if X0 Y0 then for i 1 to d 1 do if Xi=Yi then return 0 return 1-时间复杂度分析 NEST()的主要时间消耗在于排序，使用快速排序时，NEST()的时间复杂度为:O(d lgd)。算法测试 对应的算法实现 Java源文件为 NestedBox.java 输入：X(1,6,2,5,9)，Y(7,4,8,19,32)输出:Y嵌套 X 3)最长嵌套箱序列 最长嵌套箱序列 最长嵌套箱序列 最长嵌套箱序列 算法思想 将 n 个

19、d维箱之间的关系用一棵树来表示，其中可嵌套其它箱子的箱子为父节点，被嵌套的箱子作为孩子节点，无嵌套关系的节点为兄弟节点。这样就一个 d 维箱的深度值就是在这棵树中的深度。i 箱子 深度值的递归定义如下:+=嵌套其它箱子时 当箱子 中 嵌套在 箱子不嵌套其它箱子时 当箱子i i j j Depth Maxi1|)(0 Depth(i)只要找出深度最大的节点，然后递归地输出它嵌套的箱子，结果就是最长嵌套箱序列。贪心选择性质 假设最长 d 维箱序列的一个最优解是 B1,B2,Bk(k1),其对应的深度值分别为 H1,H2,Hk(H1 H2 Hk)。a.若 H1为最大的深度值，则说明问题的最优解以一个

20、贪心选择开始。b.若 H1不是最大的深度值，不妨设 H1Hj(1jk)。但 B1嵌套-9-Bj 可得 H1 Hj。与假设矛盾。所以 H1为最大的深度值，这说明问题的最优解以一个贪心选择开始。最优子结构性质 设嵌套序列 B1,B2,Bk(k1)是问题的一个最优解，各个箱子的深度值为 H1,H2,Hk(H1 H2 Hk)。由贪心选择性质可知 H1为最大深度值，其余箱子组成的序列 B2,B3,Bk(k1)是在所有箱子中去掉 B1 及与其具有相同深度值的箱子后，在剩下的箱子中查找最长嵌套箱序列的一个最优解。因此，最长嵌套箱序列问题具有最优子结构性质。算法实现-求最长嵌套箱序列的伪代码:B为存放 n 个

21、 d 维箱的二维数组 Longest(B,n,d):A 存放各箱子嵌套关系的二维数组,下标从 0 开始,列数为 n+1.Ai,n表示箱子 i的深度值 初始化 A数组 for i 0 to n do Ai,n 0 计算嵌套关系 for i 0 to n 1 do for j i+1 to n 1 do Ai,j nest(Bi,Bj,d)Aj,i Ai,j 递归地修改嵌套的深度值 for i 0 to n 1 do for j 0 to n 1 if Ai,j=1 then addHeight(A,n,i,j)查找深度值最大的箱子作为首嵌套箱 maxBoxIndex findMax()输出最长嵌

22、套箱序列 trace(maxBoxIndex)-递归地修改嵌套箱的深度值 addHeight(A,n,i,j):if Ai,n=Aj,n then Aj,n Aj,n+1-10-for k 0 to n 1 do if Aj,k=1 then addHeight(A,n,j,k)-查找深度值最大的箱子作为首嵌套箱 findMax(A,n):max A0,n maxBoxIndex 0 for i 0 to n 1 do if Ai,n max then max Ai,n maxBoxIndex i return maxBoxIndex-根据深度值最大的箱子,输出最长嵌套箱序列 trace(n,

23、maxIndex):while Amaxn 0 do seq(max+1)+“”+seq m 0 for i 0 to n 1 do if Amax,i=1 and Ai,n=m then m Ai,n temp i max temp seq(max+1)+“”+seq print seq-时间复杂度分析:算法的主要时间消耗在于 Longest()中计算嵌套关系的时候，其中nest()算法的时间复杂度为 O(d lgd)。所以总时间复杂度为:O(n2 d lgd)。算法测试:相应的算法实现文件为 LongestNestedBox.java 输入数据:(8个 6 维箱)5,2,20,1,30,1

24、0,23,15,7,9,11,3,40,50,34,24,14,4,9,10,11,12,13,14,31,4,18,8,27,17,44,32,13,19,41,19,1,2,3,4,5,6,80,37,47,18,21,9 输出数据:(输出数据中的数字代表按顺序输入的箱子，编号从 1开始)最长嵌套箱序列:7256-11-三 三 三 三、四柱汉诺塔问题 四柱汉诺塔问题 四柱汉诺塔问题 四柱汉诺塔问题 3、四塔问题：设有 A，B，C，D四个柱子(有时称塔)，在 A柱上有由小到大堆放的 n个盘子，如图所示。今将 A 柱上的盘子移动到 D 柱上去。可以利用 B，C 柱作为工作栈用，移动的规则如下:

25、每次只能移动一个盘子。在移动的过程中，小盘子只能放到大盘子的上面。设计并实现一个求解四塔问题的动态规划算法，并分析时间和空间复杂性。算法思想:用如下算法移动盘子(记为FourPegsHanoi):1)、将A 柱上n 个盘子划分为上下两部分，下方部分共有k(1kn)个盘子，上方部分共有n-k个盘子。2)、将 A 柱上面部分 nk 个盘子使用 FourPegsHanoi 算法经过C、D 柱移至B 柱。3)、将 A 柱剩余的 k 个盘子使用 ThreePegsHanoi 算法经过 C 柱移至D 柱。4)、将B 柱上的nk 个盘子使用FourPegsHanoi 算法经过A、C柱移至D 柱。ThreeP

26、egsHanoi 算法如下(设三个柱子分别为 A、B、C，A 柱上共有k 个盘子):1)、将 A 柱上方 k-1 个盘子使用 ThreePegsHanoi 算法经过 B 柱移至C 柱。2)、将C 柱上最后一个盘子直接移至C 盘。3)、将 B 柱上 k-1 个盘子使用 ThreePegsHanoi 算法经过 A 柱移至C 柱。-12-算法步骤：根据动态规划的四个步骤，求解如下:1)、最优子结构性质:四柱汉诺塔问题的最优解是用最少的移动次数将 A 柱上的盘子全部移到 D 柱上。当盘子总数为 i 时，我们不妨设使用FourPegsHanoi的最少移动次数为f(i)。相应的ThreePegsHanoi

27、 算法移动次数为g(k)，由于g(k)=2g(k-1)+1=2k-1,当k 确定时，g(k)也是不变的。f(i)为最优解时，其子问题f(i-k)也必为最优解。如果f(i-k)不是最优解，那么存在f(i-k)-+-=1 1 2)(21 1)(min1i k i fii fki k 3)、自底向上地计算最优解的值:(相应的 Java源程序在 Hanoi.java中。)f(i)对应算法中的 mi,si。-求四柱汉诺塔最小移动次数伪代码：数组下标从 0 开始，数组 m,s 大小为 n+1。数组 m存储计算最小移动次数的中间值。数组 s 存储每步最小移动次数所对应的分割值 k。MinMovements(

28、n):m0,0 s0 0 为了方便计算增加了 f(0)=m0,s0=0 for i 1 to n do min for k 1 to i do mi,k 2*mi k,si k+2k 1 if mi,k min then min mi,k si=k return mn,sn&s-13-4)、根据计算信息构造最优解:MinMovements 求出的数组 s 中，si是 f(i)所对应的最优分割位置。根据数组 s 来构造移动盘子的最佳序列，伪代码如下:-FourPegsHanoi(i,src,temp1,temp2,dest):if i=1 then move(src,dest)else Four

29、PegsHanoi(i si,src,temp2,dest,temp1)ThreePegsHanoi(si,src,temp2,dest)FourPegsHanoi(i si,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

30、+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):m0 s0 0 for i 1 to n do mi for k 1 to i do q 2*mi k+2k 1 if q mi then mi q si k return mn&s-14-算法测试 当 n=10 时，最小移动次数 49。移动序列如下:1 A-D 2 A-B 3 A

31、-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

32、 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

33、-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

34、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

35、 122 C-A 123 C-D 124 A-D 125 B-A 126 B-C 127 B-D 128 C-D 129 A-D-15-四 四 四 四、参考文献 参考文献 参考文献 参考文献 1 王晓东.计算机算法设计与分析(第 2 版).北京:电子工业出版社,2004 2 Thomas H.Cormen 等.算法导论(第二版 影印版).北京:高等教育出版社,2002 3 Nicolas Devillard.Fast median search:an ANSI C implementation.http:/ndevilla.free.fr/median/median.pdf,1998 4 宋传鸣,王相海.最长 d维箱嵌套问题的贪心算法.计算机科学.2003 5 谭浩强.C程序设计(第二版).北京:清华大学出版社,1999 6 杨楷,徐川.四柱汉诺塔之初步探究.北京大学学报(自然科学版),2004 7 傅清祥,王晓东.算法与数据结构.北京:电子工业出版社,1998 8 William H.Press等.C数值方法(第二版).北京:电子工业出版社,2004