- 浏览: 276003 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
tuspark:
总结的不错,只是格式太规范。如果说最全面的泛型内容总结,我推荐 ...
Java泛型编程最全总结 -
huihui_0218:
泛型方法go的调用fg.<String>go(&q ...
Java泛型编程最全总结 -
fantaxy025025:
楼主总结的不错~赞一个!
Java泛型编程最全总结 -
rocksword:
<name> hbase.tmp.dir</ ...
Fedora13中安装HBase笔记 -
lijunwyf41:
public static void main(String[ ...
Java泛型编程最全总结
算法导论第二章习题答案
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; }
|
相关推荐
《算法导论》还包含丰富的实例和习题,这些不仅有助于巩固理论知识,还能培养读者解决问题的能力。书后附有参考文献和索引,方便读者进一步深入研究特定主题。总的来说,这本书是学习和理解算法的理想教材,无论你是...
2. **第二章:函数的增长率** - **Lecture Notes**:这一章深入探讨了算法效率评估的关键指标——时间复杂度和空间复杂度,特别是O记号、Ω记号和θ记号的概念及其应用。 - **Solutions**:通过具体的例子来解释...
所有代码都是在我学习这本书时亲手敲出来的,并且调试正确了,包括:第三部分到第六部分(即10-26章),外加第七部分31和32章所有的算法和数据结构以及编程习题还有思考题的C++实现源代码; 第一、二部分学习的较早...
**第二章:开始** - **主要内容**:包括基本的数据结构和算法设计的基础知识。 - **关键概念**: - **数据结构**:数组、链表等。 - **排序算法**:插入排序、归并排序等。 - **例题解析**:对插入排序进行...
- **多做练习题**:通过大量的习题练习来巩固所学知识,提高解决实际问题的能力。 - **参与讨论和合作**:与其他学习者一起讨论和解决难题,可以加深对知识点的理解。 - **实践应用**:尝试将所学算法应用到实际项目...
第二版相比第一版进行了大量的修订和完善,包括增加了新的章节、更新了部分算法的最新研究成果、改进了解释方式以及添加了大量的练习题和示例。这些改进不仅增强了教材的实用性和教学效果,也为学生和自学者提供了...
Rivest以及Clifford Stein所著的第二版《算法导论》的一部详尽的教学辅助资料。这本书由Thomas H. Cormen、Clara Lee和Erica Lin共同编写,旨在为教师提供深入理解算法概念、解决课后习题的全面指导,同时也为学生...
根据提供的文件信息,可以看出这是一本关于《算法导论》习题解答的手册。下面将对文件中的几个关键章节进行详细解析,以便更好地理解其中所包含的重要知识点。 ### 一、算法在计算中的角色(第1章) 这一章主要...
《算法导论》(第二版)教师用书是一部专为教师设计的教学辅助资料,旨在帮助教师更好地讲解和理解算法概念及其应用。该教师用书是《算法导论》(第二版)教材的补充材料,适用于计算机科学专业的本科生及研究生课程...
为了帮助读者更好地理解和掌握书中的知识点,《算法导论(第二版)的习题答案和教师手册》应运而生。 #### 二、教师手册的重要性 《算法导论(第二版)的习题答案和教师手册》是学习本书不可或缺的辅助材料之一。...
#### 算法导论第二版习题答案解析 **算法导论**(第二版)是一本经典的计算机科学教材,它深入浅出地介绍了算法的基本概念、设计技巧以及分析方法。本书由Thomas H. Cormen、Charles E. Leiserson、Ronald L. ...
2. **第二章:开始** - **内容**:包括基础数据结构的介绍、算法的表示方法等。 - **重要性**:为学习复杂算法打下坚实的基础。 - **例题解析**:例如,如何通过不同的数据结构实现数组的查找操作,理解其时间...
《算法导论》(Introduction to Algorithms)原书第二版,Thomas H. Cormen(科曼)、Charles E. Leiserson、Ronald L.Rivest、Clifford Stein著,南京大学潘金贵、顾铁成、李成法、叶懋等译,机械工业出版社,2006...
《算法导论》(Introduction to Algorithms)第二版,Thomas H. Cormen、Charles E. Leiserson、Ronald L.Rivest、Clifford Stein著,南京大学潘金贵、顾铁成、李成法、叶懋译,机械工业出版社,2006。本书简称CLRS...