实验四最大子段和问题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=max{}(1<=i<=n/2),s2=max｛｝(n/2+1<=j<=n),则 s1+s2 为情况③的最大子段和。（3）合并：比较在划分阶段三种情况下的最大子段和，取三者中比较大者为原问题的解。动态规划法划分子问题(1) 划分子问题；(2) 确定动态规划函数；(3) 填写表格；分为两种情况：（1）、当 b[j-1]>0时， b[j]=b[j-1]+a[j]。（2）、当 b[j-1]<0时， b[j]=a[j]然后做递归操作求出最大子段和；5. 实验结果蛮力法#include#include<>usingnamespace std;/*------------------------------------------------------------------------------*/int manlifa(inta[],intx){int i, j,sum=0,maxsum=0;for (i = 0; i < x; i++){for (j = i+1; j < x; j++){sum = a[i];a[i] += a[j];if ( a[i]>sum){sum = a[i];}if (sum>maxsum){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 << sum;cin >> y;return 0;}分治法#include#include<>usingnamespace std;int MaxSum(inta[], intleft, intright){int sum = 0, midSum = 0, leftSum = 0, rightSum = 0;int center, s1, s2, lefts, rights;if ( left == right )sum = a[ left];else{center = (left + right ) / 2;leftSum = MaxSum( a, left, cen...
VIP
