文档章节

算法导论复习:第四章

fzyz_sb
 fzyz_sb
发布于 2014/01/02 00:22
字数 653
阅读 57
收藏 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;
}



程序输出:


© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
考研-专业课-c语言

为了我家娘子,猪猪臭 本人计划考研:报考学校北京工业大学--计算机 专业课编号985:教材为C语言程序设计案例教程和严蔚敏的数据结构那本 我知道 本书是没有答案的 下面的全都是 自己写的 并在...

20111564
2014/10/16
0
0
算法-第四版习题索引汇总

算法-第四版习题索引汇总 持续更新中。。。 第一章 基础 算法-第四版-1.1 基础编程模型-习题索引汇总 算法-第四版-1.2 数据抽象-习题索引汇总 算法-第四版-1.3 背包、队列和栈-习题...

himayan46
2016/09/28
0
0
数据结构(C语言版)第五章:树

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-英语流利阅读-待学习

健身最大的敌人不是懒惰,而是逞强 Daniel 2018-09-19 1.今日导读 还记得 2008 年北京奥运会运动员刘翔的退赛风波吗?那天几乎所有中国人都将视线聚焦在了鸟巢体育馆 110 米栏的项目上,迫不...

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

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

王鑫linux
今天
3
0
分布式框架spring-session实现session一致性使用问题

前言:项目中使用到spring-session来缓存用户信息,保证服务之间session一致性,但是获取session信息为什么不能再服务层获取? 一、spring-session实现session一致性方式 用户每一次请求都会...

WALK_MAN
今天
6
0
C++ yield()与sleep_for()

C++11 标准库提供了yield()和sleep_for()两个方法。 (1)std::this_thread::yield(): 线程调用该方法时,主动让出CPU,并且不参与CPU的本次调度,从而让其他线程有机会运行。在后续的调度周...

yepanl
今天
4
0
Java并发编程实战(chapter_3)(线程池ThreadPoolExecutor源码分析)

这个系列一直没再写,很多原因,中间经历了换工作,熟悉项目,熟悉新团队等等一系列的事情。并发课题对于Java来说是一个又重要又难的一大块,除非气定神闲、精力满满,否则我本身是不敢随便写...

心中的理想乡
今天
53
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部