《算法导论》第 4 章 - 分治策略

#include <iostream>
#include <vector>
#include <climits> // 用于INT_MIN
#include <algorithm> // 用于max函数

using namespace std;

/**
 * 计算跨越中间点的最大子数组和
 * @param nums 输入数组
 * @param left 左边界索引
 * @param mid 中间索引
 * @param right 右边界索引
 * @return 跨越中间点的最大子数组和
 */
int maxCrossingSubarray(const vector<int>& nums, int left, int mid, int right) {
    // 计算左半部分（从mid向左）的最大和
    int left_sum = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= left; --i) {
        sum += nums[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // 计算右半部分（从mid+1向右）的最大和
    int right_sum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= right; ++i) {
        sum += nums[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // 返回左右两部分的和（跨越中间点）
    return left_sum + right_sum;
}

/**
 * 递归求解最大子数组和
 * @param nums 输入数组
 * @param left 左边界索引
 * @param right 右边界索引
 * @return 最大子数组和
 */
int maxSubarrayRecursive(const vector<int>& nums, int left, int right) {
    // 基本情况：数组只有一个元素
    if (left == right) {
        return nums[left];
    }

    // 计算中间索引
    int mid = (left + right) / 2;

    // 递归求解左子数组、右子数组的最大和
    int left_sum = maxSubarrayRecursive(nums, left, mid);
    int right_sum = maxSubarrayRecursive(nums, mid + 1, right);

    // 求解跨越中间的最大和
    int cross_sum = maxCrossingSubarray(nums, left, mid, right);

    // 返回三者中的最大值
    return max({left_sum, right_sum, cross_sum});
}

/**
 * 最大子数组问题的分治解法
 * @param nums 输入数组
 * @return 最大子数组和
 */
int maxSubArray(const vector<int>& nums) {
    if (nums.empty()) {
        throw invalid_argument("数组不能为空");
    }
    return maxSubarrayRecursive(nums, 0, nums.size() - 1);
}

// 测试函数
int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "数组: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    try {
        int result = maxSubArray(nums);
        cout << "最大子数组和: " << result << endl; // 预期输出：6
    } catch (const invalid_argument& e) {
        cout << "错误: " << e.what() << endl;
    }

    return 0;
}

A = [[A₁₁, A₁₂],    B = [[B₁₁, B₁₂],    C = [[C₁₁, C₁₂],
     [A₂₁, A₂₂]]         [B₂₁, B₂₂]]         [C₂₁, C₂₂]]

#include <iostream>
#include <vector>
#include <cmath> // 用于ceil函数

using namespace std;

// 定义矩阵类型
using Matrix = vector<vector<int>>;

/**
 * 矩阵加法
 * @param A 矩阵A
 * @param B 矩阵B
 * @return 矩阵A + B
 */
Matrix add(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix result(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            result[i][j] = A[i][j] + B[i][j];
        }
    }
    return result;
}

/**
 * 矩阵减法
 * @param A 矩阵A
 * @param B 矩阵B
 * @return 矩阵A - B
 */
Matrix subtract(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix result(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            result[i][j] = A[i][j] - B[i][j];
        }
    }
    return result;
}

/**
 * 普通矩阵乘法（用于小矩阵或边界情况）
 * @param A 矩阵A
 * @param B 矩阵B
 * @return 矩阵A * B
 */
Matrix multiplyNaive(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix result(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < n; ++k) {
            if (A[i][k] != 0) { // 优化：跳过零元素
                for (int j = 0; j < n; ++j) {
                    result[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }
    return result;
}

/**
 * 将大矩阵分割为4个子矩阵
 * @param parent 父矩阵
 * @param child 子矩阵（输出）
 * @param row 子矩阵在父矩阵中的起始行（0或n/2）
 * @param col 子矩阵在父矩阵中的起始列（0或n/2）
 * @param n 子矩阵的大小
 */
void splitMatrix(const Matrix& parent, Matrix& child, int row, int col, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            child[i][j] = parent[row + i][col + j];
        }
    }
}

/**
 * 将4个子矩阵合并为大矩阵
 * @param parent 父矩阵（输出）
 * @param child 子矩阵
 * @param row 子矩阵在父矩阵中的起始行（0或n/2）
 * @param col 子矩阵在父矩阵中的起始列（0或n/2）
 * @param n 子矩阵的大小
 */
void mergeMatrix(Matrix& parent, const Matrix& child, int row, int col, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            parent[row + i][col + j] = child[i][j];
        }
    }
}

/**
 * Strassen算法实现矩阵乘法
 * @param A 矩阵A
 * @param B 矩阵B
 * @return 矩阵A * B
 */
Matrix strassenMultiply(const Matrix& A, const Matrix& B) {
    int n = A.size();

    // 基本情况：当矩阵大小较小时，使用普通乘法（效率更高）
    if (n <= 64) { // 阈值可调整，通常取64或32
        return multiplyNaive(A, B);
    }

    // 计算新的矩阵大小（确保是2的幂，便于分割）
    int new_size = 1;
    while (new_size < n) {
        new_size <<= 1; // 等价于new_size *= 2
    }

    // 补全矩阵为new_size x new_size（不足部分补0）
    Matrix A_padded(new_size, vector<int>(new_size, 0));
    Matrix B_padded(new_size, vector<int>(new_size, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            A_padded[i][j] = A[i][j];
            B_padded[i][j] = B[i][j];
        }
    }

    // 分割矩阵为4个子矩阵
    int half = new_size / 2;
    Matrix A11(half, vector<int>(half));
    Matrix A12(half, vector<int>(half));
    Matrix A21(half, vector<int>(half));
    Matrix A22(half, vector<int>(half));
    Matrix B11(half, vector<int>(half));
    Matrix B12(half, vector<int>(half));
    Matrix B21(half, vector<int>(half));
    Matrix B22(half, vector<int>(half));

    splitMatrix(A_padded, A11, 0, 0, half);
    splitMatrix(A_padded, A12, 0, half, half);
    splitMatrix(A_padded, A21, half, 0, half);
    splitMatrix(A_padded, A22, half, half, half);

    splitMatrix(B_padded, B11, 0, 0, half);
    splitMatrix(B_padded, B12, 0, half, half);
    splitMatrix(B_padded, B21, half, 0, half);
    splitMatrix(B_padded, B22, half, half, half);

    // 计算7个中间矩阵
    Matrix M1 = strassenMultiply(add(A11, A22), add(B11, B22));
    Matrix M2 = strassenMultiply(add(A21, A22), B11);
    Matrix M3 = strassenMultiply(A11, subtract(B12, B22));
    Matrix M4 = strassenMultiply(A22, subtract(B21, B11));
    Matrix M5 = strassenMultiply(add(A11, A12), B22);
    Matrix M6 = strassenMultiply(subtract(A21, A11), add(B11, B12));
    Matrix M7 = strassenMultiply(subtract(A12, A22), add(B21, B22));

    // 计算C的4个子矩阵
    Matrix C11 = add(subtract(add(M1, M4), M5), M7);
    Matrix C12 = add(M3, M5);
    Matrix C21 = add(M2, M4);
    Matrix C22 = add(subtract(add(M1, M3), M2), M6);

    // 合并子矩阵
    Matrix C_padded(new_size, vector<int>(new_size));
    mergeMatrix(C_padded, C11, 0, 0, half);
    mergeMatrix(C_padded, C12, 0, half, half);
    mergeMatrix(C_padded, C21, half, 0, half);
    mergeMatrix(C_padded, C22, half, half, half);

    // 截取结果为n x n矩阵（去除补全的部分）
    Matrix C(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            C[i][j] = C_padded[i][j];
        }
    }

    return C;
}

/**
 * 打印矩阵
 * @param mat 要打印的矩阵
 */
void printMatrix(const Matrix& mat) {
    for (const auto& row : mat) {
        for (int val : row) {
            cout << val << "\t";
        }
        cout << endl;
    }
}

// 测试函数
int main() {
    // 测试用例：2x2矩阵乘法
    Matrix A = {{1, 2},
                {3, 4}};
    Matrix B = {{5, 6},
                {7, 8}};

    cout << "矩阵A:" << endl;
    printMatrix(A);
    cout << endl << "矩阵B:" << endl;
    printMatrix(B);

    Matrix C_naive = multiplyNaive(A, B);
    cout << endl << "普通乘法结果:" << endl;
    printMatrix(C_naive);

    Matrix C_strassen = strassenMultiply(A, B);
    cout << endl << "Strassen算法结果:" << endl;
    printMatrix(C_strassen);

    // 测试用例：3x3矩阵乘法
    Matrix D = {{1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}};
    Matrix E = {{9, 8, 7},
                {6, 5, 4},
                {3, 2, 1}};

    cout << endl << "矩阵D:" << endl;
    printMatrix(D);
    cout << endl << "矩阵E:" << endl;
    printMatrix(E);

    Matrix F_naive = multiplyNaive(D, E);
    cout << endl << "普通乘法结果:" << endl;
    printMatrix(F_naive);

    Matrix F_strassen = strassenMultiply(D, E);
    cout << endl << "Strassen算法结果:" << endl;
    printMatrix(F_strassen);

    return 0;
}