算法导论复习:第四章
博客专区 > fzyz_sb 的博客 > 博客详情
算法导论复习:第四章
fzyz_sb 发表于4年前
算法导论复习:第四章
  • 发表于 4年前
  • 阅读 47
  • 收藏 0
  • 点赞 0
  • 评论 0
摘要: 复习算法导论第四章:分治策略.主要有两个问题:1是最大子数组问题,而是矩阵乘法的strassen算法

分治策略的三个步骤:

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



程序输出:


标签: 算法基础 C
共有 人打赏支持
粉丝 354
博文 209
码字总数 447144
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: