【算法设计与分析】最大子段和问题

  • 说明:这是武汉理工大学计算机学院【算法设计与分析】课程的第二次实验第一题:最大子段和问题
  • >>点击查看WUTer计算机专业实验汇总
  • 谨记:纸上得来终觉浅,绝知此事要躬行。

 一、实验题目:

给定由n个整数组成的序列(a_{1},a_{2},a_{3} …… a_{n}……a_{n}),求该序列形如\sum_{k=i}^{j}a_{k}的子段和的最大值,当所有整数均为负整数时,其最大子段和为0

二、实验要求:

1)分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法;

2)比较不同算法的时间性能;

3)给出测试数据,写出程序文档。

三、实验代码

// 实验2.1最大字段和问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。

#include <iostream>
using namespace std;

//最大字段和:蛮力法
int MaxSum_Manli(int a[], int n){

	int sum, maxSum;
	sum = 0;
	maxSum = 0;
	int i, j, k;
	for (i = 0; i < n; i++)	{
		for (j = i; j < n; j++){
			sum = 0;
			for (k = i; k <= j; k++)
				sum += a[k];
			if (sum > maxSum)
				maxSum = sum;
		}
	}
	return maxSum;
}

//最大字段和:分治法实现
int MaxSum_Fenzhi(int a[], int left, int right) {
	int sum = 0, midSum = 0, leftSum = 0, rightSum = 0, i, j;
	int center, s1, s2, lefts, rights;
	if (left == right)                      //如果序列长度为1,直接求解
		sum = a[left];
	else {
		center = (left + right) / 2;             //划分
		leftSum = MaxSum_Fenzhi(a, left, center);          //对应情况①,递归求解
		rightSum = MaxSum_Fenzhi(a, center + 1, right);      //对应情况②,递归求解
		s1 = 0; lefts = 0;                         //以下对应情况③,先求解s1
		for (i = center; i >= left; i--){
			lefts += a[i];
			if (lefts > s1) s1 = lefts;
		}
		s2 = 0; rights = 0;                        //再求解s2
		for (j = center + 1; j <= right; j++){
			rights += a[j];
			if (rights > s2) s2 = rights;
		}
		midSum = s1 + s2;                          //计算情况③的最大子段和
		if (midSum < leftSum) sum = leftSum;           //合并解,取较大者
		else sum = midSum;
		if (sum < rightSum) sum = rightSum;
	}
	return sum;

}

//最大字段和:动态规划法
int MaxSum_Dongtai(int a[], int n){
	int sum, maxSum;
	int i;
	sum = 0;
	maxSum = 0;
	for (i = 0; i < n; i++)	{
		sum += a[i];
		if (sum > maxSum)
			maxSum = sum;
		else if (sum < 0)
			sum = 0;
	}
	return maxSum;
}

int main(){
	int a[100] = { 2,11,-4,13,-5,-2,20 };
	int n = 7;
	cout << "请输入数字串个数:";
	cin >> n;
	cout << "请依次输入 " << n << " 个数字:";
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << endl;
	int sum1 = MaxSum_Manli(a, n);
	int sum2 = MaxSum_Fenzhi(a, 0, n-1);
	int sum3 = MaxSum_Dongtai(a, n);
	cout << "使用蛮力法求得:" << sum1 << endl;
	cout << "使用分治法求得:" << sum2 << endl;
	cout << "使用动态规划法求得:" << sum3 << endl;
}



四、运行结果:


 

相关推荐

发表评论

路人甲
看不清楚?点图切换

网友评论(1)

呲牙
路人甲 1个月前 (2019-11-04) 回复