【正文】 ，使所需的總比較次數(shù)最多。 原理分析 這個程序比較適合用堆，最優(yōu)用最小堆，最差用最大堆；以最優(yōu)合并為例：（1）使用各序列的長度建堆； （2）兩個最小的元素出堆，計算這兩序列合并需要的比較次數(shù)，該次數(shù)入堆； （3）重復(fù)（2），直到堆只剩下一個元素； 最后剩下的元素即為題目的解。 算法時間復(fù)雜度分析復(fù)雜度為O(nlogn)，排序后，最小的兩個序列是前兩個，計算最小的兩個序列的合并次數(shù)后，該次數(shù)不一定是新的最小的兩個序列之一，所以在下一次合并前，必需使數(shù)組仍舊有序，讓最小的兩個序列在數(shù)組的最前面，為使數(shù)組重新有序，可以使用類似插入排序的插入過程，將新得到的數(shù)字直接插入到數(shù)組，這樣不需要額外的儲存空間，但總復(fù)雜度是O(n2)，考慮到需要計算最優(yōu)與最差，實際上也必須需要額外的O(n)的空間來保存排序后的結(jié)果，如果將排序后的數(shù)組按照順序作成一個鏈表，那么鏈表的最前的兩節(jié)點就是最小的兩序列，計算合并次數(shù)，刪除該兩節(jié)點，將新得到的次數(shù)插入到鏈表，注意到，后面需要插入的數(shù)字肯定比前面插入的數(shù)字大，所以從上一次插入的位置之后查找新的插入位置，這樣插入數(shù)字的總的時間復(fù)雜度是O(n)的，總的時間復(fù)雜度仍舊是O(nlogn)，并使用了額外的O(n)的空間。第8章 會場安排問題 問題的提出假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計一個有效的貪心算法進(jìn)行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點，不相容活動間用邊相連。使相鄰頂點著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會場數(shù)。) 數(shù)據(jù)輸入：。第一行有1個正整數(shù)k，表示有k個待安排的活動。接下來的k行中，每行有2個正整數(shù)，分別表示k個待安排的活動開始時間和結(jié)束時間。時間以0點開始的分鐘計。結(jié)果輸出：。輸入文件示例輸出文件示例 5 3 1 23 12 28 25 35 27 80 36 50 編碼分析根據(jù)會場安排問題的定義，首先將問題簡化為：找出兩個活動，若ei和ej滿足si≥fj或sj≥fi，則稱這兩個活動相容，即問題轉(zhuǎn)化為：要求找出最多相容會場集合A。問題簡化為對相容會場A的尋找，下面用貪心方法分析過程，根據(jù)題意，選取一種量度標(biāo)準(zhǔn)，然后按量度標(biāo)準(zhǔn)對n個輸入排序，按順序一次輸入一個量。如果這個輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法就是貪心方法。那么問題轉(zhuǎn)化為對度量標(biāo)準(zhǔn)的尋找，判斷各個數(shù)據(jù)是否可以包含在解向量中去，然后根據(jù)目標(biāo)函數(shù)來選擇最優(yōu)解。 貪心算法（1）將所有活動按結(jié)束時間排序，得到活動集合E={e1，e2，…，en}；（2）先將e1選入結(jié)果集合A中，即A={e1}；（3）依次掃描每一個活動ei：如果ei的開始時間晚于最后一個選入A的活動ej的結(jié)束時間，則將ei選入A中，否則放棄ei。 最優(yōu)解證明若E={e1，e2…en}是按結(jié)束時間排序的活動集合，則e1具有最早的結(jié)束時間，設(shè)存在一個最優(yōu)安排A不包含e1，并以ei開始，則易見：A{ei}∪{e1}也是最優(yōu)的活動安排；依此類推，即可推出上述活動都為A中的不相容最優(yōu)活動。俗話所的好的：紙上得來終覺淺，絕知此事要躬行！那么讓我們舉個例子來進(jìn)一步清晰化問題：下面表格有12個活動，并給出各個活動的開始時間與結(jié)束時間，那么請用上述貪心解法分析并求解最優(yōu)會場數(shù)目。如表81所示。Table 81 The ploy in assembly room arrange table表81 會場活動安排表活動i1234567891011開始時間s（i）130535688212結(jié)束時間E（i）4567891011121314（1）根據(jù)貪心策略：現(xiàn)將1～12個活動的結(jié)束時間排序（為解說方便上表格已經(jīng)排好）排序可用快速排序。（2）毋庸置疑將E1先分配入會場集合A1，然后按照順序找出下個活動，使得其開始時間小于E1的結(jié)束時間（即滿足時間不沖突），如圖易知為E4，再將E4分配給A1，以后每一步驟都重復(fù)如E4的選擇。經(jīng)過第一輪的篩選可知會場集合A1中包含：A1={E1，E4，E8，E11}。（3）此時已經(jīng)沒有活動在相容于會場A1中，那么再繼續(xù)對A2進(jìn)行同樣的選取，同理：A2={E2，E6} A3={E3，E7} A4={E5，E9} A5={E10}。（4）那么得出總的會場數(shù)目：S=5。 算法時間復(fù)雜度分析算法的時間復(fù)雜度為O（n）。第9章 貪心算法的C++實現(xiàn) C++語言概述據(jù)統(tǒng)計，目前世界上支持面向?qū)ο蟪绦蛟O(shè)計的語言已近百種，除了大多數(shù)是供研究用的非商業(yè)軟件外，具有強大競爭力OOP語言也很多，其中一類是以Smalltalk和EIFFEL語言為代表的新的面向?qū)ο笳Z言。它們以其全新的語言規(guī)范和與開發(fā)工具緊密結(jié)合的編程機制為特征，特別是Smalltalk作為第一個面向?qū)ο笳Z言在程序設(shè)計領(lǐng)域的影響非常巨大。另一類則是傳統(tǒng)的重要編程語言向面向?qū)ο蟪绦蛟O(shè)計靠攏的結(jié)果，除了C++語言之外，幾乎所有成功的語言，包括Pascal語言、Ada語言、C語言和Fortran語言，都發(fā)展了它們自己的面向?qū)ο蟮男掳姹?，其中常見的有Ada9Borland開發(fā)的Turbo 、ObjectC、Forth等。C++語言最初被稱為“帶類的C”（C with Class）也應(yīng)屬于此類。這種情形在結(jié)構(gòu)程序設(shè)計時期也曾出現(xiàn)，一些傳統(tǒng)的編程語言如Fortran、BASIC語言都開發(fā)了結(jié)構(gòu)化的新版本，不過其影響還是沒有超過Pascal和C語言。在這樣的面向?qū)ο蟮摹罢Z言之林”中，C++語言能夠獲得成功，應(yīng)該說不是偶然的。在程序設(shè)計語言的歷史上，在所有比較成功的高級語言中，C++語言有著不少與眾不同的地方，它的這些特點既是人們愿意選擇它的原因，主要有：（1）C++語言是支持面向?qū)ο蟪绦蛟O(shè)計的最主要的代表語言之一。C++語言包括了幾乎所有的支持OOP的語法特征，基本上反映了20世紀(jì)80年代到90年代以來的所有程序設(shè)計和軟件開發(fā)的新思想和新技術(shù)。其中包括：1）封裝和信息隱藏。把數(shù)據(jù)和對數(shù)據(jù)的操作一起封裝到類和對象之中。2）抽象數(shù)據(jù)類型。一種新的類的定義就是一種新的抽象數(shù)據(jù)類型，經(jīng)可以用在不同的程序系統(tǒng)之中。3）以繼承和派生的方式實現(xiàn)程序的重用機制，為程序的重用找到了一種可靠而方便的方式。4）通過函數(shù)與運算符的重載和派生類中虛函數(shù)的多重定義，實現(xiàn)多種情形下的多態(tài)特征，明顯提高了程序的水平。5）通過模板等特征實現(xiàn)了類型和函數(shù)定義的參數(shù)化，把抽象又提升了一級。（2）C++語言是程序員和軟件開發(fā)者在實現(xiàn)中創(chuàng)造的，無論是語言的各個特征還是整個研制過程，都體現(xiàn)了面向?qū)嵱?，面向軟件開發(fā)者的思想。鑒于該語言有這么優(yōu)秀的特點，該論文選擇C++為編程語言。 具體實現(xiàn)步驟 哈夫曼算法的實現(xiàn)通過第三章對哈夫曼問題的分析，可以得出哈夫曼算法思路為：（1）以n個字母為結(jié)點構(gòu)成n棵僅含一個點的二叉樹集合，字母的頻率即為結(jié)點的權(quán)。（2）每次從二叉樹集合中找出兩個權(quán)最小者合并為一棵二叉樹：增加一個根結(jié)點將這兩棵樹作為左右子樹。新樹的權(quán)為兩棵子樹的權(quán)之和。（3）反復(fù)進(jìn)行步驟（2）直到只剩一棵樹為止。abcdef623349abcdef6233495abcdef62334957abcdef623349571111abcdef6233495711111611a)b)c)d)e)Fig. Huffman tree 哈夫曼樹哈夫曼樹的算法：templateclass TBinaryTreeintHuffmanTree(T f[]， int n){//根據(jù)權(quán)f[1:n]構(gòu)造霍夫曼樹//創(chuàng)建一個單節(jié)點樹的數(shù)組Huffman T*W=newHuffmanT [n+1]；BinaryTreeint z，zero；for(int i=1；i=n；i++){(i， zero， zero)；W[i].weight=f[i]；W[i].tree=z； }//數(shù)組變成—個最小堆MinHeapHuffmanTQ(1)；(w，n，n)；//將堆中的樹不斷合并HuffmanT x,yfor(i=1。in。i++){(x)；(y)；(0, , )；+=；=z(x)； }Q. DeleteMin(x)；//最后的樹Q. Deactivate()；delete[]w；return ；算法分析HuffmanTree初始化優(yōu)先隊列Q需要O(n)。DeleteMin和Insert需O(logn)。n1次的合并總共需要O(nlogn)。所以n個字符的哈夫曼算法的計算時間為O(nlogn)。 單源最短路徑問題問題：給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是一個非負(fù)實數(shù)。要計算從V的一點v0(源)到所有其他各頂點的最短路長度。路長指路上各邊權(quán)之和。算法思路(Dijkstra)：設(shè)最短路長已知的終點集合為S，初始時v0∈S，其最短路長為0，然后用貪心選擇逐步擴充S：每次在VS中，選擇路徑長度值最小的一條最短路徑的終點x加入S。構(gòu)造路長最短的最短路徑：設(shè)已構(gòu)造i條最短路徑，則下一個加入S的終點u必是VS中具有最小路徑長度的終點，其長度或者是弧(v0，u)，或者是中間只經(jīng)過S中的頂點而最后到達(dá)頂點u的路徑。算法描述：(1)用帶權(quán)的鄰接矩陣c來表示帶權(quán)有向圖，c[i][j]表示弧vi，v上的權(quán)值。若vi，vj∈V，則置c[i][j]為∞。設(shè)S為已知最短路徑的終點的集合，它的初始狀態(tài)為空集。從源點v到圖上其余各點vi的當(dāng)前最短路徑長度的初值為：dist[i]=c[v][i] vi∈V(2)選擇vj，使得dist[j]=Min{dist[i]|vi∈VS}，vj就是長度最短的最短路徑的終點。令S=SU{j}。(3)修改從v到集合VS上任一頂點vk的當(dāng)前最短路徑長度：如果dist[j]+c[j][k]dist[k]則修改dist[K]=dist[j]+c[j][k]。(4)重復(fù)操作(2)，(3)共n1次。voidDijkstra(int n, intv,Type dist[], int prev[], Type **c){ bool s[maxint]；for (int i=1。i=n。 i++){dist[i]=c[v][i]；s[i]=false；if(dist[i]= =maxint) prev[i]=0else prev[i]=v 。 }dist[v]=0；s[v]=true；for (int i=1。in；i++){int temp=maxint；int u= v；for (int j= 1；j=n；j++)if ((!s[j])amp。amp。(dist[j]temp)){u=j；temp=dist[j]；}s[u]=true；for (int j=1；j=n。j++) ；if((!s[j])＆＆(c[u][j]maxint)){Type newdist=dist[u)+c[u][j]if (newdistdist[j]){dist[]]=newdist； prev[j]=u。 }}}}算法分析用帶權(quán)鄰接矩陣表示有n個頂點和e條邊的帶權(quán)有向圖，主循環(huán)體需要O(n)時間，循環(huán)需要執(zhí)行n1次，所以完成循環(huán)需要O(n2)。 刪數(shù)問題通過第五章對刪數(shù)問題的分析，可以得出刪數(shù)算法的思路為：（1）x1x2…xixj；（2）如果xkxj，則刪去xj，即得到一個新的數(shù)且這個數(shù)為n一1位中為最小的數(shù)Nl，可表示為x1x2…xixkxm…xn。（3）對N1而言，即刪去了1位數(shù)后，原問題T變成了需對n1位數(shù)刪去k1個數(shù)新問題T’。（4）新問題和原問題相同，只是問題規(guī)模由n減小為n1，刪去的數(shù)字個數(shù)由k減少為k1。（5）基于此種刪除策略，對新問題T’，選擇最近下降點的數(shù)進(jìn)行刪除，如此進(jìn)行下去，直至刪去k個數(shù)為止。算法分析：時間復(fù)雜性為O(n)，空間復(fù)雜性為O(n)。 會場安排問題通過第八章對會場安排問題的分析，可以得出解會場安排問題的思路為：（1）n個活動開始和結(jié)束時間分別是s[i]和f[i]，而且f[1]f[2]…f[n]（2）把n個活動時間看做直線上n個半閉區(qū)間，s[i]和f[i]和組成2n個有序數(shù)組。Count用于會場數(shù)使用的最大數(shù)，遍歷數(shù)組，統(tǒng)計區(qū)間的最大的重疊數(shù)目。遇到s[i]，一種活動進(jìn)棧（相當(dāng)于要安排一個會場），比較當(dāng)前的會場使用數(shù)是否是最大。遇到f[i]，一種活動出棧（相當(dāng)于一個會場用完，可以作為其他活動用），直到遇到最后一個活動的開始時間，把所有的活動都安排好，結(jié)束遍歷。注：這里的stack只是作為統(tǒng)計最大的重疊數(shù)目用，如果要真的模擬使用情況，用queue模擬響應(yīng)的活動安排好。算法復(fù)雜度為O（nlogn）。具體應(yīng)用核心代碼見附錄，、。Fig. Huffman code after debug to resultFig. Dijkstra debug 單源最短路徑問題的調(diào)試Fig. Delete data problem debug