第四章作业 部分参考答案1． 设有n 个顾客同时等待一项服务。

顾客i 需要的服务时间为n i t i ≤≤1,。

应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。

试给出你的做法的理由（证明）。

策略：对 1i t i n ≤≤进行排序，,21n i i i t t t ≤≤≤ 然后按照递增顺序依次服务12,,...,ni i i 即可。

解析：设得到服务的顾客的顺序为12,,...,n j j j ，则总等待时间为,2)2()1(1221--+++-+-=n n j j j j t t t n t n T 则在总等待时间T 中1j t 的权重最大，jnt 的权重最小。

故让所需时间少的顾客先得到服务可以减少总等待时间。

证明：设,21n i i i t t t ≤≤≤ ，下证明当按照不减顺序依次服务时，为最优策略。

记按照n i i i 21次序服务时，等待时间为T ，下证明任意互换两者的次序，T都不减。

即假设互换j i ,)(j i <两位顾客的次序，互换后等待总时间为T ~，则有.~T T ≥由于,2)2()1(1221--+++-+-=n n i i i i t t t n t n T,2)()()2()1(1221--+++-++-++-+-=n n j i i i i i i i t t t j n t i n t n t n T ,2)()()2()1(~1221--+++-++-++-+-=n n i j i i i i i i t t t j n t i n t n t n T则有.0))((~≥--=-i j i i t t i j T T同理可证其它次序，都可以由n i i i 21经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而n i i i 21为最优策略。

2． 字符h a ~出现的频率分布恰好是前8个Fibonacci 数，它们的Huffman 编码是什么？将结果推广到n 个字符的频率分布恰好是前n 个Fibonacci 数的情形。

Fibonacci 数的定义为：1,1,11210>+===--n if F F F F F n n n解：前8个数为a ， b ， c ， d ， e ， f ， g ， h1， 1， 2， 3， 5， 8， 13， 21Huffman 哈夫曼编码树为：所以a 的编码为：1111111 b 的编码为：1111110 c 的编码为：111110 d 的编码为：11110e 的编码为：1110f 的编码为：110g 的编码为：10 h 的编码为：0推广到n 个字符：第1个字符： n-1个1，1111-n 第2个字符： n-2个1，1个0， 01112-n 第3个字符： n-3个1，1个0， 01113-n ……第n-1个字符：1个1 ，1个0， 10 第 n 个字符：1个0 ， 03． 设n p p p ,,,21 是准备存放到长为L 的磁带上的n 个程序，程序i p 需要的带长为i a 。

设L a ni i >∑=1，要求选取一个能放在带上的程序的最大子集合（即其中含有最多个数的程序）Q 。

构造Q 的一种贪心策略是按i a 的非降次序将程序计入集合。

1) 证明这一策略总能找到最大子集Q ，使得∑∈≤Qp ii L a 。

2) 设Q 是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？ 3) 试说明1)中提到的设计策略不一定得到使∑∈Qp ii L a /取最大值的子集合。

1）证明：不妨设12...n a a a ≤≤≤，若该贪心策略构造的子集合Q 为},,,{21s a a a ，则s 满足∑∑=+=>+≤si s s si i L a a L a 111、。

要证明能找到最大子集，只需说明s 为可包含的最多程序段数即可。

即证不存在多于s 个的程序集合)(},,,,{~21s k a a a Q k i i i >= ，使得∑∈≤Qp i i L a ~。

反证法，假设存在多于s 个的程序集)(},,,,{~21s k a a a Q k i i i >= ，满足∑=≤kj i L a j 1。

因为12...n a a a ≤≤≤非降序排列，则L a a a a a a a k i i i k s ≤+++≤++++ 2121。

因为s k >且为整数，则其前s+1项满足L a a a a s s ≤++++121 。

这与贪心策略构造的子集和Q 中s 满足的∑=+>+si s sL a a11矛盾。

故假设不成立，得证。

2）磁带的利用率为∑∈Qp ii L a/;（甚至最小可为0，此时任意L a i >或者∑∈<<Qp i i L a ）3)按照1）的策略可以使磁带上的程序数量最多，但程序的总长度不一定是最大的，假设},,,{21i a a a 为Q 的最大子集，但是若用1+i a 代替i a ，仍满足∑-=+<+111i k i kL a a，则},,,,{1121+-i i a a a a 为总长度更优子集。

4.答案见后面所附程序。

5. 已知n 种货币12,,,nc c c 和有关兑换率的n n ⨯表R ，其中[,]R i j 是一个单位的货币i c可以买到的货币j c 的单位数。

1）试设计一个算法，用以确定是否存在一货币序列12,,,ki i i c c c 使得：12231[,][,][,]1kR i i R i i R i i > 2）设计一个算法打印出满足1）中条件的所有序列，并分析算法的计算时间。

解：基本解题思想：通过FLOYD 算法求出最大环。

判断最大环的权值之积是否大于1，如果大于1说明可以实现套汇，如果不大于1 说明不能实现套汇。

在求解最大环的同时记录下兑换过程中的步骤。

算法实现的数据结构：int Path[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用来记录套汇过程中要经过的路径 float value[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用来记录经过讨回操作后得到的值 //借助图来实现该算法 typedef struct{int vexs[MAX_VERTECX_NUM]; //顶点向量 每种货币对应一个顶点float arc[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//邻接矩阵 存放兑换率信息 int vexnum,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])//这里判断是否使兑换率增大，如果增大则记录下来 {value[i][j]=value[i][k]*value[k][j]; Path[i][j]=Path[k][j]; } } }}在输出兑换序列时采用了递归算法：这个算法逆序输出了兑换序列。

void Procedure_print(int i,int j){if(Path[i][j]==i){printf("%d",i);return;}else if(Path[i][j]==0)//输出结点i与结点j之间不存在通路printf("NO path");else{printf("%d ",Path[i][j]);Procedure_print(i,Path[i][j]);//{递归，货币I至J中间顶点}}}此算法的时间复杂度是：O(v^3)算法实现代码：#include<stdio.h>#define MAX_VERTECX_NUM 20#define INT_MIN 0int n;int Path[MAX_VERTECX_NUM][MAX_VERTECX_NUM];float value[MAX_VERTECX_NUM][MAX_VERTECX_NUM];typedef struct{int vexs[MAX_VERTECX_NUM]; //顶点向量可以存储每个顶点的信息float arc[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//邻接矩阵主要存放关于边的信息int vexnum,arcnum; //图中当前顶点数和弧数}MGraph;void CreateDG(MGraph *G){int i,j,k;float w;scanf("%d%d",&(G->vexnum),&(G->arcnum));printf("G->vexnum=%d,G->arcnum=%d\n",G->vexnum,G->arcnum);for(i=1;i<=G->vexnum;i++){G->vexs[i]=i;}for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){G->arc[i][j]=INT_MIN;}}for(k=1;k<=G->arcnum;k++){scanf("%d%d%f",&i,&j,&w);G->arc[i][j]=w;}}void ShortestPath_FLOYD(MGraph *G){int i,j,k;for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){if(i==j)value[i][j]=1;elsevalue[i][j]=G->arc[i][j];if(G->arc[i][j]>INT_MIN)Path[i][j]=i;elsePath[i][j]=0;}}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]){value[i][j]=value[i][k]*value[k][j];Path[i][j]=Path[k][j];}}}}}void Procedure_print(int i,int j){if(Path[i][j]==i){printf("%d",i);return;}else if(Path[i][j]==0)//输出结点i与结点j之间不存在通路printf("NO path");else{printf("%d ",Path[i][j]);Procedure_print(i,Path[i][j]);}}int main(){int i,j;MGraph G;freopen("data.in","r",stdin);freopen("data.out","w",stdout);CreateDG(&G);ShortestPath_FLOYD(&G);i=1;if(value[i][i]>1){printf("%f ",value[i][i]);if(Path[i][i]!=0)printf("%d%d ",i,i);printf("兑换顺序的逆序输出：%d ",i);Procedure_print(i,i);printf("\n");}}4.同学们的几种不同答案构造哈夫曼树思想，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。