分治法作业答案.docVIP

1. 合并排序问题（分成四部分的情况） 算法 1. Merge4(A，1，n) 递归过程Merge4(A, low, high) 1. if lowhigh then 2. mid=(low+high)/2 3. mid1=(low+mid)/2 4. mid2=(mid+1+high)/2 5. Merge4(A, low, mid1) 6. Merge4(A, mid1+1, mid) 7. Merge4(A, mid+1, mid2) 8. Merge4(A, mid2+1, high) 9. MERGE(A, low, mid1,mid) 10. MERGE(A,mid+1,mid2,high) 11. MERGE(A,low,mid,high) 12. endif 算法分析： 最少情况： =nlog4n = nlogn /2 最多情况： = 2nlog4n-n+1 = nlogn-n+1 2. 利用分治法判断两棵二叉树是否相同。 算法 1. CmpBinTree(T1，T2) 递归过程CmpBinTree(T1，T2) 1. if (!T1 !T2) then 2. return true 3. else if(!T1 || !T2) || ( T1-data != T2-data ) 4. return false 5. else 6. SameL=CmpBinTree(T1-Lchild, T2-Lchild) 7. SameR=CmpBinTree(T1-Rchild, T2-Rchild) 8. return (SameL SameR) 9. end if 3. 利用分治法求二叉树的高度。 算法 1. hight=BinTreeHight(T1) 递归过程BinTreeHight(T1) 1. if (!T1-Lchild !T1-Rchild) then 2. return 0 3. else 4. HightL=BinTreeHight (T1-Lchild) 5. HightR=BinTreeHight (T1-Rchild) 6. return MAX(HightL , HightR)+1 7. end if 4. 大整数乘法,设两个大整数的位数n=2k。 算法1： Multi(u,v,n) 递归过程Multi(u,v,n) if n=1 then return u*v else w ← u的前n/2位 x ← u的后n/2位 y ← v的前n/2位 z ← v的后n/2位 m1 ← Multi(w,y,n/2) m2 ← Multi(w,z,n/2) m3 ← Multi(x,y,n/2) m4 ← Multi(x,z,n/2) m=m1*2n+(m2+m3)*2n/2+m4 return m endif 算法2： Multi(u,v,n) 递归过程Multi(u,v,n) if n=1 then return u*v else w ← u的前n/2位 x ← u的后n/2位 y ← v的前n/2位 z ← v的后n/2位 m1 ← Multi(w,y,n/2) m2 ← Multi(w-x,z-y,n/2) m3 ← Multi(x,z,n/2) m=m1*2n+(m2+m1+m3)*2n/2+m3 return m endif 5. 矩阵乘法 算法： MatrixMulti(A, B, n) 递归过程MatrixMulti(A, B, n) if n=1 then return A*B else 将A矩阵分为四个n/2*n/2的小矩阵(A11,A12,A21,A22) 将B矩阵分为四个n/2*n/2的小矩阵(B11,B12,B21,B22) D1←MatrixMulti ( A11+A22, B11+B22, n/2) D2←MatrixMulti ( A21+A22, B11, n/2) D3←MatrixMulti ( A11, B12-B22, n/2) D4←MatrixMulti (A22, B21-B11, n/2) D5←MatrixMulti ( A11+A12, B22, n/2