(完整版)4+四+贪心算法+习题参考答案

1、第四章作业部分参考答案1 设有 n 个顾客同时等待一项服务。顾客i 需要的服务时间为ti ,1 i n 。应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由(证明)。策略 ：Xtti 1 i n进行排序，ti1 ti2tin,然后按照递增顺序依次服务ii,i2,in即可。解 析 ： 设 得 到 服 务 的 顾 客 的 顺 序 为 j1, j2,., jn ， 则 总 等 待 时 间 为T (n 1) (n 2)九 %？或则在总等待时间T中tji的权重最大，金 的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证

2、明： 设 ti1ti2tin, ，下证明当按照不减顺序依次服务时，为最优策略。记按照iii2in次序服务时，等待时间为T ,下证明任意互换两者的次序，T都不减。即假设互换i,j (i j)两位顾客的次序，互换后等待总时间为 宁，则有 T T.由于T (n 1)ti1 (n 2)ti22tin 2 tin1,T(n1)ti1(n2)ti2(ni)tii(nj)tij2tin2tin1,T(n1)ti1(n2)ti2(ni)tij(nj)tii2tin2tin1,则有T T (j i)(tijtii ) 0.同理可证其它次序，都可以由ikin经过有限次两两调换顺序后得到，而每次交换，总时间不减，从

3、而iii2in为最优策略。2 字符a h出现的频率分布恰好是前 8个Fibonacci数，它们的Huffman编码是什么？将结果推广到n个字符的频率分布恰好是前n个Fibonacci数的情 形。Fibonacci数的定义为：F0 1, F1 1, Fn Fn 2 Fn 1 if n 1解：前 8 个数为 a,b, c,d,e, f, g, h1,1,2,3,5,8, 13, 21Huffman哈夫曼编码树为：54h:213320f:8124C:2b:1a： 1e:5d:3所以a的编码为：1111111 b的编码为：1111110 c的编码为：111110 d的编码为：11110e的编码为：11

4、10f的编码为：110g的编码为：10h的编码为：0推广到 n 个字符：11 1n111 10n211 10n3100第1个字符：n-1个1，第2个字符：n-2个1，1个0，第3个字符：n-3个1，1个0，第n-1 个字符：1 个1 ，1个0，第 n 个字符：1 个 0，3.设R,p2, ,Pn是准备存放到长为L的磁带上的n个程序，程序Pi需要的n带长为 ai 。设aiL ，要求选取一个能放在带上的程序的最大子集合（即其中i1含有最多个数的程序）Q。构造Q的一种贪心策略是按ai的非降次序将程序计入集合。1） 证明这一策略总能找到最大子集Q ，使得ai L 。pi Q2）设Q是使用上述贪心算法得

5、到的子集合，磁带的利用率可以小到何种程度？3）试说明1）中提到的设计策略不一定得到使ai/L取最大值的子集合。pi Q1）证明：不妨设a1 a2 . an,若该贪心策略构造的子集合 Q为a1,a2, ,as, ss则 s 满足ai L 、as as 1 L 。i1i1要证明能找到最大子集，只需说明s 为可包含的最多程序段数即可。 . . 一一 . 即证不存在多于s个的程序集合Q ai1 ,ai2, ，ak, （k s）,使得ai L。 pi Q k 反证法，假设存在多于 s个的程序集Q ai,ai2,曲, （k s）,满足 沏 L。 j1因为a1a2. an 非降序排列，则a1a2asakai

6、1ai2aikL 。因为 k s 且为整数，则其前s+1 项满足a1 a2as as 1 L 。s这与贪心策略构造的子集和 Q中s满足的as as 1 L矛盾。故假设不成立，得证。i12） 磁带的利用率为ai/L;（甚至最小可为0，此时任意aiL 或者aiL）pi Qpi Q3)按照1)的策略可以使磁带上的程序数量最多，但程序的总长度不一定是最大的，假设a1,a2,ai 为 Q 的最大子集，但是若用ai 1 代替 ai ，仍满足i1akai 1 L ，则 a1 ,a2,ai 1, ai 1 为总长度更优子集。k14 .答案见后面所附程序。5 .已知n种货币c1，C2，L，Cn和有关兑换率的n

7、n表R,其中RUJ是一个单位的货币ci 可以买到的货币cj 的单位数。1)试设计一个算法，用以确定是否存在一货币序列ci1,%。，Cik使得：Ri1,i2Ri2,i3L Rik,i112)设计一个算法打印出满足1)中条件的所有序列，并分析算法的计算时间。解：基本解题思想：通过 FLOYD 算法求出最大环。判断最大环的权值之积是否大于1， 如果大于1 说明可以实现套汇，如果不大于 1 说明不能实现套汇。在求解最大环的同时记录下兑换过程中的步骤。算法实现的数据结构：int PathMAX_VERTECX_NUMMAX_VERTECX_NUM;/ 用来记录套汇过程中要经过的路径float value

8、MAX_VERTECX_NUMMAX_VERTECX_NUM;/ 用来记录经过讨回操作后得到的值/借助图来实现该算法typedef structint 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)/ 这里判断

9、是否使兑换率增大，如果增大则记录下来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);/ 递归，货币I 至 J 中间顶点此算法的时间复杂度是：0(93) 算法实现代码：#i

10、nclude#define MAX_VERTECX_NUM 20#define INT_MIN 0int n;int PathMAX_VERTECX_NUMMAX_VERTECX_NUM;float valueMAX_VERTECX_NUMMAX_VERTECX_NUM; typedef structint vexsMAX_VERTECX_NUM; / 顶点向量可以存储每个顶点的信息float arcMAX_VERTECX_NUMMAX_VERTECX_NUM;/ 邻接矩阵主要存放关于边的信息int vexnum,arcnum;/图中当前顶点数和弧数MGraph;void CreateDG(M

11、Graph *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;

12、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+)if(valueik*valuekjvalueij)valueij=valueik*valuekj;Pathij=Pathkj;void Procedure_print(int i,int j)if(Pathij=i)printf(%d,i);return;else if

13、(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);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 ,

14、i);Procedure_print(i,i);printf(n);4.同学们的几种不同答案构造哈夫曼树思想，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点(树根)。答案 1)伪代码：typedef structunsigned int weight;unsigned int parent, lchild, rchild;HTNode, * HuffmanTree;typedef char * HuffmanCode;proc HuffmanCoding(Huffma

15、nTree &HT, HuffmanCode &HC, int *w, int n) if n=1 then returnHuffmanTree 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;endforfor i to m do(*p).weight = (*p).parent = (*p

16、).lchild = (*p).rchild =0;+p;endforfor i from n+1 to m doSelect(HT, i-1, s1, s2);HTs1.parent := i;HTs2.parent := i;HTi.lchild := s1;HTi.rchild := s2;HTi.weight := HTs1.weight + HTs2.weight;endforcdn-1 = 0;/编码结束符for i to n dostart := n - 1;/编码结束符位置f := i;c := i;for f from HTf.parent to f=0 doif HTf.l

17、child = ccd-start := 0;elsecd-start := 1;endelseendifendforendforendHuffmanCoding源代码：#include #include #include #include using namespace std;#define infinite 50000/定义Huffman 树和 Huffman 编码的存储表示typedef structunsigned int weight; / 字符的频数unsigned int parent, lchild, rchild;/双亲结点，左孩子，右孩子HTNode, * Huffman

18、Tree;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;

19、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中HT1 - n选择parent为且 weight最小的两个结点，其序号分别为s1 和 s2void Select(HuffmanTree HT, int n, int &s1, int &s2)int i;s1 = s2 =0;for(i=1; i HTi.weight)s2 = i;elseif (HTi

20、.parent = 0 & HTs1.weight HTi.weight)s1 = i;构造 Huffman树HT,并求出n个字符的 Huffman编码HCvoid 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;

21、/将号单元置一个较大的数for(p=HT+1, i=1; i=n; +i, +p, +w)(*p).weight = *w;/将n 个字符的频数送到HT.weight1 n(*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 编码原理进行构

22、建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;编码结束符fo

23、r(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;elsecd-start = 1;HCi = (char *)malloc(n-start) * sizeof(char); / 为第 i 个 字符编码分配空间strcpy_s(HCi,sizeof(&cdstart),&cdstart);free(cd);答案2)c语言实现：huffman 编码解码#incl

24、ude #include #include #define N 100#define M 2*N-1typedef char * HuffmanCode2*M;/haffman编码typedef structint weight;/权值int parent;/父节节点int LChild;/左子节点int RChild;/右子节点HTNode,HuffmanM+1;/huffman 树typedef struct Nodeint weight; /叶子结点的权值char c; /叶子结点int num; 叶子结点的二进制码的长度WNode,WeightNodeN;/*产生叶子结点的字符和权值*

25、/void CreateWeight(char ch,int *s,WeightNode CW,int *p)int i,j,k;int tag;*p=0;/ 叶子节点个数/统计字符出现个数，放入CWfor(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(Huff

26、man 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:s

27、1;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;/* 叶子结点的编码 */m,intvoid CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int n)int i,c,p,start;char *cd

28、;cd=(char *)malloc(n*sizeof(char);cdn-1=0;/ 末尾置 0for(i=1;i=n;i+)start=n-1; /cd串每次从末尾开始c=i;p=hti.parent;/p 在 n+1 至 2n-1while(p) /沿父亲方向遍历，直到为0start-;/依次向前置值if(htp.LChild=c)/与左子相同，置0cdstart=0;else / 否则置1cdstart=T;c=p；p=htp.parent;weighti.num=n-start; 二进制码的长度（包含末尾0）hi=(char *)malloc(n-start)*sizeof(char

29、);strcpy(hi,&cdstart);将二进制字符串拷贝到指针数组free(cd);/ 释放 cd 内存system(pause);/*所有字符的编码*/void CrtHuffmanCode(charch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,intm)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);

30、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;elsep=htp.RChild; printf(%c,wp.c); /*打印原信息 */i+； /* 释放 huffman 编码内存 */void FreeHuf

31、fmanCode(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 wei

32、ght; /*存放叶子结点的信息*/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)

33、;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( *Nod

34、eCode*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)伪代码

35、： Proc HuffmanCode(A) /A1 nf待编码的数组，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 then p = DeleteMin(h); /移除最小的两个结点 q = DeleteMin(h);r = p+q; r.left = min(p, q); r.right = max(p, q)

36、; / 构造新的结点 r,其值为 p,q 值之和。 左儿子为p和q值较小的，右儿子为较 /大的Insert(h, r); 将r插入堆中 endwhile;p = DeleteMin(h); /取出最后一个结点，此节点即为 huffman树的根节点。 endHuffmanCode (2)java code: 树节点TreeNode: package graduate; public class TreeNodeprivateTreeNodeleftprivateTreeNoderightprivateintvalue;privateintcode ;publicTreeNode() setLef

37、t( 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(

38、 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 ;堆：

39、package graduate;public class Heapprivate HeapNode heapArray ; / 堆容器private int maxSize ; / 堆得最大大小private intcurrentSize; / 堆大小publicHeap( int _maxSize) maxSize = _maxSize;heapArray = new HeapNode maxSize ;currentSize = 0;publicvoid filterDown(int start,int endOfHeap) int i = start;int j = 2 * i + 1

40、;/ j是 i 的左子女位置HeapNode temp = heapArray i;while (j = endOfHeap) / 检查是否到最后位置if (j heapArray j + 1.getKey() j+;if (temp.getKey() 0) / 沿双亲结点路径向上直达根节点/ 双亲结点值小，不调整if ( heapArray i.getKey() = temp.getKey() break ;else / 双亲结点值大，调整heapArray j = heapArray i;j = i;i = (i - 1) / 2;heapArray j = temp; / 回送publi

41、c boolean insert(HeapNode newNode) if (isFull() return false ;else heapArray currentSize = newNode;filterUp( currentSize );currentSize +;return true ;public HeapNode removeMin() if (isEmpty() return null ;HeapNode root = heapArray 0;heapArray 0 = heapArray currentSize - 1;currentSize-;filterDown(0,

42、currentSize - 1);return root;public boolean isEmpty() return currentSize = 0;public boolean isFull() return currentsize = maxSizepublic int getCurrentSize() return currentsizepublic void makeEmpty() currentsize = 0;Huffman编码方法：package graduate;import java.util.HashMap;import java.util.Iterator;publi

43、c class Huffmanpublic Heap minHeap ;public HashMap nodeMap ;public HashMapmap;public Huffman()minHeap = new Heap(20);nodeMap = new HashMap();map = new HashMap();publicvoid huffmanCode( int口 array)for(int i = 0; i 1) HeapNode n1 =minHeap .removeMin();TreeNode tn1 =nodeMap .get(n1);HeapNode n2 =minHea

44、p .removeMin();TreeNode tn2 =nodeMap .get(n2);if (tn1.getValue() tn2.getValue() tn1.setCode(0);tn2.setCode(1);else tn2.setCode(0);tn1.setCode(1);HeapNode newHeapNode =new HeapNode(n1.getKey()+n2.getKey();TreeNode newTreeNode =new TreeNode();newTreeNode.setValue(tn1.getValue()+tn2.getValue();newTreeN

45、ode.setLeft(tn1);newTreeNode.setRight(tn2);minHeap .insert(newHeapNode);nodeMap .put(newHeapNode, newTreeNode);HeapNode root = minHeap .removeMin();TreeNode treeRoot =nodeMap .get(root);leftFirst(treeRoot, );public void leftFirst(TreeNode node, String code)if (node.getCode() != -1)code += new Intege

46、r(node.getCode().toString();if (node.getLeft() =null )map.put( new Integer(node.getValue(), code); return ;leftFirst(node.getLeft(), code);leftFirst(node.getRight(), code);public static void main(String args)Huffman h = new Huffman();int array = 9, 5, 16, 12, 45, 13;h.huffmanCode(array);Iterator i = h.map.keySet().iterator();while (i.hasNext()Integer num = i.next();+ h. map.get(num);System. out .println(num +答案4)伪代码：void CreateHuffmanTree(HuffmanTree T)/构造哈夫曼树，Tm-1 为其根结点int i ， p1 ， p2；InitHuffmanTree(T) ；/将 T 初始化InputWeight(T) ；/席!入叶子权值至 T0 . n-1的 weight