算法設(shè)計(jì)與分析考試復(fù)習(xí)題(北京郵電大學(xué)-北京地區(qū)適用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)與分析實(shí)驗(yàn)與復(fù)習(xí)題第一章 引 論 習(xí)題1 寫一個(gè)通用方法用于判定給定數(shù)組是否已排好序。算法實(shí)例： Algorithm compare(a,n) Begin J=1; While (j<n and aj<=aj+1) do j=j+1; If j=n then return true Else While (j<n and aj>=aj+1) do j=j+1; If j=n then return true else return false end if End if end 習(xí)題1 寫一個(gè)算法交換兩個(gè)變量的值不使用第三個(gè)變量。 算法

2、實(shí)例： x=x+y; y=x-y; x=x-y;習(xí)題1-3 已知m,n為自然數(shù)，其上限為k（由鍵盤輸入，1<=k<=109）,找出滿足條件 (n2-mn-m2)2=1 且使n2+m2達(dá)到最大的m、 n。算法實(shí)例： m:=k; flag:=0;repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1until (flag=1) or (m=0); 第二章 基礎(chǔ)知識(shí)習(xí)題2-1 求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10n

3、; n2/10+2n; 21+1/n; logn3; 10 log3n 。解答： 3n2+10n=O（n2）， n2/10+2n=O（2n）， 21+1/n=O（1）， logn3=O（log n），10 log3n=O（n）。習(xí)題2-2 說明O(1)和 O(2)的區(qū)別。 習(xí)題2-3 照漸進(jìn)階從低到高的順序排列以下表達(dá)式：，。 解答：照漸進(jìn)階從低到高的順序?yàn)椋骸?3n、 、20n、logn、2習(xí)題2-4 （1） 假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒?，F(xiàn)有另外一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)計(jì)算機(jī)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)

4、模為多大的問題？（2） 若上述算法的計(jì)算時(shí)間改進(jìn)為，其余條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模多大的問題？（3） 若上述算法的計(jì)算時(shí)間進(jìn)一步改進(jìn)為,其余條件不變，那么在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模多大的問題？解答：（1） 設(shè)新機(jī)器用同一算法在t秒內(nèi)能解輸入規(guī)模為的問題。因此有，解得。（2） 。（3） 由于常數(shù)，因此算法可解任意規(guī)模的問題。習(xí)題2-5 XYZ公司宣稱他們最新研制的微處理器運(yùn)行速度為其競(jìng)爭(zhēng)對(duì)手ABC公司同類產(chǎn)品的100倍。對(duì)于計(jì)算復(fù)雜性分別為，和的各算法，若用ABC公司的計(jì)算機(jī)能在1小時(shí)內(nèi)能解輸入規(guī)模為的問題，那么用XYZ公司的計(jì)算機(jī)在1小時(shí)內(nèi)分別能解輸入規(guī)模為多大的問題？

5、 解答：。習(xí)題2-6對(duì)于下列各組函數(shù)和，確定或或，并簡(jiǎn)述理由。（1）。（2）。（3）。（4）。（5）。（6）。（7）。（8）。解答：（1）。（2）。（3）。（4）。（5）。（6）。（7）。（8）。習(xí)題2-7 證明：如果一個(gè)算法在平均情況下的計(jì)算時(shí)間復(fù)雜性為，則該算法在最壞情況下所需的計(jì)算時(shí)間為。證明：因此，。習(xí)題2-7 求解下列遞歸方程: s0=0 sn=2sn-1+2n -1 解答：步驟: 1應(yīng)用零化子化為齊次方程，2解此齊次方程的特征方程，3由特征根構(gòu)造一般解，4再由初始條件確定待定系數(shù)，得到解為：習(xí)題2-8 求解下列遞歸方程: 解 hn=2n+1(n+1) 第三章 遞歸與分治策略習(xí)題3-

6、1 下面的7個(gè)算法都是解決二分搜索問題的算法。請(qǐng)判斷這7個(gè)算法的正確性。如果算法不正確，請(qǐng)說明產(chǎn)生錯(cuò)誤的原因。如果算法正確，請(qǐng)給出算法的正確性證明。public static int binarySearch1(int a,int x,int n)int left=0; int right =n-1;while (left<=right) int middle = ( left + right )/2;if ( x = amiddle) return middle;if ( x> amiddle) left = middle;else right = middle;return -

7、1;public static int binarySearch2(int a, int x, int n)int left = 0; int right = n-1;while ( left < right-1 ) int middle = ( left + right )/2;if ( x < amiddle) right = middle;else left = middle;if (x = aleft) return left;else return -1public static int binarySearch3(int a, int x, int n)int left

8、 = 0; int right = n-1;while ( left +1 != right) int middle = ( left + right)/2;if ( x>= amiddle) left = middle;else right = middle;if ( x = aleft) return left ;else return -1;public static int binarySearch4(int a, int x, int n)if (n>0 && x>= a0) int left = 0; int right = n-1;while (

9、left < right ) int middle = (left + right )/2;if ( x < amiddle) right = middle -1 ;else left = middle;if ( x = aleft) return left;return -1;public static int binarySearch5(int a, int x, int n)if ( n>0 && x >= a0 ) int left = 0; int right = n-1;while (left < right ) int middle

10、= ( left + right +1)/2;if ( x < amiddle) right = middle -1;else left = middle ;if ( x = aleft) return left;return -1;public static int binarySearch6(int a, int x, int n)if ( n>0 && x>= a0) int left = 0; int right = n-1;while ( left < right) int middle = (left + right +1)/2;if (x

11、< amiddle) right = middle 1;else left = middle + 1;if ( x = aleft) return left ;return -1;public static int binarySearch7(int a, int x, int n)if ( n>0 && x>=a0) int left = 0; int right = n-1;while ( left < right) int middle = ( left + right + 1)/2;if ( x < amiddle) right = mid

12、dle;else left = middle;if ( x = aleft) return left;return -1;分析與解答：算法binarySearch1數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致陷入死循環(huán)。算法binarySearch2數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致當(dāng)x=an-1時(shí)返回錯(cuò)誤。算法binarySearch3數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致當(dāng)x=an-1時(shí)返回錯(cuò)誤。算法binarySearch4數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致陷入死循環(huán)。算法binarySearch5正確，且當(dāng)數(shù)組中有重復(fù)元素時(shí)，返

13、回滿足條件的最右元素。算法binarySearch6數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致當(dāng)x=an-1時(shí)返回錯(cuò)誤。算法binarySearch7數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致當(dāng)x=an-1時(shí)陷入死循環(huán)。習(xí)題3-2 設(shè)是已排好序的數(shù)組。請(qǐng)改寫二分搜索算法，使得當(dāng)搜索元素x不在數(shù)組中時(shí)，返回小于x的最大元素位置i和大于x的最小元素位置j。當(dāng)搜索元素在數(shù)組中時(shí)，i和j相同，均為x在數(shù)組中的位置。分析與解答：改寫二分搜索算法如下：public static boolean binarySearch(int a, int x, int left, int right

14、, int ind)int middle;while ( left <= right ) middle = (left + right)/2;if (x = amiddle) ind0=ind1=middle; return true;if (x > amiddle) left = middle + 1;else right = middle -1;ind0 = right; ind1=left;return false;返回的ind1是小于x的最大元素位置，ind0是大于x的最小元素的位置。習(xí)題3-3 設(shè)是有n個(gè)元素的數(shù)組，是非負(fù)整數(shù)。試設(shè)計(jì)一個(gè)算法講子數(shù)組與換位。要求算法在最壞

15、情況下耗時(shí)為，且只用到的輔助空間。分析與解答：算法： 三次求反法Algorithm exchange(a, k, n);BeginInverse(n,0,k-1); inverse(n,k,n-1)； inverse（n,0,n-1）End.Algorithm inverse(a, i, j); Begin h=;For k=0 to h-1 do Begin x=ai+k; ai+k=aj-k; aj-k= x end ;end習(xí)題3-4 如果在合并排序算法的分割步中，講數(shù)組劃分為個(gè)子數(shù)組，每個(gè)子數(shù)組中有個(gè)元素。然后遞歸地對(duì)分割后的子數(shù)組進(jìn)行排序，最后將所得到的個(gè)排好序的子數(shù)組合并成所要求的

16、排好序的數(shù)組。設(shè)計(jì)一個(gè)實(shí)現(xiàn)上述策略的合并排序算法，并分析算法的計(jì)算復(fù)雜性。分析與解答：實(shí)現(xiàn)上述策略的合并排序算法如下：public static void mergesort(int a, int left ,int right) if (left < right ) int j = (int) Math.sqrt(right left+1);if (j>1) for (int i=0; i<j; i+) mergesort(a, left+i*j,left+(i+1)*j-1);mergesort(a,left+i*j,right);mergeall(a,left,righ

17、t);其中，算法mergeall合并個(gè)排好序的數(shù)組段。在最壞情況下，算法mergeall需要時(shí)間。因此上述算法所需的計(jì)算時(shí)間滿足：此遞歸式的解為：。習(xí)題3-5 設(shè)是整數(shù)集合，其中每個(gè)集合中整數(shù)取值范圍是，且，試設(shè)計(jì)一個(gè)算法，在時(shí)間內(nèi)將分別排序。分析與解答：用桶排序或基數(shù)排序算法思想可以實(shí)現(xiàn)整數(shù)集合排序。習(xí)題6 設(shè)和為兩個(gè)數(shù)組，每個(gè)數(shù)組中還有n個(gè)已排好序的數(shù)。試設(shè)計(jì)一個(gè)時(shí)間的算法，找出X和Y的2n個(gè)數(shù)的中位數(shù)。分析與解答：（1） 算法設(shè)計(jì)思想考慮稍一般的問題：設(shè)和是X和Y的排序好的子數(shù)組，且長(zhǎng)度相同，即。找出這兩個(gè)數(shù)組中個(gè)數(shù)的中位數(shù)。首先注意到，若，則中位數(shù)median滿足。同理若，則。設(shè)，則由

18、于，故。因此。當(dāng)時(shí)，。當(dāng)時(shí)，設(shè)是和的中位數(shù)，則。當(dāng)時(shí)，設(shè)是和的中位數(shù)，類似地有。通過以上討論，可以設(shè)計(jì)出找出兩個(gè)子數(shù)組和的中位數(shù)median的算法。（2） 設(shè)在最壞情況下，算法所需的計(jì)算時(shí)間為。由算法中和的選取策略可知，在遞歸調(diào)用時(shí)，數(shù)組X和Y的大小都減少了一半。因此，滿足遞歸式：解此遞歸方程可得：。習(xí)題3-6 Gray碼是一個(gè)長(zhǎng)度為的序列。序列中無相同元素，每個(gè)元素都是長(zhǎng)度為n位的（0，1）串，相鄰元素恰好只有1位不同。用分治策略設(shè)計(jì)一個(gè)算法，對(duì)任意的n構(gòu)造相應(yīng)的Gray碼。分析與解答：考察的簡(jiǎn)單情形。n=101n=200011110n=3000001011010110111101100設(shè)n

19、位Gray碼序列為以相反順序排列的序列為。從上面的簡(jiǎn)單情形可以看出的構(gòu)造規(guī)律：。注意到的最后一個(gè)n位串與的第1個(gè)n位串相同，可用數(shù)學(xué)歸納法證明的上述構(gòu)造規(guī)律。由此規(guī)律容易設(shè)計(jì)構(gòu)造的分治法如下。public static void Gray(int n)if ( n = 1) a1 = 0; a2 = 1; return; Gray(n-1);for ( int k = 1<< ( n - 1), i = k; i > 0; i-) a2*k-i+1=ai + k;上述算法中將n位（0，1）串看做是二進(jìn)制整數(shù)，第i個(gè)串存儲(chǔ)在中。完成計(jì)算之后，由out輸出Gray碼序列。publ

20、ic static void out(int n)int m=1<<n;for (int i=1; i<=m; i+) String str=Integer.toBinaryString(ai);int s=str.length();for ( int j=0; j<n-s; j+) System.out.print(“0”);System.out.println(Integer.toBinaryString(ai)+” ”);System.out.println();第四章 動(dòng)態(tài)規(guī)劃 習(xí)題4-1 設(shè)計(jì)一個(gè)時(shí)間的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列。分析與解

21、答：用數(shù)組記錄以為結(jié)尾元素的最長(zhǎng)遞增子序列的長(zhǎng)度。序列a的最長(zhǎng)遞增子序列的長(zhǎng)度為。易知，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，可以遞歸地定義為：據(jù)此將計(jì)算轉(zhuǎn)化為i個(gè)規(guī)模更小的子問題。按此思想設(shè)計(jì)的動(dòng)態(tài)規(guī)劃算法描述如下：public static int LISdyna()int i, j, k;for ( i=1, b0=1; i<n;i+) for ( j=0, k=0; j<I; j+ ) if ( aj <= ai && k< bj ) k=bj;bi= k+1;return maxL(n);static int maxL(int n)int temp=0;for

22、( int i= 0; i<n; i+) if (bi > temp) temp=bi;return temp;上述算法LISdyna按照遞歸式計(jì)算出的值，然后由maxL計(jì)算出序列a的最長(zhǎng)遞增子序列的長(zhǎng)度。從算法LISdyna的二重循環(huán)容易看出，算法所需的計(jì)算時(shí)間為。習(xí)題4-2 考慮下面的整數(shù)線性規(guī)劃問題： 為非負(fù)整數(shù)，試設(shè)計(jì)一個(gè)解此問題的動(dòng)態(tài)規(guī)劃算法，并分析算法的計(jì)算復(fù)雜性。分析與解答：該問題是一般情況下的背包問題，具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)所給背包問題的子問題：的最優(yōu)值為，即是背包容量為j，可選擇物品為1，2，i時(shí)背包問題的最優(yōu)值。由背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算的遞歸式如

23、下：。按此遞歸式計(jì)算出的為最優(yōu)值。算法所需的計(jì)算時(shí)間為。習(xí)題4-3 給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如圖3-2所示。試設(shè)計(jì)一個(gè)算法，計(jì)算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。 7 3 88 1 0 2 7 4 4 4 5 2 6 5 數(shù)字三角形分析與解答：記f(uij)為至ij元素的最大路徑值, aij ：元素(i,j)之值。遞歸式: F(uij)=maxf(ui-1,j)+aij, f(ui-1,j+1)+aij (i=1,n， j=1,i)經(jīng)過一次順推，便可求出從頂至底n個(gè)數(shù)的n條路徑（這n條路徑為至底上n個(gè)數(shù)的n個(gè)最大總和的路徑），求出這n個(gè)總和的最大值，即為正確答

24、案。數(shù)據(jù)結(jié)構(gòu): ai,j.val: 三角形上的數(shù)字，ai,j.f: 由（1，1）至該點(diǎn)的最大總和路徑的總和值。type node=record val, f: integer; end;var a:array 1. maxn, 1.maxn of node;procedure findmax;begina 1,1. f :=a1,1.val; for i:=2 to n do for j:=1 to i do begin ai,j. f:=-1;if (j<>1) and (a i-1,j-1.f+ai,j.val > a i,j.f) then ai,j. f:=a i-1

25、,j-1. f+ai,j.val; if (j<>i) and(a i-1,j.f+ai,j.val > ai,j.f) then ai,j. f:=ai-1,j. f+ai,j. valend;max:=1;for i:=2 to n do if an,i. f> an, max .f then max:=i; writeln (a n, max. f)end;第五章 貪心算法 習(xí)題5-1 特殊的0-1背包問題若在0-1背包問題中，各物品依重量遞增排列時(shí)，其價(jià)值恰好依遞減序排列。對(duì)這個(gè)特殊的0-1背包問題，設(shè)計(jì)一個(gè)有效算法找出最優(yōu)解，并說明算法的正確性。分析與解答：設(shè)

26、所給的輸入為。不妨設(shè)。由題意知。由此可知，貪心選擇性質(zhì)：當(dāng)時(shí)問題無解。當(dāng)時(shí)，存在0-1背包問題的一個(gè)最優(yōu)解使得。事實(shí)上，設(shè)使0-1背包問題的一個(gè)最優(yōu)解，且。對(duì)任意，取，則滿足貪心選擇性質(zhì)的最優(yōu)解。習(xí)題5-2 Fibonacci序列的Huffman編碼試證明：若n個(gè)字符的頻率恰好是前n個(gè)Fibonacci數(shù)，用貪心法得到它們的Huffman編碼樹一定為一棵“偏斜樹”。分析與解答： 頻率恰好是前8個(gè)Fibonacci數(shù)的哈夫曼編碼樹如圖所示。543321521311320127428圖 哈夫曼編碼樹證明：n個(gè)字符的頻率恰好是前n個(gè)Fibonacci數(shù)，則相應(yīng)的哈夫曼編碼樹自底向上第i個(gè)內(nèi)結(jié)點(diǎn)中的數(shù)

27、為。用數(shù)學(xué)歸納法容易證明。因f1=1,f2=1,f3=2,可知i=1時(shí)，上述結(jié)論成立。設(shè)對(duì)i+2上述結(jié)論成立，即有， 因，說明對(duì)i+3上述結(jié)論成立. 該性質(zhì)保證了頻率恰好是前n個(gè)Fibonacci數(shù)的哈夫曼編碼樹具有“偏斜樹”形狀。習(xí)題5-3 假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的貪心算法進(jìn)行安排。分析與解答：設(shè)所給的n個(gè)活動(dòng)為1，2，n，它們的開始時(shí)間和結(jié)束時(shí)間分別為和，且?？梢詫個(gè)活動(dòng)1，2，n看作實(shí)直線上的n個(gè)半閉活動(dòng)區(qū)間。所討論的問題實(shí)際上是求這n個(gè)半閉區(qū)間的最大重疊數(shù)。因?yàn)橹丿B的活動(dòng)區(qū)間所相應(yīng)的活動(dòng)是互不相容的。若這n個(gè)活動(dòng)區(qū)間的最大重疊數(shù)為m

28、，則這m個(gè)重疊區(qū)間所對(duì)應(yīng)的活動(dòng)互不相容，因此至少安排m個(gè)會(huì)場(chǎng)來容納這m個(gè)活動(dòng)。為了有效地對(duì)這n個(gè)活動(dòng)進(jìn)行安排，首先將n個(gè)活動(dòng)區(qū)間的2n個(gè)端點(diǎn)排序。然后，用掃描算法，從左到右掃描整個(gè)實(shí)直線。在每個(gè)事件點(diǎn)處（即活動(dòng)的開始時(shí)刻或結(jié)束時(shí)刻）作會(huì)場(chǎng)安排。當(dāng)遇到一個(gè)開始時(shí)刻，就將活動(dòng)i安排在一個(gè)空閑的會(huì)場(chǎng)中。遇到一個(gè)結(jié)束時(shí)候，就將活動(dòng)i占用的會(huì)場(chǎng)釋放到空閑會(huì)場(chǎng)棧中，以備使用。經(jīng)過這樣一遍掃描后，最多安排了m個(gè)會(huì)場(chǎng)（m是最大重疊區(qū)間數(shù)）。因此所作的會(huì)場(chǎng)安排是最優(yōu)的。上述算法所需的計(jì)算時(shí)間主要用于對(duì)2n個(gè)區(qū)間端點(diǎn)的排序，這需要計(jì)算時(shí)間。具體算法描述如下。public static int greedy(poi

29、nt x)int sum=0, curr=0, n=x.length;MergeSort.mergeSort(x);for (int i=0; i<n;i+) if (xi.leftend() curr+;else curr-;/處理xi=xi+1的情況if ( i = pareTo(xi+1)<0)&& curr>sum) sum=curr;return sum;習(xí)題5-4 假設(shè)要在m個(gè)會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能多地安排活動(dòng)。設(shè)計(jì)一個(gè)有效的貪心算法進(jìn)行安排。Algorithm greedy(s,f,m,n); Input s1:n

30、, f1:n; Output x1:m, 1:n;Begin對(duì)數(shù)組s和f中的2n個(gè)元素排序存入數(shù)組y1:2n中；空閑棧清空；d數(shù)組所有元素置初值0；For i=1 to 2n do Begin If 元素yi 原屬于s then If 空閑棧不空then 取出棧頂場(chǎng)地j; dj=dj+1; yi 存入xj, dj ; If 元素yi 原屬于f then 設(shè)其相應(yīng)的s 存于xj,k 中，將j存入空閑棧中； End For i= 1 to m do For j=1 to dj do Output xi,j;End 習(xí)題5-5 刪數(shù)問題 問題描述給定n位正整數(shù)a，去掉其中任意個(gè)數(shù)字后，剩下的數(shù)字按原

31、次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)k，設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。分析與解答：貪心策略：最近下降點(diǎn)優(yōu)先。public static void delek(String a)int i,m=a.length();if ( k>= m) System.out.println(0); return;while (k>0) for (i=0; (i<a.length()-1)&&(a.charAt(i)<=a.charAt(i+1); i+)a= a.Remove(i,1); k-;while (a.length()

32、>1 && a.charAt(0)=0) a=a.Remove(0,1);System.out.println(a);第六章 回溯法 習(xí)題6-1 子集和問題 子集和問題的一個(gè)實(shí)例。其中，是一個(gè)正整數(shù)的集合，sum是一個(gè)正整數(shù)。子集和問題判定是否存在A的一個(gè)子集A1，使得。試設(shè)計(jì)一個(gè)解子集和問題的回溯法。分析與解答：設(shè)計(jì)解子集和問題的回溯法如下。Algorithm subset-sumbegin For j=1 to n do Begin sp=0; t=sum; i=j; finish=false; repeat if t>=ai then begin sp=sp+

33、1；ssp=i; t=t-ai; if t=0 then i=n; end; i=i+1; while i>n do if sp>1 then begin if t=0 then out; t=t+assp; i=ssp+1; sp=sp-1 end else begin finish=true; i=1 enduntil finishendend 習(xí)題6-2 中國(guó)象棋的半個(gè)棋盤如圖所示，馬自左下角往右上角跳。規(guī)定只許向右跳，不許向左跳，計(jì)算所有的行走路線。 Algorithm chess Begin top=0; y0=0; x0=0; di=1; r=0;push;repeat

34、 pop; while di<=4 do begin g=x0+xdi; h=y0+ydi; if (g=8) and (h=4) then out else begin di=di+1；push; x0=g; y0=h; di=1 end enduntil emptyendalgorithm pushbegin top=top+1；sxtop=x0; sytop=y0; dtop=di; end algorithm popbegin x0=sxtop; y0=sytop; di =dtop; top=top1；end 習(xí)題6-3. 在n個(gè)連成排的方格內(nèi)填入R或B，但相鄰連個(gè)方格內(nèi)不能都

35、填R。計(jì)算所有可能的填法。 RBBRBAlgorithm Red-Black;Begin For i=1 to n do bi=0; T=1;Repeat bt=bt+1  if bt>2 then 回溯 begin bt=0  t=t-1  end  else begin if bt=2 then at= B else if at-1=R then t=t-1 else at=R; if t=n then output a else t=t+1 end until t=0第七章 分支限界法習(xí)題7-1. 試寫出采用分支界限法求解下面的0、

36、1背包問題實(shí)例的過程： 物品的個(gè)數(shù)n=4, 背包的重量m=15, 各個(gè)物品的重量依次為2，4，6，9，各個(gè)物品的價(jià)值依次為10，10，12，18。 對(duì)于第i層上的每個(gè)節(jié)點(diǎn)x，其價(jià)值的上界定義為有貪心法所求出的一般背包問題的解Su(x)，下界為Sl(x)為Su(x)中減去最后放入背包的xi1的物品的相應(yīng)部分價(jià)值。解答： 習(xí)題7-2. 寫出用分支界限法求解下面的重排九宮問題的算法。開始狀態(tài) 目標(biāo)狀態(tài)8126375412384765 解答： 我們對(duì)九宮中的位置做如下的編號(hào)：位置編號(hào) 123894765則初始狀態(tài)用向量S0=（8，1，2，3，4，5，7，0，6）表示，目標(biāo)狀態(tài)用S*=（1，2，3，4，

37、5，6，7，8，0）表示。我們使用一個(gè)堆heap, 將啟發(fā)函數(shù)值H(x)最小的狀態(tài)x置于堆頂優(yōu)先搜索。H(x)定義如下： H(x)=h1(x)+3h2(x)其中，h1(x)為狀態(tài)x與目標(biāo)狀態(tài)不相同的數(shù)字的數(shù)目， ，這里，算法： Algorithm LC(S0, S*) Input: 初始狀態(tài)向量S0 , 目標(biāo)狀態(tài)S*；Output: 達(dá)到目標(biāo)狀態(tài)的狀態(tài)序列；BeginS=S0; if S目標(biāo)狀態(tài)S* then Output(S及其所有前驅(qū)) else add (S, heap) while heap非空 do取出堆heap頂部狀態(tài)E ；for E 的每個(gè)可能的后繼狀態(tài)x do if x為目標(biāo)狀

38、態(tài)S* then Output(x及其所有前驅(qū)); return else 計(jì)算x的啟發(fā)函數(shù)H(x); add(x, heap) endif endfor endwhileend 第八章 NP完全問題習(xí)題8-1 證明析取范式的可滿足性問題屬于P類。分析與解答： 析取范式是由因子之和的和式給出的。這里因子是指變量x或，每個(gè)因子之積稱為一個(gè)析取式。例如 x1x2+x2x3+x3就是一個(gè)析取范式。 設(shè)給定一個(gè)析取范式，其中是變量或，j=1n的一個(gè)析取范式，i=1m。是可滿足的，當(dāng)且僅當(dāng)存在i, ，使是可滿足的。如果有一個(gè)多項(xiàng)式時(shí)間算法能判斷任何一個(gè)析取式的可滿足性，則用該算法對(duì)的每個(gè)析取項(xiàng)逐一判斷就

39、可以在多項(xiàng)式時(shí)間內(nèi)確定析取范式的可滿足性。因此，問題可簡(jiǎn)化為找一個(gè)確定析取式可滿足性的多項(xiàng)式時(shí)間算法。 設(shè)析取范式=，其中。 可以設(shè)計(jì)在O(n+k)時(shí)間內(nèi)確定析取式=可滿足性的算法。因此，析取范式的可滿足性問題是多項(xiàng)式時(shí)間可解的，即它屬于P類。 第九章 近似算法習(xí)題9-1 瓶頸旅行售貨員問題瓶頸旅行售貨員問題是要找出圖G=(V,E)的一個(gè)哈密頓回路，且使回路中最長(zhǎng)邊的長(zhǎng)度最小。若費(fèi)用函數(shù)滿足三角不等式，給出解此問題的性能比為3的近似算法。（提示：遞歸地證明，可以通過對(duì)G的最小生成樹進(jìn)行完全遍歷并跳過某些項(xiàng)點(diǎn)，但不能跳過多于2個(gè)連續(xù)的中間頂點(diǎn)，以此方式訪問最小生成樹中每個(gè)頂點(diǎn)恰好一次。）分析與解

40、答：解瓶頸旅行售貨員問題的性能比為3的近似算法描述如下：Void approxTSP(Graph G) 選擇任一頂點(diǎn) rV； 找出G的一棵以r為根的最小瓶頸生成樹T； 選取 T的一條邊（p,q）作為哈密頓回路H的一條邊； 遍歷樹T，跳過不多于兩個(gè)連續(xù)的重復(fù)頂點(diǎn)，遞歸構(gòu)造H的其他邊； 將所得到的哈密頓回路H作為計(jì)算結(jié)果返回. 習(xí)題9-2 可滿足問題的近似算法 問題描述 設(shè)是一個(gè)含有n個(gè)變量和m個(gè)合取項(xiàng)的合取范式。關(guān)于的最大可滿足性問題要求確定的最多個(gè)數(shù)的合取式使這些合取式可同時(shí)滿足。設(shè)k是的所有合取式中因子個(gè)數(shù)的最小值。證明下面的解最大可滿足性問題的近似算法 mSAT的相對(duì)誤差為。 Set mS

41、AT(a) / , ,是a 中n個(gè)變量；Ci ，是的m個(gè)合取項(xiàng)。 c1= ; left= Ci |; lit=,|; while(lit含有在left的合取式中出現(xiàn)的因子) 設(shè)y是lit的在left的合取式中出現(xiàn)次數(shù)最多的因子； 設(shè)r是left中含有因子y的所有合取式的集合； c1= c1 r; left=left-r; lit=lit-y, ; return(c1); 第十章 隨機(jī)算法 習(xí)題10-1 模擬正態(tài)分布隨機(jī)變量在實(shí)際應(yīng)用中，常需要模擬服從正態(tài)分布的隨機(jī)變量，其密度函數(shù)為，其中，a為均值，為標(biāo)準(zhǔn)差。如果s和t是（-1，1）中均勻分布的隨機(jī)變量，且，令，則和是服從標(biāo)準(zhǔn)正態(tài)分布的兩個(gè)互相

42、獨(dú)立的隨機(jī)變量。（1） 利用上述事實(shí)，設(shè)計(jì)一個(gè)模擬標(biāo)準(zhǔn)正態(tài)分布隨機(jī)變量的算法。（2） 將上述算法擴(kuò)展到一般的正態(tài)分布。分析與解答：(1) 模擬標(biāo)準(zhǔn)正態(tài)分布隨機(jī)變量的算法如下。public double Norm()double s,t,p,q;while (true) s=2*fRandom()-1;t=2*fRandom()-1;p=s*s+t*t;if (p<1) break;q=Math.sqrt(-2*Math.log(p)/p);return s*q;(2) 擴(kuò)展到一般的正態(tài)分布的算法如下。public double Norm(double a,double b)double

43、x=Norm();return a+b*x;習(xí)題10-2 整數(shù)因子分解算法假設(shè)已有一個(gè)算法Prime(n)可用于測(cè)試整數(shù)n是否為一素?cái)?shù)。另外還有一個(gè)算法Split(n)可實(shí)現(xiàn)對(duì)合數(shù)n的因子分割。試?yán)眠@兩個(gè)算法設(shè)計(jì)一個(gè)對(duì)給定整數(shù)n進(jìn)行因子分解的算法。分析與解答：因子分解算法如下。static void fact(int n)if (prime(n) output(n); return;int i=split(n);if (i>1) fact(i);if (n>i) fact(n/i)；算法設(shè)計(jì)與分析實(shí)驗(yàn)題實(shí)驗(yàn)題1最大間隙問題：給定n個(gè)數(shù)，求這n個(gè)數(shù)在實(shí)軸上相鄰2個(gè)數(shù)之間的最大差值。

44、假設(shè)對(duì)任何實(shí)數(shù)的下取整方法耗時(shí)為，設(shè)計(jì)解最大間隙問題的線性時(shí)間算法。分析與解答：用鴿舍原理設(shè)計(jì)最大間隙問題的線性時(shí)間算法如下。Public static double maxgap(int n,double x)double minx=xmini(n,x), maxx=xmaxi(n,x);/用n-2個(gè)等間距點(diǎn)分割區(qū)間minx,maxx/產(chǎn)生n-1個(gè)桶，每個(gè)桶i中用highi和lowi分別存儲(chǔ)分配給桶i的數(shù)中的最大數(shù)和最小數(shù)int count=new intn+1;double low=new doublen+1;double high=new doublen+1;/桶初始化for (int

45、i=1, i<=n-1; i+) counti=0; lowi=maxx; highi=minx;/將n個(gè)數(shù)置于n-1個(gè)桶中for (int i=1; i<=n; i+) int bucket=(int)(n-1)*(xi-minx)/(maxx-minx)+1;countbucket+;if (xi<lowbucket) lowbucket=xi;if (xi>highbucket) highbucket=xi;/此時(shí)，除了maxx和minx外的n-2個(gè)數(shù)被置于n-1個(gè)桶中/由鴿舍原理即知，至少有一個(gè)桶式空的/這意味著最大間隙不會(huì)出現(xiàn)在同一桶中的兩個(gè)數(shù)之間/對(duì)每一個(gè)桶作一次線性掃描即可找出最大間隙double tmp=0, left=high1;for (int i=2; i<=n-1; i+) if (counti>0) double thisgap=lowi-left;if (thisgap>tmp) tmp=thisgap;left=highi