搜索
作业三作业三1.点覆盖问题解使用贪心法解使用贪心法按照贪心法从x1取起.第一个区间是[x1,x1+1]顺序考察后面的点假设最后个落入该区间的点顺序考察后面的点，假设最后一个落入该区间的点是xk,xkx1+1,xk+1x1+1.下个区间从xk+1开始，即[xk+1,xk+1+1].按照这样直到所有的点落入最后一个区间为止.按照这样直到所有的点落入最后个区间为止.T(n)=O(n).12文件存储问题2.文件存储问题解将pi从小到大排列，即p1≤p2≤…≤pn.然后按照1,2,…,n的次序将它们依次存入磁盘.下面证明正确性.序将它们依次存磁盘下面明正确性假设最优解I存j个文件，其存储次序为i1,i2,…,ij，j≤n.若{i1,i2,…ij}≠{1,2,…,j}，{i1,i2,…ij}≠{1,2,…,j}，必有某个itj，且有某个1≤k≤j，k∉{i1,i2,…ij}.交换it与k,得到的解I*占用的存储空间与I占用空间的差交换it与k,得到的解I占用的存储空间与I占用空间的差I*也是最优解，但是它比I减少了一个标号大于j的文件.tikikppISISt≤−=−由于,0)(*)(I也是最优解，但是它比I减少了个标号大于j的文件.经过至多j次交换，就可以得到最优解{1,2,…,j}.复杂度W(n)=O(nlogn)+O(n)=O(nlogn)2复杂度W(n)O(nlogn)+O(n)O(nlogn).找零钱问题{12}3.找零钱问题：{1,p,p2,…,pn}，方法方法一.n=0,只有1种钱，贪心法对任意y显然得到最优解.y假设对于任意n种币值，贪心法都得到最优解，考虑n+1种币值{1pp2pn}根据一点定理虑n+1种币值{1,p,p,...,p}.根据点定理，wn−1=wn=1，pn=pn−1⋅p−δ，δ=0.于是于是wn+Gn−1(δ)=1p=pwn−1nn1n1成立，从而贪心法得到最优解.时间W(n)=O(min{nlogy})3时间W(n)=O(min{n,logy})4进程测试问题4.进程测试问题把按截时间排序把进程按截止时间排序取第一个进程的截止时间作为第一个测试点顺序检查能够被这个点测试的进程（开始时间小于等于测试点）直到找到下一个不能被测试到的进等于测试点），直到找到下个不能被测试到的进程为止.取这个进程的截止时间作为下一个测试点.直到检查完所有的进程为止…，直到检查完所有的进程为止时间W(n)=O(nlogn)45Hff编码5.Huffman编码H:0,G:10,HG:10,F:110,E1110FGE:1110,D:11110,EFC:111110,B:1111110,DB:1111110,A:1111111ABC5证明证明设为数列面明∑k设f1,f2,…为Fibonacci数列，下面证明证对k归纳.21+=≤∑kiiff当k=1时，f1f3显然为真.假设k=n时命题成立则k=n+1时有假设k=n时命题成立，则k=n+1时，有31211+++++=+≤+=∑∑nnnnniniffffff所以命题对于k=n+1成立.于是对任意正整数k成立.312111++++==∑∑nnnniiiiffffff根据这个结果，前k个字符合并后子树的权不大于第k+2个Fibonnaci数它将继续与第k+1个字符合并6第k+2个Fibonnaci数.它将继续与第k+1个字符合并