算法导论中文版答案
《算法导论》参考答案
第2章第3章第4章第5章第6章第7章第8章第9章第15章第16章第24章第25章
第2章
2.1-1
2.1-2
2.1-3
2.1-4
2.2-1
2.2-2
2.2-3
2.2-4
2.3-1
2.3-2
void Merge(int *A,int p,int q,int r) {
//构建左半部分和右半部分的辅助数组 int n1=q-p+1; int n2=r-q;
int *L=new int[n1]; int *R=new int[n2]; for (int i=0;i
L[i]=A[p+i-1];
}
for(int j=0;j
R[j]=A[q+j]; }
int i=0; int j=0; int k=p-1;
while((i
if(L[i]
A[k]=L[i]; i++; } else {
A[k]=R[j]; j++; } k++; }
while(i
A[k]=L[i]; i++; k++; }
while(j
A[k]=R[j]; j++; k++; }
delete[]L; delete []R; } 2.3-3
2.3-4
2.3-5
2.3-6
2.3-7
第3章
3.1-1
3.1-2
3.1-3
3.1-4
3.1-5
3.1-6
3.1-7
3.1-8
3.2-1
3.2-2
3.2-3
3.2-4
3.2-5 后者大 3.2-6
数学归纳法易证 3.2-7
用数学归纳法证明
第4章
4.1-1
4.1-2
4.1-3
T(n)=cnlgn+n 4.1-4
4.1-5
4.1-6
4.2-1
4.2-2
4.2-3
4.2-4
4.2-5
4.3-1
4.3-2
4.3-3
4.3-4
不能运用主方法
4.3-5
第5章
5.1-1
因为本身就是一个排序过程
5.2-1
5.2-2
5.2-3
5.2-4
5.2-5
5.3-1
5.3-2
5.3-3
5.3-4
5.3-5
令m=n3，生成的全排列个数有mn，
其中不重复的有P(m,n)=m*(m−1)*"*(m−n+1), 所以，所有元素唯一概率为P(m,n)/mn 要证P(m,n)/mn≥1−1/n 由于P(m,n)/mn≥[(m−n)/m]n 故需证：[(m−n)/m]n≥1−1/n易证
5.3-6
第6章
6.1-1
6.1-2
6.1-3
6.1-4
6.1-5
6.1-6
6.1-7
6.2-1 见图6-2
6.2-2
6.2-3
6.2-4
6.2-5
对以i为根结点的子树上每个点用循环语句实现
6.2-6
6.3-1
见图6-3
6.3-2
6.3-3
6.4-1 见图6-4 6.4-2
HEAPSORT仍然正确，因为每次循环的过程中还是会运行MAX-HEAP的过程。
6.4-3
6.4-4
6.4-5
6.5-1 据图6-5 6.5-2
6.5-3
6.5-4
6.5-5
6.5-6
6.5-7
6.5-8
第七章
7.1-1 见图7-1
7.1-2
7.1-3
7.1-4
7.2-1
7.2-2
7.2-3
7.2-4
7.2-5
7.2-6
7.3-1
7.3-2
7.4-1
7.4-2
7.4-3
纯数学问题，对式子求导即可得。 7.4-4
见RANDOMIZED-QUICKSORT.ppt 7.4-5
见快速排序改进算法(7.4-5).pdf 7.4-6
第八章
8.1-1
8.1-2
8.1-3
8.1-4
8.2-1 见图8-2
8.2-2和
8.2-3
8.2-4
8.3-1 见图8-3 8.3-2
8.3-3
8.3-4
8.3-5(*)
8.4-1 见图8-4
8.4-2
8.4-3 3/2，1/2
8.4-4(*) 8.4-5(*)
第九章
9.1-1
9.1-2
9.2-1
9.3-1
9.3-2 9.3-3
9.3-4
9.3-5
9.3-6
9.3-7
9.3-8
9.3-9
第15章
15.1-1
15.1-2
15.1-3
fi[j]=∑∑ri(j)=2(∑2
i=1j=1
j=1
15.1-4
2nn
n−j
)=2(2−1)=2
nn+1
−1
15.1-5
15.2-1
最终答案：((A1A2)((A3A4)(A5A6)))
15.2-2
15.2-3
15.2-4
15.2-5 用递归
15.3-1
15.3-2
15.3-3
15.3-4
15.3-5
15.4-1
15.4-2
15.4-3
15.4-4
15.4-5
15.4-6
#include using namespace std;
int find(int *a,int len,int n)//修改后的二分查找，若返回值为x，则a[x]>=n {
int left=0,right=len,mid=(left+right)/2; while(left
if(n>a[mid]) left=mid+1; else if(n
int main() {
int n,a[100],c[100],i,j,len;//新开一变量len,用来储存每次循环结束后c中已经求出值的元素的最大下标
while(cin>>n) {
for(i=0;i>a[i]; b[0]=1; c[0]=-1; c[1]=a[0];
len=1;//此时只有c[1]求出来，最长递增子序列的长度为1. for(i=1;i
j=find(c,len,a[i]); c[j]=a[i];
if(j>len)//要更新len,另外补充一点：由二分查找可知j只可能比len大1 len=j;//更新len
}
cout
15.5-1
15.5-2
15.5-3
15.5-4
第16章
16.1-1
16.1-2
16.1-3
16.1-4
16.2-1
16.2-2