算法分析与设计实验2动态规划算法

淮海工学院计算机工程学院实验报告书课程名：算法分析与设计题日：实验2动态规划算法班级：*学号：201*姓名：*实验2动态规划算法一、实验目的和要求(1) 深刻掌握动态规划法的设计思想并能熟练运用；(2) 理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努 力和重新修正的结果；(3) 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；(4) 比较不同算法的时间性能；(5) 给出测试数据，写出程序文档。二、实验内容给定由n个整数(可能有负整数)组成的序列(a1,a2,an)，求该序列形如习k=,jak 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。实验环境Turbo C 或 VC+三、实验学时2学时，必做实验四、核心源代码1、蛮力法：#includeint MaxSum(int a,int n)int sum=0;int i,j;for(i=1;i=n;i+)int asum=0;for(j=i;jsum)sum=asum;return sum;void main()int n,a100,m,i,j,maxsum;cout用蛮力法求最大子段和：nendl;cout请输入整数序列的元素个数：n;cout请输入各元素的值：endl;for(m=1;mam;maxsum=MaxSum(a,n);coutn最大子段和是：maxsumendl;2、分治法：#includeint MaxSum(int a,int left,int right)int sum=0;if (left=right)if(aleft0)sum=aleft;elsesum=0;elseint center=(left+right)/2;int leftsum=MaxSum(a,left,center);int rightsum=MaxSum(a,center+1,right);int s1=0;int lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(leftss1) s1=lefts;int s2=0;int rights=0;for(int j=center+1;js2)s2=rights;sum=s1+s2;if(sumleftsum) sum=leftsum;if(sumrightsum) sum=rightsum;return sum;void main()int n,a100,m ,maxsum;cout请输入整数序列的元素个数：n;cout请输入各元素的值：endl;for(m=1;mam;maxsum=MaxSum(a,1,n);cout最大子段和是：maxsumendl;3、动态规划法：#includevoid MaxSum(int a,int n)int sum=0;int b=0;for(int i=1;i0)b+=ai;elseb=ai;if(bsum)sum=b;coutn最大子段和是： sumendl;void main()int n,a100,m ;cout用动态规划法求最大子段和：nendl;cout请输入整数序列的元素个数：n;cout请输入各元素的值：endl;for(m=1;m=n;m+)MaxSum(a,n);六、实验结果1、蛮力法：2、分治法： * E:C+ 4-Debu.exeW_回啊分治法求最大子段和:青输入整数序列的元素个数: f青输入各元素的值：12345 -6 103成大子段和是：15Press any key to continue3、动态规划法:七、实验体会* *