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