计算机算法基础 第2版 习题及答案 第7章

PAGE41第7章 贪心算法假设数组A[1..n]和B[1..m]已经排好序，A[1]£A[2]£…£A[n]，和B[1]£B[2]£…£B[m]。请设计一个复杂度为O(n+m)的贪心算法在数组A[1..n]和B[1..m]中各找一个数A[u]和B[v]使得它们的差别|A[u]-B[v]|最小。解：我们先考虑A[1]和B[1]，记下他们的差|A[1]-B[1]|。当然这个差很可能不是最小的。我们要继续找更好的解。下一步该如何做呢？我们观察到，如果A[1]B[1]，那么A[1]不可能在更好的解中，这是因为对任何B[v]，v>1，都有|A[1]-B[v]||A[1]-B[1]|。类似地，如果A[1]>B[1]，那么B[1]不可能在更好的解中。这个过程很象合并二个序列，每次取两序列的首项做比较，用它们的差来更新目前最佳解，然后，刪去较小的首项。根据这个观察，我们有以下算法。Minimum-difference(A[1..n],B[1..m],u,v,d) //d=|A[u]-B[v]|是最小差值d¬¥ //初始化i¬1j¬1whilei£nandj£m if|A[i]-B[j]|<d then u¬i v¬j d¬|A[i]-B[j]| endif ifA[i]£B[j] then i¬i+1 else j¬j+1 endifendwhilereturn(u,v,d)End因为在第4行到第14行的循环中，每检查一对数字，A[i]和B[j]，我们就从两序列中刪去一个数，所以，与合并算法类似，上述算法的复杂度为O(m+n)。请设计一个复杂度为(nlgn)的算法来确定有n个数的集合A[1..n]中是否有两个数字之和正好等于一个给定的数x。解：第一步，我们先将A[1..n]排序，使得A[1]≤A[2]≤A[3]≤…≤A[n]。 第二步，检查A[1]+A[n]。如果A[1]+A[n]=x，则任务完成。否则，如果A[1]+A[n]<x，则A[1]不会在解中，下面的检查可不考虑A[1]；如果A[1]+A[n]>x，则A[n]不会在解中，下面的检查可不考虑A[n]。第三步，重复第二步的做法，在剩下的要检查的序列中把首尾两项相加。如果和为x则搜索成功，否则，在丢弃一个数字后的序列中继续用这个办法搜索直到找到答案。算法的伪码如下。Search-SUM(A[1..n],x)SortA[1..n]suchthatA[1]≤A[2]≤A[3]≤…≤A[n]i1jnwhilei<j ifA[i]+A[j]=x thenreturn(true,i,j) else ifA[i]+A[j]<x thenii+1 elsejj-1 endif endifendwhilereturn(false)End因为排序需要(nlgn)时间，第4行到第12行的while循环需要O(n)时间，所以上面算法的复杂度为(nlgn)。给定一数组A[1..n]，请设计一个O(nlgn)的算法来确定数组A中是否有两个数A[i]和A[j](1i，jn)，使得A[i]=A[j]+1。如果有，则报告(i,j)，否则报告(0,0)。注意，数组A中的数可以是实数，不一定是整数。另外，i<j或i>j都可以。解：显然，如果我们检查所有可能的两个数的话，我们就需要(n2)次运算。我们的做法是，先把数组A[1..n]排序后放入另一数组B，使得B[1]≤B[2]≤B[3]≤…≤B[n]。我们把排序后的A[1..n]放入另一数组B，而不是数组A本身，是为了方便报告数字在原始序列中的序号。然后，用贪心法搜索是否有u和v使得B[u]=B[v]+1。如果有，找出它们在序列A中序号。设B[u]=A[i]，B[v]=A[j]，那么我们有A[i]=A[j]+1。在搜索u和v时，初始化指针v=1，u=2。如果B[u]=B[v]+1，则找到答案，输出结果。否则，如果B[u]>B[v]+1，那么B[v]不可能在解中，故在下面搜索中可刪去，我们把指针v加1。如果B[u]<B[v]+1，那么B[u]不可能是解中的B[u]或A[i]，我们把指针u加1。这样，最多经过2n-1次比较就可有答案。下面是伪码。Search(A[1..n],i,j) //n2B[1..n]A[1..n]SortB[1..n]suchthatB[1]≤B[2]≤B[3]≤…≤B[n]v1u2foundfalsewhileunandfound=false ifB[u]=B[v]+1 then foundtrue else ifB[u]>B[v]+1 //B[v]不可能是解的一部分 then vv+1 ifu=v //两个数必须不同 thenuu+1 endif else uu+1 endif endifendwhileiffound=true then findisuchthatA[i]=B[u] //在数组B排序时就可留下对应关系 findjsuchthatA[j]=B[v] return(i,j) else return(0,0)endifEnd因为排序是上面算法的主要部分，所以它的复杂度是O(nlgn)。Toyota(丰田)公司在过去的n个月中生产的汽车数分别是A[1],A[2],…,A[n]。我们希望知道是否其中有一段时间，该公司生产的汽车总数正好等于M。也就是说，能否找到i和j(1£i£j£n)，使得k=ijAk=M。请设计一个O(n)的贪心算法找出i和解：显然我们可假定A[k]0(1£k£n)。思路是，我们先从A[1]起把每月的产量累加。如果加到某个A[k]时，正好等于M，则得到解；如果小于M则继续加下一个月的产量；如果超过M，说明A[1]不可能在解之中，把它从当前累加和中丢弃，然后再继续上述做法直到找到答案。Car-Production(A[1..n],M,i,j)j¬i¬1u¬A[1] //初始累加数whilej£n ifu=M then return(i,j) //找到答案 elseif u<M //到j为止的任何期间不可能有解 then j¬j+1 u¬u+A[j] //继续累加 else i¬i+1 //A[i]开始的任何区间不可能有解 u¬u-A[i] //把A[i]从累加和中丢弃 endif //这时，如果i>j，则表明u=0 endifendwhilereturn(nosolution)end假设一长途汽車线路上有n个站点并顺序编号为1，2，…，n，其中起点站为1，终点站为n。旅客可以从任一个站i上车(1≤i≤n-1)，到下面任一站j下车(i<j≤n)。假设已知p(i,j)为需要在站i上車，在站j下車的旅客人数(1£i<j£n)。又假设每部公共汽車停靠每一个站并可载客30人。请设计一个O(n2)算法来确定至少需要多少部汽車可以满足所有旅客需要。解：我们先确定最拥挤的一段(i,i+1)至少需要多少不同的座位。然后用30去除即可。Minimum-Number-of-Buses(P,n)M¬0 //初始化forj¬2ton M¬M+p(1,j) //从起点站出发总人数endforlargest¬M //当前找到的最拥挤的一段需要的座位数fori¬2ton //计算从站i到i+1需要的座位数 fork¬1toi-1 //当前的M是从站i-1到i需要的座位数 M¬M-p(k,i) //减去所有在站i下車人数 endfor forj¬i+1ton M¬M+p(i,j) //加上所有在站i上車人数 endfor ifM>largest thenlargest¬M //更新最大值 endifendforreturnélargest/30ùEnd(a)请为下面表中的8个字符构造哈夫曼编码。它们在每100个字中出现的频率在表中给出。字符频率字符频率A5.0E13.5B7.0F10.5C19.0G25.0D6.0H14.0在这个哈夫曼编码中，平均每个字符需要多少比特？解:(a)构造的前缀码树如下，每个字符的编码显示在每个字符下面。01H,14.0A01H,14.0A,5.01001B,7.0F,10.51043.50G,25.01024.501131.5D,6.0056.5110011.017.51010010111E,13.50001C,19.00000110101(3×13.5+4×6+4×5+219+2×25+3×14+4×10.5+4×7)/100=2.845。假设我们有n张照片和n个相框。为方便起见，假定它们的宽度都一样但长度不等。这n张照片的长度由数组P[1..n]给出，而这n个相框的长度由数组F[1..n]给出。如果P[i]£F[j](1i,jn)，那么第i张照片可以装在第j个相框里。请设计一个O(nlgn)的算法将尽可能多的照片配上相框并证明算法的正确性。注意，一张照片只许配一个相框，一个相框也只许配一张照片。解：把P[1..n]和F[1..n]排序，使得P[1]≤P[2]≤P[3]≤…≤P[n]，F[1]≤F[2]≤F[3]≤…≤F[n]。假设P[i]和F[j]分别是当前照片序列和相框序列的头，如果P[i]F[j]，我们则把它们配上，并记为(i,j)。否则F[j]不可能配仼何照片，丢弃之。然后再用同样的方法为剩下的序列继续配。伪码如下。正确性证明随后。Match-Photo-to-Frame(P[1..n],F[1..n])SortP[1..n]suchthatP[1]≤P[2]≤P[3]≤…≤P[n]SortF[1..n]suchthatF[1]≤F[2]≤F[3]≤…≤F[n]S¬Æ //配好对的集合，初始为空i¬j¬1whilei£nandj£n ifP[i]£F[j] then S¬SÈ(i,j) i¬i+1 j¬j+1 else j¬j+1 endifendwhilereturnSEnd正确性证明：如果算法输出的集合S为空，则说明P[1]>F[n]，显然正确。所以我们只需考虑S非空的情况，这时，必有某个j使S含有对子(1,j)。并且，由算法知，F[j]是可以配P[1]中最短的，所有从F[1]到F[j-1]的相框都比P[1]短，从而不可能配任何相片。因此，我们只要能证明有个最佳解也包含对子(1,j)，那么算法就被证明正确了。这是因为，配完(1,j)后，最佳算法也不可能为F[1]到F[j-1]的相框配上任何相片。那么，最佳算法面对的剩余相片和相框的序列和我们面对的是完全一样的。所以，算法重复同样的方法，也必然是正确的。我们先证明存在一个最优解，它含有对子(1,v)(这里的v也许不等于j)。我们用反证法。如果不是，而某个最佳解S*中照片长度最小的对子是(u,v)，u>1。那么，因为P[1]£P[u]，我们可用对子(1,v)换走(u,v)，集合M=(S*-{(u,v)}){(1,v)}仍是一个最优解。这个最优解含有对子(1,v)。我们再证明存在一个最优解，它含有对子(1,j)。如果上面最优解所含对子(1,v)等于(1,j)，则证明完成。如果不是，一定有v>j，这是因为算法已搜索过所有短于F[j]的相框，它们都不够长。我们分两种情况讨论。最优解M中没使用F[j]。对这种情况，我们只需用对子(1,j)换走(1,v)即可。最优解M使用了F[j]，有对子(w,j)。那么，我们有关系P[1]£P[w]£F[j]£F[v]。所以，我们可以重新配对，用对子(1,j)和(w,v)换走(1,v)和(w,j)。这样得到的集合仍是最优解而且含有对子(1,j)。算法的主要部分是排序，所以有复杂度O(nlgn)。用贪心法设计一个O(n)的算法解决第2章习题3的问题。为方便起见，问题重述如下。假设Google公司在过去n天中的股票价格记录在数组A[1..n]中。我们希望从中找出两天的价格，其价格的增幅最大。也就是说，我们希望找到A[i]和A[j](i<j)使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1£i<j£n}。解：思路是，我们先找到小规模的解，然后逐步扩大。具体做法是，先找到两个数A[1..2]的最优解，再找出A[1..3]的最优解，等等，直到找出A[1..n]的最优解。假设我们已找出A[1..i]的最优解，如何找A[1..i+1]的最优解呢？因为我们已有A[1..i]的最优解，我们只需考虑是否A[i+1]可以带来更好的解。A[i+1]可以带来的最好解是A[i+1]减去A[1..i]中最小的值，即d=A[i+1]–min{A[k]|1ki}。我们只要把d和A[1..i]的最优解比较一下就可以了。根据这个思路，在算A[1..i]的最佳解时，我们一方面要更新目前最好的解，另一方面还要更新目前为止A[1..i]中最小的数以便下一步使用。伪码如下。Max-Profit(A[1..n],m,i,j) //假定n>1，m是要找的最大差价。m¬-¥ //初始值。min-index¬1 //目前看到的数组A中最小的数的序号。fork2ton ifA[k]–A[min-index]>m //A[k]带来更优解，要更新。 then m¬A[k]–A[min-index] i¬min-index j¬k endif ifA[k]<A[min-index] //无论有无更好解，总要更新最小的数。 thenmin-index¬k endifendforreturn(m,i,j)End显然，这是个O(n)算法。有n个活动a1，a2，…,an需要使用同一个礼堂。礼堂从时刻t=0可以使用，但是任何时刻只能安排最多一个活动。这些活动没有定死的开始或终止时刻，但都希望从t=0开始。假设第i个活动(1in)需要连续使用ti时间。如果在时刻t>0开始，那么必须要付出额外的开销。这个开销与开始时刻t成正比。为简单起见，就把开始时刻t作为开销。请设计一算法来找到一个最佳调度使总的开销最小。也就是说，如果活动ai开始时刻是si，算法要找到一个两两兼容的调度使i=1nsi最少。请证明算法正确性和分析解：我们的做法是先把活动以ti(1in)为关键字从小到大排好。然后以这个顺序从t=0开始逐个安排。下面是伪码，证明随后。Minimum-Overhead-Scheduling(T[1..n],S[1..n]) //计算最佳的开始时间S[1..n]SortT[1..n]suchthatT[1]T[2]…T[n] //把活动以ti排序。S[1]¬0 //从t=0开始安排。fori¬2ton S[i]S[i-1]+T[i-1]endforEnd算法复杂度因排序而有O(nlgn)。正确性证明:显然，在任一个最佳调度中，两个相邻的活动不会有时间间隔，而第一个安排的活动必定从t=0开始。下面我们证明存在一个最优调度，它安排的活动的顺序与上面算法得到的一致。我们用反证法证明。假如不存在这样的最优调度，那么在一个最优调度中，一定存在两个相邻的活动ai和aj使得T[i]>T[j]但ai却安排在aj之前。这样相邻的一对活动称为一个颠倒。我们假定最优调度M是所有最优调度中颠倒数最少的。如果它的颠倒数为0，则算法得证。故假定M有两个相邻的活动ai和aj使得T[i]>T[j]但ai却安排在aj之前。下面图(a)显示了这种情况。现在，如下图(b)所示，如果我们交换ai和aj的顺序可得到一个新的调度S*。它们的交换不影响其他活动的安排，但却使ai和aj的开销从S[i]+S[j]变为S*[i]+S*[j]。因为S[i]=S*[j]而S[j]=S*[i]–T[j]+T[i]>S*[i]。所以新的调度有较小开销。这与M是最优调度矛盾。所以，最优调度不可以含有颠倒。因此，算法是正确的。 某剧场举办一个电影节。剧场内有二个电影院，X和Y。在从t=0开始的某一段时间内，电影院X会顺序放映n个长短不一的电影x1，x2，…，xn，其每场开始和结束时间顺序为(a1，b1)，(a2，b2)，…，(an，bn)。从t=0开始，在同一期间，电影院Y会连续放映m个电影，y1，y2，…，ym，其每场开始和结束时间顺序为(c1，d1)，(c2，d2)，…，(cm，dm)。我们规定每位观众必须准时入场并不得中途退场。假定两电影院之间距离极近，覌众从一个影院走到另一个所需时间为零。请设计一个时间为O(m+n)的贪心算法以决定同一个观众最多可以看完几场电影，并为他选出这些电影。你必须解释为什么你的算法可给出最佳的解，即保证看到最多的电影。解：解的思路是，从t=0开始，决定下一场电影是去电影院X还是Y去看。如果b1£d1那么去电影院X看x1。这个决定不会错，因为如果最佳解不含有x1，那么最佳解中第一个看的电影要么是y1，或者是b1以后影院X放映的电影。如果是y1，则将y1换为x1后仍是一个最佳解。如果第一个看的电影是b1以后影院X放映的电影，则可把x1加入到最佳解中而看到更多的电影。因此，如果b1£d1选取x1不会错。反之，如果b1>d1则选y1。一旦选中，那么下一个要做决定的时刻就是看完第一场电影那个时刻(b1或d1)。这时可用同样的原理来决定下一场电影是去电影院X还是去Y。在作决定前，要找到各影院下一场开映的时间。下面是该算法的伪码。Movie-Selection(X[1..n],Y[1..m],S) //S是选中电影的集合S¬current-time¬0 //当前选下部电影的时刻i¬1 //电影院X的下一个要考虑的电影j¬1 //电影院y的下一个要考虑的电影whilei£nandj£m ifbi£dj then S¬SÈ{xi} i¬i+1 current-time¬bi whilecj<current-timeandj<m j¬j+1 //电影yj必须在current-time之后开映。 endwhile else S¬SÈ{yj} j¬j+1 current-time¬dj whileai<current-timeandi<n i¬i+1 //电影xi必须在current-time之后开映。 endwhile endifendwhileifi>n //电影院X的所有电影已检查完毕。thenfork¬jtom //电影院Y的剩余电影都可以看。 S¬SÈ{yj} endfor elsefork¬iton S¬SÈ{xi} endforendifEnd这个算法显然有O(m+n)复杂度，因为每个电影只检查一次便决定取舍，而每次检查只需O(1)时间。考虑一个加权的完全图G(V,E)，其中顶点集合是V={v1,v2,…,vn}。每个顶点vi(1£i£n)含有一个整数ai。边(vi,vj)的权值是|ai–aj|。下面一个图给出了一个5个顶点的例子。我们希望找到一条经过每个点正好一次的路径(哈密尔顿路径)使得路径的总的权值最小。这里，一条路径的权值是路径上所有边的权值总和。顶点内的数字不计入权值。(其实，把顶点内数字计入权值不会改变解。)(a)请设计一个贪心算法来找到这条最佳路径。你可以选择任一点开始和仼一点结束。(b)重复(a)，但是你必须从点vi开始和到vj结束(ij)。解：(a) 我们先把顶点按所含整数的大小排序使得a1£a2£…£an。那么这条路径可从a1的顶点开始，按照这个排序顺序走到含an的顶点止。下面给出伪码，证明随后。TSPP(A[1..n])SortverticessuchthatA[1]£A[2]£…£A[n]returnthepathof<v1,v2,…,vn> //vi含整数ai(1≤i≤n)。End正确性证明：我们用归纳法证明，对任一个序号k(1kn)，存在一个最优解，b1，b2，…，bn，使得b1是最小的，b2是第2小的，…，bk是第k小的。归纳基础：当k=1时，设最优解为b1，b2，…，bn。因为把序列反向后仍然是一个最优解，不失一般性，可假定b1bn。如果b1不是最小的，那么，因为序列中有比b1小的数而b1bn，所以一定可以找到两个相邻的数，bi和bi+1，使得bi<b1£bi+1。因此，如果我们把b1插入其中，则会得到一个更好的序列。我们来观察一下。变化前的序列：b1，b2，…，bi，bi+1，…，bn变化后的序列：b2，b3，…，bi，b1，bi+1，…，bn因为(b1–bi)+(bi+1–b1)=bi+1–bi，变化后的序列的总权值比变化前的少了|(b2–b1)|。所以，如果第一个数不是最小的，我们总可以作上述变换，直到第一个数是最小的数为止。所以可假定b1是最小的。归纳基础得证。从上面讨论我们还观察到，如果有一个顶点序列或子序列是按照它们所含数字大小排列的话，则不论序列有多长，其对应路径的总权值就等于最大数减去最小数。归纳步骤：假设最佳解的前k个顶点所含的整数是最小的k个数并且有b1£b2£…£bk。我们证明bk+1是余下序列中最小的。假设bk+1不是最小的而bj，j>k+1，是最小的。那么，如果我们把bj抽出来并插到bk+1前面，我们会得到一个更优序列。让我们来比较一下。我们分二种情况讨论：j=n。变化前的序列：b1，b2，…，bk，bk+1，…，bn-1，bn变化后的序列：b1，b2，…，bk，bn，bk+1，…，bn-1因为bkbn<bk+1，变化后的序列的总权值比原序列减少bn-1–bn0。j<n。变化前的序列：b1，b2，…，bk，bk+1，…，bj-1，bj，bj+1，…，bn变化后的序列：b1，b2，…，bk，bj，bk+1，…，bj-1，bj+1，…，bn这种情况下，变化后的序列的总权值比原序列减少:(bj-1-bj)+(bj+1–bj)–|bj+1–bj-1|=min(bj-1,bj+1)–bj+max(bj-1,bj+1)–bj–[max(bj-1,bj+1)–min(bj-1,bj+1)]=2[min(bj-1,bj+1)–bj]0。 所以，存在一个最佳解，它的前k+1个顶点所含的整数是最小的k+1个数并且有b1£b2£…£bk£bk+1，归纳成功。我们先把顶点按所含整数的大小排序使a1£a2£…£an。考虑任何一条从点vi开始到vj结束的最优路径。在这个路径上，有两种情况：v1排在vn前面。我们可以把这条最优路径分三段。第1段是从ai所在顶点到a1所在顶点v1，用[ai..a1]表示；第2段是从a1所在顶点v1到an所在顶点vn间的这一段路径，用[a1..an]表示；第3段是从an所在顶点vn到aj所在顶点vj，用[an..aj]表示。根据前面讨论，第2段序列[a1..an]对应的整数必定是排好序的。另外，第1段[ai..a1]中点的整数值必须在a1和ai之间，否则不会最优。这是因为如果有数字x>ai，我们可以将x抽出后插入到第2段序列[a1..an]中而减少总权值。同理，第3段[an..aj]中点的整数值必须在an和aj之间。这也就是说最优序列对应的整数序列可分三段，而且，每段中数字是排好序的。所以，这个最优路径的总权值必为(ai-a1)+(an-a1)+(an–aj)=(ai–aj)+2(an-a1)。进一步，我们还可以看到，如果在第1段[ai..a1]中有点x，x≠ai，x≠a1，我们都可以把x抽出后插入第2段序列[a1..an]中而总权值不变。所以可认为最优解中的第1段只有一个点ai。同理可认为最优解中的第3段只有一个点aj。v1排在vn后面。类似对(1)的讨论，这个最优序列对应的整数序列可分三段：ai，[an..a1]，aj，其中，第2段含有除ai和aj外的所有点并排好序。所以，这个最优路径的总权值为(an–ai)+(an-a1)+(aj–a1)=(aj–ai)+2(an-a1) 由上面讨论可知，如果i<j，最佳序列对应第一种情况，它由下面三段组成：ai，[a1..an]，aj，总权值为(ai–aj)+2(an-a1)。如果i>j，最佳序列对应第二种情况，它由下面三段组成：ai，[an..a1]，aj，总权值为(aj–ai)+2(an-a1)。根据以上讨论，算法如下。Path(A[1..n],i,j)Sortverticessuchthata1£a2£…£anDeleteaiandajfromthesequence //把ai和aj从序列中刪去Lettheremainingsequencebe[a1..an]ifai<aj thenreturnai，[a1..an]，aj elsereturnai，[an..a1]，aj endifEnd假设我们有n个活动，a1，a2，…,an，要租用学校的教室。每个活动ai(1£i£n)有一个固定的开始时间si和一个固定的完成时间fi(0si<fi<)。安排在同一教室的活动必须两两兼容。假设学校有足够的教室可以从t=0开始使用。请设计一个O(nlgn)贪心算法找到一个调度使我们能租用最少的教室以满足所有n个活动要求。这里，一个调度是指，租用多少教室，以及每个教室安排哪几个两两兼容的活动。(这个问题也被称为区间图着色问题。假如把每对si和fi(1£i£n)看作实数轴上区间[si，fi)的话，我们可以构造一个有n个顶点的区间图。其中n个顶点对应这n个区间(也代表了这n个活动)。如果两个顶点代表的区间有重叠部分，则它们之间有一条边。对一个图着色就是给图中每个点一个颜色使得相邻两点的颜色不同。显然，同一种颜色的点所代表的区间两两不重叠。这也就是说，它们对应的活动两两兼容，可以安排在同一教室。所以，用最少的颜色给区间图着色就对应了用最少的教室安排这n个活动。)解：设这n个活动对应的开始和结束时间分别放在数组S[1..n]和F[1..n]中。一个简单但不正确的做法是，先用书上7.2节的算法Greedy-Activity-Selection(s[1..n],f[1..n])找到一组最大的两两兼容的活动，并分配一个教室给它们。然后，再用这办法在余下的活动中找一组最大的两两兼容的活动，并分配第2个教室给这组活动。继续这样做直到n个活动全部安排好。这个算法在最坏情况下要O(n2)时间并且不保证最优。试看下面一例。i1234si1264fi3578如果用这个简单方法，我们须租用3个教室：H-1={a1，a3}，H-2={a2}，H-3={a4}。但是最好的结果是H-1={a1，a4}，H2={a2，a3}。那么，应该怎祥做才正确呢？一个正确的做法是：把2n个开始和结束时刻在一起排序。假设这个序列是C。C[1]为最小时刻。显然是某个活动的开始时刻。用h记录当前一共开启了多少教室。需要开启一个新教室时，h加1，并且标记新教室为H-h。已开启过的教室中，当前闲置可用的教室标号都存在数组A[1..j]中。开始时，可用教室的集合为空(j=0)。从C[1]开始，逐个检查C[k]，1£k£2n。如果C[k]是某活动ai的开始时刻，C[k]=S[i]，那么:(3.1)如果j>0，则分配给ai标号为A[j]的教室，然后j减1。(3.2)如果j=0，则没有现成可用的教室，需开启一个新教室，把标号放入A[1]中，j加1。然后，把这个新教室A[1]分配给活动ai后，j减1(又等于0了)。如果C[k]是某个活动ai的结束时刻，C[k]=F[i]，则把它占有的教室释放。做法是，j加1后，该教室的标号放回A[j]中。下面是伪码，正确性证明随后。Classroom(S[1..n],F[1..n],L[1..n],h)//L[i]是活动ai被分配的教室号码。教室号码从1开始按照被启用顺序标号，//h是当前被启用的教室个数。C[1..2n]Sort{S[i],F[i]|1£i£n} //把2n个开始和结束时刻在一起排序。//如果有F[i]=S[j]，把F[i]放在S[j]前面。即先释放ai所用教室，后给aj分配教室//如果有F[i]=F[j]或S[i]=S[j]，顺序可任意。j¬h¬0 //可用教室的集合是A[1..j]，一开始为空fork1to2n ifC[k]=S[i]forsomei //如果C[k]是活动ai的开始时刻 then ifj=0 //如果可用教室的集合为空 then h¬h+1 j¬1 A[j]H-h //开启新教室，标号放入A[j] endif L[i]¬A[j] //分配教室A[j]给ai j¬j-1 else ifC[k]=F[i]forsomei //C[k]是活动ai的结束时刻 then j¬j+1 A[j]L[i] //L[i]是ai使用的教室号 endif endifendforEnd正确性证明：上面算法是正确的，证明如下：显然，算法检查每一个开始时间si并为每一个活动ai都分配一个教室，并且到完成时刻fi之前不会释放，所以，所有活动都被满足。另外，分配在任一个教室的活动是两两兼客的。这是因为每次开启一个教室时，用的是新标号。所以每个教室的标号是唯一的。当标号为A[j]的教室分配给某活动ai后，一直到活动ai释放前，该标号就不存在于数组A中。因此，标号为A[j]的教室不可能同时被两个活动使用。另外，一个活动一结束，它占用的教室马上退回到数组A。所以，一个教室要么正在使用，要么回到数组A。算法所用的教室数h最小。这是因为，当我们为某活动ai而需要开启最后一个，即第h个教室时，j=0，表明所有已启用的其他教室目前都被占用。由（1）知，不同的教室被不同的活动占用。这表明在时刻S[i]，有h-1个活动正在同时进行，而且没有活动在S[i]结束。（既使有某个F[j]=S[i]，因为F[j]排序在S[i]前面，aj已被处理。）现在，又来了新活动ai，所以有h个活动在时刻S[i]之后的一段时间里需要同时进行，少于h个教室不可能满足要求。所以算法所用的教室数最少。上面算法中的排序需要O(nlgn)时间，而后的循环需要O(n)时间，所以有复杂度O(nlgn)。在第6章习题6中，我们考虑过焊接n个钢管的问题。这里，我们再次考虑这个焊接问题。不同的是，我们不限制焊接时钢管之间的顺序。每一次焊接，你可以任选两根钢管来焊接。现在，我们把问题再描述一下。假设我们需要把n个钢管，a1,a2,…,an，焊成一根钢管。这些钢管的重量分别是W[i](1£i£n)。每次焊接你可以从被焊钢管中任选二根来焊，但每次焊接的代价等于被焊两根钢管重量之和。比如我们有5根钢管，重量为3，8，5，10，13。显然，任何一个焊接计划可以用一个有n个叶子的完全二义树表示。如果我们按下面二叉树所示的顺序焊接，那么总的代价为(5+8)+(13+13)+(3+10)+(26+13)=91.(a) 假设有一棵n个叶子的完全二叉树T表示一个焊接计划，证明这个焊接计划的总代价为Cost(T)=k=1nWkdepth(k)，其中depth(k)是代表钢管(b)如果一个焊接计划有最小的总代价，则称为最佳焊接计划。证明在一个对应最佳焊接计划的二叉树T中，代表最轻二根钢管的叶子在最底层。(c)证明有一个最佳焊接计划，它的第一步是把最轻的二根钢管焊在一起。(d)设计一个O(nlgn)的算法为这n个钢管产生一个最佳焊接计划。解：因为钢管ak的重量W[k]在每次含有这根钢管的焊接中被记入代价一次，而含有这根钢管的焊接次数正好等于depth(k)。所以，由钢管ak导致的代价是W[k]depth(k)。例如，在上面的二叉树中，重量为8的钢管出现在3次焊接中，它导致的代价就是83=24。那么，把所有钢管导致的代价加在一起即得到公式Cost(T)=k=1nWkdepth(k)。(亦可用归纳法证明。)例如，在上面的二叉树中，总代价就是132+53+83+32+10(b)不失一般性，假设W[1]和W[2]是最轻二根钢管的重量，W[1]W[2]。假设W[1]的叶子不在最底层。那么因为T是个完全二叉树，在最底层一定有个叶子代表W[k]，而W[k]>W[2]。现在，如果我们让W[1]的叶子代表W[k]，而让W[k]的叶子代表W[1]，那么作这样交换后的焊接计划的代价是：Cost(new)=Cost(T)–W[1]depth(1)–W[k]depth(k)+W[1]depth(k)+W[k]depth(1)=Cost(T)–(W[1]–W[k])depth(1)+(W[1]-W[k])depth(k)=Cost(T)–(W[1]–W[k])[depth(1)-depth(k)]这里的depth(1)和depth(k)都是交换前的深度。因为W[1]<W[k]和depth(1)<depth(k)，所以有Cost(new)<Cost(T)，与T代表最佳焊接计划矛盾。所以代表W[1]的叶子在最底层。同理可证代表W[2]的叶子也在底层。(c) 因为有一个代表最佳焊接计划的二叉树T，其中代表最轻的二根钢管的叶子在最底层。不失一般性，设W[1]和W[2]为它们的重量。因为代表它们的叶子都在最底层，如果和W[1]的叶子共一个父亲的叶子不是W[2]而是W[k]的话，我们可以让代表W[2]的叶子代表W[k]而让代表W[k]的叶子代表W[2]。这样一来，W[1]和W[2]的叶子有同一个父结点。而且，因为这个交换是在同一层进行，总代价不变。现在，按照新的计划，最轻的二根钢管可以在第一步焊在一起。(d)从上面几个问题的答案可知，找一个最佳焊接计划和找一个哈夫曼编码的过程完全一样。故有下面的伪码。Least-Cost-Welding(W[1..n],c) //c是总代价ifn=1 thenreturn(c=0)endifConstructamin-heapHonW[1..n] //为W[1..n]构造最小堆，每个数对应一个结点fori¬1ton-1 x¬extract-min(H) //提取堆中最小数 y¬extract-min(H) //提取堆中第2小数 constructanodezwithtwochildren//构造有二个儿子的结点z left(z)¬x //以x为根(或叶子)的子树是z的左子树 right(z)¬y //以y为根(或叶子)的子树是z的右子树 W(z)¬W[x]+W[y] //x和y的重量和为z的重量insert(H,z) //将z插入堆中endforreturnH[1] //以H[1]为根的二叉树代表一个最佳焊接计划End算法的正确性由以上讨论已清楚。因为每次在最小堆上的操作需要O(lgn)时间，算法复杂度为O(nlgn)。作为例子，下面图中的二叉树是题目中例子的最佳焊接计划。考虑一个与上题不同的焊接问题。假设我们需要把n个钢管，a1,a2,…,an，焊成一根钢管。这些钢管的直径不同，分别是D[i](1£i£n)。假设焊接点的强度与被焊两根钢管直径的乘积成正比。为简单起见，就假定这焊点强度等于被焊两根钢管直径的乘积。显然，焊接完成后的钢管有(n-1)个焊点，而它的强度就等于这(n-1)个焊点中最薄弱的焊点强度。我们注意到，把钢管排成不同的顺序来焊会得到不同的强度。比如，4根钢管的直径分别是2，4，5，8。如果按这个顺序焊的话，三个焊点强度分别是24，45，和58。所以，焊好后的钢管强度是8。但如果焊接顺序是2，8，5，4，那么焊好后的钢管强度是min{28，85，54}=16。请设计一个O(nlgn)的贪心算法来确定一个最优的焊接顺序使焊好后的钢管强度最大。你需要证明算法的正确性。解：直覚告诉我们，焊接时应粗细钢管搭配着焊。如果二根粗的相邻，就一定会有二根细的相邻而造成薄弱的焊点。所以如果把直径D[i](1£i£n)排序的话，那么焊接顺序应该是A[1]，A[n]，A[2]，A[n-1]，A[3]，A[n-2]，…。我们将证明这个直觉是对的。下面是伪码。正确性证明随后。Largest-Strength-Welding(D[1..n],B[1..n]) //数组B给出最佳焊接顺序。SortD[1..n]suchthatD[1]≤D[2]≤…≤D[n]k=n/2fori=1tok B[2i-1]i //钢管序号放入数组B B[2i](n–i+1) endforifn>2k //n是奇数 then B[n]k+1 //D的中位数endifEnd正确性证明：首先，我们证明存在一个最优序列，其中A[1]在序列的头部或尾部。如果不是，那么A[1]在最优序列的中间。可假定最优序列是A[i],…,A[j],A[1],A[k],…。现在，如果我们把从A[i]到A[1]这段子序列，即A[i],…,A[j],A[1]，翻转一下的话，得到下面的新序列：A[1],A[j],…,A[i],A[k],…。因为D[1]D[i]，D[i]D[k]D[1]D[k]，按这个新序列焊接的钢管只会有更大的强度，不会削弱。所以我们可确定A[1]在最优序列的头部。下一步，我们证明在一个最优序列中，A[n]是在序列中的第二个钢管。假设最优序列是A[1],A[i],…,A[n],A[q],…，而A[i]A[n]，D[i]≤D[n]。那么，如果我们把从A[i]到A[n]这一段子序列翻转的话，我们会得到一个新的序列：A[1],A[n],…,A[i],A[q],….。因为D[1]D[n]D[1]D[i]，D[q]D[i]≥D[1]D[i]，这个新序列引入的两个新焊点的强度都不比原序列中第一个焊点弱。所以这个新序列也是最优的。这就证明了存在一个最优序列以A[1]，A[n]开头。我们观察到，因为对任何i>1，D[1]D[n]D[i]D[n]，所以无论那一根钢管排在A[n]后面，它和A[n]之间的焊点不会影响整个钢管的强度。所以，我们只要保证余下的(n-2)根钢管有最大强度即可。重复上面的推理，我们可知，在某个(n-2)根钢管的最优序列中，开头两钢管是A[2]，A[n-1]。这也就是说，原问题的一个最佳序列中A[1]，A[n]，A[2]，A[n-1]是开头的4项。显然，我们可以继续这样做下去，所以算法产生最优的焊接顺序。算法的主要时间化在排序，所以有O(nlgn)复杂度。假设我们开一部卡车从城市A到城市B，沿路经过一些苹果市场。城市A和城市B也有苹果市场。为方便起见，假定一共有n个市场，顺序编号为1到n，其中城市A的市场为第1号，城市B的市场为第n号。在每个市场i(1≤i≤n)，我们可以买苹果，买入价格已知为B[i](元/斤)，也可以卖苹果，卖出价为S[i]。我们希望在某个市场i买苹果，然后在某市场j卖掉，ji，使得赚的钱最多，即M=S[j]-B[i]最大。请设计一个O(n)的贪心算法找出这两个市场i和j并报告这个最大差价M=S[j]-B[i]。我们规定，车子只能向前开，不可以往回开。你可以在同一市场买和卖，但只能买一次和卖一次。如果这个最大差价是负数也给予报告，说明最少会亏多少。解：和第8题的思路一样，我们先找到小规模的解，然后逐步扩大。具体做法是，先考虑k=1的情况，即只能在市场1买和卖，然后考虑k=2的情况，即可以在市场1和2买和卖，随后再考虑k=3的情况，等等，直到找出k=n时的最优解。假设我们已找出k=i时的最优解，如何找k=i+1的最优解呢？我们只须考虑是否市场i+1可以带来更好的解。市场i+1可以提供的最好解是，在市场1到市场i+1中以最低价买入，以S[i+1]卖出，即d=S[i+1]–min{B[k]|1ki+1}。我们只要把d和k=i时的最优解比较一下就可以了。根据这个思路，在算k=i时的最佳解时，我们一方面要更新目前最好的解，另一方面还要更新目前为止{B[k]|1ki}中最小的数以便下一步使用。伪码如下。Max-Apple-Profit(B[1..n],S[1..n],M,i,j) MS[1]–B[1]ij1lowest1foru2ton ifB[u]<B[lowest] thenlowestu //更新最低买入价 endif ifS[u]–B[lowest]>M then MS[u]–B[lowest] //更新最好结果 ilowest ju endifendforreturn(M,i,j)上面算法显然有O(n)复杂度。*重新考虑上面第15题。假设我们做两次买卖，即在某个市场i1买苹果，然后在某市场j1i1卖掉，这是第一次买卖。然后，我们再在某市场i2j1买苹果和在市场j2i2卖掉。我们希望两次买卖的总收入最大，即M=(S[j1]-B[i1])+(S[j2]-B[i2])最大。我们规定，车子只能向前开，不可以往回开。你可以在同一市场买和卖，但只能最多买两次和卖两次。如果这个最大差价是负数也给予报告。请设计一个O(n)贪心算法解决这个问题。解：这个问题的关键是找出两次买卖的最佳分界点k，也就是说我们要决定市场k，使得第一次买卖在市场1到市场k之间进行，而第二次买卖在市场k到市场n之间进行的总结果最好。这似乎是动态规划问题，但不需用动态规划。让我们定义以下符号。L[k]表示在市场1到市场k之间进行一次买卖可得最大收益，R[k]表示在市场k到市场n之间进行一次买卖可得最大收益。那么，原问题的解是M=max1≤k≤n我们用类似上一题的贪心法，在O(n)时间内，算出所有L[k](1≤i≤n)。同样，在O(n)时间内，算出所有R[k](1≤i≤n)。那么M可在O(n)时间内得到。伪码如下。Max-Apple-Profit-Two-trade{B[1..n],S[1..n],M} L[0]-ij1lowest1fork1ton ifB[k]<B[lowest] thenlowestk //更新有最低买入价格的市场 endif ifS[k]–B[lowest]>L[k-1] then L[k]S[k]–B[lowest] L-Buy[k]lowest //市场1到k之间最佳买入点 L-Sell[k]k //市场1到k之间最佳卖出点 else L[k]L[k-1] L-Buy[k]L-Buy[k-1] L-Sell[k]L-Sell[k-1] endifendforR[n+1]- //从右向左算R[k]，初始化ijnhighestn //S[n]是当前最高卖出价forkndownto1 ifS[k]>S[highest] thenhighestk //更新最高卖出价市场 endif ifS[highest]–B[k]>R[k+1] then R[k]S[highest]–B[k] R-Buy[k]k //市场k到n之间最佳买入点 R-Sell[k]highest //市场k到n之间最佳卖出点 else R[k]R[k+1] R-Buy[k]R-Buy[k+1] R-Sell[k]R-Sell[k+1] endifendforM-fork1ton ifL[k]+R[k]>M then ML[k]+R[k] divide-pointk endifendforreturnM,L-Buy[divide-point],L-Sell[divide-point],R-Buy[divide-point],R-Sell[divide-point]End这个算法显然有O(n)复杂度。这个算法有动态规划的影子，但划入贪心法更合适，因为在计算L[k]和R[k]时，每一步只用到一个确定的子问题的解，不存在动态选择问题。考虑一个与第6章习题10有关的问题。如下图所示，两条平行线A和B上各有n个点，并且从左到右依次编号为1，2，3，…，n。另外，直线A上每个点和直线B上唯一的一个点有线段相连，反之亦然。设直线A上点i与直线B上点π(i)相连，那么这n个线段为(i,π(i))(1≤i≤n)。下图的例子中，我们有π(1)=3,π(2)=1,π(3)=6,π(4)=8,π(5)=2,π(6)=5,π(7)=4,π(8)=7。如果i<j但是π(i)>π(j)，那么线段(i,π(i))和(j,π(j))会相交，否则不相交。第6章习题10要求找出最大的一组互不相交的线段。本题的问题是要把这些线段分组使得在同一组里的线段互不相交。例如，在下图中，这8个线段可分为三组：{(1,3),(3,6),(4,8)}，{(2,1),(5,2),(6,5),(8,7)}，{(7,4)}。请设计一个O(n2)的贪行算法用最少的组数把这n个线段分组使得在同一组里的线段互不相交。(可改进为O(nlgn))解： 我们用贪心法顺序处理这n个线段。一开始，我们把(1,π(1))放入第一组。当我们处理(i,π(i))时，就顺序查看每一组，一旦找到一组，其线段都与(i,π(i))兼容(互不相交)，则把(i,π(i))放入该组。如果已建立的每一组中都有线段与(i,π(i))相交(不兼容)，那我们就新增加一组，把(i,π(i))放入该组，并顺序给这一组编号。注意，当我们检查某一组是否与(i,π(i))兼容时，我们只需要检查该组中最后一个放入的线段是否与(i,π(i))兼容即可，也就是有最大序号j或最大π(j)值的线段(j,π(j))。伪码如下，证明随后。Min-Number-of-Groups([1..n],k,S[1..k]) //输出k个组，S[1]到S[k]k1 //第一组组号S[1]{(1,[1])} //起始只有一个组S[1]，含线段(1,[1])maxpi[1]π(1) //maxpi[j]=max{π(p)|(p,π(p))S[j]}fori2ton //顺序检查每个线段 foundfalse //为(i,[i])找一可加入的集合 j1 while(found=false)andjk if[i]>maxpi[j] then found=true S[j]S[j]{(i,[i])} maxpi[j][i] else jj+1 endif endwhile iffound=false then kk+1 //只好为(i,[i])新建一个集合 S[k]{(i,[i])} maxpi[k][i] endifendforreturnk,S[1..k]End正确性证明：我们可假定，每个分组中的线段按序号顺序排列。我们对算法中的循环变量i用归纳法证明以下命题：存在一个最佳解，它对线段(1,[1]),(2,[2]),…,(i,[i])的分组与上面算法Min-Number-of-Groups的分组一样。归纳基础：当i=1时，只有一个线段。我们可以把最佳解中有线段(1,[1])的集合标为S[1]。命题显然正确。归纳步骤：假设存在一个最佳解M，它对线段(1,[1]),(2,[2]),…,(i-1,[i-1]),2in,的分组与上面算法的分组一样，分为k组。我们证明存在一个最佳解M*，它对线段(1,[1]),(2,[2]),…,(i-1,[i-1]),(i,[i])的分组与上面算法的分组一样。我们分3种情况分析：线段(i,[i])不能放入已有的k组中任何一组，因为每一组都有线段与(i,[i])相交([i]<maxpi[j]，j=1,2,…,k)。这种情况下，最佳解M也必须为(i,[i])新建一个集合。我们可以把该集合标为S[k+1]。命题得证。存在一个或几个集合与线段(i,[i])兼容。这种情况下，上面的算法找到最小的j，使(i,[i])与S[j]兼容，把(i,[i])放入S[j]。如果最佳解M也把(i,[i])放入S[j]，那么，最佳解M就是M*，它对线段(1,[1]),(2,[2]),…,(i-1,[i-1]),(i,[i])的分组与上面算法的分组一样。命题得证。如果最佳解M不把(i,[i])放入S[j]，而是放入S[u]中，u>j。那么，在刚要放(i,[i])时，必有maxpi[j]>maxpi[u]。原因如下：设maxpi[j]=[j’]，maxpi[u]=[u’]，(j’,[j’])和(u’,[u’])分别是S[j]和S[u]中最后一个线段。如果u’>j’，那么必有[u’]<[j’]，否则两线段兼容，根据算法，当我们处理(u’,[u’])时，应该把(u’,[u’])放入S[j]中或更前面的集合。如果u’<j’，那么也必有[u’]<[j’]，否则当我们处理(u’,[u’])时，(u’,[u’])必与S[j]中所有线段都不相交，应该放入S[j]中或更前面的集合。因此，必有maxpi[j]>maxpi[u]。让我们记M[j,i]=maxpi[j]，M[u,i]=maxpi[u]，表示这两个数是在我们处理(i,[i])时的值，并有M[j,i]>M[u,i]。因为最佳解M在(i,[i])之后放入集合S[j]中的任何线段(w,[w])，w>i，都必须有[w]>M[j,i]>M[u,i]。所以，在(i,[i])之后，最佳解M放入集合S[j]中的任何线段都与(i,[i])之前放入集合S[u]中的任何线段不相交。同时，最佳解M在(i,[i])之后放入集合S[u]中的任何线段(w,[w])，w>i，都必须有[w]>[i]>M[j,i]。所以，在(i,[i])之后放入集合S[u]中的任何线段(包括(i,[i]))都与(i,[i])之前放入集合S[j]中的任何线段不相交。我们可以把最佳解M中集合S[u]和集合S[j]中(i,[i])之后的线段(包括(i,[i]))进行交换。显然，交换后的集合S[j]和S[u]中的线段仍然不相交，并且集合的个数不变。因此，交换后得到的解M*也是最佳解，并且线段(i,[i])被放到S[j]中，命题得证。存在一个或几个集合与线段(i,[i])兼容（当然包括S[j]）但是最佳解M不把(i,[i])放入S[j]，而是放入新建的一个集合S[v]中，v>k。这种情况与(B)相似，我们可以把S[v]和集合S[j]中(i,[i])之后的线段(包括(i,[i]))进行交换得到解M*。归纳成功。所以，上面算法输出的分组数是最少的，算法的复杂度显然是O(n2)。注意，由上面证明中对情况(B)的討论知，算法运行的任何时刻都有maxpi[1]>maxpi[2]>…>maxpi[k]。所以用二元搜索可把算法复杂度改进为O(nlgn)。假设A[1]，A[2]，…，A[n]是n个数的一个序列，请设计一个O(n2)贪心算法把它分成最少的几个递增的子序列。这里，递增意味不减少，即递增序列中允许相等数字。例如，序列4，8，2，3，6，9，7可以分为两个子序列：<4，8，9>，<2，3，6，7>。显然这是最好的了。(可改进为O(nlgn))解：这题与上一题有相同本质，因为递增序列中的两个数字，A[i]和A[j]，如果i<j，那么必有A[i]A[j]。把A[i]视为[i]就变为上一题了。 伪码如下。Min-Number-of-Increasing-Subsequences(A[1..n],k,S[1..k]) //输出k个序列，S[1]到S[k]k1S[1,1]A[1] //起始只有一个序列S[1]，含A[1])last[1]1 //S[1]中有1个数fori2ton foundfalse //为A[i]找一个序列接上 j1 while(found=false)andjk ulast[j] //S[j]的最后一个数 ifA[i]S[j,u] then found=true S[j,u+1]A[i] //A[i]接在S[j]后面 last[j]u+1 //更新S[j]中数字个数 else jj+1 endif endwhile iffound=false then kk+1 //只好为A[i]新建一个序列 S[k,1]A[i] last[k]i endifendforreturnk,S[1..k]End*重新考虑第3章习题13中构造最小优先树的问题。给定一个n个数的序列，A[1]，A[2]，…，A[n]，用贪心法设计一个最坏情况O(n)的算法为这个序列构造出最小优先树。解：贪心法的思路是，先构造只有一个数的最小优先树，然后构造二个数的最小优先树，再构造三个数的最小优先树，等等。也就是说，每次在前面已构造好的最小优先树中插入一个新的数使其成为一个新的最小优先树。关键是，如何能快速地插入。假设我们已构造了序列A[1]，A[2]，…，A[i-1]的最小优先树。现在考虑如何插入A[i]。显然，如果我们对A[1]，A[2]，…，A[i-1]的最小优先树做中序遍历的话，内结点的顺序一定是A[1]，A[2]，…，A[i-1]。下面图(a)显示的是插入A[i]前的这个最小优先树，其中A[i-1]是最后一个内结点。它的右子树一定是个叶子，而左子树不一定。 如果我们顺着从A[i-1]到根这条路径走的话，数字会一个比一个小。当我们碰到一个结点的数a满足aA[i]时停下。假定结点a的右儿子是数字b，那么我们有aA[i]<b。这说明a小于等于序列中他右边的任何数，包括A[i]。所以，原来最小优先树中a左边的结构不需改变。但是，因为A[i]<b，所以，a的右儿子应该是A[i]而不是b。所以，我们第一步要做的是把a的右儿子改为A[i]。因为A[i]是序列中到A[i]为止的最后一个数，所以A[i]的右儿子是个叶子。而A[i]的左儿子应该是从结点a之后到A[i-1]为止这一段的最小优先树。这恰恰就是原先以b为根的子树。所以，插入A[i]的步骤如下：顺着从A[i-1]到根的路径找到第一个结点A[k]满足A[k]A[i]切下A[k]的右儿子R置A[k]的右儿子为A[i]置A[i]的左儿子为R置A[i]的右儿子为一片树叶。下面是伪码。复杂度分析随后。不难看出，当A[i]比根里的数字还小或比A[i-1]还大时，下面算法仍正确。Min-First-Tree(A[1..n],T)root¬A[1]left(root)¬nilright(root)¬nil //先为A[1]建二叉树，nil表示叶子，没有数字(root)¬nil //A[1]的父亲为空fori¬2ton //从A[2]开始，逐个插入这个二叉树 a¬A[i-1] whilea>A[i]andanil a¬[a] endwhile ifa=nil //A[i]比根里的数还小 then left(A[i])¬root //原来的树成了A[i]左儿子 (root)¬A[i] right(A[i])¬nil root¬A[i] //A[i]是新的根 (root)¬nil else b¬right(a) left(A[i])¬b (b)¬A[i] right(A[i])¬nil right(a)A[i] (A[i])¬a endifendforEnd现在来分析一下复杂度。当我们在插入A[i]时，我们沿着A[i-1]到根的路径走。如果我们经过了k次比较而在结点a处停下的话，那么在a之前比较过的k个数字都随着a的右子树被切去而永远不会再出现在将来被检查的路径上。假定在我们插入A[i]时作了n(i)次比较，那么总的比较次数是i=2nn(i)。因为我们在插入A[i]时要从这条被检查路径上永久除去n(i)–1个数，所以我们一共除去的数字有i=2n(ni=2n(ni-1)=i=2nn(i)-(n-1)n-1，也就是i=2nn(i)所以，总的比较次数是i=2nn(i)2(n-1)。由此，算法的复杂度是O(n设计一个复杂度为O(n)的算法来解第2章习题20。问题叙述如下。在序列A[1]，A[2]，…，A[n]中，如果一个数出现的次数k超过一半，即k>n/2，那么这个数称为垄断数(dominatingnumber)。如果序列有垄断数，则报告这个数及其出现次数k，否则报告k=0。规定，算法只能用比较序列中两数字是否相同来判断，比较不告诉谁大谁小，只告诉相同或不相同。其它数字间的比较无此限制。解：我们的策略是，把不同的数字配对，任何两个不同的数字都可以配。我们用集合S来保存当前还没有配上对子的数，起始为空。显然，集合S中的数有相同的数值。从A[1]开始，我们逐个扫描序列，A[1]，A[2]，…，A[i]，…。如果A[i]与集合S中的数不相等，则取集合S里一个数与A[i]配对。否则，则把A[i]放入集合S。一个有趣的观察是，如果序列有一个垄断数x，它一定出现在集合S中。这是因为没有足够的数可以与它配对。所以，如果有垄断数，唯一可能的数就是在集合S中的那个数x。我们只要再数一下序列中有多少个数等于x即可得解。管理集合S最方便的数据结构是堆栈。算法显然有复杂度O(n)。下面是伪码。Dominating-Number(A[1..n],u,k) //如果有，A[u]是垄断数，出现k次，否则u=0,k=0S //堆栈初始为空 fori1ton ifS= then Push(S,A[i]) //压A[i]进栈 ui else ifA[i]=A[u] thenPush(S,A[i]) elsePop(S) //A[i]与Top(S)配对，不需记录 endif endifendfor ifS then k0 fori1ton ifA[i]=A[u] then kk+1 endif endforendififk>n/2 thenreturnu,k elsereturn0,0endifEnd*改进7.5节中最佳加油计划问题的贪心算法使其复杂度为O(n)。解：7.5节中最佳加油站问题的贪心算法的复杂度取决于L。如果在L公里内最多有k个加油站，那么这个复杂度为O(kn)。这是因为在每个停靠站要检查最多k个油站的价格和距离，处理时间为O(k)。所以总的时间为O(kn)。这个算法可改进为，在k为任意变量时，复杂度仍为O(n)。关键的思路是，每个油站的价格和距离只检查一次以省去重复计算的时间。假设我们停靠在加油站i。我们看一下算法对两种情况的处理。在L公里内，加油站k是第一个加油站满足P[k]<P[i]。那么，我们在当前加油站i加入正好能跑到加油站k的油。下一个停靠站是k。在L公里内任一加油站价格都大于等于P[i]。这种情况下，找出最远的一个价格最低的加油站k。这时，应把油箱加满，并且下一站应停在加油站k。如果