最大子段和问题实验报告.doc

实验四 最大子段和问题1.实验目的（1）掌握动态规划的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果；2.实验要求（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（2）比较不同算法的时间性能；（3）给出测试数据，写出程序文档；3.实验设备和软件环境操作系统：Windows 7（64x）开发工具：Visual Studio 20134. 实验步骤以下实验数据都是以数组a=-2, 11, -4, 13, -5, -2为例子； 蛮力法蛮力法是首先通过两个for循环去求出所有子段的值，然后通过if语句查找出maxsum，返回子序列的最大子段和；分治法（1） 划分：按照平衡子问题的原则，将序列（a1，a2，an）划分成长度相同的两个子序列（a1，a2，.，an/2）和（an/2+1,an）;（2） 求解子问题：对与划分阶段的情况和可递归求解，情况需要分别计算s1=maxk=in/2ak(1=i=n/2),s2=maxk=n2+1jak(n/2+1=j0时，bj=bj-1+aj。（2）、当bj-10时，bj=aj然后做递归操作求出最大子段和；5.实验结果蛮力法#include #include using namespace std;/*-*/int manlifa(int a,int x)int i, j,sum=0,maxsum=0;for (i = 0; i x; i+)for (j = i+1; j sum)sum = ai;if (summaxsum)maxsum = sum;return maxsum;int main()int y,sum;int a = -20, 11, -4, 13, -5, -2 ;int c = sizeof(a)/sizeof(int);sum = manlifa(a, c);cout y;return 0;分治法#include #include using namespace std;int MaxSum(int a, int left, int right)int sum = 0, midSum = 0, leftSum = 0, rightSum = 0;int center, s1, s2, lefts, rights;if (left = right)sum = aleft;elsecenter = (left + right) / 2;leftSum = MaxSum(a, left, center);rightSum = MaxSum(a, center + 1, right);s1 = 0;lefts = 0;for (int i = center; i = left; i-)lefts += ai;if (lefts s1) s1 = lefts;s2 = 0;rights = 0;for (int j = center + 1; j s2) s2 = rights;midSum = s1 + s2;if (midSum leftSum) sum = leftSum;elsesum = midSum;if (sum rightSum) sum = rightSum;return sum;int main()/*int sum;/int a = -20, 11, -4, 14, -5, -2 ;/sum1 = MaxSum(a, 0, 5);cout sum1 endl;*/int j,n;int b100;cout n;cout 请输入序列子段:;for (j = 0; j bj;int sum,i;sum = MaxSum(b, 0, 5);cout sum i;return 0;动态规划法#include using namespace std;int MaxSum(int n, int *a)int sum = 0, b = 0;for (int i = 1; i 0)b += ai;elseb = ai;if (bsum)sum = b;return sum;int main()int k;int a = -2, 11, -4, 13, -5, -2 ;for (int i = 0; i6; i+)cout ai ;cout endl;cout 数组a的最大连续子段和为: MaxSum(6, a) k;return 0;6. 讨论和分析在一开始做最大子段问题的实验的时候，对于蛮力法和分治法的理解还是可以的，但是对于动态规划法的理解还不是那么明确透彻，通过网上的一些解释和结合自己书本上的知识，对动态规划法得到了进一步的理解，接下来是三种算法时间性能的比较：