算法設計與分析自學指導書

1、算法設計與分析自學指導書習題一、填空題：1、按照漸近階從低到高的順序排列下列表達式：20n，4n2，logn，3n，2，n2/3，n!，2n。_2、分治法的基本思想是將一個規(guī)模為n的問題分解為與原問題_（相同/不相同）的k個規(guī)模較小且_（互相獨立/相關）的子問題。3、一個直接或間接地調用自身的算法稱為_，它有兩個條件，一個是要直接或間接地調用自身，另一個是必須有_。4、在一個n×n（n=2k）個方格組成的特殊棋盤中，需要_個l型骨牌完成棋盤覆蓋。5、在循環(huán)賽日程表問題中，若給定的運動員數n=2k-1，則至少需要_天完成比賽；n=2k時，則需要_天。其中，k為自然數。6、動態(tài)規(guī)劃算法的

2、主要步驟包括刻畫最優(yōu)解的性質和結構、遞歸定義最優(yōu)值、以自底向上的方式計算最優(yōu)值、根據計算最優(yōu)值的相關信息構造最優(yōu)解，在分析了最優(yōu)解的性質和結構之后，一個比較至關重要的步驟是給出最優(yōu)值的遞歸定義，請給出下面幾個問題的最優(yōu)值的遞歸定義：（1） 矩陣連乘積問題中，ai：j連乘所需的最少乘法次數定義為mi，j（1ijn），mi，j的初始值定義為0（i=j），則mi，j遞歸定義為：mi，j=_（2） 最長公共子序列問題中，ci，j表示序列xi和yj的最長公共子序列的長度，則ci，j可遞歸定義為：7、在使用回溯法考慮求解一個具體問題時，往往需要設計出約束條件和限界條件。裝載問題的約束條件是_；限界條件是b

3、estw>cw+r，其中，bestw是當前最優(yōu)值，cw=_，r=_。8、0-1背包問題的回溯法和分支限接法求界中都涉及到活結點的上界函數uprofit的計算問題，它是由兩部分組成，一是該活結點已經獲得的價值之和profit，另一個則是剩余未考慮物品的價值上界rprofit，這個值可通過_獲得。二、求解題：1、請用快速排序法升序排序下面實例，給出每一趟排序的結果。（3，20，5，9，2，30，25，18，16，3）2、已知元素a，b，h依次有概率0.1，0.2，0.05，0.1，0.3，0.05，0.15，0.05，其余情況的概率為0，請建立其最優(yōu)二叉搜索樹。123456799854758

4、46653、用動態(tài)規(guī)劃算法求下面網絡的最短路：4、求解如下遞歸式，已知t(1)=1，a、b、c均為常數且a=b=c=1。（1）t(n)=at(n-1)+bn（2）t(n)=at(n/2)+bnc5、有0-1背包問題如下：n=6，c=20，p=（11，8，15，18，12，6），w=（5，3，2，10，4，2）。試分別畫出用回溯法或優(yōu)先隊列式分支限界法求解時的搜索情況。1234557213231446、有如下城市網絡圖：試分別畫出用回溯法或優(yōu)先隊列式分支限界法求解時的搜索情況。三、證明題：1、若t(n2/2r)=nt(n)+bn2（其中r=0，t(2)=2）則t(n)=o(n(logn)rlog

5、logn)。2、試證明流水作業(yè)調度問題的johnson算法是滿足johnson法則的最優(yōu)調度。其中：流水作業(yè)調度問題的johnson算法是：（1）令n1=i|ai<bi，n2=i|aibi；（2）將n1中的作業(yè)按ai非減序排序，將n2中的作業(yè)按bi非增序排列；（3）n1中的作業(yè)接n2中的作業(yè)就構成滿足johnson法則的最優(yōu)調度。滿足johnson法則的調度是最優(yōu)調度，調度滿足johnson法則，當且僅當對任意i<j，有minb(i)，a(j)minb(j)，a(i)3、試證明若在0-1背包問題中，各物品依重量遞增排列時，其價值恰好依遞減序排列，則用貪心算法可以找出其最優(yōu)解。四、選

6、作題：1、考慮下面的用最少硬幣個數找出n分錢的問題。（1） 當時用2角5分、一角、5分和1分四種硬幣面值時，設計一個貪心算法找出n分錢，并證明算法能夠產生一個最優(yōu)解。（2） 假設可使用的硬幣面值是c0，c1，ck，其中，c是一個正整數且c>1，k1。證明在這種情況下貪心算法總能產生最優(yōu)解。（3） 給出一個貪心算法不能產生最優(yōu)解的硬幣面值組合。2、設g是一個有n個頂點的有向圖，從頂點i出發(fā)的邊的最小費用記為min(i)，證明圖g的所有前綴為x1.i的旅行售貨員回路的費用至少為，其中，a(u，v)是邊(u，v)的費用。3、在一個圓形操場的四周擺放著n堆石子，現(xiàn)要將石子有次序地合并成一堆。規(guī)定

7、每次只能選相鄰的兩堆石子合并成一堆，并將新的一堆石子數記為該次合并的得分。試設計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分，并分析算法的計算復雜性。習題答案一、填空題1、2 logn n2/3 20n 40n2 2n 3n n!2、相同 互相獨立3、遞歸算法 初始條件或非遞歸定義的初始值4、（4k-1）/3或(n2-1)/35、n或2k-1 n-1或2k-16、 7、 8、（普通）背包貪心方法或按單位重量價值降序排序后選擇物品直到裝滿背包二、求解題1、 30 25 18 16 20 30 25 18 16 20 20 25 18 16 30 18 16 20 25 16 18 結

8、果： 16 18 20 25 302、（動態(tài)規(guī)劃算法）m1,8=2.1,k=5,w18=1m1,4=0.75,k=2,w14=0.45m6,8=0.35,k=7,w68=0.25m1,1=0.1m3,4=0.2,k=4,w34=0.15m6,6=0.05m8,8=0.05m3,3=0.050ebadcgfh3、（動態(tài)規(guī)劃算法）m,sj1234567i184,15,18,110,212,315,52886,26,215,411,5385,313,47,311,6488,49,49,45885,5684,678最短路：12574、a=b=c=15、最優(yōu)值：53，最優(yōu)解：bestx=（0，1，1，1，1，0）6、最優(yōu)值：10，最優(yōu)解：bestx=（1，2，5，4，3）或（1，3，4，5，2）三、證明題1、 k個bn相加，其中 =n+bnloglogn=（bloglogn+1）n=o（nloglogn）2、設i<j，分別證明：1）當時，滿足johnson不等式；2）當時，滿足johnson不等式；3）當時，滿足johnson不等式3、分別證明：貪心選擇性質；最優(yōu)子結構性質四、選作題1、1）貪心算法正確性的證