分治策略的实现

前言

分治策略的应用

最大子数组问题

矩阵乘法问题

求解递归式的三种方法

代入法求递归式

用递归树求递归式

主方法求递归式

前言

分治三个步骤：

分解：分解原问题为子问题，这些子问题为原问题的较小规模的问题。

解决：递归地解决这些子问题，如果规模小到一定程度，则直接得出答案。

合并：合并上述解决地子问题地解，得出最终解。

递归情况：当子问题规模比较大时，成为递归情况；

基本情况：当子问题规模不需要递归，已经触底时，此时称作基本情况。

递归式：刻画算法的运行时间的等式或者不等式，如归并排序中的最坏情况下的时间复杂

分治策略的应用

最大子数组问题

最大子数组：一个数组中的非空连续的数组元素和最大的集合成为最大子数组。

a[4] = {-1，-2，3，4};

数组a的子数组有{-1}，{-2}，{3}，{4}，{-1，-2}，{-2，3}，{3，4}，{-1，-2，3}，

{-2，3，4}，{-1，-2，3，4}.

其中{3,4}子数组的和为7，是这些数组中和最大的子数组。

代码：

#include "stdio.h"
#define MAXSIZE 100
#define MINNUM -10000
int *find_cross_max_subarray(int A[MAXSIZE], int low, int mid, int high);
int *find_maxium_subarray(int a[MAXSIZE], int low, int high);
int *max(int *x, int *y, int *z);
int result[3] = {0};

void main() {
    int A[6] = {-1,3,-2,5,-4, 6};
    find_maxium_subarray(A, 0, 5);
    printf("%d, %d, %d", result[0], result[1], result[2]);
}

int *find_cross_max_subarray(int A[MAXSIZE], int low, int mid, int high) {

    int sum = 0;
    int max_sum = 0;
    result[0] = MINNUM;
    for (int i = mid + 1; i <= high; i++)
    {
        sum = sum + A[i];
        if(result[0] < sum) {
            result[0] = sum;
            result[2] = i;
        }

    }
    max_sum = result[0];
    result[0] = MINNUM;
    sum = 0;
    for (int i = mid; i >= 0; i--)
    {
        sum = sum + A[i];
        if(result[0] < sum) {
            result[0] = sum;
            result[1] = i;
        }
    }
    result[0] = max_sum + result[0];
    return result;
}

int *find_maxium_subarray(int a[MAXSIZE], int low, int high) {
    if(low == high) {
        result[0] = a[low];
        result[1] = low;
        result[2] = high;
        return result;
    }
    int mid = (low+high)/2;
    //int right_res[3] = {0};
    //int left_res[3] = {0};

    int *left_res = find_maxium_subarray(a, low, mid);
    int *right_res = find_maxium_subarray(a, mid+1, high);
    int *cross_res = find_cross_max_subarray(a, low, mid, high);

    return max(left_res, right_res, cross_res);

}

int *max(int *x, int *y, int *z) {
 
    int *max = x;
 
    if(x[0] > y[0]) {
 
        max = x;
    } else{
 
        max = y;
 
    }
 
    if (z[0] > max[0]) {
        max = z;
    }
 
    return max;
}

输出结果：

时间复杂度：O(n*lgn);

矩阵乘法问题

前提：由于矩阵需要能够被分解成4个子矩阵运算，所以Strassen算法的前提条件式矩阵的长和宽n是2的幂函数。

代码：

#include "stdio.h"
#define MAXSIZE 4

void multiply_matrix(int a[MAXSIZE][MAXSIZE], int b[MAXSIZE][MAXSIZE], int c[MAXSIZE][MAXSIZE], int n, int i, int j);
int n = MAXSIZE;
void main() {
    int a[MAXSIZE][MAXSIZE] = {
        {1,2,3,4},
        {1,2,3,4},
        {1,2,3,4},
        {1,2,3,4}
    };
    int b[MAXSIZE][MAXSIZE] = {
        {1,1,1,1},
        {1,1,1,1},
        {1,1,1,1},
        {1,1,1,1}
    };
    int c[MAXSIZE][MAXSIZE] = {0};
    multiply_matrix(a, b, c, n, 0, 0);
}

void multiply_matrix(int a[MAXSIZE][MAXSIZE], int b[MAXSIZE][MAXSIZE], int c[MAXSIZE][MAXSIZE], int n, int i, int j) {
    int length = n/2;
    if(n == 1) {
        c[i][j] = a[i][j]*b[i][j];
    } else {
        multiply_matrix(a, b, c, length, i, j);
        multiply_matrix(a, b, c, length, i, j + length);
        multiply_matrix(a, b, c, length, i + length, j);
        multiply_matrix(a, b, c, length, i + length, j + length);
    }
    
}