转载

算法导论（第三版）Exercises4.2(第四章二节）

4.2-1（计算结果）

18 14

62 66

4.2-2（Strassen算法计算矩阵乘法）

void multiplyMatrix(int a[], int b[], int n, int result[]) {  int i, j, dim=n/2;  int n1=(n/2) * (n/2);  int a11[n1], a12[n1], a21[n1], a22[n1];  int b11[n1], b12[n1], b21[n1], b22[n1];  int s1[n1], s2[n1], s3[n1], s4[n1], s5[n1];  int s6[n1], s7[n1], s8[n1], s9[n1], s10[n1];  int p1[n1], p2[n1], p3[n1], p4[n1];  int p5[n1], p6[n1], p7[n1];  int c11[n1], c12[n1], c21[n1], c22[n1];  if(n == 1)  {   result[0] = a[0] * b[0];   return;  }  if(n%2 != 0)  {   printf("wrong array!/n");   return;  }  divideMatrix(a, n, a11, a12, a21, a22);  divideMatrix(b, n, b11, b12, b21, b22);  subtractMatrix(b12, b22, dim, s1);  addMatrix(a11, a12, dim, s2);  addMatrix(a21, a22, dim, s3);  subtractMatrix(b21, b11, dim, s4);  addMatrix(a11, a22, dim, s5);  addMatrix(b11, b22, dim, s6);  subtractMatrix(a12, a22, dim, s7);  addMatrix(b21, b22, dim, s8);  subtractMatrix(a11, a21, dim, s9);  addMatrix(b11, b12, dim, s10);  multiplyMatrix(a11, s1, dim, p1);  multiplyMatrix(s2, b22, dim, p2);  multiplyMatrix(s3, b11, dim, p3);  multiplyMatrix(a22, s4, dim, p4);  multiplyMatrix(s5, s6, dim, p5);  multiplyMatrix(s7, s8, dim, p6);  multiplyMatrix(s9, s10, dim, p7);  addMatrix(p5, p4, dim, c11);  subtractMatrix(c11, p2, dim, c11);  addMatrix(c11, p6, dim, c11);  addMatrix(p1, p2, dim, c12);  addMatrix(p3, p4, dim, c21);  addMatrix(p5, p1, dim, c22);  subtractMatrix(c22, p3, dim, c22);  subtractMatrix(c22, p7, dim, c22);  combineMatrix(c11, c12, c21, c22, dim, result); } void addMatrix(int a[], int b[], int n, int result[]) {  int i;  for(i=0; i<n*n; i++) result[i] = a[i] + b[i]; } void subtractMatrix(int a[], int b[], int n, int result[]) {  int i;  for(i=0; i<n*n; i++) result[i] = a[i] - b[i]; } void divideMatrix(int a[], int n, int a11[], int a12[], int a21[], int a22[]) {  int i, mid, j, k, h;  mid = n / 2;  for(i=0; i<mid; i++)  {   for(j=0; j<mid; j++)   {    h = i * mid + j;    k = i * n + j;    a11[h] = a[k];    a12[h] = a[k+mid];    a21[h] = a[k+n*n/2];    a22[h] = a[k+n*n/2+mid];   }  } } void combineMatrix(int a11[], int a12[], int a21[], int a22[], int n, int result[]) {  int i, j, h, k, dim, mid;  mid = n;  dim = mid * 2;  for(i=0; i<mid; i++)  {   for(j=0; j<mid; j++)   {    h = i * mid + j;    k = i * dim + j;    result[k] = a11[h];    result[k+mid] = a12[h];    result[k+n*n*2] = a21[h];    result[k+n*n*2+mid] = a22[h];   }  } }

4.2-3

当矩阵的n不是2的指数时，添加0补足，即可按上述算法运行

4.2-4

4.2-5

72x72的那个最佳，比Strassen算法好

4.2-6

当knXn矩阵时，按4.2-3的方法处理，同样nXkn也一样，可以看出nXkn计算时间短

4.2-7(用数组存储复数）

void multiplyComplex(double c1[], double c2[], double result[]) {  double p1, p2, p3;  p1 = c1[0] + c1[1];  p2 = c2[0] + c2[1];  p1 = p1 * p2;  p2 = c1[0] * c2[0];  p3 = c1[1] * c2[1];  result[0] = p2 - p3;  result[1] = p1 - p2 - p3; }