4 四 贪心算法 习题参考答案.doc_第1页
4 四 贪心算法 习题参考答案.doc_第2页
4 四 贪心算法 习题参考答案.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第四章作业 部分参考答案1 设有个顾客同时等待一项服务。顾客需要的服务时间为。应该如何安排个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。策略：对进行排序，然后按照递增顺序依次服务即可。解析：设得到服务的顾客的顺序为，则总等待时间为则在总等待时间T中的权重最大，的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证明：设，下证明当按照不减顺序依次服务时，为最优策略。记按照次序服务时，等待时间为，下证明任意互换两者的次序，都不减。即假设互换两位顾客的次序，互换后等待总时间为，则有由于则有同理可证其它次序，都可以由经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而为最优策略。2 字符出现的频率分布恰好是前8个Fibonacci数，它们的Huffman编码是什么？将结果推广到个字符的频率分布恰好是前个Fibonacci数的情形。Fibonacci数的定义为：解：前8个数为a， b， c， d， e， f， g， h1， 1， 2， 3， 5， 8， 13， 21Huffman哈夫曼编码树为： 54h:21332012742g:13f:8e:5d:3C:2b:1a：101000000111111所以a 的编码为：1111111b的编码为：1111110c的编码为：111110 d的编码为：11110e的编码为：1110 f的编码为：110g的编码为：10h的编码为：0推广到n个字符：第1个字符： n-1个1， 第2个字符： n-2个1，1个0， 第3个字符： n-3个1，1个0， 第n-1个字符：1个1 ，1个0， 10第 n 个字符：1个0 ， 03 设是准备存放到长为L的磁带上的n个程序，程序需要的带长为。设，要求选取一个能放在带上的程序的最大子集合（即其中含有最多个数的程序）。构造的一种贪心策略是按的非降次序将程序计入集合。1) 证明这一策略总能找到最大子集，使得。2) 设是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？3) 试说明1)中提到的设计策略不一定得到使取最大值的子集合。1） 证明：不妨设，若该贪心策略构造的子集合为，则满足、。要证明能找到最大子集，只需说明s为可包含的最多程序段数即可。即证不存在多于s个的程序集合，使得。反证法，假设存在多于s个的程序集，满足。因为非降序排列，则。因为且为整数，则其前s+1项满足。这与贪心策略构造的子集和中s满足的矛盾。故假设不成立，得证。2）磁带的利用率为;（甚至最小可为0，此时任意或者）3)按照1）的策略可以使
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论