`
qiemengdao
  • 浏览: 275712 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

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

阅读更多

算法导论第二章习题答案

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=1A[1...0],显然没有元素等于v

2)在循环中,只要找到有A[i]=v就返回,故循环不变式得到保持。

3)循环结束后,若i=n+1,则A[1...n]中没有元素等于v。若i!=n+1,则找到了A[i]=vA[1...i-1]没有元素等于v

 

 

2.1-4 有两个各存放在数组AB中的n位二进制数,考虑它们的相加问题。两个整数的和以二进制形式存放在具有n + 1个元素的数组C中。请给出这个问题的形式化描述,并写出伪代码。

解答:该问题主要是判断一下进位。A[i] + B[i] + C[i], 其中C[i]为进位标志。

/**整数和代码,其中nAB的二进制位数*/

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个元素执行该操作。该算法最好与最差情况都是On^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在查找数组中每个元素可能性相等的情况下,线性查找平均情况和最坏情况都是On)。

 

 

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]为空,显然包含了leftright子数组的k-p=0个元素。又i=j=0left[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]包含了leftright数组中r-p+1个最小元素,且已经排好序的。而leftright数组中共有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]中应插入的位置,其最坏情况会不会改善至Onlgn)?

解答:不会。因为最坏情况是当a[1]-a[j-1]所有元素都大于a[j]时,虽然可以在Olgj)的时间内找到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给出一个Onlgn)的算法,使之能在给定的一个由n个整数构成的集合S和另一个整数x,判断出S中是否存在有两个元素之和为x

解法1以算法导论上面的标准答案步骤是这样的:

1)将S中的元素排序。

2)构建另一个集合S‘={z:z=x-y , 其中y属于S}

3)对S‘中的元素排序。

4)如果S中有元素出现多余一次,则移除多余的,只剩下一个。对于S’也移除重复的元素。

5)合并两个排好序集合SS‘

6)只要在合并好的集合中有同样的元素出现两次(它们必然在相邻的位置),则存在和为x的两个数。假定该元素为y,则另一个元素为x-y

13步所需时间为O(nlgn)2456步所需时间为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-1C代码如下:

/**

**参数:按升序排列的数组,数组的起始位置, 末尾位置, 查找和为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),插入排序最坏运行情况为On^2),然而插入排序的常数因子使得在n较小时,运行得更快。考虑在合并排序中,当子问题足够小时,采用插入排序。使用插入排序策略,对n/k个长度为k的子序列进行排序,然后在用标准的合并机制将它们合并。

1)证明最坏情况n/k个子序列可以用插入排序在Onk)的时间内完成。

2)证明子列表可以在Onlg(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个排序列表中选择最小的元素,这需要On/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=Olgn)。(因为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中的jj-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,子数组为空,所以满足条件。

保持: 由循环不变式,对于某个迭代值iA[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;

}

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics