首页 / 算法 / 算法第四章上机实践报告
算法第四章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第四章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2947字,纯文字阅读大概需要5分钟。
内容图文
1.实践题目:
程序存储问题
2.问题描述:
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li,1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案, 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度,计算磁带上最多可以存储的程序数。
3.算法描述:
因为要尽可能装在更多的程序,所以贪心算法的选择基准为程序在磁带上的长度,优先选择长度短的程序。
①贪心选择性质:
设程序已经参照长度从小到大排序,(x1, x2, ..., xn)是程序储存问题的一个最优解,设k = min(1<=i<=n) {i | xi = 1},如果给定的程序存储问题有解,则1<=k<=n。
当k = 1时,(x1, x2, ..., xn)是一个满足贪心选择性质的最优解。
当k > 1时,取y1 = 1,yk = 0,yi = xi,1<i<=n,i≠k,则(n∑i=1)liyi = l1 - lk + (n∑i=1)lixi <= (n∑i=1)lixi <= L
因此,(y1, y2, ..., yn)是所给程序存储问题的可行解。此外,由(n∑i=1)yi = (n∑i=1)xi知,(y1, y2, ..., yn)是满足贪心选择性质的最优解。所以,程序存储问题具有贪心选择性质。
②最优子结构性质:
设(x1,x2,x3,...,xn)是程序存储问题的满足贪心选择性质的最优解,则x1 = 1,(x2,x3...,xn)是磁带容量为c - w1,待装载程序为{2,3,4...,n}时相应最优程序存储问题的解。也就是说,最优程序存储问题具有最优子结构性质。
4.算法时间及空间复杂度分析(要有分析过程)
算法时间复杂度:O(nlogn) —— 快排的时间复杂度为:O(nlogn),排序好后贪心选择过程时间复杂度为:O(n),故综合来看算法时间复杂度为O(nlogn)
空间复杂度:O(n)——因为需要长度为n的数组来存储每段程序的长度。
5.心得体会(对本次实践收获及疑惑进行总结)
贪心算法比之前学的动态规划以及分治法要来的简洁,更为直接。但在利用贪心算法前,要理清好思路,确定好选择的标准,并且一以贯之。同时在利用贪心算法这一思想的时候,会感觉比动态规划实现起来要麻烦不少,经常要借助栈等数据结构。
内容总结
以上是互联网集市为您收集整理的算法第四章上机实践报告全部内容,希望文章能够帮你解决算法第四章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。