算法导论系列——第二章习题乱解【原创】
算法导论第二章习题答案
2.1插入排序
2.1-1-2.1-2略过。
?
2.1-3查找问题：
输入：一列数A={a1,a2, ...an}和值v。
输出：下标i，使得v=A[i],若v不在A中，则输出NIL。
写出针对该线性查找问题的伪代码，利用循环不变式证明算法的正确性。
?
?
?
?
?
?
解答：伪代码如上。循环不变式A[1...i-1]中没有元素等于v：
1）在循环开始前，i=1，A[1...0]，显然没有元素等于v。
2）在循环中，只要找到有A[i]=v就返回，故循环不变式得到保持。
3）循环结束后，若i=n+1，则A[1...n]中没有元素等于v。若i!=n+1,则找到了A[i]=v，A[1...i-1]没有元素等于v。
?
?
2.1-4有两个各存放在数组A和B中的n位二进制数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有n+ 1个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。
解答：该问题主要是判断一下进位。A[i]+ B[i] + C[i], 其中C[i]为进位标志。
/**整数和代码，其中n为A和B的二进制位数*/
for(i= 0; i < n; i++) {
if(A[i] + B[i] +C[i] == 0) {
C[i]= 0;
} else if(A[i] + B[i] + C[i] == 1) {
C[i]= 1;
} else if(A[i] + B[i] + C[i] == 2) {
C[i]= 0;
C[i+ 1] = 1;
} else if(A[i] + B[i] + C[i] == 3) {
C[i] = 1;
C[i+ 1] = 1;
}
}
?
2.2算法分析
2.2-2选择排序的实现。
解答：选择排序的思想即是先找出数组A中的最小的元素，并将其与A[1](数组第一个元素，在代码中为a[0])中的元素进行交换。接着找出次最小的元素与A[2]中的元素进行交换。对数组A中的前n-1个元素执行该操作。该算法最好与最差情况都是O（n^2）。
?
伪代码：
SELECTION-SORT( A)
n← length[A]
fori← 1 to n ? 1
do smallest ←i
forj← i+ 1 to n
do if A[j] < A[smallest]
thensmallest ← j
exchangeA[ i] ? A[smallest]
循环不变式：在每次外层for循环迭代执行前，子数组A[1,2,...i-1]由数组A[1,2,...n]中最小的i-1个数构成，且已经排好序。for循环执行完前n-1个元素后，A[1,2,...n-1]包含A中的最小的n-1个元素，且已经排好序。故整个不变式成立。
?
/*选择排序代码**/
voidselectSort(int a[], int n)
{
inti, j;
for(i=0; i<n-1; i++){
intmin = i;
for(j=i+1; j<n; j++){
if(a[j] < a[min]) //如果这里写成a[j]<a[i],那就错了。
min= j; //对于{1,4, 2, 3, 5}类型的序列，错误就显现出来了。
}
swap(a,i, min); /**swap a[i] with a[min]**/
}
}
?
2.2-3在查找数组中每个元素可能性相等的情况下，线性查找平均情况和最坏情况都是O（n）。
?
?
2.3算法设计
2.3-2归并排序的实现（不使用哨兵值）
解答：主程序还是一样的，只是归并方法略有不同。
/*归并排序代码*/
voidmergeSort(int a[], int p, int r)
{
if(p < r) {
intq = (p + r)/2; //注意：实际程序中为了防止溢出，最好写成intq = p+(r-p)/2;
mergeSort(a,p, q);
mergeSort(a,q+1, r);
merge(a,p, q, r);
}
}
?
merge函数在使用哨兵值的时候，如下所示：
voidmerge(int a[], int p, int q, int r)
{
intn1 = q - p + 1;
intn2 = r - q;
intleft[n1+1];
intright[n2+1];
inti, j, k;
for(i=0; i<n1; i++)
left[i]= a[p+i];
for(j=0; j<n2; j++)
right[j]= a[q+1+j];
?
left[n1]= INT_MAX;
right[n2]= INT_MAX;
?
i=j=0;
for(k=p; k<=r; k++) {
if(left[i] <= right[j]) {
a[k]= left[i];
i= i+1;
}else {
a[k]= right[j];
j= j+1;
}
}
}
循环不变式：在for循环迭代开始前，子数组a[p..k-1]包含了left[0..n1]和right[0..n2]中的k-p个元素。
证明：
初始化:for循环第一次迭代开始前，k=p,此时子数组a[p..k-1]为空，显然包含了left和right子数组的k-p=0个元素。又i=j=0，left[i]与right[j]都是各自所在数组中、尚未被复制回数组a的最小元素。
保持：假设left[i]<right[j],那么left[i]就是未被复制回数组a的最小元素。由于a[p..k-1]包含了k-p个最小的元素，则将left[i]复制回a后，a[p..k]包含了k-p+1个最小的元素。增加k的值和i的值，会为下一次迭代建立循环不变式的值。（left[i]>right[j]情况类似）
终止：终止时，k=r+1。根据循环不变式，此时a[p..k-1]包含了left和right数组中r-p+1个最小元素，且已经排好序的。而left和right数组中共有r-p+3个元素，除去两个哨兵值，所有的元素都已经复制回数组a中。
?
merge函数不使用哨兵值
voidmerge(int a[], int start, int mid, int end)
{
intn1 = mid - start + 1;
intn2 = end - mid;
intleft[n1], right[n2];
inti, j, k;
?
for(i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i]= a[start+i];
for(j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j]= a[mid+1+j];
?
i= j = 0;
k= start;
while(i < n1 && j < n2)
if(left[i] < right[j])
a[k++]= left[i++];
else
a[k++]= right[j++];
?
while(i < n1) /* left[] is not exhausted */
a[k++]= left[i++];
while(j < n2) /* right[] is not exhausted */
a[k++]= right[j++];
}
?
?
2.3-3用数学归纳法证明递归式。T(n)=2T(n/2)+ n (如果n=2^k,k>1)
=2(如果n=2)
的解为T(n)= n lgn。
解答：当n=2时，nlg n = 2 lg 2 = 2 1 = 2.
?
假设当n/2时，有T(n/2) = (n/2) lg(n/2).
则T(n) = 2T (n/2) + n = 2(n/2) lg(n/2) + n
=n(lg n ? 1) + n = n lg n ? n + n = n lg n 。
证明完成。
?
?
2.3-4插入排序递归实现。
解答：先递归排序前n-1个元素，然后将第n个元素插入到已经排序的数组中。
voidinsertSort(int a[], int n)
{
if(n < 1) {
return;
}
insertSort(a,n-1);
intkey = a[n];
inti = n - 1;
while(i>=0 && a[i]>key)
{
a[i+1]= a[i];
i--;
}
a[i+1]= key;
}
?
?
2.3-5二分查找问题
解答：需要注意的问题一个是循环条件low<=high。若写成low<high则错误。
另一个是溢出问题。
1）迭代版本
intbsearch(int a[], int low, int high, int key)
{
while(low <= high) {
intmid = low+(high-low)/2;
if(a[mid] == key)
returnmid;
elseif (a[mid] > key)
high= mid - 1;
else
low= mid + 1;
}
?
return-(low+1);
}
?
2）递归版本
intrbsearch(int a[], int low, int high, int key)
{
if(low > high)
return-(low+1);
intmid = low+(high-low)/2;
if(a[mid] == key)
returnmid ;
elseif (a[mid] > key)
returnrbsearch(a, low, mid-1, key);
else
returnrbsearch(a, mid+1, high, key);
}
?
?
2.3-6若在插入排序中使用二分查找来寻找a[j]在已经排序的a[1...j-1]中应插入的位置，其最坏情况会不会改善至O（nlgn)?
解答：不会。因为最坏情况是当a[1]-a[j-1]所有元素都大于a[j]时，虽然可以在O（lgj）的时间内找到a[j]的插入位置，但是还是要移动j-1个元素。所以最坏情况并不会改善。
voidinsertSort(int a[], int len)
{
inti, j, k,key, pos, rpos;
for(j = 1; j < len; j++) {
key= a[j];
pos= bsearch(a, 0, j-1, key);
if(pos >= 0)
rpos= pos;
else
rpos= -pos - 1;
for(k=j-1; k>=rpos; k--)
a[k+1]= a[k];
a[rpos]= key;
}
}
?
2.3-7给出一个O（nlgn）的算法，使之能在给定的一个由n个整数构成的集合S和另一个整数x，判断出S中是否存在有两个元素之和为x。
解法1：以算法导论上面的标准答案步骤是这样的:
1）将S中的元素排序。
2）构建另一个集合S‘={z:z=x-y, 其中y属于S}。
3）对S‘中的元素排序。
4）如果S中有元素出现多余一次，则移除多余的，只剩下一个。对于S’也移除重复的元素。
5）合并两个排好序集合S和S‘。
6）只要在合并好的集合中有同样的元素出现两次（它们必然在相邻的位置），则存在和为x的两个数。假定该元素为y，则另一个元素为x-y。
第1，3步所需时间为O(nlgn)，2，4，5，6步所需时间为O(n)。所以总的时间为O(nlgn)。
?
解法2：其实对于从排好序的大小为n的数组a中找两个数之和等于某个数，可以这样做：设置两个值，一个指向数组的头部，另一个指向尾部。令start=0,end=n-1。若a[start]+a[end]>key，则end-1，继续循环。若a[start]+a[end]<key,则start+1。若a[start]+a[end]=key，则输出一组结果，并且start+1,end-1。C代码如下:
/**
**参数：按升序排列的数组，数组的起始位置，末尾位置， 查找和为key的两个元素。
**返回结果：若不存在和为key的两个元素，返回0。否则，返回存在的组数。
**
*/
intfind(int a[], int start, int end, int key)
{
inti=start, j=end, num=0;//num是符合条件的组数。
while(1)
{
if(i >= j)
break;
if(a[i]+a[j]<key)
i++;
elseif (a[i]+a[j]>key)
j--;
else{
printf("%d+%d=%d\n",a[i], a[j], key);
i++,j--;
num++;
}
}
returnnum;
?
}
?
?
?
思考题
2-1尽管合并排序最坏运行情况为O(n)，插入排序最坏运行情况为O（n^2)，然而插入排序的常数因子使得在n较小时，运行得更快。考虑在合并排序中，当子问题足够小时，采用插入排序。使用插入排序策略，对n/k个长度为k的子序列进行排序，然后在用标准的合并机制将它们合并。
1）证明最坏情况n/k个子序列可以用插入排序在O（nk）的时间内完成。
2）证明子列表可以在O（nlg(n/k))时间内完成合并。
3）修改后运行时间为O(nk+nlg(n/k))，要与标准合并排序同样的渐进时间，则k的最大渐近值为多少？（以O形式表示）
4）实践中，k的值如何选取？
?
解答：
1）每一个大小为k的子序列最坏情况可以在O(k^2)内完成排序，则n/k个子序列可以在n/k* O(k^2) = O(nk)时间内完成排序。
2）若直接扩展2个列表的合并到合并n/k个列表，则需要的时间为O(n*(n/k))。因为一共需要复制n个元素到目的数组，而每次复制元素的时候需要从n/k个排序列表中选择最小的元素，这需要O（n/k）时间。
为了达到O(nlg(n/k))的时间，可以考虑成对合并。从而最开始有n/k个序列，成对合并一次后变成n/k*1/2...直到列表为1个。所以共需要合并O(lg(n/k))次。每次成对合并所花时间为O(n)，故总的时间为O(nlg(n/k))。
3）令O(nk+ n lg(n/k)) =O (n lg n)，则k=O（lgn）。（因为k若大于lgn，则修改后算法运行时间的阶会高于nlgn）。
4）实践中k应该尽量选择为插入排序比合并排序快的最大的列表长度。
修改后的合并排序。
?
/**
*参数：数组a，起始位置，结束位置。
**/
voidmergeSort(int a[], int p, int r)
{
if(r-p <= 6) { //这里的r-p+1 < = 7, 即r-p<=6, k值为7。
returninsertSort(a, p, r);
} else {
intq = (p + r)/2;
mergeSort(a, p,q);
mergeSort(a, q+1,r);
merge(a, p, q,r);
}
}
?
/**插入排序**/
voidinsertSort(int a[], int p, int r)
{
inti, j, key;
?
for(j = p+1; j <= r; j++) {
key= a[j];
i= j - 1;
while(i>=p && a[i]>key) {
a[i+1]= a[i];
i--;
}
a[i+1]= key;
}
}
?
//下面是插入排序的变形。
voidinsertsort(int a[], int p, int r){
inti, j;
for(i=p; i<r; i++)
for(j=i+1; j>p && a[j-1]>a[j]; j--)
swap(a,j, j-1); //交换数组a中的j和j-1位置处的值。
}
?
?
2-2.冒泡排序
bubbleSort(A)
1fori=1 to length[A]
2dofor j=length[A] downto i+1
3do if A[j-1] > A[j]
4 then exchange A[j]<->A[j-1]
1)循环不变式证明第二个for循环。
循环不变式：在第二个for循环迭代前，A[j ] = min { A[k] : j ≤ k ≤ n}。且此时子数组A[j...n]是数组A[j...n]在迭代开始时的一个排列。
初始化：初始情况，j=n，则子数组A[j...n]只包含A[n]，显然成立。
保持：对于给定的一个迭代值j，由循环不变式，A[j]是A[j...n]中的最小值。第3-4行总是在A[j-1]>A[j]时交换两者的值，从而使得A[j-1]是A[j-1...n]中的最小值。不变式得到保持。
终止：终止时，j=i，由不变式得到A[i]= min { A[k] :i≤ k ≤ n}，且子数组A[i...n]是数组A[i...n]在迭代开始时的一个排列。
?
2）第一个For循环的循环不变式
?
循环不变式：在循环开始迭代前，子数组A[1...i-1]包含了数组A[1..n]的i-1个最小值，且是排好序的。
初始化：i=1，子数组为空，所以满足条件。
保持：由循环不变式，对于某个迭代值i，A[1...i-1]包含了数组A[1...n]的i-1个最小值，且排好序的。在2-4行的for循环执行完成后，由1）知A[i]是A[i...n]的最小值。故执行完这次循环后，A[1...i]包含了数组A[1...n]的i个最小值，且排好序的。
终止：执行完成后，i=n+1，此时子数组为A[1...n]，此时包含了整个数组，且已经排好序。
?
3）冒泡排序最好运行时间和最坏运行时间都是O(n^2)。
?
?
2-3霍规则问题
1）渐近时间O(n)。
2）求多项式原始算法
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3）循环不变式证明
初始化：
?
?
?
?
?
保持：
?
?
?
?
?
?
终止：i=-1,
?
?
?
?
?
?
?
2-4逆序对问题：设A[1..n]是一个包含n个不同数的数组。如果在i<j的情况下，有A[i]>A[j]，则(i,j)就称为A中的一个逆序对。给出一个算法，它能用Θ(nlg n)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。
解答：1）{2,3, 8, 6, 1}中逆序对有(2,1),(3, 1), (8, 6), (8, 1), (6, 1)。
2）当数组将序排列时，逆序对最多，为n(n-1)/2。
3）插入排序中，每一个逆序对导致执行一次循环操作。
4）修改归并排序求逆序对的数目。
?
?
/**
*求逆序对，只需要修改归并排序即可。
**/
intinversions(int a[], int start, int end)
{
intcount = 0;
if(start < end) {
intmid = (start + end) / 2;
count+= inversions(a, start, mid);
count+= inversions(a, mid+1, end);
count+= merge(a, start, mid, end);
}
returncount;
}
?
intmerge(int a[], int start, int mid, int end)
{
intn1 = mid - start + 1;
intn2 = end - mid;
intleft[n1], right[n2];
inti, j, k, v;
?
for(i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i]= a[start+i];
for(j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j]= a[mid+1+j];
?
i= j = 0;
k= start;
v= 0;
while(i < n1 && j < n2)
if(left[i] <= right[j])
a[k++]= left[i++];
else{
a[k++]= right[j++];
v+= n1-i;
}
?
while(i < n1) /* left[] is not exhausted */
a[k++]= left[i++];
while(j < n2) /* right[] is not exhausted */
a[k++]= right[j++];
returnv;
}
?
若不考虑时间因素，修改插入排序也是可以的。
/**
*修改插入排序用来求逆序对。更简单。
*/
intinsert_inverse(int a[], int len)
{
inti, j, key, count=0;
for(j = 1; j < len; j++) {
key= a[j];
i= j - 1;
while(i >= 0 && a[i] > key) {
count++;
a[i+1]= a[i];
i--;
}
a[i+1]= key;
}
returncount;
}
?
?