fzyz_sb 发表于4年前

• 发表于 4年前
• 阅读 47
• 收藏 0
• 评论 0

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;
}``````

×