用c++编写对于两个 n×n 的矩阵 A 和 B，计算 C=A×B。采用分治法设计实现更有效的算法。

可以采用Strassen算法来对两个矩阵进行分治计算，时间复杂度为O(n^log2(7))。

以下是C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

void strassen(int n, int **A, int **B, int **C);
void add(int n, int **A, int **B, int **C);
void sub(int n, int **A, int **B, int **C);
void split(int n, int **A, int ***A11, int ***A12, int ***A21, int ***A22);
void merge(int n, int ***A11, int ***A12, int ***A21, int ***A22, int **A);
void printMatrix(int n, int **A);

int main()
{
    int n;
    printf("Enter the size of matrix: ");
    scanf("%d", &n);

    int **A, **B, **C;
    A = (int **)malloc(n * sizeof(int *));
    B = (int **)malloc(n * sizeof(int *));
    C = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++)
    {
        A[i] = (int *)malloc(n * sizeof(int));
        B[i] = (int *)malloc(n * sizeof(int));
        C[i] = (int *)malloc(n * sizeof(int));
    }

    printf("Enter elements of matrix A:\n");
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &A[i][j]);
        }
    }

    printf("Enter elements of matrix B:\n");
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &B[i][j]);
        }
    }

    strassen(n, A, B, C);

    printf("Resultant matrix C is:\n");
    printMatrix(n, C);

    for (int i = 0; i < n; i++)
    {
        free(A[i]);
        free(B[i]);
        free(C[i]);
    }
    free(A);
    free(B);
    free(C);

    return 0;
}

void strassen(int n, int **A, int **B, int **C)
{
    if (n == 1)
    {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }

    int **A11, **A12, **A21, **A22, **B11, **B12, **B21, **B22;
    A11 = (int **)malloc((n / 2) * sizeof(int *));
    A12 = (int **)malloc((n / 2) * sizeof(int *));
    A21 = (int **)malloc((n / 2) * sizeof(int *));
    A22 = (int **)malloc((n / 2) * sizeof(int *));
    B11 = (int **)malloc((n / 2) * sizeof(int *));
    B12 = (int **)malloc((n / 2) * sizeof(int *));
    B21 = (int **)malloc((n / 2) * sizeof(int *));
    B22 = (int **)malloc((n / 2) * sizeof(int *));
    for (int i = 0; i < n / 2; i++)
    {
        A11[i] = (int *)malloc((n / 2) * sizeof(int));
        A12[i] = (int *)malloc((n / 2) * sizeof(int));
        A21[i] = (int *)malloc((n / 2) * sizeof(int));
        A22[i] = (int *)malloc((n / 2) * sizeof(int));
        B11[i] = (int *)malloc((n / 2) * sizeof(int));
        B12[i] = (int *)malloc((n / 2) * sizeof(int));
        B21[i] = (int *)malloc((n / 2) * sizeof(int));
        B22[i] = (int *)malloc((n / 2) * sizeof(int));
    }

    split(n, A, &A11, &A12, &A21, &A22);
    split(n, B, &B11, &B12, &B21, &B22);

    int **P1, **P2, **P3, **P4, **P5, **P6, **P7;
    P1 = (int **)malloc((n / 2) * sizeof(int *));
    P2 = (int **)malloc((n / 2) * sizeof(int *));
    P3 = (int **)malloc((n / 2) * sizeof(int *));
    P4 = (int **)malloc((n / 2) * sizeof(int *));
    P5 = (int **)malloc((n / 2) * sizeof(int *));
    P6 = (int **)malloc((n / 2) * sizeof(int *));
    P7 = (int **)malloc((n / 2) * sizeof(int *));
    for (int i = 0; i < n / 2; i++)
    {
        P1[i] = (int *)malloc((n / 2) * sizeof(int));
        P2[i] = (int *)malloc((n / 2) * sizeof(int));
        P3[i] = (int *)malloc((n / 2) * sizeof(int));
        P4[i] = (int *)malloc((n / 2) * sizeof(int));
        P5[i] = (int *)malloc((n / 2) * sizeof(int));
        P6[i] = (int *)malloc((n / 2) * sizeof(int));
        P7[i] = (int *)malloc((n / 2) * sizeof(int));
    }

    int **A_temp1, **A_temp2, **B_temp1, **B_temp2, **C11, **C12, **C21, **C22;
    A_temp1 = (int **)malloc((n / 2) * sizeof(int *));
    A_temp2 = (int **)malloc((n / 2) * sizeof(int *));
    B_temp1 = (int **)malloc((n / 2) * sizeof(int *));
    B_temp2 = (int **)malloc((n / 2) * sizeof(int *));
    C11 = (int **)malloc((n / 2) * sizeof(int *));
    C12 = (int **)malloc((n / 2) * sizeof(int *));
    C21 = (int **)malloc((n / 2) * sizeof(int *));
    C22 = (int **)malloc((n / 2) * sizeof(int *));
    for (int i = 0; i < n / 2; i++)
    {
        A_temp1[i] = (int *)malloc((n / 2) * sizeof(int));
        A_temp2[i] = (int *)malloc((n / 2) * sizeof(int));
        B_temp1[i] = (int *)malloc((n / 2) * sizeof(int));
        B_temp2[i] = (int *)malloc((n / 2) * sizeof(int));
        C11[i] = (int *)malloc((n / 2) * sizeof(int));
        C12[i] = (int *)malloc((n / 2) * sizeof(int));
        C21[i] = (int *)malloc((n / 2) * sizeof(int));
        C22[i] = (int *)malloc((n / 2) * sizeof(int));
    }

    // P1 = (A11 + A22) * (B11 + B22)
    add(n / 2, A11, A22, A_temp1);
    add(n / 2, B11, B22, B_temp1);
    strassen(n / 2, A_temp1, B_temp1, P1);

    // P2 = (A21 + A22) * B11
    add(n / 2, A21, A22, A_temp1);
    strassen(n / 2, A_temp1, B11, P2);

    // P3 = A11 * (B12 - B22)
    sub(n / 2, B12, B22, B_temp1);
    strassen(n / 2, A11, B_temp1, P3);

    // P4 = A22 * (B21 - B11)
    sub(n / 2, B21, B11, B_temp1);
    strassen(n / 2, A22, B_temp1, P4);

    // P5 = (A11 + A12) * B22
    add(n / 2, A11, A12, A_temp1);
    strassen(n / 2, A_temp1, B22, P5);

    // P6 = (A21 - A11) * (B11 + B12)
    sub(n / 2, A21, A11, A_temp1);
    add(n / 2, B11, B12, B_temp1);
    strassen(n / 2, A_temp1, B_temp1, P6);

    // P7 = (A12 - A22) * (B21 + B22)
    sub(n / 2, A12, A22, A_temp1);
    add(n / 2, B21, B22, B_temp1);
    strassen(n / 2, A_temp1, B_temp1, P7);

    // C11 = P1 + P4 - P5 + P7
    add(n / 2, P1, P4, C11);
    sub(n / 2, C11, P5, C11);
    add(n / 2, C11, P7, C11);

    // C12 = P3 + P5
    add(n / 2, P3, P5, C12);

    // C21 = P2 + P4
    add(n / 2, P2, P4, C21);

    // C22 = P1 - P2 + P3 + P6
    sub(n / 2, P1, P2, C22);
    add(n / 2, C22, P3, C22);
    add(n / 2, C22, P6, C22);

    merge(n, &C11, &C12, &C21, &C22, C);

    for (int i = 0; i < n / 2; i++)
    {
        free(A11[i]);
        free(A12[i]);
        free(A21[i]);
        free(A22[i]);
        free(B11[i]);
        free(B12[i]);
        free(B21[i]);
        free(B22[i]);
        free(P1[i]);
        free(P2[i]);
        free(P3[i]);
        free(P4[i]);
        free(P5[i]);
        free(P6[i]);
        free(P7[i]);
        free(A_temp1[i]);
        free(A_temp2[i]);
        free(B_temp1[i]);
        free(B_temp2[i]);
        free(C11[i]);
        free(C12[i]);
        free(C21[i]);
        free(C22[i]);
    }
    free(A11);
    free(A12);
    free(A21);
    free(A22);
    free(B11);
    free(B12);
    free(B21);
    free(B22);
    free(P1);
    free(P2);
    free(P3);
    free(P4);
    free(P5);
    free(P6);
    free(P7);
    free(A_temp1);
    free(A_temp2);
    free(B_temp1);
    free(B_temp2);
    free(C11);
    free(C12);
    free(C21);
    free(C22);
}

void add(int n, int **A, int **B, int **C)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
}

void sub(int n, int **A, int **B, int **C)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            C[i][j] = A[i][j] - B[i][j];
        }
    }
}

void split(int n, int **A, int ***A11, int ***A12, int ***A21, int ***A22)
{
    *A11 = (int **)malloc((n / 2) * sizeof(int *));
    *A12 = (int **)malloc((n / 2) * sizeof(int *));
    *A21 = (int **)malloc((n / 2) * sizeof(int *));
    *A22 = (int **)malloc((n / 2) * sizeof(int *));
    for (int i = 0; i < n / 2; i++)
    {
        (*A11)[i] = (int *)malloc((n / 2) * sizeof(int));
        (*A12)[i] = (int *)malloc((n / 2) * sizeof(int));
        (*A21)[i] = (int *)malloc((n / 2) * sizeof(int));
        (*A22)[i] = (int *)malloc((n / 2) * sizeof(int));
    }

    for (int i = 0; i < n / 2; i++)
    {
        for (int j = 0; j < n / 2; j++)
        {
            (*A11)[i][j] = A[i][j];
            (*A12)[i][j] = A[i][j + n / 2];
            (*A21)[i][j] = A[i + n / 2][j];
            (*A22)[i][j] = A[i + n / 2][j + n / 2];
        }
    }
}

void merge(int n, int ***A11, int ***A12, int ***A21, int ***A22, int **A)
{
    for (int i = 0; i < n / 2; i++)
    {
        for (int j = 0; j < n / 2; j++)
        {
            A[i][j] = (*A11)[i][j];
            A[i][j + n / 2] = (*A12)[i][j];
            A[i + n / 2][j] = (*A21)[i][j];
            A[i + n / 2][j + n / 2] = (*A22)[i][j];
        }
    }
}

void printMatrix(int n, int **A)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }
}