实验2动态规划算法

《实验2动态规划算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验2动态规划算法班级：学号：姓名：《算法分析与设计》实验报告-7-实验2动态规划算法实验目的和要求（（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努（3）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（4）比较不同算法的时间性能；（3）给出测试数据，写出程序文档。实验内容给定由n个整数组成的序列(a1,a2,…,an)，求该序列形如ai到aj的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。实验环境Turbo

2、C或VC++实验学时2学时，必做实验数据结构与算法核心源代码蛮力法：#include#includeintSum(inta[]){intmax_sum=0;intsum=0;for(inti=0;i<6;i++)//从第一个数开始算起{for(intj=i+1;j<6;j++)//从i的第二个数开始算起{sum=a[i];a[i]=a[i]+a[j];if(a[i]>sum){《算法分析与设计》实验报告-7-sum=a[i];//每一趟的最大值}}if(sum>max_sum){max_sum=sum;}}returnmax_su

3、m;}intmain(void){inta[5];for(inti=0;i<6;i++){printf("请输入第%d个数:",i+1);scanf("%d",&a[i]);}cout<#includeintMaxSum(inta[],intleft,intright);intmain(){inta[5];for(inti=0;i<=5;i++)《算法分析与设计》实验报告-7-{printf("请

4、输入第%d个数:",i+1);scanf("%d",&a[i]);}cout<

5、=(left+right)/2;//划分leftSum=MaxSum(a,left,center);//对应情况①，递归求解rightSum=MaxSum(a,center+1,right);//对应情况②，递归求解s1=0;lefts=0;//以下对应情况③，先求解s1for(i=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;//再求解s2for(j=center+1;j<=right;j++){rights+=a[j];if(rights>s2)s2=rights;}《算法分析与

6、设计》实验报告-7-midSum=s1+s2;//计算情况③的最大子段和if(midSum#includeintmax_sum(intn,int*a,int*besti,int*bestj){int*b=(int*)malloc(n*sizeof(int));intsum=0;inti=-1;inttemp=0;for(i=0;i

7、;i++){if(temp>0)temp=temp+a[i];elsetemp=a[i];b[i]=temp;}sum=b[0];for(i=1;i=0;i--){if(b[i]==a[i]){*besti=1;break;}}free(b);returnsum;}intmain(void){intnum[5];for(inti=0;i<=5;i++){printf("请输入第%d