柚子快報(bào)激活碼778899分享：算法 分治策略的實(shí)現(xiàn)

http://yzkb.51969.com/

目錄

前言

?分治策略的應(yīng)用

最大子數(shù)組問題

矩陣乘法問題

求解遞歸式的三種方法

代入法求遞歸式

用遞歸樹求遞歸式

主方法求遞歸式

前言

分治三個(gè)步驟：

分解：分解原問題為子問題，這些子問題為原問題的較小規(guī)模的問題。

解決：遞歸地解決這些子問題，如果規(guī)模小到一定程度，則直接得出答案。

合并：合并上述解決地子問題地解，得出最終解。

遞歸情況：當(dāng)子問題規(guī)模比較大時(shí)，成為遞歸情況；

基本情況：當(dāng)子問題規(guī)模不需要遞歸，已經(jīng)觸底時(shí)，此時(shí)稱作基本情況。

遞歸式：刻畫算法的運(yùn)行時(shí)間的等式或者不等式，如歸并排序中的最壞情況下的時(shí)間復(fù)雜

?分治策略的應(yīng)用

最大子數(shù)組問題

最大子數(shù)組：一個(gè)數(shù)組中的非空連續(xù)的數(shù)組元素和最大的集合成為最大子數(shù)組。

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

數(shù)組a的子數(shù)組有{-1}，{-2}，{3}，{4}，{-1，-2}，{-2，3}，{3，4}，{-1，-2，3}，

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

其中{3,4}子數(shù)組的和為7，是這些數(shù)組中和最大的子數(shù)組。

代碼：

#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;

}

?輸出結(jié)果：

時(shí)間復(fù)雜度：O(n*lgn);?

矩陣乘法問題

前提：由于矩陣需要能夠被分解成4個(gè)子矩陣運(yùn)算，所以Strassen算法的前提條件式矩陣的長和寬n是2的冪函數(shù)。

代碼：

#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);

}

}

求解遞歸式的三種方法

代入法：猜測(cè)一個(gè)邊界，用數(shù)學(xué)歸納法證明這個(gè)邊界的正確性；

遞歸樹法：將遞歸式轉(zhuǎn)化為一棵樹，其結(jié)點(diǎn)表示不同層次的遞歸調(diào)用產(chǎn)生的代價(jià)，然后采用邊界和技術(shù)求解遞歸式。

主方法：可求解如下遞歸式的界：

?遞歸式的技術(shù)細(xì)節(jié)：

代入法求遞歸式

猜測(cè)解的形式；使用數(shù)學(xué)歸納法證明解中常數(shù)，并證明解是正確的。

用遞歸樹求遞歸式

猜測(cè)解的形式有時(shí)候會(huì)比較棘手，所以可以通過遞歸樹的方法來需求解的形式。

主方法求遞歸式

柚子快報(bào)激活碼778899分享：算法 分治策略的實(shí)現(xiàn)

http://yzkb.51969.com/

文章鏈接