欢迎来到天天文库
浏览记录
ID:47037065
大小:314.50 KB
页数:29页
时间:2019-07-03
《4+四+贪心算法+习题参考答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章作业部分参考答案1.设有个顾客同时等待一项服务。顾客需要的服务时间为。应该如何安排个顾客的服务次序才能使总的等待时间达到最小?总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由(证明)。策略:对进行排序,然后按照递增顺序依次服务即可。解析:设得到服务的顾客的顺序为,则总等待时间为则在总等待时间T中的权重最大,的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证明:设,下证明当按照不减顺序依次服务时,为最优策略。记按照次序服务时,等待时间为,下证明任意互换两者的次序,都不减。即假设互换两位顾客的次序,互换后等待总时间为,则有由于则有同理可证其它次序,都可
2、以由经过有限次两两调换顺序后得到,而每次交换,总时间不减,从而为最优策略。1.字符出现的频率分布恰好是前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的编码为:111110d的编码为:11110e的编码为:111
3、0f的编码为: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,01.设是准备存放到长为L的磁带上的n个程序,程序需要的带长为。设,要求选取一个能放在带上的程序的最大子集合(即其中含有最多个数的程序)。构造的一种贪心策略是按的非降次序将程序计入集合。1)证明这一策略总能找到最大子集,使得。2)设是使用上述贪心算法得到的子集合,磁带的利用率可以小到何种程度?3)试说明1)中提到的设计策略不一定得到使取最大值的子集合。1)证明:不妨设,若
4、该贪心策略构造的子集合为,则满足。要证明能找到最大子集,只需说明s为可包含的最多程序段数即可。即证不存在多于s个的程序集合,使得。反证法,假设存在多于s个的程序集,满足。因为非降序排列,则。因为且为整数,则其前s+1项满足。这与贪心策略构造的子集和中s满足的矛盾。故假设不成立,得证。2)磁带的利用率为;(甚至最小可为0,此时任意或者)3)按照1)的策略可以使磁带上的程序数量最多,但程序的总长度不一定是最大的,假设为Q的最大子集,但是若用代替,仍满足,则为总长度更优子集。4.答案见后面所附程序。5.已知种货币和有关兑换率的表,其中是一个单位的货币可以买到的货币的单位数。1)试设计一个
5、算法,用以确定是否存在一货币序列使得:2)设计一个算法打印出满足1)中条件的所有序列,并分析算法的计算时间。解:基本解题思想:通过FLOYD算法求出最大环。判断最大环的权值之积是否大于1,如果大于1说明可以实现套汇,如果不大于1说明不能实现套汇。在求解最大环的同时记录下兑换过程中的步骤。算法实现的数据结构:intPath[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用来记录套汇过程中要经过的路径floatvalue[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用来记录经过讨回操作后得到的值//借助图来实现该算法typedefs
6、truct{intvexs[MAX_VERTECX_NUM];//顶点向量每种货币对应一个顶点floatarc[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//邻接矩阵存放兑换率信息intvexnum,arcnum;//图中当前顶点数和弧数}MGraph;算法中的关键步骤:for(k=1;k<=G->vexnum;k++){for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){if(value[i][k]*value[k][j]>value[i][j])//这里判断是否使兑换率增大,如果增大则记录下来{val
7、ue[i][j]=value[i][k]*value[k][j];Path[i][j]=Path[k][j];}}}}在输出兑换序列时采用了递归算法:这个算法逆序输出了兑换序列。voidProcedure_print(inti,intj){if(Path[i][j]==i){printf("%d",i);return;}elseif(Path[i][j]==0)//输出结点i与结点j之间不存在通路printf("NOpath");else{printf("%d",Pa
此文档下载收益归作者所有