算法分析与设计重点课后习题答案

1、习题13设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C+描述。/采用分治法/对数组先进行快速排序/在依次比较相邻的差#include using namespace std;int partions(int b,int low,int high)int prvotkey=blow;b0=blow;while (lowhigh) while (low=prvotkey) -high; blow=bhigh; while (lowhigh&blow=prvotkey) +low; bhigh=blow;blow=b0;return low;void qsort(in

2、t l,int low,int high)int prvotloc;if(lowhigh) prvotloc=partions(l,low,high); /将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); /递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); /递归调用排序 由 prvotloc+1到 highvoid quicksort(int l,int n)qsort(l,1,n); /第一个作为枢轴 ，从第一个排到第n个int main()int a11=0,2,32,43,23,45,36,57,14,27,

3、39;int value=0;/将最小差的值赋值给valuefor (int b=1;b11;b+)coutab ;coutendl;quicksort(a,11);for(int i=0;i!=9;+i) if( (ai+1-ai)=(ai+2-ai+1) ) value=ai+1-ai; else value=ai+2-ai+1;coutvalueendl;return 0;4 设数组an中的元素均不相等，设计算法找出an中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C+描述。#includeusing namespace std; int main()

4、 int a=1,2,3,6,4,9,0; int mid_value=0;/将“既不是最大也不是最小的元素”的值赋值给它 for(int i=0;i!=4;+i) if(ai+1ai&ai+1ai+2) mid_value=ai+1; coutmid_valueendl;break;else if(ai+1ai+2) mid_value=ai+1;coutmid_valueendl;break; /for return 0;5. 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。#includeusing namespace std;int main() double val

5、ue=0; for(int n=1;n=10000 ;+n) value=value*10+1; if(value%2013=0) coutn至少为:nendl; break; /for return 0;习题2（1）int Stery(int n) int S = 0; for (int i = 1; i = n; i+) S = S + i * i; return S;（2）int Q(int n) if (n = 1) return 1; else return Q(n-1) + 2 * n - 1;2考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多

6、少次？算法的时间复杂性是多少？（1） 完成的是1-n的平方和基本语句：s+=i*i，执行了n次时间复杂度O（n）（2） （2）完成的是n的平方基本语句：return Q(n-1) + 2 * n 1，执行了n次时间复杂度O（n）3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。（1）for (i = 1; i = n; i+)if (2*i = n) for (j = 2*i; j = n; j+) y = y + i * j；（2）m = 0;for (i = 1; i = n; i+) for (j = 1; j = 2*i; j+) m=m+1; （1） 基本语句2*i1

7、)return 3*T(n-1);(2)int T(int n) if(n=1)return 1;else if(n1)return 2*T(n/3)+n;习题36. 设计算法，在数组rn中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。#include using namespace std;void deletere(int a,int N)int b100=0;int i,k;k=0;static int j=0;for(i=0;iN;i+)bai+;for(i=0;i100;i+) if(bi!=0)if(bi=2)k+;aj=i;j+;for(i=0;iN-

8、k;i+)coutaiendl;int main()int a=1,2,1,3,2,4;deletere(a,6);return 0;8. 设表A=a1, a2, , an，将A拆成B和C两个表，使A中值大于等于0的元素存入表B，值小于0的元素存入表C，要求表B和C不另外设置存储空间而利用表A的空间。 /先对A进行快排/将大于0的元素给B，小于0的元素给C#include using namespace std;int partions(int l,int low,int high)int prvotkey=llow;l0=llow;while (lowhigh) while (low=prv

9、otkey) -high; llow=lhigh; while (lowhigh&llow=prvotkey) +low; lhigh=llow;llow=l0;return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh) prvotloc=partions(l,low,high); /将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); /递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); /递归调用排序 由 prvotloc+1到 highv

10、oid quicksort(int l,int n)qsort(l,1,n); /第一个作为枢轴 ，从第一个排到第n个int main()int a11=-2,2,32,43,-23,45,36,-57,14,27,-39;quicksort(a,11);for(int i=1;i11;i+)if(ai0) coutC: ai ;elsecoutB: ai ; coutendl;return 0;习题44. 对于待排序序列(5, 3, 1, 9)，分别画出归并排序和快速排序的递归运行轨迹。 归并排序： 第一趟：（5,3）（1,9）；第二趟：（3,5,1,9）；第三趟：（1,3,5,9）；快速排

11、序： 第一趟：5（ ,3,1,9）；/5为哨兵，比较9和5 第二趟：5（1,3, ,9）；/比较1和5，将1挪到相应位置； 第三趟：5（1,3, ,9）;/比较3和5； 第四趟：（1,3,5,9）; 5. 设计分治算法求一个数组中的最大元素，并分析时间性能。/简单的分治问题/将数组均衡的分为“前”，“后”两部分/分别求出这两部分最大值，然后再比较这两个最大值#includeusing namespace std;extern const int n=6;/声明int main()int an=0,6,1,2,3,5;/初始化int mid=n;int num_max1=0,num_max2=0

12、;for(int i=0;inum_max1) num_max1=ai;for(int j=n+1;jnum_max2) num_max2=aj;if(num_max1=num_max2)cout数组中的最大元素： num_max1endl;else cout数组中的最大元素： num_max2endl;return 0;时间复杂度：O（n）9. 在有序序列(r1, r2, , rn)中，存在序号i（1in），使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。/在有序数组中/采用二分法查找符合条件的元素#includeusing namespace

13、 std;void Findnum(int *a,int n) int low=0; int high=n-1; while(low=high) int mid=(low+high)/2;if(amid=mid)cout这个数是： amidmid)high=mid-1;elselow=mid+1; int main()int a7=1,0,2,5,6,7,9; Findnum(a,7);return 0;时间复杂度为O(log2n)。10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。 /先对序列进行快速排序/再进行一次遍历/输出众数的重复次数#inclu

14、de using namespace std;int partions(int b,int low,int high)int prvotkey=blow;b0=blow;while (lowhigh) while (low=prvotkey) -high; blow=bhigh; while (lowhigh&blow=prvotkey) +low; bhigh=blow;blow=b0;return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh) prvotloc=partions(l,low,high); /将第

15、一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); /递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); /递归调用排序 由 prvotloc+1到 highvoid quicksort(int l,int n)qsort(l,1,n); /第一个作为枢轴 ，从第一个排到第n个int main()int a10=1,2,3,5,3,3,3,2,5,1;int i=0;int count=0;int max=0;/max表示出现的次数qsort(a,0,10); while(i10)int j;j=i+1; if(ai=aj&

16、imax) max=count; count=0; /while cout重复次数：maxendl; return 0;时间复杂度nlog(n)习题52.请写出折半查找的递归算法，并分析时间性能。/折半查找的递归实现#includeusing namespace std;int digui_search(int a,int low,int high,int x) if (low high) return 0; int mid = (low+high)/2; if (amid = x) return mid; else if (amid x) digui_search(a,low,mid-1,x

17、); else digui_search(a,mid+1,high,x); int main()int a6=0,1,2,9,5,3;int result=digui_search(a,0,5,5); coutaresultendl;return 0;10. 在120枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，最坏情况下，能不能只比较5次就检测出这枚假币？将120枚平均分为三组，记为：A，B，C；先将A,B比较，如果A,B重量不同（假如B比A重），再将B与C比较，如果B，C相同，则A有假币；如果B,C不同，再将A,C比较，如果A,C相同，则B有假币；如果A,C不同，则B有假币；如果A,B相同，则C有假币；习题61. 动态规划法为什么都需要填表？如何设计表格的结构？在填写表格过程中，不仅可以使问题更加清晰，更重要的是可以确定问题的存储结构； 设计表格，以自底向上的方式计算各个子问题的解并填表。2. 对于图6.26所示多段图，用动态规划法求从顶点0到顶点12的最短路径，写出求解过程。883510234101112图6.26 第2题图567891367683533463552643 将该多段图分为四段；首先求解初始子问题，可直接获得：d(0, 1)=c015(01)d(0, 2)=c02