算法設(shè)計與分析課后習(xí)題集答案

1、第一章3. 最大公約數(shù)為1。快1414倍。程序1-2的while循環(huán)體做了10次，程序1-3的while循環(huán)體做了14141次（14142-2循環(huán)）8.（1）畫線語句的執(zhí)行次數(shù)為。（2）畫線語句的執(zhí)行次數(shù)為。（3）畫線語句的執(zhí)行次數(shù)為 。（4）當(dāng)n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為 ，當(dāng)n為偶數(shù)時畫線語句的執(zhí)行次數(shù)為 。10.（1） 當(dāng)時，所以，可選 ，。對于，所以，。（2） 當(dāng)時，所以，可選 ，。對于，所以，。（3） 由（1）、（2）可知，取，當(dāng)時，有，所以。11. (1) 當(dāng)時，所以，。可選 ，。對于，即。（2） 當(dāng) 時，所以 ，。可選 ，。對于 ，即 。（3）因為，。當(dāng) 時，。所以，可選 ，對

2、于，即 。第二章2-17. 證明：設(shè)，則 。當(dāng) 時，。所以，。第五章5-4.SolutionType DandC1(int left,int right)while(!Small(left,right)&&left<right)int m=Divide(left,right);if(x<P(m) right=m-1; else if(x>Pm) left=m+1; else return S(P)5-7.template <class T>int SortableList<T>:BSearch(const T&x,int lef

3、t,int right) constif (left<=right)int m=left+(right-left+1)/3;if (x<lm) return BSearch(x,left,m-1);else if (x>lm) return BSearch(x,m+1,right);else return m;return -1;7m=left+(right-left+1)/3 不能用：m=(left+right)/3 ，兩者不同。 受對半搜索的影響：m=(left+right)/2和m=left+(right-left+1)/2是一樣的9462353445231101256

4、7677801234560證明：因為該算法在成功搜索的情況下，關(guān)鍵字之間的比較次數(shù)至少為，至多為。在不成功搜索的情況下，關(guān)鍵字之間的比較次數(shù)至少為，至多為。所以，算法的最好、最壞情況的時間復(fù)雜度為。假定查找表中任何一個元素的概率是相等的，為，那么，不成功搜索的平均時間復(fù)雜度為，成功搜索的平均時間復(fù)雜度為。其中，是二叉判定樹的內(nèi)路徑長度，是外路徑長度，并且。11.步數(shù)012345初始時11111111111211111311111411111排序結(jié)果11111步數(shù)01234567初始時55834321423358523234585332345854233458552334558排序結(jié)果23345

5、5812.（1）證明：當(dāng)或或時，程序顯然正確。當(dāng)n=right-left+1>2時，程序執(zhí)行下面的語句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);首次遞歸StoogeSort(left,right-k);時，序列的前2/3的子序列有序。當(dāng)遞歸執(zhí)行StoogeSort(left+k,right);時，使序列的后2/3的子序列有序，經(jīng)過這兩次遞歸排序，使原序列的后1/3的位置上是整個序列中較大的數(shù)，即序列后1/3的位置上數(shù)均大于前2/3的數(shù)

6、，但此時，前2/3的序列并不一定是有序的。再次執(zhí)行StoogeSort(left,right-k);使序列的前2/3有序。經(jīng)過三次遞歸，最終使序列有序。所以，這一排序算法是正確的。（2）最壞情況發(fā)生在序列按遞減次序排列。，。設(shè)，則。冒泡排序最壞時間復(fù)雜度為，隊排序最壞時間復(fù)雜度為，快速排序最壞時間復(fù)雜度為。所以，該算法不如冒泡排序，堆排序，快速排序。13.template <class T>select (T&x,int k)if(m>n) swap(m,n);if(m+n<k|k<=0) cout<<"Out Of Bounds&q

7、uot; return false;int *p=new tempk;int mid,left=0,right=n-1,cnt=0,j=0,r=0;for(int i=0;i<m;i+)while(k>0)domid=(left+right)/2;if(amid<bi) left=mid;else if(amid>bi) right=mid;else cnt=mid; break;while(left<right-1)if(aleft<bi) cnt=left;else cnt=left-1;if(k>cnt)if(cnt>0)for(j=0;j

8、<cnt;j+)tempj=ar;r+;left=cnt;k-=cnt;elsetempj=bi;left=0;k-;elsefor(j=0;j<k;j+)tempj=ar;r+;left=cnt;k-=cnt;return tempk-1;第六章1.由題可得：，所以，最優(yōu)解為，最大收益為。8.(n-1)%(K-1)=(11-1)%(3-1)=0, 故無需補充虛游程。9普里姆算法。 因為圖G是一個無向連通圖。 所以n-1<=m<=n (n-1)/2; O(n)<=m<=O(n2);克魯斯卡爾對邊數(shù)較少的帶權(quán)圖有較高的效率，而，此圖邊數(shù)較多，接近完全圖，故選用

9、普里姆算法。10. T仍是新圖的最小代價生成樹。 證明：假設(shè)T不是新圖的最小代價生成樹，T是新圖的最小代價生成樹，那么cost(T)<cost(T)。有cost(T)-c(n-1)<cost(t)-c(n-1)，即在原圖中存在一顆生成樹，其代價小于T的代價，這與題設(shè)中T是原圖的最小代價生成樹矛盾。所以假設(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)=mi

10、n6+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(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)+B

11、cost(4,6),c(7,8)+Bcost(4,7)=min7+9,3+9=12（0，2，4，7，8）2.向后遞推的計算過程如上題所示 向前遞推過程如下： cost(5,8)=0 cost(4,6)=7,cost(4,7)=3 cost(3,3)=min1+cost(4,6),4+cost(4,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

12、(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(1,0)=2, d(2,2)=4, d(3,4)=7, d(4,7)=8),路徑長為12。9. char A8=0,x,z,y,z,z,y,x B8=0,z,x,y,y,z,x,z (a) cij （b）sij所以，最長公共字串為 (x,y,z,z)。11. void LCS:CLCS ( int i,

13、 int j ) if ( i = = 0 | j = = 0) return;if (xi=yj) CLCS ( i-1,j-1);Cout<<ai; else if ( ci-1j>=cij-1) CLCS (i-1,j); else CLCS (i,j-1); 12. LCS:LCS(int nx, int ny, char *a, char *b) m=nx; n=ny; x=a; y=b; c=new int*2; for(int i=0; i<2; i+) ci=new int n+1;int LCS:LCSLength() c10=0; /0列置0 for

14、(int i=0; i<=n; i+) c0i=0; /0行置0 for(i=1; i<=m; i+) for(int j=1; j<=n; j+) if(xi=yj) c1j=c0j-1+1; /xi=yj時，左上格+1 else if(c0j>=c1j-1) c1j=c0j; /上格左格，則取上格 else c1j=c1j-1; /否則取左格 for(j=0; j<=n; j+) c0j=c1j; return c1n; /或return c0n也行15. , , , , , ,第八章1狀態(tài)空間：描述問題的各種可能的情況，一種情況對呀狀態(tài)空間的一個狀態(tài)。顯示約

15、束：用于規(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)?；罱Y(jié)點：回溯法從開始結(jié)點出發(fā)，以深度優(yōu)先的方式搜索整個解空間，這個開始結(jié)點就成為一個活結(jié)點。未檢測的結(jié)點稱為活結(jié)點擴展結(jié)點：算法從x出發(fā)，訪問x的摸個后繼結(jié)點y，則x被稱為擴展結(jié)點約束函數(shù)：一個約束函數(shù)是關(guān)于部分向量的函數(shù)Bk(x0,x1.xk),它被定義為：如果可以判定Y的子樹上不含任何答案狀態(tài)

16、，則Bk(x0,x1.xk)為false,否則為true.剪枝函數(shù)：約束函數(shù)和限界函數(shù)的目的相同，都是為了剪去不必要搜索的子樹，減少問題求解所需實際生成的狀態(tài)節(jié)點數(shù)，他們統(tǒng)稱為剪枝函數(shù)2int count=0;int N=1;bool place(int k,int ,I,int*x)For(int j=0,j<k,j+)If(xj=i)|(abs(xj-j)=abs(j-k)Return false;Return true;Void nqueens(int k,int n,int *x)For(int i=0;i<n;i+) if(place(k,i,x) Xk=i;If(k=n

17、-1)For(i=0;i<n;i+)cout<<xi;cout<<endl;count+;Else if(count<N) nqueens(k+1,n,x) Void nqueens(int n,int *x)Nqueens(0,n,x);6.狀態(tài)空間樹如下：可行解：（1，0，0，1，0，1）， （0，1，1，0，0，1），（1，0，1，0，0，0，1）， （0，0，0，0，1，0，1）7. 可行解為： （1）（1，0，0，1，0，1）， （0，1，1，0，0，1），（1，0，1，0，0，0，1）， （0，0，0，0，1，0，1） （2）（1，0，1）， （0，1，0，0，1，1），（1，0，0，0，1，0，1）， （0，1，0，1，0，0，1） （3）（1，0，1）， （0，1，0，0，1，1），（0，0，1，1，0，1）， （0，0，1，1，0，1） 第三組的計算時間最少，其次是第二組，最慢的是第一組。第九章9.1template<class T>void JS<T>:GenerateAns(int *x, int &k)