资源描述：
《多米诺-分治法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机算法设计与分析分治法求解多米诺骨牌题目：现有n块“多米诺骨牌”S1，S2，……，Sn水平放成一排，每块骨牌Si包含左右两个部分，每个部分赋予一个非负整数值，如下图所示为包含6块骨牌的序列。骨牌可做180度旋转，使得原来在左边的值变到右边，而原来在右边的值移到左边，假设不论si如何旋转，L[i]总是存储si左边的值，R[i]总是存储右边的值，W[i]用于存储si的状态：当L[i]<=R[i]时记为0，否则记为1，试采用分治法设计算法求i=1n-1R[i]L[i+1]最大值，以及当取得最大之时每个骨牌的状态。解：输入为n个多米诺骨牌S1，S2，……，Sn，可将输入在中间那块骨牌的中间，即
2、骨牌S1+n2的中间处拆分，这样原问题就被拆分为两个子问题，但是可以发现，新的子问题与原问题结构不完全一样。为解决这一问题，可对原始的输入作如下处理：此处拆分在原始输入序列左右两端各加半块骨牌，记为S0和Sn+1，对应于L、R则为R[0]和L[n+1]，并且令R[0]和L[n+1]里面的值为0。如下图所示：则原规模为n的问题求MAX（i=1n-1R[i]L[i+1]）变为规模为规模为n+2的问题求i=0nR[i]L[i+1]，结构有所变化，但实际上由于左右两边加的半块骨牌中的元素值为0，对原问题结果并不会产生影响。这时在按原来的拆分方法进行拆分，就可将问题拆为两个规模为原问题一半的子问题。
3、具体算法如下：(其中数组W用于存放所求和最大时各个骨牌的状态，first和last分别为第一块和最后一块骨牌的序号)AlgorithmMax_of_Domino(L,R,first,last,W)1.iflast-first=0thenreturn;//骨牌数不能少于两个2.R[first-1]=0,L[last+1]=0;3.Max=Simplify_Max_of_Domino(L,R,first-1,last+1);4.returnMax;AlgorithmSimplify_Max_of_Domino(L,R,first,last)1.iflast-first=1thenMax=R[f
4、irst]*L[last];2.elsemid=<(first+last)/2>;//这里用<>表示上取整1.ifL[mid]>R[mid]//L>R,这时W[mid]状态为12.MaxL1=Simplify_Max_of_Domino(L,R,first,mid);3.MaxR1=Simplify_Max_of_Domino(L,R,mid,last);4.Max1=MaxL1+MaxR1;5.Swap(L[mid],R[mid]);//再交换被拆分的骨牌的左右半块，使W[mid]状态为06.MaxL0=Simplify_Max_of_Domino(L,R,first,mid);7.Ma
5、xR0=Simplify_Max_of_Domino(L,R,mid,last);8.Max0=MaxL0+MaxR0;9.ifMax1>Max010.Max=Max1,W[mid]=1;11.elseMax=Max0,W[mid]=0;12.else//L<=R,W[mid]=013.MaxL0=Simplify_Max_of_Domino(L,R,first,mid);14.MaxR0=Simplify_Max_of_Domino(L,R,mid,last);15.Max0=MaxL0+MaxR0;16.Swap(L[mid],R[mid]);//再交换被拆分的骨牌的左右半块，使W[m
6、id]状态为017.MaxL1=Simplify_Max_of_Domino(L,R,first,mid);18.MaxR1=Simplify_Max_of_Domino(L,R,mid,last);19.Max1=MaxL1+MaxR1;20.ifMax1>Max021.Max=Max1,W[mid]=1;22.ElseMax=Max0,W[mid]=0;23.end24.end25.returnMax;现在分析时间复杂度：算法中较多的操作是乘法操作，可将乘法操作视为关键操作，除法也看作是乘法。用T(n)表示原问题的时间复杂度，H(n)为加入两个半块，即R[0]和L[n+1]后的问题的时
7、间复杂度，则有：T(n)=H(n+2);n>=2由算法可知：H(n)=2(H(n/2)+H(n/2))+1=4H(n/2)+1;根据主定理：b=4,c=2;E=logcb=2;f(n)=1;...H(n)∈O(n2);T(n)=H(n+2)∈O(n2);原问题以乘法为关键操作的时间复杂度为：A(n)∈O(n2)
