算法第三章上机实践报告

2021/10/23 17:12:59

本文主要是介绍算法第三章上机实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

7-1 最大子段和

1.1 问题描述

 

1.2 算法描述

int Maxsum(int n, int a[])
{
  int sum = 0,b=0;
  for(int i=1;i<=n;i++)
  {
    if(b>0) b+=a[i];
    else b=a[i];
    if(b>sum) sum=b;
  }
  return sum;
}

 

1.3 问题求解

在对于上述分治算法的分析中我们注意到,若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且1<=j<=n。则所求的最大子段和为max b[j],1<=j<=n。
由b[j]的定义可易知,当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。故b[j]的动态规划递归式为:  b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n。

 

1.1.1 根据最优子结构性质,列出递归方程式

故b[j]的动态规划递归式为:  b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n

 

1.1.2 给出填表法中表的维度,填表范围和填表顺序

表的维度:一维

填表范围:由递归方程 b[ j ] = max { b[ j-1] + a[ j ] , a[ j ] },可得填表范围[1,n]

填表顺序:自底向上、从后往前

 

1.1.3 分析该算法的时间和空间复杂度

时间复杂度分析:
因为该算法只循环了一次数组,并且数组长度为n,所以时间复杂度为O(n)。

空间复杂度分析:

因为是数组a[n],因此空间复杂度为 O(n)。

 

1.3 心得体会(对本次实践收获及疑惑进行总结)

为了更好的理解,可以用数组来记录当前最大子段和,但其实也可以直接用一个整型变量来记录就可以了,能更节省空间。

 

2.我对动态规划算法的理解和体会

能采用动态规划求解的问题的一般要具有3个性质:

    (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

  (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

 



这篇关于算法第三章上机实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程