算法导论系列——第二章习题乱解【原创】

算法导论第二章习题答案

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;

}