算法設(shè)計(jì)與分析習(xí)題與實(shí)驗(yàn)題

1、算法設(shè)計(jì)與分析?習(xí)題第一章 引 論習(xí)題 1-1 寫一個(gè)通用方法用于判定給定數(shù)組是否已排好序。 解答：Algorithm compare(a,n)BeginJ=1;While (j<n and aj<=aj+1) do j=j+1;If j=n then return trueElseWhile (j<n and aj>=aj+1) do j=j+1;If j=n then return true else return false end if End ifend習(xí)題 1-2 寫一個(gè)算法交換兩個(gè)變量的值不使用第三個(gè)變量。 解答： x=x+y; y=x-y; x=x-y;

2、習(xí)題1-3m,n為自然數(shù)，其上限為k (由鍵盤輸入，1<=k<=109)，找出滿 足條件 (n2-mn-m2)2=1 且使 n2+m2 到達(dá)最大的 m、 n。解答： 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-1 until (flag=1) or (m=0);第二章 根底知識(shí)習(xí)題2-1求以下函數(shù)的漸進(jìn)表達(dá)式：3n2+10n; n2/10+2n; 2

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

4、為 第一臺(tái)計(jì)算機(jī)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在 t秒內(nèi)能解輸 入規(guī)模為多大的問題？(2) 假設(shè)上述算法的計(jì)算時(shí)間改良為T(n)= n2，其余條件不變，那么在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模多大的問題？(3) 假設(shè)上述算法的計(jì)算時(shí)間進(jìn)一步改良為T(n)=8,其余條件不變，那么在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模多大的問題？解答：(1) 設(shè)新機(jī)器 用同一算法在t秒內(nèi)能解輸 入規(guī)模為 山的問題。因此有t =3 2n =3 201 /64，解得 = n 6。2 2(2) nj = 64n= n 8n。(3) 由于T(n )=常數(shù)，因此算法可解任意規(guī)模的問題。習(xí)題2-5 XYZ公司宣稱他們最新研制的

5、微處理器運(yùn)行速度為其競(jìng)爭(zhēng)對(duì)手ABC公司同類產(chǎn)品的100倍。對(duì)于計(jì)算復(fù)雜性分別為n，n2，n3和n!的各算法， 假設(shè)用ABC公司的計(jì)算機(jī)能在1小時(shí)內(nèi)能解輸入規(guī)模為n的問題，那么用XYZ公 司的計(jì)算機(jī)在1小時(shí)內(nèi)分別能解輸入規(guī)模為多大的問題？解答：n =100n。2 2n =100n n =10n。n 3 =100n3 二 3 100n = 4.64n。n ! =100n! = n ： n log 100 = n 6.64。習(xí)題2-6對(duì)于以下各 組函數(shù)f(n)和g(n),確定f(n)=O(g(n)或 f (n) - '(g(n)或 f (n) - (g(n)，并簡(jiǎn)述理由。(1) f (n)

6、= log n ； g (n) = log n 5。(2) f (n) =log n 2;g( n) n。(3) f (n)二 n； g(n) = log2 n。(4) f (n) = nlog n n; g(n) = log n。(5) f (n) =10;g(n) = log 10。(6) f (n) =log2 n;g(n) =log n。(7) f (n)=2n;g( n)=100 n2。(8) f(n)=2n;g(n) = 3n。解答：(1) log n2 -)(log n 5)。(2) log n2 = 0( n)。(3) n -門(log 2 n)。(4) n log n n =

7、 '"log n)。(5) 10 - "log 10)。(6) log 2 n 二 11 (log n)。(7) 2n "(100n2)。(8) 2n =0(3n)。習(xí)題2-7證明：如果一個(gè)算法在平均情況下的計(jì)算時(shí)間復(fù)雜性為r(f(n),那么該算法在最壞情況下所需的計(jì)算時(shí)間為1 (f (n)。證明：Tavg(N) =、P(I)T(N,I)1 In一、P(I)maxT(N,I )I.DnI Dn= T(N,I*r P(I)丨田N= T(N,I*)二 Tmax(N)因此，Tmax(N):=門仃 avg(N) "3(f( n)(f( n)。習(xí)題2-7求

8、解以下遞歸方程：So=O-Sn=2Sn-1+2n-1解答:步驟：1應(yīng)用零化子化為齊次方程,2解此齊次方程的特征方程，3由特征根構(gòu)造一般解，4再由初始條件確定待定系數(shù)，得到解為:Sn =( n-1)2n 1習(xí)題2-8求解以下遞歸方程：ho = 2<hi =8hn=2n+1( n+1)=4hnJ -4hnd解第三章遞歸與分治策略習(xí)題3-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 lef

9、t=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 -1;public static int binarySearch2(int a, int x, int n) int left = 0; int right = n-1;while ( left < right-1 ) int middle = (

10、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 = 0; int right = n-1;while ( left +1 != right) int middle = ( left + right)/2; if ( x>= amiddle) left = middle; else rig

11、ht = 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 (left < right ) int middle = (left + right )/2; if ( x < amiddle) right = middle -1 ;else left = middle;if ( x = ale

12、ft) 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 = ( left + right +1)/2; if ( x < amiddle) right = middle -1; else left = middle ;if ( x = aleft) return left; return

13、-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 < amiddle) right = middle T; else left = middle + 1;if ( x = aleft) return left ;return -1;public static int binar

14、ySearch7(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 = middle; else left = middle;if ( x = aleft) retur n left;return -1;分析與解答：算法binarySearchl數(shù)組段左右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致陷入死

15、循環(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í)，返回滿足條件的最右算法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=a

16、n-1 時(shí)陷入死循環(huán)。習(xí)題3-2設(shè)a0: n1是已排好序的數(shù)組。請(qǐng)改寫二分搜索算法，使得當(dāng)搜 索元素x不在數(shù)組中時(shí)，返回小于x的最大元素位置i和大于x的最小元素位置 j。當(dāng)搜索元素在數(shù)組中時(shí)，i和j相同，均為x在數(shù)組中的位置。分析與解答：改寫二分搜索算法如下：public static boolea n bin arySearch(i nt a, int x, int left, int right, i nt i nd)int middle;while ( left <= right ) middle = (left + right)/2;if (x = amiddle) ind0=i

17、nd1=middle; return true;if (x > amiddle) left = middle + 1;else right = middle -1;in d0 = right; in d1=left;return false;返回的ind1是小于x的最大元素位置，ind0是大于x的最小元素的位置。習(xí)題3-3 設(shè)a0: n-1是有n個(gè)元素的數(shù)組，k(1豈k乞n-1)是非負(fù)整數(shù)。試設(shè)計(jì)一個(gè)算法講子數(shù)組aO:k1與ak: n1換位。要求算法在最壞情況下耗時(shí)為0(n),且只用到0(1)的輔助空間。分析與解答：算法：三次求反法Algorithmexcha nge(a, k, n);

18、Beg inInverse(n,0,k-1); inverse(n,k,n-1)；inverse( n,O,n-1)End.Algorithminv erse(a, i, j);Beg inh=j _i +1一 2For k=0 to h-1 doBegi n x=ai+k; ai+k=aj-k; aj-k= x end ; end習(xí)題3-4如果在合并排序算法的分割步中，講數(shù)組 a0: n -1劃分為氐n個(gè) 子數(shù)組，每個(gè)子數(shù)組中有O(、. n)個(gè)元素。然后遞歸地對(duì)分割后的子數(shù)組進(jìn)行排序， 最后將所得到的心n個(gè)排好序的子數(shù)組合并成所要求的排好序的數(shù)組 a0: n-1。設(shè)計(jì)一個(gè)實(shí)現(xiàn)上述策略的合并排

19、序算法，并分析算法的計(jì)算復(fù)雜性。 分析與解答：實(shí)現(xiàn)上述策略的合并排序算法如下：public static void mergesort(i nt a, int left ,i nt right) if (left < right ) int j = (int) Math.sqrt(right -eft+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,right);其中，算法mergeall合

20、并.n個(gè)排好序的數(shù)組段。在最壞情況下，算法 mergeall 需要O(nlog n)時(shí)間。因此上述算法所需的計(jì)算時(shí)間 T(n)滿足:0(1)nT(n) =廠廠InT(Jn)n a 1此遞歸式的解為：T (n) =O(nlog n)。習(xí)題3-5 設(shè),S2,.Sk是整數(shù)集合，其中每個(gè)集合 乜(1叮豈k)中整數(shù)取值k范圍是1n，且送冋=n，試設(shè)計(jì)一個(gè)算法，在O( n)時(shí)間內(nèi)將Si,S2,Sk分別i 4排序。分析與解答：用桶排序或基數(shù)排序算法思想可以實(shí)現(xiàn)整數(shù)集合排序。習(xí)題6設(shè)X0: n 一1和Y0: n1為兩個(gè)數(shù)組，每個(gè)數(shù)組中還有n個(gè)已排好序的 數(shù)。試設(shè)計(jì)一個(gè)O(log n)時(shí)間的算法，找出X和Y的2

21、n個(gè)數(shù)的中位數(shù)。分析與解答：(1)算法設(shè)計(jì)思想考慮稍一般的問題：設(shè)Xi1 : jj和Yi2 : j2是X和Y的排序好的子數(shù)組， 且長(zhǎng)度相同，即j1 -h二j2 “2。找出這兩個(gè)數(shù)組中2(h-j1 T)個(gè)數(shù)的中 位數(shù)。首先注意到，假設(shè)Xi1H： Y j2，貝U中位數(shù) median滿足XhMm e d 芒創(chuàng)免。同理假設(shè) Xi1pYj2，那么 Yj2蘭 media Xi1。設(shè)m1 =(h jJ/2，m2 =仏 j2)/2，那么m1 m2 =(ijJ/2 (i2 j2)/2 7 (h -iJ/2 i? j 譏)二h i2 (j1-iJ/2 厲“"由于 j1 -i j2 -i2，故(j1 -h

22、)/2 (j2 7)/2 二 j1 -h = j2 7。因此匕 m1 m2 = i1 i2 ji 二屛=i2 j i1 i2 j2 _ i2 = h j2。當(dāng) Xm1Ym2時(shí)，median = Xm1 = Ym2。當(dāng) Xlm ：Ym2】時(shí)，設(shè) median 是 Xm1 : j1和 Y j2 : m2的中位數(shù)，那么median = medianj。當(dāng)Xmi Ym2】時(shí)，設(shè)media七是Xii：mi和Ym2 : j2的中位數(shù)，類似地有 median 二 median2。通過以上討論，可以設(shè)計(jì)出找出兩個(gè)子數(shù)組Xii : j和丫亞:j2的中位數(shù)media n的算法。(2)設(shè)在最壞情況下，算法所需的計(jì)算

23、時(shí)間為 T (2n)。由算法中mi和m2的選取策略可知，在遞歸調(diào)用時(shí)，數(shù)組X和Y的大小都減少了一半。因此，T(2n)滿足遞歸式:T(2 n)=丿01)T(n)+O(1)n ： c n _ c習(xí)題3-6解此遞歸方程可得：T(2n) =O(log n)Gray碼是一個(gè)長(zhǎng)度為2n的序列。序列中無相同元素，每個(gè)元素1位不同。用分治策略設(shè)計(jì)都是長(zhǎng)度為n位的(0，1 )串，相鄰元素恰好只有 個(gè)算法，對(duì)任意的n構(gòu)造相應(yīng)的Gray碼。分析與解答：考察n =1,2,3的簡(jiǎn)單情形n=101n=200011110n=3000001011010110111101100設(shè)n位Gray碼序列為G(n)以相反順序排列的序列

24、為G *(n)。從上面的簡(jiǎn)單情形可以看出G(n)的構(gòu)造規(guī)律：G(n 1) = 0G(n) 1G(n)注意到G(n)的最后一個(gè)n位串與G (n)的第1個(gè)n位串相同，可用數(shù)學(xué)歸納法證明G(n)的上述構(gòu)造規(guī)律。由此規(guī)律容易設(shè)計(jì)構(gòu)造G(n)的分治法如下。public static void Gray(i nt 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;上述算法中將門位(0，1)串看做是二進(jìn)制整數(shù)，第i個(gè)串存

25、儲(chǔ)在ai中 完成計(jì)算之后，由out輸出Gray碼序列。public static void out(i nt n)int m=1< <n;for (i nt i=1; i<=m; i+) String str=Integer.toBinaryString(ai);int s=str.le ngth();for ( int j=0; j<n-s; j+) System.out.print( 0；System.out.println(Integer.toBinaryString(ai)+ )；System.out.pri ntl n();第四章動(dòng)態(tài)規(guī)劃習(xí)題4-1設(shè)計(jì)一個(gè)O(

26、n?)時(shí)間的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào) 遞增子序列。分析與解答：用數(shù)組b0: n -1記錄以ai,0 _ i ： n為結(jié)尾元素的最長(zhǎng)遞增子序列的長(zhǎng)度。序列a的最長(zhǎng)遞增子序列的長(zhǎng)度為maxbi。o_i:n易知，bi滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，可以遞歸地定義為：b0 = 1,bi =°max bk 1akkai據(jù)此將計(jì)算bi轉(zhuǎn)化為i個(gè)規(guī)模更小的子問題按此思想設(shè)計(jì)的動(dòng)態(tài)規(guī)劃算法描述如下: public static int LISd yn a()int i, j, k;for ( i=1, b0=1; i<n;i+) for ( j=0, k=0; jvl; j+ ) if (

27、aj <= ai && k< bj ) k=bj; bi= k+1;return maxL( n);static int maxL(i nt n)int temp=0;for ( int i= 0; i<n; i+) if (bi > temp) temp=bi; return temp;上述算法LISdyna按照遞歸式計(jì)算出b0: n 一1的值，然后由maxL計(jì)算出序 列a的最長(zhǎng)遞增子序列的長(zhǎng)度。從算法LISdyna的二重循環(huán)容易看出，算法所需 的計(jì)算時(shí)間為0(n2)。習(xí)題4-2考慮下面的整數(shù)線性規(guī)劃問題：nmax' cixin 7Xi為非負(fù)整

28、數(shù)，1M蘭n' aixbi =1試設(shè)計(jì)一個(gè)解此問題的動(dòng)態(tài)規(guī)劃算法，并分析算法的計(jì)算復(fù)雜性。分析與解答：該問題是一般情況下的背包問題，具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)所給背包問題的子問題：imax' CkXkk=1i ' akXk - j的最優(yōu)值為m(i,j)，即m(i,j)是背包容量為j，可選擇物品為1，2，i時(shí)背包問題的最優(yōu)值。由背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i,j)的遞歸式如下：；maxm(i 1, j),m(i, j aj+gj 蘭 am(i, j)=丿Lm(i -1, j)0 蘭 jy按此遞歸式計(jì)算出的m(n,b)為最優(yōu)值。算法所需的計(jì)算時(shí)間為 O(nb)習(xí)題

29、4-3給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如圖 3-2所示。試設(shè)計(jì)個(gè)算法，計(jì)算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。738810274445265數(shù)字三角形分析與解答： 記f(uj)為至ij元素的最大路徑值，aj ：元素(i,j)之值。遞歸式：F(uij)=maxf(ui-i,j)+aij, f(ui-i,j+i)+aij(i=1,j=1,i)經(jīng)過一次順推，便可求出從頂至底n個(gè)數(shù)的n條路徑(這n條路徑為至底上n個(gè)數(shù)的n個(gè)最大總和的路徑)，求出這n個(gè)總和的最大值，即為正確答案。數(shù)據(jù)結(jié)構(gòu)：ai,j.val:三角形上的數(shù)字， ai,j.f:由(1，1)至該點(diǎn)的最大總和路徑的總和值。

30、type no de=recordval, f: in teger;end;var a:array 1. maxn, 1.max n of no de; procedure fin dmax;begi na 1,1. f :=a1,1.val;for i:=2 to n dofor j:=1 to i do beg in 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,j-1. f+ai,j.val;if (j<>i) an d(a i-1,j.f+ai,j

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

32、知_；2 -_；n 0。由此可知 丄一1，1 乞n -1 貪心選擇性質(zhì)：當(dāng)1 W時(shí)問題無解。當(dāng).<<W時(shí)，存在0-1背包問題的一個(gè)最優(yōu)解S 1,2,., n使得1 S。事實(shí)上，設(shè) S 1,2,., n使0-1背包問題的一個(gè)最優(yōu)解，且V S。對(duì)任意S，取S二S 一1 -i，那么&滿足貪心選擇性質(zhì)的最優(yōu)解。習(xí)題5-2 Fibonacci序列的Huffman編碼試證明：假設(shè)n個(gè)字符的頻率恰好是前n個(gè)Fibonacci數(shù)，用貪心法得到它們的Hufman編碼樹一定為一棵“偏斜樹。圖哈夫曼編碼樹證明：n個(gè)字符的頻率恰好是前n個(gè)Fib on acci數(shù)，那么相應(yīng)的哈夫曼編碼樹自底向上第i

33、ii個(gè)內(nèi)結(jié)點(diǎn)中的數(shù)為V fk。用數(shù)學(xué)歸納法容易證明V fk：fi2。k 30k 30因fl = 1,f2=1,f3=2,可知i = 1時(shí)，上述結(jié)論成立。i設(shè)對(duì)i+2上述結(jié)論成立，即有 7 fk£2，因k衛(wèi)ii -1fifi 2 fifk fi .1 - 7 fk，k呂k=1說明對(duì)i+3上述結(jié)論成立.該性質(zhì)保證了頻率恰好是前n個(gè)Fib on acci數(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í)間分別為si和fi,i =1 n，

34、且 f1 ： f2:：f n?？梢詫個(gè)活動(dòng)1, 2,，n看作實(shí)直線上的n個(gè)半閉活動(dòng)區(qū)間si, f i), i =1n。所討論的問題實(shí)際上是求這 n個(gè)半閉區(qū)間的最大重疊數(shù)。 因?yàn)橹丿B的活動(dòng)區(qū)間所相應(yīng)的活動(dòng) 是互不相容的。假設(shè)這 n個(gè)活動(dòng)區(qū)間的最大重疊數(shù)為 m,那么這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í)刻si，就將活動(dòng)i安排在一個(gè)空閑的會(huì)場(chǎng)中。遇到一個(gè)結(jié)束時(shí)候fi，就將活動(dòng)

35、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)的排序，這需要 O(n log n)計(jì)算時(shí)間。具體算法描述如下。public static int greedy(po in t x)int sum=O, curr=O, n=x.len gth;MergeSort.mergeSort(x);for (i nt i=0; i<n ;i+) if (xi.leftend() curr+;else curr-;處理xi=xi+1的情況if ( i = n-1 II

36、xi 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, f1: n;Output x1:m, 1: n;Beg in對(duì)數(shù)組s和f中的2n個(gè)元素排序存入數(shù)組y1:2n中； 空閑棧清空；d數(shù)組所有元素置初值0；For i=1 to 2n doBegi nIf元素yi原屬于s thenIf空閑棧不空then取出棧頂場(chǎng)地 j; dj=dj+1;

37、yi存入 xj, dj;If元素yi原屬于f then設(shè)其相應(yīng)的s存于xj,k中，將j存入空閑棧中；EndFor i= 1 to m doFor j=1 to dj doOutput xi,j;End習(xí)題5-5刪數(shù)問題問題描述給定n位正整數(shù)a，去掉其中任意k豈n個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(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.

38、println(0); return;while (k>0) for (i=0; (i<a.le ngth()-1)&&(a.charAt(i)<=a.charAt(i+1); i+) a= a.Remove(i,1); k-;while (a.length()>1 && a.charAt(0)= '' a=a.Remove(0,1); System.out.pri ntl n( a);習(xí)題6-1子集和冋題子集和問題的一個(gè)實(shí)例:A, sum .。其中，A = 知a2,，an是一個(gè)正整數(shù)的集合，sum是一個(gè)正整數(shù)。子集和問題

39、判定是否存在A的一個(gè)子集A1,使得a = sum。試設(shè)計(jì)一個(gè)解子集和問題的回溯法。分析與解答：設(shè)計(jì)解子集和問題的回溯法如下。Algorithm subset-sum beginFor j=1 to n doBegi nsp=0; t=sum; i=j; fini sh=false; repeatif t>=ai the nbeginsp=sp+1 ； ssp=i; t=t-ai; if t=0 then i=n;en d;i=i+1;while i>n doif sp>1 the nbeginif t=0 the n out; t=t+assp; i=ssp+1; sp=sp

40、-1begi n fini sh=true; i=1 end un til finishend end習(xí)題6-2中國(guó)象棋的半個(gè)棋盤如下圖，馬自左下角往右上角跳。規(guī)定只許向右跳，不許 向左跳，計(jì)算所有的行走路線。Algorithm chessBegintop=0; y0=0; x0=0; di=1; r=0;push;repeatpop;while di<=4 dobeging=xO+xdi; h=yO+ydi;if (g=8) and (h=4) the n outelse begin di=di+1 ； push; x0=g; y0=h; di=1 end endun til empt

41、yendalgorithm pushbegin top=top+1 ； sxtop=xO; sytop=yO; dtop=di;endalgorithm popbeginxO=sxtop; yO=sytop; di =dtop; top=top 1;習(xí)題6-3.在n個(gè)連成排的方格內(nèi)填入 R或B ,但相鄰連個(gè)方格內(nèi)不能都填R。計(jì)算所有可能的填法。RBBRBAlgorithm Red-Black;BeginFor i=1 to n do bi=0;T=1;Repeatbt=bt+1 ;if bt>2 then 回溯 begin bt=0 ; t=t-1 ; end else beg inif

42、 bt=2 then at= B 'else if at-1= 'R'then t=t-1 else at= R'if t=n the n output a else t=t+1 endun til t=0第七章分支限界法習(xí)題7-1.試寫出采用分支界限法求解下面的0、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)，下界為S|(X)為Su(X)中減去最后放入背包的Xi* 1的物品

43、的相應(yīng)局部?jī)r(jià)值。解答：(X1X2X3X4) wx,px U,L0, 0(00?)0, 08(000?)0, 01 0, 0 /(?)38,322,1032,22.38,32n=4, m=15 w=2,4,6,9 p=10,10,12,1864, 106, 2075(01?)2,106,206, 129) (001?)4,1010(010?)(011?)10,2236,22 (10?)2,1012(100?)8,22(101?)(110?)38,32 /(11?)12,32153,3838,32(111?)0,09,186,1215,304,1013,28X10,22X19,402,1011,2

44、88,2217,406,2015,382?_12,32X21,50一 20 3121(0000(0001X0010)(0011)(0100)(0101)(0110) (0111)(1000)(1001)(1010)(1011)(110(520,20(1101)38,381110) (1111)習(xí)題7-2.寫出用分支界限法求解下面的重排九宮問題的算法。81263754開始狀態(tài)12384765目標(biāo)狀態(tài)解答：我們對(duì)九宮中的位置做如下的編號(hào):位置編號(hào)123894765那么初始狀態(tài)用向量 So=( 8，1，2，3，4，5，7, 0，6)表示，目標(biāo)狀態(tài)用 S*=( 1，2，3, 4， 5， 6， 7， 8

45、， 0)表示。我們使用一個(gè)堆heap,將啟發(fā)函數(shù)值 H(x)最小的狀態(tài)x置于堆頂優(yōu)先搜索。H(x)定義如 下：H(x)=h i(x)+3h 2(x)其中，hi(x)為狀態(tài)x與目標(biāo)狀態(tài)不相同的數(shù)字的數(shù)目，h2(x)=v N(y)，y這里，0,1y和其后繼的相對(duì)位置不變N(y)二 1,2,y處于中心其它算法：AlgorithmLC(So, S )In put:初始狀態(tài)向量 S0 ,目標(biāo)狀態(tài)S ；Output:到達(dá)目標(biāo)狀態(tài)的狀態(tài)序列；Beg inS=S。；if S 目標(biāo)狀態(tài) S then Output(S 及其所有前驅(qū))else add (S, heap) while heap 非空 do取出堆he

46、ap頂部狀態(tài)E ;for E的每個(gè)可能的后繼狀態(tài)x doif x為目標(biāo)狀態(tài) S then Output(x及其所有前驅(qū));returnelse計(jì)算x的啟發(fā)函數(shù)H(x);add(x, heap)en difen dforen dwhileend第八章NP完全問題習(xí)題8-1證明析取范式的可滿足性問題屬于P類。分析與解答：析取范式是由因子之和的和式給出的。這里因子是指變量x或x，每個(gè)因子之積稱為個(gè)析取式。例如x1x2+x2x3+ x1 X2X3就是個(gè)析取范式。m_設(shè)給定一個(gè)析取范式- -fi(x1,x2,.xn)，其中fi(x1,x2,.xn)是變量 為或X，j=1ni 1的一個(gè)析取范式，i=1m。

47、：是可滿足的，當(dāng)且僅當(dāng)存在i, 1二i二m，使fi(X1, X2,.xn)是可滿足的。如果有一個(gè)多項(xiàng)式時(shí)間算法能判斷任何一個(gè)析取式的可滿足性，那么用該算法對(duì):的每個(gè)析取項(xiàng)逐一判斷就可以在多項(xiàng)式時(shí)間內(nèi)確定析取范式:的可滿足性。因此，問題可簡(jiǎn)化為找一個(gè)確定析取式可滿足性的多項(xiàng)式時(shí)間算法。設(shè)析取范式 f(X1, X2,.Xn)=-:九沢-汀，其中xj, xj |1 一 j _ n?？梢栽O(shè)計(jì)在 0(n+k)時(shí)間內(nèi)確定析取式 f (X1, X2,.Xn)v 2.J k可滿足性的算法。因此，析取范式的可滿足性問題是多項(xiàng)式時(shí)間可解的，即它屬于P類。第九章近似算法習(xí)題9-1瓶頸旅行售貨員冋題瓶頸旅行售貨員問題

48、是要找出圖G=(V,E)的一個(gè)哈密頓回路，且使回路中最長(zhǎng)邊的長(zhǎng)度最小。假設(shè)費(fèi)用函數(shù)滿足三角不等式，給出解此問題的性能比為3的近似算法。(提示：遞歸地證明，可以通過對(duì) G的最小生成樹進(jìn)行完全遍歷并跳過某些項(xiàng)點(diǎn)，但不能跳過多于2個(gè)連續(xù)的中間頂點(diǎn)，以此方式訪問最小生成樹中每個(gè)頂點(diǎn)恰好一次。)分析與解答：解瓶頸旅行售貨員問題的性能比為3的近似算法描述如下：Void approxTSP(Graph G) 選擇任一頂點(diǎn)r V ； 找出G的一棵以r為根的最小瓶頸生成樹 T ； 選取T的一條邊(p,q)作為哈密頓回路 H的一條邊； 遍歷樹T,跳過不多于兩個(gè)連續(xù)的重復(fù)頂點(diǎn)，遞歸構(gòu)造H的其他邊; 將所得到的哈密頓

49、回路H作為計(jì)算結(jié)果返回.習(xí)題9-2可滿足問題的近似算法 問題描述設(shè)是一個(gè)含有n個(gè)變量和m個(gè)合取項(xiàng)的合取范式。關(guān)于:的最大可滿足性問題要求確定的最多個(gè)數(shù)的合取式使這些合取式可同時(shí)滿足。設(shè)k是的所有合取式中因子個(gè)1數(shù)的最小值。證明下面的解最大可滿足性問題的近似算法mSAT的相對(duì)誤差為。k + 1Set mSAT(a)/ xi, 1 < H： n ,是a中n個(gè)變量；Ci ，1 < m，是的m個(gè)合取項(xiàng)。c1= I;left= Ci | 1 _ i _ m；lit=刃，為|1乞i巴n ;while(lit含有在left的合取式中出現(xiàn)的因子)設(shè)y是lit的在left的合取式中出現(xiàn)次數(shù)最多的因子

50、; 設(shè)r是left中含有因子y的所有合取式的集合；c仁 c1J r;left=left-r;lit=lit-y, y;return(c1);第十章隨機(jī)算法習(xí)題10-1模擬正態(tài)分布隨機(jī)變量1(x-a)2在實(shí)際應(yīng)用中，常需要模擬服從正態(tài)分布的隨機(jī)變量，其密度函數(shù)為 e云廠，其中，2 二a為均值，二為標(biāo)準(zhǔn)差。如果s和t是(-1，1)中均勻分布的隨機(jī)變量，且s2 t2 < 1 ，令p = s t2, q= (-21 np)/p,u = sq, v=tq，那么u和v是服從標(biāo)準(zhǔn)正態(tài)分布(a =0,-1)的兩個(gè)互相獨(dú)立的隨機(jī)變量。(1) 利用上述事實(shí)，設(shè)計(jì)一個(gè)模擬標(biāo)準(zhǔn)正態(tài)分布隨機(jī)變量的算法。(2) 將

51、上述算法擴(kuò)展到一般的正態(tài)分布。 分析與解答：(1) 模擬標(biāo)準(zhǔn)正態(tài)分布隨機(jī)變量的算法如下。public double Norm()double s,t,p,q;while (true) s=2*fRa ndom()-1;t=2*fRa ndom()-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 x=Norm();return a+b*x;習(xí)題10-2整數(shù)因子分解算法假設(shè)已有

52、一個(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(i nt 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ù) x1 , x2 ,., x n ，求這 n 個(gè)數(shù)在實(shí)軸上相鄰 2 個(gè)數(shù)之 間的最大差值。假設(shè)對(duì)任何實(shí)數(shù)的下取整方法

53、耗時(shí)為 O(1) ，設(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 i=1, i<=n-1; i+) counti=0; lowi=maxx; highi=minx;/將 n