最大字段和问题
1.实验题目
给定由N 个整数（可能有负整数）组成的序列（1a ，2a ，…，n a ），求该序列形如∑=j i k k a
的子段和的最大值，当所有整数均为负整数是，其最大子段和为0。
2.实验目的
（1）深刻掌握动态规划法的设计思想并能熟练运用；
（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。
3.实验分析
蛮力法：利用3个for 的嵌套（实现从第1个数开始计算子段长度为1，2，3…n 的子
段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n 个数开始计算的长为1的子段和）和一个if （用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。
用了3个for 嵌套所以时间复杂性为○(n 3)。
分治法：
（1）划分：按照平衡子问题的原则，将序列（1a ，2a ，…，n a ）划分成长度相同的
两个字序列（1a ，…，??2/n a ）和（??12/+n a ，…，n a ）
。 （2）求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在
两端之间需要分别计算
s1=??
??)2/1(max 2/n i a n i k k ≤≤∑=，s2=????)2/(max 12/n j n a j n k k
≤≤∑+=，
则s1+s2为最大子段和。若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。
（3）合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问
题的解。
（4）时间复杂性分析: f(n) = 2*f(n/2) + ○(n/2), 最后为○(nlogn)。
动态规划法：
动态规划法求解最大字段和问题的关键是要确定动态规划函数。记
)1(max )(1n j a j b i i k k j i ≤≤?
?????=∑=≤≤ 则
{})(max max max max 1111j b a a n j j i k k j i n j j
i k k n j i ≤≤=≤≤≤≤=≤≤≤=??????=∑∑ 由b （j ）的定义，当b （j-1）>0是，b （j ）=b （j-1）+a ，否则，b （j ）=a 。可得如下递推式：
)1()(0
)1(0)1()1({n j j b j b j b a j b a j j ≤≤=>-≤-+-
代码实现过程中只用了一个for, 时间复杂性为：○(n)
三种方法写在同一cpp 上，比较其时间，由于分治法和动态规划法，要用比较比长的序列，故把程序设计成有手动输入和随机输入，对于随机生成函数rand()只生成正数，故引入了rand()/13-1129，使其既有正数生成，也有负数生成。程序运行如下：
首先先用手动输入：
由于要比较时间，故要用到大量数据，所以用随机输入：
至于序列在此不作输出，若输出将会造成截屏不方便，
可见蛮力法只可以处理小理的数据。
当数据量超过10000时，由蛮力法要等很久才输出，所先把蛮力去掉，就比较分治法和动态
规划法：
明显可以动态规划法所用的时间要少。
1459:Power Network Time Limit: 2000MS Memory Limit: 32768K Total Submissions: 17697 Accepted: 9349 Description A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l max(u,v) of power delivered by u to v. Let Con=Σu c(u) be the power consumed in the net. The problem is to compute the maximum value of Con. An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and c max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6. Input There are several data sets in the input. Each data set encodes a power network. It starts with four integers: 0 <= n <= 100 (nodes), 0 <= np <= n (power stations), 0 <= nc <= n (consumers), and 0 <= m <= n^2 (power transport lines). Follow m data triplets (u,v)z, where u and v are node identifiers (starting from 0) and 0 <= z <= 1000 is the value of l max(u,v). Follow np doublets (u)z, where u is the identifier of a power station and 0 <= z <= 10000 is the value of p max(u). The data set ends with nc doublets (u)z, where u is the identifier of a consumer and 0 <= z <= 10000 is the value of
oracle大字段问题 0、LARGE OBJECT ORACLE8中有4种LOB - BLOB：Binary Large Object - CLOB：Character Large Object - NCLOB：固定长度的多字节Character Large Object - BFILE：DB外部的二进制文件 它们分为两类： 内部LOB：存放在DB内部，包括BLOB，CLOB，BCLOB 外部文件：存放在DB外面，就是BFILE 要注意的是ORACLE8不自动转换这些类型的数据。 1、LONG和LOB的比较 LONG/LONG RAW LOB -------------------------------------------------- 表中只能由一个列可以有多列 最大2G 最大4G SELECT返回值SELECT返回指针 存放在DB内可以在DB的内或者外 不支持OBJECT类型支持 顺序存取随机存取 --------------------------------------------------
NCLOB不支持OBJECT类型 LOB小于4000字节时是内部存放 2、LOB解析 LOB有两个不同的部分 - LOB值：LOB代表的数据 - LOB指针：LOB存放数据的位置 LOB列内部不存放数据，而是LOB值的位置。当创建内部LOB时，值存放在LOB SEGMENT中，指向OUT-OF-LIN数据的指针放在列中。对外部LOB，只在列中存放位置。 3、内部LOB 就是存放在DB内部的LOB，包括BLOB,CLOB,NCLOB。它们可以是 用户自定义的类型中的属性 表中某列 SQL 变量 程序host变量 PL/SQL中的变量、参数、返回值 内部LOB可以使用ORACLE的并发机制、REDO LOG、RECOVERY 机制。 BLOB被ORACLE8解释为二进制位流，类似LONG RAW。 CLOB解释为单字节字符流
算法分析与设计题目：最大流算法 院系：软件工程 班级：软件11-2班 ：慕永利 学号： 23 号
目录 1算法提出背景........................................................... - 3 - 2 问题实例及解决......................................................... - 3 - 3算法论述............................................................... - 4 - 3.1、可行流.......................................................... - 4 - 3.2 最大流.......................................................... - 5 - 3.3最大流算法....................................................... - 6 - 3.3.1 增广路径................................................. - 6 - 3.3.2沿增广路径增广............................................. - 7 - 3.3.3样例：..................................................... - 8 - 3.3.4定理：.................................................... - 13 - 3.3.5算法的实现：.............................................. - 13 - 3.3.6 优化...................................................... - 16 - 4算法应用.............................................................. - 18 -
最大字段和 【实验目的】 1掌握动态规划法的设计思想并能熟练运用； 2分别用分治法和动态规划法设计最大子段和问题的算法； 【实验设备与环境】 1 PC机一台 2 Turbo C 或VC++ 【实验内容：】 给定由n个整数（可能为负整数）组成的序列a1, a2, …, an，求该序列形如的子段和的最大值，当所有整数均为负整数时定义其最大子段和为0。 【实验方法步骤】 1用分治法求最大子段和 程序代码： #include
for(i=center+1;i<=right;i++) { rights+=a[i]; if(rights>s2) s2=rights; } sum=s1+s2; if(sum 最大字段和问题 1.实验题目 给定由N 个整数（可能有负整数）组成的序列（1a ，2a ，…，n a ），求该序列形如∑=j i k k a 的子段和的最大值，当所有整数均为负整数是，其最大子段和为0。 2.实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 3.实验分析 蛮力法：利用3个for 的嵌套（实现从第1个数开始计算子段长度为1，2，3…n 的子 段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n 个数开始计算的长为1的子段和）和一个if （用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。 用了3个for 嵌套所以时间复杂性为○(n 3)。 分治法： （1）划分：按照平衡子问题的原则，将序列（1a ，2a ，…，n a ）划分成长度相同的 两个字序列（1a ，…，??2/n a ）和（??12/+n a ，…，n a ） 。 （2）求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在 两端之间需要分别计算 s1=?? ??)2/1(max 2/n i a n i k k ≤≤∑=，s2=????)2/(max 12/n j n a j n k k ≤≤∑+=， 则s1+s2为最大子段和。若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。 （3）合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问 题的解。 （4）时间复杂性分析: f(n) = 2*f(n/2) + ○(n/2), 最后为○(nlogn)。 动态规划法： 动态规划法求解最大字段和问题的关键是要确定动态规划函数。记 )1(max )(1n j a j b i i k k j i ≤≤? ?????=∑=≤≤ 则 最大流算法 clc,clear,M=1000; c(1,2)=3;c(1,4)=3; c(2,3)=1;c(2,4)=20; c(3,6)=3; c(4,5)=10; c(5,1)=4;c(5,3)=2;c(5,6)=13; n=length(u); list=[]; maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0)); label1=index1(find(u(flag,index1)... -f(flag,index1)~=0)); label1=setdiff(label1,record); list=union(list,label1); pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0 最大字段和 1.实验目的和要求 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力 和重新修正的结果。 （3）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （4）比较不同算法的时间性能； （5）给出测试数据，写出程序文档 2.实验内容 给定由n 个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 3.实验环境 Turbo C 或VC++ 4.实验学时 2学时，必做实验 5.数据结构与算法 数据结构: 程序中所用的数据都是储存在数组当中 算法: 蛮力法函数MaxSum(int a[],int n,int &besti,int &bestj) 分治法函数MaxSum(int a[],int left,int right) 动态规划法函数 MaxSum(int n,int a[]) 6.核心源代码及时间性能分析 （1）蛮力法： #include if(asum>sum) { sum=asum; besti=i; bestj=j; } } } return sum; } void main() { int n,a[ cout<<"请输入各元素的值(一共"<100],m,i,j,maxsum; cout<<"请输入整数序列的元素个数n:"< 第四章 例15 求数列的最大子段和 给定n个元素的整数列（可能为负整数）a1,a2,…..,an。求形如： ai,ai+1,……aj i,j=1,…..,n,i<=j 的子段，使其和为最大。当所有整数均为负整数时定义其最大子段和为0. 程序： #include int maxsum1(int a[],int n) { return(maxsum2(a,1,n)); } void main() { int a[100],n; printf("enter a number:"); scanf("%d",&n); printf("enter the number of a[]:"); for(int i=1;i<=n;i++) scanf("%d",&a[i]); printf("%d",maxsum1(a,n)); printf("\n"); } 运行结果： 最大子段和问题 1、实验环境 Visual Studio 2、实验目的和要求 问题重述：求解最大子段和问题 3、解题思路、伪代码 3.1解题思路、伪代码（算法一） int LSS_SlowEnumerate(int a[]) //最大子段和，枚举算法，O(n^3) { int max = 0, n = a[0], sum; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { sum = 0; //sum 为区间[i, j] 之间的最大和 for (int k = i; k <= j; k++) { sum += a[k]; } if (sum > max) max = sum; } } return max; } 3.2 解题思路、伪代码（算法二） int LSS_Enumerate(int a[]) //最大子段和，枚举算法，O(n^2) { int sum[101], i, n = a[0], max = -200000000, t; //sum[i] 表示a[i] 的 前i 项和 sum[0] = 0; for (i = 1; i <= n; i++) { sum[i] = sum[i - 1] + a[i]; } for (i = 0; i <= n - 1; i++) //枚举每个可能的子段 { for (int j = i + 1; j <= n; j++) { t = sum[j] - sum[i]; if (t > max) max = t; } } return max; } 3.3 解题思路、伪代码（算法三） int LSS_Recursion(int a[], int l, int r) //最大子段和，分治算法，O(nlgn) { int m = (l + r) / 2, t = 0, L = 0, R = 0; //L为左区间能取到的最大，R为右区间能取到的最大 if (l == r) //边际条件：当区间元素只有一个的时候返回自身return a[m]; if (r - l == 1) //边际条件：当区间元素只有两个的时候返回左、右、左右相加三者中的最大值 return Max(Max(a[l], a[r]), a[l] + a[r]); int LMax = LSS_Recursion(a, l, m); //递归左区间 int RMax = LSS_Recursion(a, m + 1, r); //递归右区间 for (int i = m; i >= 1; i--) //左边找一个最大的和 { t += a[i]; if (t > L) L = t; } 今天写sql语句，需要取出多个字段列中的最大值和最小值。 本来想到的做法比较麻烦，要分别取出max(one),max(two),max(three)，放到pb中在编程处理。 后来找到个greatest函数和least函数，只用写greatest (max(one),max(two),max(three))就解决问题，least用法同，good。 求多列的最大值，oracle中的greatest 函数 已知表TB的数据如下 SQL> select * from tb; ID CHINESE MATH ENGLISH ---------- ---------- ---------- ---------- 1001 89 98 87 1002 81 87 79 现在要得到如下的结果，该怎么来解决 ID CHINESE MATH ENGLISH MAX MIN ---------- ---------- ---------- ---------- ---------- ---------- 1001 89 98 87 98 87 1002 81 87 79 87 79 想了半天也没想到啥好办法，首先自然而然想到用MAX和MIN函数，但是显然这两个是聚集函数，是要作用在同一个column的一个Group上面的，而现在要得到的MAX和MIN 的值却是作用于每一行上面的，如果要借助于MAX（）和MIN（）的话，还需要对原表的数据结构进行下处理（先进行转列操作unpivot)，但是显然不是很好。 看到有个网友回帖用greatest和least函数来做，真是简洁漂亮，也为自己的孤陋寡闻而狂汗呀 解决方式如下 SQL> SELECT id, chinese, math, english, 2 greatest (chinese, math, english) max, 3 least(chinese, math, english) min 4 FROM tb; ID CHINESE MATH ENGLISH MAX MIN 网络最大流的算法 网络最大流的算法分类： 一、Ford-Fulkerson增广路方法 1、Ford-Fulkerson标号算法（最简单的实现） 分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个点），检查与它连接的所有边，并进行扩展，直到扩展到t。 2、最大容量增广路算法 每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。 3、Edmonds-Karp，最短路增广算法的BFS实现 每次找一条最短的增广路，BFS是一个可以很方便的实现思想。 4、距离标号算法 最短路增广的O(n)寻找实现，使用距离函数d：d[t]=0;d<=d[j]+1若存在(i,j)∈E；只有路径上满足d=d[i+1]+1的增广路才为满足要求的，一开始我们初始化使标号恰好满足要求，之后不断更改标号使其可以使增广继续。 5、Dinic，分层思想 对网络分层（按照距t的距离），保留相邻层之间的边，然后运用一次类似于距离标号的方法（其实质是DFS）进行增广。 二、预留与推进算法 1、一般性算法 随便找个点，要么将他的盈余推出去，要么对他进行重标记，直至无活跃点为止。 2、重标记与前移算法 维护一个队列，对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。 3、最高标号预留与推进算法 记录d值，然后优先处理d值较高的，直至没有盈余。 网络最大流的算法实现 一、Edmonds-Karp（EK）算法 就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)，Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的Dinic 算法都属于此。SAP 类算法可统一描述如下： Shortest Augmenting Path { x <-- 0 while 在残量网络Gx 中存在增广路s ~> t do { 找一条最短的增广路径P delta <-- min{rij:(i,j) 属于P} 沿P 增广delta 大小的流量 更新残量网络Gx } return x } 在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索(BFS)，E-K 算法就直接来源于此。每次用一遍BFS 寻找从源点s 到终点t 的最短路作为增广路径，然后增广流量 f 并修改残量网络，直到不存在新的增广路径。 E-K 算法的时间复杂度为O(V*E^2)，由于BFS 要搜索全部小于最短距离的分支路径之后才能找到终点，因此可以想象频繁的BFS 效率是比较低的。实践中此算法使用的机会较少。代码如下： #define VMAX 201 int n, m; //分别表示图的边数和顶点数 int c[VMAX][VMAX]; //容量 int Edmonds_Karp( int s, int t ) //输入源点和汇点 { int p, q, queue[VMAX], u, v, pre[VMAX], flow= 0, aug; while(true) { memset(pre,-1,sizeof(pre)); //记录父节点 for( queue[p=q=0]=s; p<=q; p++ ) //广度优先搜索 { u= queue[p]; for( v=0; v 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验2 动态规划算法 最大子段和问题 班级：软件081班 学号：110831116 姓名：陈点点 实验2 动态规划算法 实验目的和要求 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 （3）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （4）比较不同算法的时间性能； （5）给出测试数据，写出程序文档 实验内容 给定由n 个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 数据结构: 程序中所用的数据都是储存在数组当中 算法: 蛮力法函数MaxSum(int a[],int n,int &besti,int &bestj) 分治法函数MaxSum(int a[],int left,int right) 动态规划法函数 MaxSum(int n,int a[]) 核心源代码 1， 蛮力法 T(n)=O(n2)。 #include 查找某个字段最大值的记录 SQL语句select table_name.*from table_name,(select max(price) as price,pid from table_name group by pid) as table_name_temp where table_name_temp.price=table_name.price and table_name_temp.pid=table_name.pid; --SQL code create table lk1 ( uid int, pid int, price int, `time` date )engine=myisam; insert into lk1 values (1, 1, 100, '2007-07-01'), (1, 2, 150, '2007-07-02 '), (2, 1, 110, '2007-07-03 '), (3, 1, 120, '2007-07-04 '), (4, 2, 180, '2007-07-04 '), (3, 2, 170, '2007-07-04 '), (6, 3, 130, '2007-07-04 '); select*from lk1 where price in (select max(price) from lk1 group by pid) group by pid; --结果1： query result(3 records) uid pid price time 311202007-07-04 421802007-07-04 631302007-07-04 truncate table lk1; insert into lk1 values (1, 1, 200, '2007-07-01'), (1, 2, 200, '2007-07-02 '), (2, 1, 110, '2007-07-03 '), (3, 1, 120, '2007-07-04 '), (4, 2, 180, '2007-07-04 '), (3, 2, 170, '2007-07-04 '), (6, 3, 130, '2007-07-04 '); select*from lk1 where price in (select max(price) from lk1 group by pid) group by pid; --结果2： query result(3 records) uid pid price time 112002007-07-01 122002007-07-02 从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。 2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例 实验题目 给定由n 个整数组成的序列(a 1, a 2, …, an )，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 实验内容（包括代码和对应的执行结果截图） 实验代码如下: #include { int i,j,k=0; for(i=0;i<6;i++) s[i][i]=a[i]; for(i=0;i<6;i++) for(j=i+1;j<6;j++) s[i][j]=s[i][j-1]+a[j]; for(i=0;i<6;i++) for(j=i;j<6;j++) if(s[i][j]>k) k=s[i][j]; if(k<0) k=0; return k; } //分治法求解最大字段和问题 int MaxSum(int a[],int left,int right) { int sum=0; if(left==right) { //如果序列长度为1，直接求解 if (a[left]>0) sum=a[left]; else sum=0; } else { int center=(left+right)/2; //划分 int leftsum=MaxSum(a,left,center); //对应情况①，递归求解 int rightsum=MaxSum(a,center+1,right); //对应情况②，递归求解 int s1=0; int lefts=0; //以下对应情况③，先求解s1 for (int i=center;i>=left;i--) { lefts+=a[i]; if (lefts>s1) s1=lefts; } int s2=0; int rights=0; //再求解s2 for (int j=center+1;j<=right;j++) { rights+=a[j]; 实验报告 课程名称算法分析与设计 实验项目名称最大字段和问题 班级与班级代码 实验室名称（或课室）实验楼802 专业：计算机科学与技术 任课教师：李绍华 学号： 姓名： 实验日期：2016年11月25日 广东财经大学教务处制 姓名实验报告成绩 评语： 指导教师（签名） 年月日说明：指导教师评分后，实验报告交院（系）办公室保存。 一、实验目的 (1)能够熟悉最大字段和问题这个算法 (2)分别使用三种不同算法：暴力算法、分治算法、动态规划算法，体会其算法思想并比较时间复杂度。 二、实验设备 硬件： P4 2.0G 1G 内存60G 硬盘以上电脑 软件： C 、C++编程环境，Java 编程环境，windows7 三、问题与算法描述 1、问题描述 给定由n 个整数（可能为负整数）组成的序列a1、a2、……a n ，求该序列形如∑=j i k k a 的字段和的最大值。当所有整数均为负整数时定义其最大字 段和为0。依次定义，所求的最优值为max{0，max \ 1n j i <=<=<=∑=j i k k a }。 2、算法描述 BF 算法 对于起点 i ，遍历所有长度为1,2,…,n-i+1的子区间和，遍历所有的字 段，找出最大字段和。 分治算法 求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间 [start, end]只可能有以下三种可能性: 1.在[1, n/2]这个区域内 2.在[n/2+1, n]这个区域内 3.起点位于[1,n/2],终点位于[n/2+1,n]内 以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路分别向左右扩张求出。 动态规划 扩展到二维空间令b[j]表示以位置 j 为终点的所有子区间中和最大的一个子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中，如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含；如果 b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大。 3、算法时间复杂性分析 BF算法：经过两次嵌套循环时间复杂度：O(n2) 分治算法：每递归一次需logn，全部需要n次运算量，时间复杂度：O(nlogn)动态规划算法：只经历了一次循环，时间复杂度：O(n) 四、实验调试过程中出现的问题 实验过程中，主要遇到了两个问题，随机函数和时间计算函数不知如何进行，虽然之前在以前的课程中学习过，但是由于时间长已经忘记，通过查阅和同学帮助最终解决。 五、实验结果 1.源代码 package算法实验2; 山东科技大学 本科毕业设计（论文）题目最大流问题以及应用 学院名称数学与系统科学学院 专业班级信息与计算科学2011级2班学生姓名吕永强 学号201101051416 摘要 网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。 本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。 为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时 刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。 本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。 Abstract The network flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can bring us great convenience. The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons. In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train numbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algorithm, and ultimately solve the problem. In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and最大字段和问题
图论算法 最大流算法和最大匹配算法
最大字段和实验报告
二分法求最大字段和
算法最大字段和
sql语句,需要取出多个字段列中的最大值和最小值
最大流算法小结
最大字段和问题 动态规划法
查找某个字段最大值的记录 SQL语句
从一道题目的解法试谈网络流的构造与算法
动态规划法求最大字段和
算法分析与设计实验报告-最大字段和问题
(毕业设计论文)最大流问题及应用
相关主题
文本预览