首页 > 编程语言 > 详细

算法第四章上机实践报告

时间:2019-11-19 01:01:35      阅读:125      评论:0      收藏:0      [点我收藏+]

 算法第四章上机实践报告

组员:王昕宇、吴佩毅

 

1.实践题目:

4-1 程序存储问题 

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li,1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案, 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度,计算磁带上最多可以存储的程序数。

 

2.问题描述:

在给定的一段长度的磁带上要存储尽可能多的程序           =>         每次存储的程序要尽可能的小或者短才能使得存的多,那么可以使用贪心的策略,同时,不可以超过磁带长度。

 

3.算法描述(说明你的贪心策略,并且参考会场安排问题,利用反证法证明贪心选择和最优子结构性质):

 贪心策略:

每一次优先选择该次的所有程序的长度中最短的那一个程序

贪心即只选在剩下的长度中选择最短的程序

  

反证法证明贪心选择:

设集合A={x1,x2,x3...xn}(该集合已经进行过排序,从小到大)

假设最优解B不包含x1(x1是该集合A最短长度的程序),其中最短的程序长度为j,假若j = x1,则最优解中包含x1; 若B中j > x1 ,x1余B中其他的程序长度相容,故存在一个C = {B-{j}∪{x1}} ,从而C也是最优解,故可知最优解一定含有X1 - > 长度最短的程序  - > 贪心选择成立。

 

证明最优子结构性质:

几乎与贪心选择证明类似,主要是,假设A是原问题的最优解,其中包含X1,同时有B = A -{x1}为取出x1的集合的最优解,假设存在B‘ > B , 则B‘+{x1} >A 则此时相矛盾,故不存在此时的B‘

 

4.算法时间及空间复杂度分析(要有分析过程):

 时间复杂度:

 该程序的主要时间在sort()排序上,其中为快排,因此时间复杂度为O(nlogn)

空间复杂度:

 仅存储有限个变量结果和输入数组,其空间复杂度为O(1)

 

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

 本次很多题目都是自己打出来的,自己的实战有所提高?

对贪心算法主要是选择好是取大还是取小比较好的问题,同时因为本章学习的是贪心算法,在打题的时候直接跳过了论证步骤,下次要注意。

很多时候还是要注意一下算法的选择,比如背包问题,0-1的背包问题等等都需要去自己去论证,否则写出来的代码与事实不符。

算法第四章上机实践报告

原文:https://www.cnblogs.com/JeffKing11/p/11884338.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!