算法导论系列——第二章习题乱解
算法导论第二章习题答案
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] for i← 1 to n − 1 do smallest ←i for j← i+ 1 to n do if A[j] < A[smallest] then smallest ← j exchange A[ 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个元素，且已经排好序。故整个不变式成立。
|
/*选择排序代码**/ void selectSort(int a[], int n) { int i, j; for (i=0; i<n-1; i++){ int min = 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归并排序的实现（不使用哨兵值）
解答：主程序还是一样的，只是归并方法略有不同。
|
/*归并排序代码*/ void mergeSort(int a[], int p, int r) { if (p < r) { int q = (p + r)/2; //注意：实际程序中为了防止溢出，最好写成int q = p+(r-p)/2; mergeSort(a, p, q); mergeSort(a, q+1, r); merge(a, p, q, r); } } |
merge函数在使用哨兵值的时候，如下所示：
|
void merge(int a[], int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; int left[n1+1]; int right[n2+1]; int i, 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函数不使用哨兵值
|
void merge(int a[], int start, int mid, int end) { int n1 = mid - start + 1; int n2 = end - mid; int left[n1], right[n2]; int i, 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时，n lg 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个元素插入到已经排序的数组中。
|
void insertSort(int a[], int n) { if (n < 1) { return; } insertSort(a, n-1); int key = a[n]; int i = 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）迭代版本
|
int bsearch(int a[], int low, int high, int key) { while (low <= high) { int mid = low+(high-low)/2; if (a[mid] == key) return mid; else if (a[mid] > key) high = mid - 1; else low = mid + 1; }
return -(low+1); } |
2）递归版本
|
int rbsearch(int a[], int low, int high, int key) { if (low > high) return -(low+1); int mid = low+(high-low)/2; if (a[mid] == key) return mid ; else if (a[mid] > key) return rbsearch(a, low, mid-1, key); else return rbsearch(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个元素。所以最坏情况并不会改善。
|
void insertSort(int a[], int len) { int i, 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。否则，返回存在的组数。 ** */ int find(int a[], int start, int end, int key) { int i=start, j=end, num=0;//num是符合条件的组数。 while (1) { if (i >= j) break; if (a[i]+a[j]<key) i++; else if (a[i]+a[j]>key) j--; else{ printf("%d+%d=%d\n", a[i], a[j], key); i++,j--; num++; } } return num;
} |
思考题
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， 起始位置，结束位置。 **/ void mergeSort(int a[], int p, int r) { if (r-p <= 6) { //这里的r-p +1 < = 7, 即r-p<= 6, k值为7。 return insertSort(a, p, r); } else { int q = (p + r)/2; mergeSort(a, p, q); mergeSort(a, q+1, r); merge(a, p, q, r); } }
/**插入排序**/ void insertSort(int a[], int p, int r) { int i, 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; } }
//下面是插入排序的变形。 void insertsort(int a[], int p, int r){ int i, 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)
1for i=1 to length[A]
2 do for j=length[A] downto i+1
3 do 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中的一个逆序对。给出一个算法，它能用Θ(n lg 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）修改归并排序求逆序对的数目。
|
/** *求逆序对，只需要修改归并排序即可。 **/ int inversions(int a[], int start, int end) { int count = 0; if (start < end) { int mid = (start + end) / 2; count += inversions(a, start, mid); count += inversions(a, mid+1, end); count += merge(a, start, mid, end); } return count; }
int merge(int a[], int start, int mid, int end) { int n1 = mid - start + 1; int n2 = end - mid; int left[n1], right[n2]; int i, 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++]; return v; }
若不考虑时间因素，修改插入排序也是可以的。 /** *修改插入排序用来求逆序对。更简单。 */ int insert_inverse(int a[], int len) { int i, 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; } return count; }
|