Java教程

算法第三次上机实验报告

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

1. 实践报告任选一题进行分析。内容包括:

问题描述

题目:

 

求最大子段和

 

问题描述:

 

给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时,定义子段和为0

 

算法描述

 

设一个数组a[ ],用于存放n个数,定义一个整型sum存放最大和,定义一个整型b用于计算最大子段和。

 

for语句访问数组,当b<0时,可将它直接赋值为a[i];

 

b0时,如果加上a[i]后小于0,就赋值a[i],大于零就和sun比较,如果比较后sum<b,就另sum=b,否则不变。

 

时间,空间复杂度

 

只需要循环n次,时间复杂度为O(n), 空间复杂度也一样。

 

心得与体会:

 

与组员一起讨论之后的结果如下:因为当总和小于0时,最后返回的结果都为0,所以当b已经小于0时可直接将a[i]的值赋给b,先前的数组成员最大子段和都小于0可不用管了。

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

 

动态规划就是把一个大问题一步步降解成越来越小的子问题,直到子问题小到可以用确定的条件来解答。但是动态规划的本质不是递归,递归是完全自顶而下的,每次求解都需要重新计算所有的子问题。我觉得反映动态规划本质的解法是自底而上的解法,即按照顺序,从基元问题一步步扩大问题的规模,直到问题的规模覆盖了我要求解的问题。每一个规模的问题的解叫做一个状态,每个不同规模的问题的解的关系叫做状态转移方程。

 

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