1、第四章作业 部分参考答案1 设有 个顾客同时等待一项服务。顾客 需要的服务时间为 。ni niti1,应该如何安排 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明） 。策略：对 进行排序， 然后按照递增顺序依次服务 1itn,21niiitt即可。12,.ni解析：设得到服务的顾客的顺序为 ，则总等待时间为12,.njj则在总等待时间 T 中 的权重最大，)2()( 121 nnjjjj tttT 1jt的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。jnt证明：设 ，下证明当按照不减顺序依次服务时，为最优策略。,
2、21niiitt记按照 次序服务时，等待时间为 ，下证明任意互换两者的次序， T都不减。即假设互换 两位顾客的次序，互换后等待总时间为 ，则Tji,)( T有 .由于 ,2)()1( 12nniiii ttntT ,2)()( 121 nnji iiiii ttn ,)()( 1221 nnij iiiii ttt 则有 .0)(ijitT同理可证其它次序，都可以由 经过有限次两两调换顺序后得到，而ni21每次交换，总时间不减，从而 为最优策略。2 字符 出现的频率分布恰好是前 8 个 Fibonacci 数，它们的 Huffmanha编码是什么？将结果推广到 个字符的频率分布恰好是前 个 F
3、ibonacci 数的情nn形。Fibonacci 数的定义为： 1,1, 120 ifFFn解：前 8 个数为 a， b， c， d， e， f， g， h1， 1， 2， 3， 5， 8， 13， 21Huffman 哈夫曼编码树为： 54h:21 332012742g:13f:8e:5d:3C:2b:1 a：10 1000000 111111所以 a 的编码为： 1111111b 的编码为：1111110c 的编码为： 111110d 的编码为：11110e 的编码为： 1110f 的编码为：110g 的编码为：10h 的编码为：0推广到 n 个字符：第 1 个字符： n-1 个 1，
4、1n第 2 个字符： n-2 个 1，1 个 0， 2第 3 个字符： n-3 个 1，1 个 0， 3n第 n-1 个字符：1 个 1 ，1 个 0， 10第 n 个字符：1 个 0 ， 03 设 是准备存放到长为 L 的磁带上的 n 个程序，程序 需要np,2 ip的带长为 。设 ，要求选取一个能放在带上的程序的最大子集合（即iaLi1其中含有最多个数的程序） 。构造 的一种贪心策略是按 的非降次序将程Qia序计入集合。1) 证明这一策略总能找到最大子集 ，使得 。QpiiL2) 设 是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？Q3) 试说明 1)中提到的设计策略不一定得
5、到使 取最大值的子集合。Qpiia/1）证明：不妨设 ，若该贪心策略构造的子集合 为 ，12.na ,21sa则 满足 。ssissi LL111、要证明能找到最大子集，只需说明 s 为可包含的最多程序段数即可。即证不存在多于 s 个的程序集合 ，使得 。)(,21 skaQii QpiiLa反证法，假设存在多于 s 个的程序集 ，满足 。,21kii kjij1因为 非降序排列，则 。12.na Laaakiiiks 21因为 且为整数，则其前 s+1 项满足 。sk Ls21这与贪心策略构造的子集和 中 s 满足的 矛盾。故假设不成立，得证。Qsisa112）磁带的利用率为 ;（甚至最小可
6、为 0，此时任意 或者QpiiLa/ Lai）QpiiLa3)按照 1）的策略可以使磁带上的程序数量最多，但程序的总长度不一定是最大的，假设 为 Q 的最大子集，但是若用 代替 ，仍满足,2ia 1iai，则 为总长度更优子集。11ikiLa,121iia4.答案见后面所附程序。5. 已知 种货币 和有关兑换率的 表 ，其中 是一个单位的n12,nc nR,ij货币 可以买到的货币 的单位数。icj1）试设计一个算法，用以确定是否存在一货币序列 使得：12,kiic1231,kRiiRi2）设计一个算法打印出满足 1）中条件的所有序列，并分析算法的计算时间。解：基本解题思想：通过 FLOYD
7、算法求出最大环。判断最大环的权值之积是否大于 1，如果大于 1 说明可以实现套汇，如果不大于 1 说明不能实现套汇。在求解最大环的同时记录下兑换过程中的步骤。算法实现的数据结构：int PathMAX_VERTECX_NUMMAX_VERTECX_NUM;/用来记录套汇过程中要经过的路径float valueMAX_VERTECX_NUMMAX_VERTECX_NUM;/用来记录经过讨回操作后得到的值/借助图来实现该算法typedef structint vexsMAX_VERTECX_NUM; /顶点向量 每种货币对应一个顶点float arcMAX_VERTECX_NUMMAX_VERTE
8、CX_NUM;/邻接矩阵 存放兑换率信息int vexnum,arcnum; /图中当前顶点数和弧数MGraph;算法中的关键步骤：for(k=1;kvexnum;k+)for(i=1;ivexnum;i+)for(j=1;jvexnum;j+) if(valueik*valuekjvalueij)/这里判断是否使兑换率增大，如果增大则记录下来valueij=valueik*valuekj;Pathij=Pathkj; 在输出兑换序列时采用了递归算法：这个算法逆序输出了兑换序列。void Procedure_print(int i,int j)if(Pathij=i)printf(“%d“,i
9、); return;else if(Pathij=0)/输出结点 i 与结点 j 之间不存在通路printf(“NO path“);elseprintf(“%d “,Pathij); Procedure_print(i,Pathij);/递归，货币 I 至 J 中间顶点此算法的时间复杂度是：O(v3)算法实现代码：#include#define MAX_VERTECX_NUM 20#define INT_MIN 0int n;int PathMAX_VERTECX_NUMMAX_VERTECX_NUM;float valueMAX_VERTECX_NUMMAX_VERTECX_NUM;type
10、def structint vexsMAX_VERTECX_NUM; /顶点向量 可以存储每个顶点的信息float arcMAX_VERTECX_NUMMAX_VERTECX_NUM;/邻接矩阵 主要存放关于边的信息int vexnum,arcnum; /图中当前顶点数和弧数MGraph;void CreateDG(MGraph *G)int i,j,k;float w;scanf(“%d%d“,printf(“G-vexnum=%d,G-arcnum=%dn“,G-vexnum,G-arcnum);for(i=1;ivexnum;i+)G-vexsi=i;for(i=1;ivexnum;i+
11、)for(j=1;jvexnum;j+)G-arcij=INT_MIN;for(k=1;karcnum;k+)scanf(“%d%d%f“,G-arcij=w; void ShortestPath_FLOYD(MGraph *G)int i,j,k;for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)if(i=j)valueij=1;elsevalueij=G-arcij;if(G-arcijINT_MIN)Pathij=i;elsePathij=0; for(k=1;kvexnum;k+)for(i=1;ivexnum;i+)for(j=1;jvexnum;j+) i
12、f(valueik*valuekjvalueij)valueij=valueik*valuekj;Pathij=Pathkj; void Procedure_print(int i,int j)if(Pathij=i)printf(“%d“,i); return;else if(Pathij=0)/输出结点 i 与结点 j 之间不存在通路printf(“NO path“);elseprintf(“%d “,Pathij); Procedure_print(i,Pathij);int main()int i,j;MGraph G;freopen(“data.in“,“r“,stdin);freo
13、pen(“data.out“,“w“,stdout);CreateDG(ShortestPath_FLOYD(i=1; if(valueii1)printf(“%f “,valueii); if(Pathii!=0)printf(“%d%d “,i,i);printf(“兑换顺序的逆序输出：%d “,i);Procedure_print(i,i); printf(“n“); 4.同学们的几种不同答案构 造 哈 夫 曼 树 思 想 ， 将 所 有 的 节 点 放 到 一 个 队 列 中 ， 用 一 个 节 点 替 换 两 个 频 率 最 低 的 节点 ， 新 节 点 的 频 率 就 是 这 两
14、个 节 点 的 频 率 之 和 。 这 样 ， 新 节 点 就 是 两 个 被 替 换 节 点 的 父节 点 了 。 如 此 循 环 ， 直 到 队 列 中 只 剩 一 个 节 点 （ 树 根 ） 。答案 1）伪代码： typedef struct unsigned int weight; unsigned int parent, lchild, rchild; HTNode, * HuffmanTree; typedef char * HuffmanCode; proc HuffmanCoding(HuffmanTree #define infinite 50000 /定义 Huffman
15、树和 Huffman 编码的存储表示 typedef struct unsigned int weight; /字符的频数 unsigned int parent, lchild, rchild; /双亲结点，左孩子，右孩子 HTNode, * HuffmanTree; typedef char * HuffmanCode; void Select(HuffmanTree HT, int n, int void HuffmanCoding(HuffmanTree void main() int i, n, *w; cout n; cout wi; HuffmanTree HT; Huffman
16、Code HC; HuffmanCoding(HT, HC, w+1, n); cout HTi.weight) s2 = i; else if (HTi.parent = 0 /构造 Huffman 树 HT，并求出 n 个字符的 Huffman 编码 HC void HuffmanCoding(HuffmanTree HuffmanTree p; int s1, s2, i, m, start, c, f; char *cd; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); HT0.weight = infini
17、te; /将号单元置一个较大的数 for(p=HT+1, i=1; i=n; +i, +p, +w) (*p).weight = *w; /将 n 个字符的频数送到HT.weight1n (*p).parent = (*p).lchild = (*p).rchild = 0; /双亲孩子初始化为 for(; i=m; +i, +p) (*p).weight = (*p).parent = (*p).lchild = (*p).rchild = 0; /将 HuffmanTree 结点权值 HT.weightn+1m+1（频数）及双亲孩子初始化为 for(i= n+1; i=m; +i) /根据 Huffman 编码原理进行构建 Huffman树
