北大屈婉玲算法分析与设计-习题解答6

Exercise31.给定数轴X上n个不同点的集合{x1,x2,…,xn},其中x1x2…xn.现在用若干个长度为1的闭区间来覆盖这些点.设计一个算法找到最少的闭区间个数和位置，说明算法的设计思想并估计算法的时间复杂度.2．有n个文件需要存储在磁盘上，第i个文件需要pi个字节的存储空间，i=1,2,…,n。磁盘的总容量是C，且Cpnii∑=1.如果要求存入的文件个数达到最多，选用哪种算法设计技术？简述算法设计思想，证明算法的正确性，并估计算法最坏情况下的复杂度.3.假设零钱系统的币值是{1,p,p2,…,pn}，p1，且每个钱币的重量都等于1.设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少.说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度分析.4.有n个进程p1,p2,…,pn.对于i=1,2,…,n，进程i的开始时间为s[i],截止时间为d[i].可以通过监测程序Test来测试正在运行的进程.Test每次测试的时间很短，可以忽略不计.换句话说，如果Test在时刻t进行测试，那么它将对满足s[i]≤t≤d[i]的所有进程pi同时取得测试数据.假设最早运行的进程的开始时刻是0，问：如何安排测试时刻，使得对每个进程至少测试一次，且Test测试的次数达到最少？说明你的算法的主要设计思想，给出伪码，并分析算法最坏情况下的时间复杂度.5.设字符集S，其中8个字符A,B,C,D,E,F.G.,H的频率是f1,f2,...,f8，且100×fi是第i个Fibannaci数的值，i=1,2,...,8.(1)给出这8个字符的Huffman树和编码.(2)如果有n个字符，其频率恰好是前n个Fibanacci数，那么Huffman树是什么结构，证明你的结论.