算法設計課程習題答案

1、算法設計課程習題答案第一章1-1什么是算法？它與計算過程和程序有什么區(qū)別？算法是指求解一個問題所需要的具體步驟和方法。它是指令的有限序列。算法有一系列明確定義的基本指令序列所描述的，求解特定問題的過程，它能夠?qū)戏ǖ妮斎耄谟邢迺r間內(nèi)產(chǎn)生所要求的輸出，取消有窮性限制則是計算過程；而程序是算法的描述。1-11使用歸納法證明漢諾塔函數(shù)的正確性。用數(shù)學歸納法證明漢諾塔函數(shù)對任何n（即n可以是任何正整數(shù)）有解。（1）當盤子數(shù)n=1時，只需直接將此盤從A柱搬到C柱即可。（2）現(xiàn)假設n=k時有解，即可以將k個盤子（在不違反規(guī)則的情況下）從一個源柱，通過一個中間柱移到目的柱上。（3）現(xiàn)在證明n=k+1時也有

2、解。開始時A柱上的k+1個盤子可以看成由k個盤和最底下的一個最大盤組成。根據(jù)歸納假設這k個盤可以（在不違反規(guī)則的情況下）通過C柱移到B柱上（在這k個盤的移動過程中，最大盤可以看成不存在）。完成這一大步后，只要將A柱上的最大盤直接搬到C柱上。再根據(jù)歸納假設B柱上的這k個盤可以（在不違反規(guī)則的情況下）通過A柱移到C柱上。至此證明結束。第二章2-8確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，計算它們的漸近時間復雜度。（1）程序步為畫線語句的執(zhí)行次數(shù)為。劃線語句的執(zhí)行次數(shù)應該理解為一個整體。（2）畫線語句的執(zhí)行次數(shù)為 。（3）畫線語句的執(zhí)行次數(shù)為 。（4）當n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為 ，當n

3、為偶數(shù)時畫線語句的執(zhí)行次數(shù)為 。 2-11設有和如下所示，分析為、還是。(1) 當時，所以，?？蛇x ，。對于，即。注意：是f(n)和g(n)的關系。(2) 當 時，所以，?？蛇x ，。對于 ，即 。（3）因為 ，。當 時，。所以，可選 ，對于，即 。（4）因為，。當時，所以，可選，,對于，即。（5）因為,。當n0時，,所以取, ,對于，即。第四章4-10識別圖4-15的圖的關節(jié)點，畫出它們的雙連通分圖。01732456圖G101632457圖G2圖G1的關節(jié)點3、7、1，圖G2關節(jié)點沒有關節(jié)點。它們的雙連通圖如下。01732456圖G101632457圖G20-1-32-3-43-77-6-5第

4、五章5-11對兩組數(shù)據(jù)（1,1,1,1,1）和（5,5,8,3,4,3,2）執(zhí)行程序5-12的快速排序，按照 表5-1的格式分別列表表示執(zhí)行過程。步數(shù)012345初始時11111111111211111311111411111排序結果11111步數(shù)01234567初始時55834321423358523234585332345854233458552334558排序結果2334558第六章11.由題可得：，所以，最優(yōu)解為，最大收益為。3.設有帶時限的作業(yè)排序n=7，(p0，p1,p6)=(3,5,20,18,1,6,30)；（d0,d1,d6）=(1,3,4,3,2,1,2)以此實例為輸入的最

5、優(yōu)解和最大收益。按收益大小遞減排序：p6,p2,p3,p5,p1,p0,p4=(30,20,18,6,5,3,1)最優(yōu)解： (0，0，1，1，0，1，1) 由作業(yè)2,3,5,6產(chǎn)生最大收益：748.第七章7-1. Bcost(1,0)=0; Bcost(2,1)=c(1,1)+Bcost(1.0)=5 Bcost(2,2)=c(1,2)+Bcost(1,0)=2 Bcost(3,3)=minc(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)=min6+2,3+5=8 Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7 Bcost(3,5)=minc(1,5

6、)+Bcost(2,1),c(2,5)+Bcost(2,2)=min3+5,8+2=8 Bcost(4,6)=minc(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)=min1+8,6+7,6+8=9 Bcost(4,7)=minc(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)=min4+8,2+7,6+8=9Bcost(5,8)=minc(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)=min7+9,3+9=127-9. char A8=0,x,z,y,z,z

7、,y,x B8=0,z,x,y,y,z,x,z (a) cij （b）sij所以，最長公共字串為 (x,y,z,z)。7-15 , , , , , , ,8-1狀態(tài)空間：描述問題的各種可能的情況，一種情況對呀狀態(tài)空間的一個狀態(tài)。顯示約束：用于規(guī)定每個xi取值的約束條件稱為顯示約束隱式約束：用于判定一個候選解是否為可行解的條件問題狀態(tài)：在狀態(tài)空間樹中的每個節(jié)點稱為一個問題狀態(tài)解狀態(tài)：如果從根到樹中某個狀態(tài)的路徑代表一個作為候選解的元組，則該狀態(tài)為解狀態(tài)答案狀態(tài)：如果從根到樹中某個狀態(tài)的路徑代表一個作為可行解的元組，則該狀態(tài)為解狀態(tài)。活結點：回溯法從開始結點出發(fā)，以深度優(yōu)先的方式搜索整個解空間，這個開始結點就成為一個活結點。未檢測的結點稱為活結點擴展結點：算法從x出發(fā)，訪問x的摸個后繼結點y，則x被稱為擴展結點約束函數(shù)：一個約束函數(shù)是關于部分向量的函數(shù)Bk(x0,x1.xk),它被定義為：如果可以判定Y的子樹上不含任何答案狀態(tài)，則Bk(x0,x1.xk)為false,否則為true.剪枝函數(shù)：約束函數(shù)和限界函數(shù)的目的相同，都是為了剪去不必