# 算法导论复习:第四章 原

fzyz_sb

1. 分解步骤:将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小.

2. 解决步骤:递归的求解子问题.如果子问题的规模足够小,则停止递归,直接求解.

3. 合并步骤:将子问题的解组合成原问题的解.

1. 最大子数组问题:

``````#include <stdio.h>
#include <limits.h>

int findMaxCrossingSubarray( int *A, int low, int mid, int high, int *maxLeft, int *maxRight)
{
int			leftSum = INT_MIN;
int			rightSum = INT_MIN;
int			sum = 0;
int			i = 0;
for ( i = mid; i >= 0; i-- ){
sum += A[ i ];
if ( sum > leftSum ){
leftSum = sum;
*maxLeft = i;
}
}
sum = 0;
for ( i = mid + 1; i <= high; i++ ){
sum += A[ i ];
if ( sum > rightSum ){
rightSum = sum;
*maxRight = i;
}
}

return ( leftSum + rightSum );
}

int findMaximumSubarray( int *A, int low, int high, int *maxLeft, int *maxRight )
{
int mid = 0;
int leftSum = 0;
int rightSum = 0;
int crossSum = 0;
int leftLow, leftHigh, rightLow, rightHigh, crossLow, crossHigh;
if ( low == high ){
return A[ low ];
}
else{
mid = ( low + high ) / 2;
leftSum = findMaximumSubarray( A, low, mid, &leftLow, &leftHigh );
rightSum = findMaximumSubarray( A, mid + 1, high, &rightLow, &rightHigh );
crossSum = findMaxCrossingSubarray( A, low, mid, high, &crossLow, &crossHigh );
if ( leftSum >= rightSum && leftSum >= crossSum ){
*maxLeft = leftLow;
*maxRight = leftHigh;
return leftSum;
}
else if ( rightSum >= leftSum && rightSum >= crossSum ){
*maxLeft = rightLow;
*maxRight = rightHigh;
return rightSum;
}
else{
*maxLeft = crossLow;
*maxRight = crossHigh;
return crossSum;
}
}
}

int main( void )
{
int arr[ 16 ] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
int left;
int right;
int sum = 0;
sum = findMaximumSubarray( arr, 0, 15, &left, &right );

printf("%d--%d : %d\n", left, right, sum );

return 0;
}``````

PS:这里有一个非常重要的细节,我带入的参数是0,15而不是0,16.记住:在递归的程序中,带入的参数最好有效,如A[15],否则万一发生A[16]就会出问题.而且本题中涉及到的边界问题,导致带入16使程序很难编写.

2. 矩阵乘法的strassen算法

``````#include <stdio.h>

int main( void )
{
int i = 0;
int j = 0;
int A[ 2 ][ 2 ] = { 2, 3, 4, 5 };
int B[ 2 ][ 2 ] = { 2, 3, 4, 5 };
int C[ 2 ][ 2 ];
int s1 = B[ 0 ][ 1 ] - B[ 1 ][ 1 ];
int s2 = A[ 0 ][ 0 ] + A[ 0 ][ 1 ];
int s3 = A[ 1 ][ 0 ] + A[ 1 ][ 1 ];
int s4 = B[ 1 ][ 0 ] - B[ 0 ][ 0 ];
int s5 = A[ 0 ][ 0 ] + A[ 1 ][ 1 ];
int s6 = B[ 0 ][ 0 ] + B[ 1 ][ 1 ];
int s7 = A[ 0 ][ 1 ] - A[ 1 ][ 1 ];
int s8 = B[ 1 ][ 0 ] + B[ 1 ][ 1 ];
int s9 = A[ 0 ][ 0 ] - A[ 1 ][ 0 ];
int s10 = B[ 0 ][ 0 ] + B[ 0 ][ 1 ];
int p1 = A[ 0 ][ 0 ] * s1;
int p2 = s2 * B[ 1 ][ 1 ];
int p3 = s3 * B[ 0 ][ 0 ];
int p4 = A[ 1 ][ 1 ] * s4;
int p5 = s5 * s6;
int p6 = s7 * s8;
int p7 = s9 * s10;

C[ 0 ][ 0 ] = p5 + p4 - p2 + p6;
C[ 0 ][ 1 ] = p1 + p2;
C[ 1 ][ 0 ] = p3 + p4;
C[ 1 ][ 1 ] = p5 + p1 - p3 - p7;

for ( i = 0; i < 2; i++ ){
for ( j = 0; j < 2; j++ ){
printf("%d ", C[ i ][ j ] );
}
printf("\n");
}

return 0;
}``````

### fzyz_sb

20111564
2014/10/16
0
0

himayan46
2016/09/28
0
0

5.2 二叉树 我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正...

fzyz_sb
2013/12/07
0
2
ZOJ 3499. Median

地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4322 　　　　题意：寻找中位数。对于一个（浮点数）数组，如果含有奇数个元素，“中位数”就是排序后位于数组中...

hoodlum1980
2012/06/13
0
0

modernizr
2014/05/22
28.1K
13

day92-20180918-英语流利阅读-待学习

6分钟前
1
0
70.shell的函数 数组 告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析 20.16/20.17 shell中的函数： ~1. 函数就是把一段代码整理到了一个小单元中，并给这个小单元起一个名字，当用到这段...

3
0

WALK_MAN

6
0
C++ yield()与sleep_for()

yepanl

4
0

53
0