算法設(shè)計(jì)與分析C++語言描述陳慧南版課后答案

1、-. z.第一章1-3. 最大公約數(shù)為1?？?414倍。主要考慮循環(huán)次數(shù)，程序1-2的while循環(huán)體做了10次，程序1-3的while循環(huán)體做了14141次14142-2循環(huán)假設(shè)考慮其他語句，則沒有這么多，可能就601倍。第二章2-8.1畫線語句的執(zhí)行次數(shù)為。劃線語句的執(zhí)行次數(shù)應(yīng)該理解為一格整體。2畫線語句的執(zhí)行次數(shù)為。3畫線語句的執(zhí)行次數(shù)為。4當(dāng)n為奇數(shù)時(shí)畫線語句的執(zhí)行次數(shù)為，當(dāng)n為偶數(shù)時(shí)畫線語句的執(zhí)行次數(shù)為。2-10.1當(dāng)時(shí)，所以，可選，。對(duì)于，所以，。2當(dāng)時(shí)，所以，可選，。對(duì)于，所以，。3由1、2可知，取，當(dāng)時(shí)，有，所以。2-11. (1) 當(dāng)時(shí)，所以，?？蛇x，。對(duì)于，即。注意：是f(

2、n)和g(n)的關(guān)系。2當(dāng)時(shí)，所以，。可選，。對(duì)于，即。3因?yàn)椋?。?dāng)時(shí)，。所以，可選，對(duì)于，即。第二章2-17. 證明：設(shè)，則。當(dāng)時(shí)，。所以，。第五章5-4. SolutionType DandC1(int left,int right)while(!Small(left,right)&leftright)int m=Divide(left,right);if(*Pm) left=m+1; else return S(P)5-7. template int SortableList:BSearch(const T&*,int left,int right) constif (left=righ

3、t)int m=(right+left)/3;if (*lm) return BSearch(*,m+1,right);else return m;return -1;第五章9證明：因?yàn)樵撍惴ㄔ诔晒λ阉鞯那闆r下，關(guān)鍵字之間的比擬次數(shù)至少為，至多為。在不成功搜索的情況下，關(guān)鍵字之間的比擬次數(shù)至少為，至多為。所以，算法的最好、最壞情況的時(shí)間復(fù)雜度為。假定查找表中任何一個(gè)元素的概率是相等的，為，則，不成功搜索的平均時(shí)間復(fù)雜度為，成功搜索的平均時(shí)間復(fù)雜度為。其中，是二叉判定樹的路徑長度，是外路徑長度，并且。11.步數(shù)012345初始時(shí)11111111111211111311111411111排序結(jié)果1

4、1111步數(shù)01234567初始時(shí)55834321423358523234585332345854233458552334558排序結(jié)果233455812.1證明：當(dāng)或或時(shí)，程序顯然正確。當(dāng)n=right-left+12時(shí)，程序執(zhí)行下面的語句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k); = 1 * GB3 首次遞歸StoogeSort(left,right-k);時(shí)，序列的前2/3的子序列有序。 = 2 * GB3 當(dāng)遞歸執(zhí)行StoogeSo

5、rt(left+k,right);時(shí)，使序列的后2/3的子序列有序，經(jīng)過這兩次遞歸排序，使原序列的后1/3的位置上是整個(gè)序列中較大的數(shù)，即序列后1/3的位置上數(shù)均大于前2/3的數(shù)，但此時(shí)，前2/3的序列并不一定是有序的。 = 3 * GB3 再次執(zhí)行StoogeSort(left,right-k);使序列的前2/3有序。經(jīng)過三次遞歸，最終使序列有序。所以，這一排序算法是正確的。2最壞情況發(fā)生在序列按遞減次序排列。，。設(shè)，則。冒泡排序最壞時(shí)間復(fù)雜度為，隊(duì)排序最壞時(shí)間復(fù)雜度為，快速排序最壞時(shí)間復(fù)雜度為。所以，該算法不如冒泡排序，堆排序，快速排序。13. template select (T&*,i

6、nt k)if(mn) swap(m,n);if(m+nk|k=0) coutOut Of Bounds; return false;int *p=new tempk;int mid,left=0,right=n-1,t=0,j=0,r=0;for(int i=0;i0)domid=(left+right)/2;if(amidbi) right=mid;else t=mid; break;while(leftright-1)if(aleftt)if(t0)for(j=0;jt;j+)tempj=ar;r+;left=t;k-=t;elsetempj=bi;left=0;k-;elsefor(j

7、=0;jk;j+)tempj=ar;r+;left=t;k-=t;return tempk-1;第六章1.由題可得：，所以，最優(yōu)解為，最大收益為。8.第六章6-9.普里姆算法。因?yàn)閳DG是一個(gè)無向連通圖。所以n-1=m=n (n-1)/2; O(n)=m=O(n2);克魯斯卡爾對(duì)邊數(shù)較少的帶權(quán)圖有較高的效率，而，此圖邊數(shù)較多，接近完全圖，應(yīng)選用普里姆算法。6-10. T仍是新圖的最小代價(jià)生成樹。證明：假設(shè)T不是新圖的最小代價(jià)生成樹，T是新圖的最小代價(jià)生成樹，則cost(T)cost(T)。有cost(T)-c(n-1)cost(t)-c(n-1)，即在原圖中存在一顆生成樹，其代價(jià)小于T的代價(jià)，這

8、與題設(shè)中T是原圖的最小代價(jià)生成樹矛盾。所以假設(shè)不成立。證畢。第七章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)+Bcost(2,1),c(2,5)+Bcost(2,2)=min3+5,8+2=8 Bcost(4,6)=minc(3,6)+Bcost(

9、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=122.向后遞推的計(jì)算過程如上題所示向前遞推過程如下： cost(5,8)=0 cost(4,6)=7,cost(4,7)=3 cost(3,3)=min1+cost(4,6),4+cost(4

10、,7)=7, cost(3,4)=min6+cost(4,6),2+cost(4,7)=5cost(3,5)=min6+cost(4,6),2+cost(4,7)=5cost(2,1)=min3+cost(3,3),3+cost(3,5)=8cost(2,2)=min6+cost(3,3),8+cost(3,5),5+cost(3,4)=10cost(1,0)=min5+cost(2,1),2+cost(2,2)=12所以，d(4,6)=d(4,7)=8, d(3,3)=d(3,4)=d(3,5)=7, d(2,1)=5, d(2,2)=4, d(1,0)=2從s到t的最短路徑為 (0, d(

11、1,0)=2, d(2,2)=4, d(3,4)=7, d(4,7)=8),路徑長為12。第七章9. char A8=0,*,z,y,z,z,y,* B8=0,z,*,y,y,z,*,z (a) cij bsij所以，最長公共字串為 (*,y,z,z)。第七章11. void LCS:CLCS ( int i , int j ) if ( i = = 0 | j = = 0) return;if (cij = = ci-1j-1+1) CLCS ( i-1,j-1); Cout=cij-1) CLCS (i-1,j); else CLCS (i,j-1); 12. int LCS:LCSLen

12、gth() for ( int i =1; i=m; i+) ci0=0;for (i =1; i=n; i+) c0i=0;for (i =1; i=m; i+) for (int j =1; j=cij-1) cij=ci-1j; else cij=cij-1;return cmn; 15. , , , , , ,8-1狀態(tài)空間：描述問題的各種可能的情況，一種情況對(duì)呀狀態(tài)空間的一個(gè)狀態(tài)。顯示約束：用于規(guī)定每個(gè)*i取值的約束條件稱為顯示約束隱式約束：用于判定一個(gè)候選解是否為可行解的條件問題狀態(tài)：在狀態(tài)空間樹中的每個(gè)節(jié)點(diǎn)稱為一個(gè)問題狀態(tài)解狀態(tài)：如果從根到樹中*個(gè)狀態(tài)的路徑代表一個(gè)作為候選解的元

13、組，則該狀態(tài)為解狀態(tài)答案狀態(tài)：如果從根到樹中*個(gè)狀態(tài)的路徑代表一個(gè)作為可行解的元組，則該狀態(tài)為解狀態(tài)?；罱Y(jié)點(diǎn)：回溯法從開場結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間，這個(gè)開場結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)。未檢測的結(jié)點(diǎn)稱為活結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)：算法從*出發(fā)，訪問*的摸個(gè)后繼結(jié)點(diǎn)y，則*被稱為擴(kuò)展結(jié)點(diǎn)約束函數(shù)：一個(gè)約束函數(shù)是關(guān)于局部向量的函數(shù)Bk(*0,*1.*k),它被定義為：如果可以判定Y的子樹上不含任何答案狀態(tài)，則Bk(*0,*1.*k)為false,否則為true.剪枝函數(shù)：約束函數(shù)和限界函數(shù)的目的一樣，都是為了剪去不必要搜索的子樹，減少問題求解所需實(shí)際生成的狀態(tài)節(jié)點(diǎn)數(shù)，他們統(tǒng)稱為剪枝函數(shù)8-2bool place(int k,int ,I,int*)For(int j=0,jk,j+) If(*j=i)|(abs(*j-j)=abs(j