算法导论第四章习题解答

def matrixGetSub(matrix, row1, row2, col1, col2): data = [] rows = matrix[row1:row2] for row in rows: data.append(row[col1:col2]) return data def matrixAdd(m1, m2): assert(len(m1) == len(m2)) result = [[0 for col in range(len(m1))] for row in range(len(m1))] for i in range(0, len(m1)): for j in range(0, len(m1)): result[i][j] = m1[i][j] + m2[i][j] return result def matrixSub(m1, m2): assert(len(m1) == len(m2)) result = [[0 for col in range(len(m1))] for row in range(len(m1))] for i in range(0, len(m1)): for j in range(0, len(m1)): result[i][j] = m1[i][j] - m2[i][j] return result def matrixMerge(A, A11, A12, A21, A22): assert(len(A11) == len(A12)) assert(len(A) <= len(A11) + len(A21)) mid = (len(A) + 1) // 2 for i in range(0, len(A)): for j in range(0, len(A)): if i < mid and j < mid: A[i][j] = A11[i][j] elif i < mid and j >= mid: A[i][j] = A12[i][j-mid] elif i >= mid and j < mid: A[i][j] = A21[i- mid][j] elif i >= mid and j >= mid: A[i][j] = A22[i - mid][j-mid] def matrixExtend(A): """ 进行这样的一次扩展并不增加递归乘法的次数，其复杂的依然是theta(n^lg7) """ n = len(A) if (n % 2) != 0: n = n + 1 else: return A extend = [[0 for col in range(n)] for row in range(n)] for i in range(0, len(A)): for j in range(0, len(A)): extend[i][j] = A[i][j] return extend def STRASSEN_METHOD(A, B): assert(len(A) == len(B)) n = len(A) C = [[0 for col in range(n)] for row in range(n)] if n == 1: C[0][0] = A[0][0] * B[0][0] else: if (n % 2) != 0: A = matrixExtend(A) B = matrixExtend(B) n = len(A) mid = len(A)//2 A11 = matrixGetSub(A, 0, mid, 0, mid) A12 = matrixGetSub(A, 0, mid, mid, n) A21 = matrixGetSub(A, mid, n, 0, mid) A22 = matrixGetSub(A, mid, n, mid, n) B11 = matrixGetSub(B, 0, mid, 0, mid) B12 = matrixGetSub(B, 0, mid, mid, n) B21 = matrixGetSub(B, mid, n, 0, mid) B22 = matrixGetSub(B, mid, n, mid, n) S1 = matrixSub(B12, B22) S2 = matrixAdd(A11, A12) S3 = matrixAdd(A21, A22) S4 = matrixSub(B21, B11) S5 = matrixAdd(A11, A22) S6 = matrixAdd(B11, B22) S7 = matrixSub(A12, A22) S8 = matrixAdd(B21, B22) S9 = matrixSub(A11, A21) S10 = matrixAdd(B11, B12) P1 = STRASSEN_METHOD(A11, S1) P2 = STRASSEN_METHOD(S2, B22) P3 = STRASSEN_METHOD(S3, B11) P4 = STRASSEN_METHOD(A22, S4) P5 = STRASSEN_METHOD(S5, S6) P6 = STRASSEN_METHOD(S7, S8) P7 = STRASSEN_METHOD(S9, S10) C11 = matrixAdd(matrixSub(matrixAdd(P5, P4), P2), P6) C12 = matrixAdd(P1, P2) C21 = matrixAdd(P3, P4) C22 = matrixSub(matrixSub(matrixAdd(P5, P1), P3), P7) matrixMerge(C, C11, C12, C21, C22) return C def SQUARE_MATRIX_MULTIPLY(A, B): assert(len(A) == len(B)) n = len(A) C = [[0 for col in range(n)] for row in range(n)] for i in range(0, n): for j in range(0, n): for k in range(0, n): C[i][j]= C[i][j] + A[i][k]*B[k][j] return C if __name__ == "__main__" : A = [[1, 3, 5], [7, 5, 2], [6, 23, 1]] B = [[6, 8, 3], [4, 2, 12], [12, 5, 8]] C = SQUARE_MATRIX_MULTIPLY(A, B) print(C) C = STRASSEN_METHOD(A, B) print(C)