四贪心算法习题参考答案.doc

第四章作业 部分参考答案1 设有个顾客同时等待一项服务。顾客需要的服务时间为。应该如何安排个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。策略：对进行排序，然后按照递增顺序依次服务即可。解析：设得到服务的顾客的顺序为，则总等待时间为则在总等待时间T中的权重最大，的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证明：设，下证明当按照不减顺序依次服务时，为最优策略。记按照次序服务时，等待时间为，下证明任意互换两者的次序，都不减。即假设互换两位顾客的次序，互换后等待总时间为，则有由于则有同理可证其它次序，都可以由经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而为最优策略。2 字符出现的频率分布恰好是前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的编码为：111110 d的编码为：11110e的编码为：1110 f的编码为：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 ， 03 设是准备存放到长为L的磁带上的n个程序，程序需要的带长为。设，要求选取一个能放在带上的程序的最大子集合（即其中含有最多个数的程序）。构造的一种贪心策略是按的非降次序将程序计入集合。1) 证明这一策略总能找到最大子集，使得。2) 设是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？3) 试说明1)中提到的设计策略不一定得到使取最大值的子集合。1） 证明：不妨设，若该贪心策略构造的子集合为，则满足。要证明能找到最大子集，只需说明s为可包含的最多程序段数即可。即证不存在多于s个的程序集合，使得。反证法，假设存在多于s个的程序集，满足。因为非降序排列，则。因为且为整数，则其前s+1项满足。这与贪心策略构造的子集和中s满足的矛盾。故假设不成立，得证。2）磁带的利用率为;（甚至最小可为0，此时任意或者）3)按照1）的策略可以使磁带上的程序数量最多，但程序的总长度不一定是最大的，假设为Q的最大子集，但是若用代替，仍满足，则为总长度更优子集。4.答案见后面所附程序。5. 已知种货币和有关兑换率的表，其中是一个单位的货币可以买到的货币的单位数。1）试设计一个算法，用以确定是否存在一货币序列使得： 2）设计一个算法打印出满足1）中条件的所有序列，并分析算法的计算时间。解：基本解题思想：通过FLOYD算法求出最大环。判断最大环的权值之积是否大于1，如果大于1说明可以实现套汇，如果不大于1 说明不能实现套汇。在求解最大环的同时记录下兑换过程中的步骤。算法实现的数据结构：int PathMAX_VERTECX_NUMMAX_VERTECX_NUM;/用来记录套汇过程中要经过的路径float valueMAX_VERTECX_NUMMAX_VERTECX_NUM;/用来记录经过讨回操作后得到的值/借助图来实现该算法typedef struct int vexsMAX_VERTECX_NUM; /顶点向量 每种货币对应一个顶点 float arcMAX_VERTECX_NUMMAX_VERTECX_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); return; else if(Pathij=0)/输出结点i与结点j之间不存在通路 printf(NO path); else printf(%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;typedef struct int 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,&(G-vexnum),&(G-arcnum); printf(G-vexnum=%d,G-arcnum=%dn,G-vexnum,G-arcnum); for(i=1;ivexnum;i+) G-vexsi=i; for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) G-arcij=INT_MIN; for(k=1;karcnum;k+) scanf(%d%d%f,&i,&j,&w); 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; else valueij=G-arcij; if(G-arcijINT_MIN) Pathij=i; else Pathij=0; 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); return; else if(Pathij=0)/输出结点i与结点j之间不存在通路 printf(NO path); else printf(%d ,Pathij); Procedure_print(i,Pathij); 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(valueii1) printf(%f ,valueii); if(Pathii!=0) printf(%d%d ,i,i); printf(兑换顺序的逆序输出：%d ,i); Procedure_print(i,i); printf(n); 4.同学们的几种不同答案构造哈夫曼树思想，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。答案1）伪代码： typedef struct unsigned int weight; unsigned int parent, lchild, rchild; HTNode, * HuffmanTree; typedef char * HuffmanCode; proc HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) if n=1 then return HuffmanTree p; integer s1, s2, i, m, start, c, f; char *cd; m := 2 * n - 1; HT0.weight := 1000000; p := HT+1; for i to n do (*p).weight := *w; (*p).parent := (*p).lchild := (*p).rchild := 0; +p; +w; endfor for i to m do (*p).weight = (*p).parent = (*p).lchild = (*p).rchild = 0; +p; endfor for i from n+1 to m do Select(HT, i-1, s1, s2); HTs1.parent := i; HTs2.parent := i; HTi.lchild := s1; HTi.rchild := s2; HTi.weight := HTs1.weight + HTs2.weight; endfor cdn-1 = 0; /编码结束符 for i to n do start := n - 1; /编码结束符位置 f := i; c := i; for f from HTf.parent to f=0 do if HTf.lchild = c cd-start := 0; else cd-start := 1; endelse endif endfor endfor endHuffmanCoding 源代码： #include #include #include #include using namespace std; #define infinite 50000 /定义Huffman树和Huffman编码的存储表示 typedef struct unsigned int weight; /字符的频数 unsigned int parent, lchild, rchild; /双亲结点，左孩子，右孩子 HTNode, * HuffmanTree; typedef char * HuffmanCode; void Select(HuffmanTree HT, int n, int &s1, int &s2); void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n); void main() int i, n, *w; cout n; cout endl; w = (int*) malloc( (n+1) * sizeof(int); cout enter the weight of the code:endl; for(i=1; iwi; HuffmanTree HT; HuffmanCode HC; HuffmanCoding(HT, HC, w+1, n); cout the huffmancode is: endl; for(i=1; i=n; i+) coutwi: ; coutHCi ; coutendl; system(pause); /在HuffmanTree中HT1n选择parent为且weight最小的两个结点，其序号分别为s1和s2 void Select(HuffmanTree HT, int n, int &s1, int &s2) int i; s1 = s2 =0; for(i=1; i HTi.weight) s2 = i; else if (HTi.parent = 0 & HTs1.weight HTi.weight) s1 = i; /构造Huffman树HT，并求出n个字符的Huffman编码HC void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) if (n = 1) return; 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 = infinite; /将号单元置一个较大的数 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树 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /从叶子到根逆向求每个字符的Huffman编码 HC = (HuffmanCode) malloc (n+1) * sizeof (char *); /分配n个字符编码的头指针向量，注号单元未用 cd = (char *) malloc (n * sizeof (char); /分配求编码的工作空间 cdn-1 = 0; /编码结束符 for(i=1; i=n; +i) /逐个字符求Huffman编码 start = n - 1; /编码结束符位置 for(c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) /从叶子到根逆向求编码 if(HTf.lchild = c) cd-start = 0; else cd-start = 1; HCi = (char *)malloc(n-start) * sizeof(char); /为第i个字符编码分配空间 strcpy_s(HCi,sizeof(&cdstart),&cdstart); free(cd); 答案2）c语言实现:huffman编码解码#include #include #include #define N 100 #define M 2*N-1 typedef char * HuffmanCode2*M;/haffman编码 typedef struct int weight;/权值 int parent;/父节节点 int LChild;/左子节点 int RChild;/右子节点 HTNode,HuffmanM+1;/huffman树 typedef struct Node int weight; /叶子结点的权值 char c; /叶子结点 int num; /叶子结点的二进制码的长度 WNode,WeightNodeN; /*产生叶子结点的字符和权值*/ void CreateWeight(char ch,int *s,WeightNode CW,int *p) int i,j,k; int tag; *p=0;/叶子节点个数 /统计字符出现个数,放入CW for(i=0;chi!=0;i+) tag=1; for(j=0;ji;j+) if(chj=chi) tag=0; break; if(tag) CW+*p.c=chi; CW*p.weight=1; for(k=i+1;chk!=0;k+) if(chi=chk) CW*p.weight+;/权值累加 *s=i;/字符串长度 /*创建HuffmanTree*/ void CreateHuffmanTree(Huffman ht,WeightNode w,int n) int i,j; int s1,s2; /初始化哈夫曼树 for(i=1;i=n;i+) hti.weight =wi.weight; hti.parent=0; hti.LChild=0; hti.RChild=0; for(i=n+1;i=2*n-1;i+) hti.weight=0; hti.parent=0; hti.LChild=0; hti.RChild=0; for(i=n+1;i=2*n-1;i+) for(j=1;j=i-1;j+) if(!htj.parent) break; s1=j; /找到第一个双亲不为零的结点 for(;jhtj.weight?j:s1; hts1.parent=i; hti.LChild=s1; for(j=1;j=i-1;j+) if(!htj.parent) break; s2=j; /找到第二个双亲不为零的结点 for(;jhtj.weight?j:s2; hts2.parent=i; hti.RChild=s2; hti.weight=hts1.weight+hts2.weight;/权值累加 /*叶子结点的编码*/ void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n) int i,c,p,start; char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1=0;/末尾置0 for(i=1;i=n;i+) start=n-1; /cd串每次从末尾开始 c=i; p=hti.parent;/p在n+1至2n-1 while(p) /沿父亲方向遍历,直到为0 start-;/依次向前置值 if(htp.LChild=c)/与左子相同,置0 cdstart=0; else /否则置1 cdstart=1; c=p; p=htp.parent; weighti.num=n-start; /二进制码的长度(包含末尾0) hi=(char *)malloc(n-start)*sizeof(char); strcpy(hi,&cdstart);/将二进制字符串拷贝到指针数组h中 free(cd);/释放cd内存 system(pause); /*所有字符的编码*/ void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m) int i,k; for(i=0;im;i+) for(k=1;k=n;k+) /*从weightk.c中查找与chi相等的下标K*/ if(chi=weightk.c) break; hci=(char *)malloc(weightk.num)*sizeof(char); strcpy(hci,hk); /拷贝二进制编码 /*解码*/ void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m) int i=0,j,p; printf(*StringInformation*n); while(im) p=2*n-1;/从父亲节点向下遍历直到叶子节点 for(j=0;hcij!=0;j+) if(hcij=0) p=htp.LChild; else p=htp.RChild; printf(%c,wp.c); /*打印原信息*/ i+; /*释放huffman编码内存*/ void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m) int i; for(i=1;i=n;i+)/释放叶子结点的编码 free(hi); for(i=0;im;i+) /释放所有结点的编码 free(hci); void main() int i,n=0; /*n为叶子结点的个数*/ int m=0; /*m为字符串ch的长度*/ char chN; /*chN存放输入的字符串*/ Huffman ht; /*Huffman二叉数 */ HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/ WeightNode weight; /*存放叶子结点的信息*/ printf(t*HuffmanCoding*n); printf(please input information :); gets(ch); /*输入字符串*/ CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch的长度*/ printf(*WeightInformation*n Node ); for(i=1;i=n;i+) /*输出叶子结点的字符与权值*/ printf(%c ,weighti.c); printf(nWeight ); for(i=1;i=n;i+) printf(%d ,weighti.weight); CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/ printf(n*HuffamnTreeInformation*n); printf(titweighttparenttLChildtRChildn); for(i=1;i=2*n-1;i+) /*打印Huffman树的信息*/ printf(t%dt%dt%dt%dt%dn,i,hti.weight,hti.parent,hti.LChild,hti.RChild); CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/ printf( *NodeCode*n); /*打印叶子结点的编码*/ for(i=1;i=n;i+) printf(t%c:,weighti.c); printf(%sn,hi); CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/ printf(*StringCode*n); /*打印字符串的编码*/ for(i=0;im;i+) printf(%s,hci); system(pause); TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/ FreeHuffmanCode(h,hc,n,m); system(pause); 答案3）(1) 伪代码：Proc HuffmanCode(A)/A1n是待编码的数组，n为数组长度local h; /最小化堆，内含元素为结点类型，堆初始为空integer i;Node p, q, r; /结点数据结构，内含数值以及分别指向左、右儿子的两个指针for i from 1 to to n do /将数组A中的所有元素插入堆Insert(h, A(i);endfor;while h元素个数大于1 thenp = DeleteMin(h); /移除最小的两个结点q = DeleteMin(h);r = p+q; r.left = min(p, q); r.right = max(p, q); /构造新的结点r，其值为p,q值之和。/左儿子为p和q值较小的，右儿子为较/大的Insert(h, r); /将r插入堆中endwhile;p = DeleteMin(h); /取出最后一个结点，此节点即为huffman树的根节点。endHuffmanCode(2)java code：树节点TreeNode:package graduate;public class TreeNodeprivate TreeNode left;private TreeNode right;private int value;private int code;public TreeNode() setLeft(null);setRight(null);setValue(0);setCode(-1);public TreeNode getLeft()return left;public void setLeft(TreeNode left)this.left = left;public TreeNode getRight()return right;public void setRight(TreeNode right)this.right = right;public int getValue()return value;public void setValue(int value)this.value = value;public int getCode()return code;public void setCode(int code)this.code = code;堆节点HeapNode:package graduate;public class HeapNodeprivate int iData;public HeapNode(int key) iData = key;public void setKey(int id) iData = id;public int getKey() return iData;堆：package graduate;public class Heapprivate HeapNode heapArray; / 堆容器private int maxSize; / 堆得最大大小private int currentSize; / 堆大小public Heap(int _maxSize) maxSize = _maxSize;heapArray = new HeapNodemaxSize;currentSize = 0;public void filterDown(int start, int endOfHeap) int i = start;int j = 2 * i + 1; / j是i的左子女位置HeapNode temp = heapArrayi;while (j = endOfHeap) / 检查是否到最后位置if (j heapArrayj + 1.getKey() j+;if (temp.getKey() 0) / 沿双亲结点路径向上直达根节点if (heapArrayi.getKey() = temp.getKey() / 双亲结点值小，不调整break; else / 双亲结点值大，调整heapArrayj = heapArrayi;j = i;i = (i - 1) / 2;heapArrayj = temp; / 回送public boolean insert(HeapNode newNode) if (isFull() return false; else heapArraycurrentSize = newNode;filterUp(currentSize);currentSize+;return true;public HeapNode removeMin() if (isEmpty() retu