《计算机算法基础》第三版,课后习题答案

4.11写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。答： 见《数据结构》

算法MPass（R，n，1ength．X） MP1 [初始化] i 1．\

MP2 [合并相邻的两个长度为length的子文件] WHILE i≤n–2*length + 1 DO

（Merge（R，i，i＋length–l，i＋2*length– 1．\）.i

i＋2*length）．

MP3 [处理余留的长度小于2*length的子文件] IF i+length–1 < n

THEN Merge（R，i，i+length–1，n. X）

ELSE FOR j = i TO n DO Xj←Rj▌算法MSort(R，排序算法，X是辅助文件，其记录结构与R相同

MS1 [初始化] length 1．\

MS2 [交替合并] WHILE length < n DO

（MPass（R，n，length．X）.

6 / 38

n) //直接两路合并

length2*length

if length > n

then FOR j = 1 TO n DO Rj←Xj else MPass（X，n，length．R）. length2*length）

endif)

4.23通过手算证明（ 4.\）和(

4.\式确实能得到C 11,C 12,C 21和C 22的正确值。 P=(A 11+A 22)(B 11+B

22) T=(A 11+A 12)B 22

7 / 38

Q=(A 21+A 22)B 11U=(A 21-A 11)(B 11+B 12) R=A 11(B 12-B

22) V=(A 12-A 22)(B 21+B 22)

S=A22(B21-B11)C11=P+S-T+V =(A 11+A22)(B 11+B 22) +A

8 / 38

22(B 21-B 11) -(A 11+A 12)B 22+(A 12-A 22)(B 21+B 22)=A 11B 11+A 22B 11+A 11B 22+A 22B 22+A 22B 21 -A

9 / 38

22B 11-A 11B 22-A 12B 22+A 12B 21+A 12B 22-A 22B 21-A 22B 22 =A 11B 11+A 12B 21C12=R+T = A 11B

10 / 38