算法設(shè)計題目

1、第2章1、大整數(shù)乘法的O(nmlog(3/2)算法 給定2個大整數(shù)u和v，它們分別有m位和n位數(shù)字，且mn。用通常的乘法求uv的值須要O(mn)時間。可以u和v均看作是有n位數(shù)字的大整數(shù)，用教材第2章介紹的分治法，在O(nlog3)時間內(nèi)計算uv的值。當(dāng)m比n小得多時，用這種方法就顯得效率不夠高。試設(shè)計一個算法，在上述狀況下用O(nmlog(3/2)時間求出uv的值。2、O(1)空間子數(shù)組換位算法設(shè)a0:n-1是一個有n個元素的數(shù)組，k(1kn-1)是一個非負(fù)整數(shù)。試設(shè)計一個算法將子數(shù)組a0:k-1和ak+1:n-1換位。要求算法在最壞狀況下耗時O(n)，且只用到O(1)的協(xié)助空間。3、段合并

2、排序算法 假如在合并排序算法的分割步驟中，將數(shù)組a0:n-1劃分為個子數(shù)組，每個子數(shù)組中有O()個元素。然后遞歸地對分割后的子數(shù)組進(jìn)行排序，最終將所得到的個排好序的子數(shù)組合并成所要的排好序的數(shù)組a0:n-1。設(shè)計一個實現(xiàn)上述策略的合并排序算法，并分析算法的計算困難性。4、合并排序算法對撥給元素存儲于數(shù)組和存儲于鏈表中的2種情形，寫出合并排序算法。5、非增序快速排序算法如何修改QuickSort才能使其將輸入元素按非增序排序？第三章1、整數(shù)線性規(guī)劃問題考慮下面的整數(shù)線性規(guī)劃問題試設(shè)計一個解此問題的動態(tài)規(guī)劃算法，并分析算法的計算困難性。2、Ackermann函數(shù)Ackermann函數(shù)A(m,n)可

3、遞歸地定義如下：A（m，n）=試設(shè)計一個計算A(m,n)的動態(tài)規(guī)劃算法，該算法只占用O(m)空間。3、獨立任務(wù)最優(yōu)調(diào)試問題問題描述：用2臺機(jī)A和B處理n個作業(yè)。設(shè)第i個作業(yè)交給機(jī)器A處理時須要時間ai，若由機(jī)器B來處理，則須要時間bi。由于各作業(yè)的選戰(zhàn)和機(jī)器的性能關(guān)系，很可能對于某些i，有aibi，而對于某些j，ji，有aibj。既不能將一個作業(yè)分開由2臺機(jī)器處理，也沒有一臺機(jī)器能同時處理2個作業(yè)。設(shè)計一個動態(tài)規(guī)劃算法，使得這2臺機(jī)器處理完這n個作業(yè)的時間最短（從任何一臺機(jī)器開工到最終一臺機(jī)器停工的總時間）。探討一個實例：（a1，a2，a3，a4，a5，a6）=（2，5，7，10，5，2）；（

4、b1，b2，b3，b4，b5，b6）=（3，8，4，11，3，4）。算法設(shè)計：對于給定的2臺處理機(jī)A和B處理n個作業(yè)，找出一個最優(yōu)調(diào)試方案，使2臺機(jī)器焉得完這n個作業(yè)的時間最短。數(shù)據(jù)輸入：由文件input.txt供應(yīng)輸入數(shù)據(jù)。文件的第1行是1個正整數(shù)n，表示要處理n個作業(yè)。在接下來的2行中，每行有n個正整數(shù)，分別表示處理機(jī)A和處理機(jī)B處理第i個作業(yè)須要的處理時間。結(jié)果輸出：將計算出的最短處理時間輸出到文件output.txt。輸入文件示例輸出文件示例input.txtoutput.txt6152 5 7 10 5 23 8 4 11 3 44、三角形問題問題描述：給定一個由n行數(shù)字組成的數(shù)字三

5、角形，如下圖所示。試設(shè)計一個算法，計算出從三角形的頂究竟的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。738810274445265編程任務(wù)：對于給定的由n行數(shù)字組成的數(shù)字三角形，編程計算從三角形的頂究竟的路徑經(jīng)過的數(shù)字和的最大值。數(shù)據(jù)輸入：由文件input.txt供應(yīng)輸入數(shù)據(jù)。文件的第1行是數(shù)字三角形的行數(shù)n，1n100。接下來n行是數(shù)字三角形各行中的數(shù)字。全部數(shù)字在099之間。結(jié)果輸出：程序運行結(jié)束時，將計算結(jié)果輸出到文件output.txt中。文件第1行中的數(shù)是計算出的最大值。輸入文件示例輸出文件示例Input.txtoutput.txt53073 88 1 02 7 4 44 5 2 6 5

6、5、租用游艇問題問題描述：長江游艇俱樂部在長江上設(shè)置了n個游艇出租站1，2，n。游客可在游艇站租用游艇，并在下游的任何一個游艇站歸還游艇。游艇站i到游艇出租站j之間的租金為r(i,j)，1ijn。試設(shè)計一個算法，計算出從游艇出租站1到游艇出租站n所需的最少租金。編程任務(wù)：對于給定的游艇出租站i到游艇出租站j之間的租金為r(i,j)，1ijn，編程計算從游艇出租站1到游艇出租站n所需的最少租金。數(shù)據(jù)輸入：由文件input.txt供應(yīng)輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n200），表示有n個游艇出租站。接下來的n-1行是r(i,j)，1ijn。結(jié)果輸出：程序運行結(jié)束時，將計算出的從游艇出租站1

7、到游艇出租站n所需的最少租金輸出到文件output.txt中。輸入文件示例輸出文件示例input.txtoutput.txt3125 157第四章1、刪數(shù)問題問題描述：給定n位正整數(shù)a，去掉其中隨意kn個數(shù)字后，剩下的數(shù)字按原次序排列組成一個新的正整數(shù)。對于給定的n位正整數(shù)a和正整數(shù)k，設(shè)計一個算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。編程任務(wù)：對于給定的正整數(shù)a，編程計算刪去k個數(shù)字后得到的最小數(shù)。數(shù)據(jù)輸入：由文件input.txt供應(yīng)輸入數(shù)據(jù)。文件的第1行是1個正整數(shù)a。第2行是正整數(shù)k。結(jié)果輸出：程序運行結(jié)束時，將計算出的最小數(shù)輸出到文件output.txt。輸入文件示例輸出文件示例In

8、put.txtoutput.txt1785431342、套匯問題問題描述：套匯是指利用貨幣兌換率的差異將一個單位的某種貨幣轉(zhuǎn)換為大于一個單位的同種貨幣。例如，嘉定1美元可以買0.7英鎊，1英鎊可以買9.5法郎，且1法郎可以買到0.16美元。通過貨幣兌換，一個商人可以從1美元起先買入，得到0.79.50.16=1.064美元，從而獲得6.4%的利潤。編程任務(wù)：給定n種貨幣c1，c2，cn的有關(guān)兌換率，試設(shè)計一個有效算法，用以確定是否存在套匯的可能性。數(shù)據(jù)輸入：由文件input，txt供應(yīng)輸入數(shù)據(jù)。文件含多個測試數(shù)據(jù)項，每個測試數(shù)據(jù)項的第1行中只有個整數(shù)n（1n30），表示貨幣總數(shù)。其后n行給出n

9、種貨幣的名稱。接下來的一行中有1個整數(shù)m，表示有m種不同的貨幣兌換率，其后m行給出m種不同的貨幣兌換率，每行有3個數(shù)據(jù)項ci，rij和cj，表示貨幣ci和cj的兌換率為rij。文件最終以數(shù)字0結(jié)束。結(jié)果輸出：程序運行結(jié)束時，對每個測試數(shù)據(jù)項j，假如存在套匯的可能性則輸出 “case j yes”,否則輸出“case j no”。全部結(jié)果輸出到文件output.txt。 輸入文件示例 輸出文件示例 Input.txt output.txt 3 case 1 yes USDollar case 2 no BritishPound FrenchFranc 3 USDollar 0.5 British

10、Pound BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar 03、磁帶最大利用率問題問題描述：設(shè)有n個程序1,2，n要存放在長度為L的磁帶上。程序i存放在磁帶上的長度是li，1in。程序存儲問題要求確定這n個程序在磁帶上的一個存儲方案，使得能夠在磁帶上存儲盡可能多的程序。在保證存儲最多程序的前提下還要求磁帶的利用率達(dá)到最大。編程任務(wù)：對于給定的n個程序放在磁帶上的長度，編程計算磁帶上最多可以存儲的程序數(shù)和占用磁帶的長度。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行是2個正整數(shù)，分別表示文件個數(shù)n和磁帶的長度L。家下來的1

11、行中，有n個正整數(shù)，表示程序存放在磁帶上的長度。結(jié)果輸出：將編程計算出的最多可以存儲的程序數(shù)和占用磁帶上的每個程序的長度輸出到文件output.txt。第1行輸出最多可以存儲的程序數(shù)和占用磁帶的長度；第2行輸出存放在磁帶上的每個程序的長度。 輸入文件示例 輸出文件示例 input.txt output.txt 9 50 5 49 2 3 13 8 80 20 21 22 23 2 3 13 8 234、多元Huffman編碼問題問題描述：在一個操場的四周擺放著n堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次至少選2堆最多選k堆石子合并成新的一堆，合并的費用為新的一堆的石子數(shù)。試設(shè)計一個算法，計

12、算出將n堆石子合并成一堆的最大總費用和最小總費用。編程任務(wù)：對于給定的n堆石子，編程計算合并成一堆的最大總費用和最小總費用。數(shù)據(jù)輸入：由文件input.txt供應(yīng)輸入數(shù)據(jù)。文件的第1行有2個正整數(shù)n和k，表示有n堆石子，每次至少選2堆最多選k堆石子合并。第2行有n個數(shù)，分別表示每堆石子的個數(shù)。結(jié)果輸出：程序運行結(jié)束時，將計算的最大總費用和最小總費用輸出到output.txt。 輸入文件示例 輸出文件示例 input.txt output.txt 7 3 593 199 45 13 12 16 9 5 22 5、最優(yōu)分解問題問題描述：設(shè)n是一個正整數(shù)?，F(xiàn)在要求將n分解為若干互不相同的自然數(shù)的和，

13、且使這些自然數(shù)的乘積最大。編程任務(wù):對于給定的正整數(shù)n，編程計算最優(yōu)分解方案。數(shù)據(jù)輸入：由文件input.txt供應(yīng)輸入數(shù)據(jù)。文件的第1行是正整數(shù)n。結(jié)果輸出：程序運行結(jié)束時，將計算出的最大乘積輸出到文件output.txt。 輸入文件示例 輸出文件示例 input.txt output.txt 10 30第五章1、最小重量機(jī)器設(shè)計問題問題描述：設(shè)某一機(jī)器由n個部件組成，每一種部件都可以從m個不同的供應(yīng)商處購得。高wij是從供應(yīng)商j處購得的部件i的重量，cij是相應(yīng)的價格。試設(shè)計一個算法，給出總價格不超過c的最小重量機(jī)器設(shè)計。編程任務(wù)：對于給定的機(jī)器部件重量和機(jī)器部件價格，編程計算總價格不超過

14、d的最小重量機(jī)器設(shè)計。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有3個正整數(shù)n，m和d。接正業(yè)的2n行，每行n個數(shù)。前n行是c，后n行是w。結(jié)果輸出：將計算出的最小重量，以及每個部件的供應(yīng)商輸出到文件output.txt。輸入文件示例輸出文件示例input.txtoutput.txt3 3 441 2 31 3 13 2 12 2 22、運動員最佳配對問題問題描述：羽毛球有男女運動員各n人。給定2個nn矩陣P和Q。Pij是男運動員i和女運動員j配對組成混合雙打的男運動員競賽優(yōu)勢；Qij是女運動員i和男運動員j協(xié)作的女運動員競賽優(yōu)勢。由于技術(shù)協(xié)作和心理狀態(tài)等各種因素影響，Pij不肯定

15、等于Qji。男運動員i和女運動員j配對組成混合雙打的男女雙方競賽優(yōu)勢為Pij*Qji。設(shè)計一個算法，計算男女運動員最佳配對法，使各組男女雙方競賽優(yōu)勢的總和達(dá)到最大。編程任務(wù)：設(shè)計一個算法，對于給定的男女運動員競賽優(yōu)勢，計算男女運動員最佳配對法，使各組男女雙方競賽優(yōu)勢的總和達(dá)到最大。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有1個正整數(shù)n（1n20）。接下來的2n行，每行n個數(shù)。前n行是p，后n行是q。結(jié)果輸出：將計算出的男女雙方競賽優(yōu)勢的總和的最大值輸出到文件output.txt。輸入文件示例輸出文件示例Input.txtoutput.txt35210 2 32 3 43 4 52

16、 2 23 5 34 5 13、無和集問題問題描述：設(shè)S是正整數(shù)集合。S是一個無和集當(dāng)且僅當(dāng)x,yS蘊含x+yS。對于隨意正整數(shù)k，假如可將1，2，k劃分為n個無和子集S1，S2，Sn，則稱正整數(shù)k是n可分的。記F(n)=maxk|k是n可分的。試設(shè)計一個算法，對隨意給定的n，計算F(n)的值。編程任務(wù)：對隨意給定的n，編程計算F(n)的值。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有1個正整數(shù)n。結(jié)果輸出：將計算出的F(n)的值以及1，2，F(xiàn)(n)的一個n劃分輸出到文件output.txt。文件的第1行是F(n)的值。接下來的n行，每行是一個無和子集Si。輸入文件示例輸出文件示例

17、input.txtoutput.txt281 2 4 83 5 6 74、整數(shù)變換問題問題描述：關(guān)于整數(shù)i的變換f和g定義如下：f(i)=3i；g(i)= i/2。試設(shè)計一個算法，對于給定的2個整數(shù)n和m，用最少的f和g變換次數(shù)將n變換為m。例如，可以將整數(shù)15用4次變換將它變換為整數(shù)4：4=gfgg(15)。當(dāng)整數(shù)n不行能變換為整數(shù)m時，算法應(yīng)如何處理？編程任務(wù)：對隨意給定的整數(shù)n和m，編程計算將整數(shù)n變換為整數(shù)m所須要的最少變換次數(shù)。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行有2個正整數(shù)n和m。結(jié)果輸出：將計算出的最少變換次數(shù)以及相應(yīng)的變換序列輸出到文件output.txt。文

18、件的第一行是最少變換次數(shù)。文件的第2行是相應(yīng)的變換序列。輸入文件示例輸出文件示例input.txtoutput.txt15 44gfgg5、布線問題問題描述：假設(shè)要將一組元件安裝在一塊線路板上，為此須要設(shè)計線路板布線方案。各元件的連線數(shù)由連線矩陣conn給出。元件i和元件j之間的連線數(shù)為conn(i,j)。假如將元件i安裝在線路板上位置r處，而將元件j安裝在線路板上位置s處，則元件i和元件j之間的距離為dist(r,s)。確定了所給的n個元件的安裝位置，就確定了一個布線方案。和此布線方案相應(yīng)的布線成本為。試設(shè)計一個算法找出所給n個元件的布線成本最小的布線方案。編程任務(wù)：設(shè)計一個算法，對于給定的n個元件，計算最佳布線方案，使布線費用達(dá)到最小。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行有1個正整數(shù)n（1n20）。接下來的n-1行，每行n-i個數(shù)，表示元件i和元件j之間連線數(shù)，1ij20。結(jié)果輸出：將計算出的最小布線費用以及相應(yīng)的最佳布線方案輸出到文件output.txt。輸入文件示例輸出文件示例input.txtoutput.txt3102 31 3 23第六章1、0-1背包問題的棧式分支限界法棧式分支限界法將活結(jié)點表以后進(jìn)先出(LIFO)的方式存儲于一個棧中。試設(shè)計一個解0-1背