算法第三次上机实验报告
2021/11/1 1:10:27
本文主要是介绍算法第三次上机实验报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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];
当b>0时,如果加上a[i]后小于0,就赋值a[i],大于零就和sun比较,如果比较后sum<b,就另sum=b,否则不变。
时间,空间复杂度
只需要循环n次,时间复杂度为O(n), 空间复杂度也一样。
心得与体会:
与组员一起讨论之后的结果如下:因为当总和小于0时,最后返回的结果都为0,所以当b已经小于0时可直接将a[i]的值赋给b,先前的数组成员最大子段和都小于0可不用管了。
2. 你对动态规划算法的理解和体会
动态规划就是把一个大问题一步步降解成越来越小的子问题,直到子问题小到可以用确定的条件来解答。但是动态规划的本质不是递归,递归是完全自顶而下的,每次求解都需要重新计算所有的子问题。我觉得反映动态规划本质的解法是自底而上的解法,即按照顺序,从基元问题一步步扩大问题的规模,直到问题的规模覆盖了我要求解的问题。每一个规模的问题的解叫做一个状态,每个不同规模的问题的解的关系叫做状态转移方程。
这篇关于算法第三次上机实验报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)