《算法分析与设计重点课后习题答案(共12页)》由会员分享，可在线阅读，更多相关《算法分析与设计重点课后习题答案(共12页)（12页珍藏版）》请在金锄头文库上搜索。
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;
2、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到 highvoid quicksort(int l,int n)qsort(l,1,n); /第一个作为枢轴 ，从第一个排到第n个int main()int a11=0,2,32,43,23,45
3、,36,57,14,27,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 st
4、d; int main() 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
5、() double value=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;
7、 （1） 基本语句2*i1)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
8、+;for(i=0;iN-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) w
9、hile (low=prvotkey) -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); /递归调用排序 由 prvo
10、tloc+1到 highvoid 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）；第三趟：
11、（1,3,5,9）；快速排序： 第一趟：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;for(int i=0;inum_max1) num_max1=ai;
