资源预览内容
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
第9页 / 共12页
第10页 / 共12页
亲,该文档总共12页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
精选优质文档-倾情为你奉上习题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(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,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 std; 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() 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考虑下面的算法,回答下列问题:算法完成什么功能?算法的基本语句是什么?基本语句执行了多少次?算法的时间复杂性是多少?(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)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-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=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); /递归调用排序 由 prvotloc+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);第三趟:(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;
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号