4.1 最大子数组问题
一个数组arr长度为len,假定0<=i<=j<len,求arr[ j ] - arr[ i ]的最大值.
暴力求解方法,复杂度为n*n:
#include程序输出:int max_sub( int arr[], int len ){ int i = 0; int j = 0; int maxValue = 0; for ( i = 0; i < len - 1; i++ ){ for ( j = i + 1; j < len; j++ ){ if ( arr[ j ] - arr[ i ] > maxValue ){ maxValue = arr[ j ] - arr[ i ]; } } } return maxValue;}int main( void ){ int arr[ 100 ]; int i = 0; int result = 0; for ( i = 0; i < 50; i++ ){ arr[ i ] = -i; } for ( i = 0; i < 50; i++ ){ arr[ i + 50 ] = i; } result = max_sub( arr, 100 ); printf("%d\n", result ); return 0;}
分治法:
#include程序输出:#include int find_max_crossing_subarray( int arr[], int low, int mid, int high, int *left_or_right_low, int *left_or_right_high ){ int left_sum = INT_MIN; int right_sum = INT_MIN; int sum = 0; int i = 0; int max_left; int max_right; for ( i = mid; i >= low; i-- ){ sum += arr[ i ]; if ( sum > left_sum ){ left_sum = sum; max_left = i; } } sum = 0; for ( i = mid + 1; i <= high; i++ ){ sum += arr[ i ]; if ( sum > right_sum ){ right_sum = sum; max_right = i; } } *left_or_right_low = max_left; *left_or_right_high = max_right; return left_sum + right_sum;}int find_maximum_subarray( int arr[], int low, int high, int *left_or_right_low, int *left_or_right_high ){ int mid; int left_sum; int right_sum; int cross_sum; int left_low, left_high, right_low, right_high, cross_low, cross_high; if ( low == high ){ return arr[ low ]; } else{ mid = ( low + high ) / 2; left_sum = find_maximum_subarray( arr, low, mid, &left_low, &left_high ); right_sum = find_maximum_subarray( arr, mid + 1, high, &right_low, &right_high ); cross_sum = find_max_crossing_subarray( arr, low, mid, high, &cross_low, &cross_high ); if ( left_sum >= right_sum && left_sum >= cross_sum ){ *left_or_right_low = left_low; *left_or_right_high = left_high; return left_sum; } else if ( right_sum >= left_sum && right_sum >= cross_sum ){ *left_or_right_low = right_low; *left_or_right_high = right_high; return right_sum; } else{ *left_or_right_low = cross_low; *left_or_right_high = cross_high; return cross_sum; } }}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 = find_maximum_subarray( arr, 0, 15, &left, &right ); printf("%d--%d : %d\n", left, right, sum ); return 0;}
具体分析请参考书本上的讲解.
习题4.1-3:
对于此习题,由于分治法处理的数组和暴力求解法处理的数组完全不一样(虽然分治法的数组出自暴力求解法),所以将两个算法合并起来,实际上增加了难度和算法的复杂度.....
习题4.1-4:
可以用INT_MIN来初始化数组,返回为0.若返回为0,则要么为空数组,要么就是我们要找的答案,没任何冲突.
习题4.1-5:
下列代码参考以下网址:
#include程序输出:#include int find_maximum_subarray( int arr[], int low, int high, int *left, int *last ){ int i = 0; int maxValue = INT_MIN; int sum = 0; int cur_low = 0; for ( i = low; i < high; i++ ){ sum += arr[ i ]; if ( sum > maxValue ){ *left = cur_low; maxValue = sum; *last = i; } else if ( sum < 0 ){ //当sum < 0的时候,说明最大子数组不包括之前的子数组,直接抛弃 sum = 0; cur_low = i + 1; } } return maxValue;}int main( void ){ int arr[ 16 ] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 }; int temparr[ 16 ]; int sum = 0; int left; int last; int i = 0; for ( i = 0; i < 16; i++ ){ temparr[ i ] = -i - 1; } sum = find_maximum_subarray( arr, 0, 16, &left, &last ); printf("%d--%d: %d\n", left, last, sum ); return 0;}
4.2 矩阵乘法的Strassen算法
我们一般的矩阵相乘都类似于下列的代码:
#include程序输出:int main( void ){ int arr1[ 2 ][ 2 ] = { 2, 3, 4, 5 }; int arr2[ 2 ][ 2 ] = { 2, 3, 4, 5 }; int arr3[ 2 ][ 2 ]; int i = 0; int j = 0; int k = 0; for ( i = 0; i < 2; i++ ){ for ( j = 0; j < 2; j++ ){ arr3[ i ][ j ] = 0; for ( k = 0; k < 2; k++ ){ arr3[ i ][ j ] += arr1[ i ][ k ] * arr2[ k ][ j ]; } } } for ( i = 0; i < 2; i++ ){ for ( j = 0; j < 2; j++ ){ printf("%d ", arr3[ i ][ j ] ); } printf("\n"); } return 0;}
而strassen的算法代码如下:
#include程序输出: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;}
但是如果n不是等于2,则不知道如何进行编写代码..........
习题4.2-7:
( a + bi ) * ( c + di ) = ac - bd + ( ad + bc )i,但是bc = ac * bc / ad算出,所以只要3步即可.