文档章节

算法导论复习:第四章

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



程序输出:


© 著作权归作者所有

共有 人打赏支持
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
get数据技能

《哈佛商业评论》把数据科学家誉为“21 世纪最性感的职业”。虽说如此称呼有些夸张,但这个名称对数据科学的推崇却一点也没错,也预示了数据科学行业的蓬勃发展和无限前途。 今天小编就盘点了...

图灵教育
2016/08/17
0
0
欢迎进入Hensen_的博客目录(全站式导航)

Android基础 Java基础 Java基础——Java内存模型和垃圾回收机制 语法基础 语法基础——C语法基础 语法基础——C++语法基础 语法基础——Objective-C语法基础 语法基础——PHP语法基础 面试复...

qq_30379689
2016/09/23
0
0
操作系统:精髓与设计原理(原书第6版).PDF

操作系统:精髓与设计原理(原书第6版) 书名原文:Operating Systems: Internals and Design Principles, Sixth Edition 作者:(美)斯托林斯(Stallings,W.) 译者:陈向群 出版社:机械工...

刘静
2010/09/16
5.6K
2
团队拙作《Python机器学习实战》

之前看国内外的 Python 机器学习的书,鲜有将机器学习到底怎么做人脸识别、怎么做风险控制、怎么做 OCR 算法模型列出的,并且真正的一个 Python 应用,不止是从机器学习库中导入一下配置一下...

yijun2018
04/20
0
0
算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于恨,是因为它在进行算法分析的时候所体现的数学思想...

chambai
2015/09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Centos7通过yum安装nginx

添加源地址(直接install可能不是最新版本的) sudo rpm -Uvh http://nginx.org/packages/centos/7/noarch/RPMS/nginx-release-centos-7-0.el7.ngx.noarch.rpm 安装 sudo yum install -y ng......

iplusx
3分钟前
0
0
ef .core Dapper Helper

using System; using System.Collections.Generic; using System.Configuration; using System.Data; using System.Data.SqlClient; using System.Threading.Tasks; using Dapper; using Dap......

Lytf
4分钟前
0
0
iOS 小笔记

1.以下代码打印什么     __block int val = 10;    void (^blk)(void) = ^{        printf("val=%d\n",val);        };       val = 2;    blk(); /...

风了个1
6分钟前
0
0
【Spring Boot 系列 Spring Boot示例程序】

入门程序步骤,创建一个Maven项目。继承Spring Boot官方提供的父工程。再引入一个Web的应用启动器。 1、选择一个合适的IDEA工具 创建一个Maven工程,并添加如下配置 <parent> <...

HansonReal
8分钟前
0
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意:判断数组中是否有重复元素 思路:构造一个set,不重复就加进去,重复返回true,如果数据量大的话,可以用布隆过滤器 Java实现: publ...

yysue
12分钟前
0
0
istio 处理失败 (理论)

Envoy提供了一套开箱即用的选择加入故障恢复功能,可以通过应用程序中的服务进行利用。功能包括: 超时 具有超时预算和重试之间的可变抖动的有界重试 限制并发连接数和对上游服务的请求 对负...

xiaomin0322
13分钟前
0
0
eclipse解决git冲突举例

本地修改了两个文件,提交时提示有冲突,想来应该是没有从远程仓库下载最新代码导致的。通过右击项目 -> Team -> Sychronized WorkSpace,比较本地仓库和远程仓库的异同:   此时没有更好的...

Code辉
21分钟前
0
0
运行.jar后缀的文件

前提必须安装了jdk,正确配置环境变量。 在dos窗口执行以下命令即可。 java -jar C:\Users\10492\Desktop\turn.jar

haha360
24分钟前
0
0
Java程序员如何做代码压力测试?【JWordPress前台项目实战】

代码 pom.xml文件引入包 <dependency><groupId>com.taobao.stresstester</groupId><artifactId>stresstester</artifactId><version>1.0</version></dependency> 编写测试代码 /**......

迷你芊宝宝
29分钟前
0
0
面试宝典-什么是缓存穿透?

缓存穿透是说收到了一个请求,但是该请求缓存里没有,只能去数据库里查询,然后放进缓存。 这里面有两个风险,一个是同时有好多请求访问同一个数据,然后业务系统把这些请求全发到了数据库;...

suyain
35分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部