算法分析考试题

给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1]中的元素的最大值和次大值.(算法分析与设计习题2.16)（分治法）算法思想用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。b、复杂度分析：把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算：有递推公式为：T(n)=1n=1T(n)=2T(n/2)+1n>1所以，分治算法的时间复杂度是n+[logn]-2，当n为奇数时，logn取上线，当n为偶数时，logn取下线。//不知道为什么会-2！C、代码实现：#include<stdio.h>inta[100];voidmaxcmax(inti,intj,int&max,int&cmax){intlmax,lcmax,rmax,rcmax;intmid;if(i==j){max=a[i];cmax=a[i];}elseif(i==j-1)if(a[i]<a[j]){max=a[j];cmax=a[i];}else{max=a[i];cmax=a[j];}else{mid=(i+j)/2;maxcmax(i,mid,lmax,lcmax);maxcmax(mid+1,j,rmax,rcmax);if(lmax>rmax)if(lcmax>rmax){max=lmax;cmax=lcmax;}else{max=lmax;cmax=rmax;}elseif(rcmax>lmax){if(rmax==rcmax){max=rmax;cmax=lmax;}else{max=rmax;cmax=rcmax;}}else{max=rmax;cmax=lmax;}}}intmain(){intn;intmax,cmax;printf("输入数组长度");scanf("%d",&n);printf("输入数组:\n");for(inti=0;i<n;i++){scanf("%d",&a[i]);}maxcmax(0,n-1,max,cmax);printf("最大数为%d\n",max);printf("次大数为%d\n",cmax);return0;}C、运行结果为求数列的最大子段和(要求时间复杂为nlogn)(算法设计与分析吕国英清华大学出版社135页4..3.3二分法变异)（分治法）（也可用动态规划算法参看递归王晓东计算机算法设计与分析第三版p61页）a、基本思想：用分治法求最大子段和首先将问题划分，即将一直序列划分成长度相等的两个序列，这时会出现3种情况，即=1\*GB3①最大子段和在第一个序列，=2\*GB3②最大子段和在第二个序列和=3\*GB3③最大子段和在第一个序列与第二个序列之间。然后，将3种情况的最大子段和合并，取三者之中的最大值为问题的解。b、复杂度分析：对应划分得到的情况=1\*GB3①和=2\*GB3②，需要分别递归求解，对应情况=3\*GB3③，两个并列的for循环的时间复杂度是O(n)，所以有递推公式为：T(n)=1n=1T(n)=2T(n/2)+n-1n>1所以，分治算法的时间复杂度是O(nlogn)c、代码实现#include<iostream.h>#definem10intMaxSubSum(inta[],intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{inti=(left+right)/2;intmax1=MaxSubSum(a,left,i);intmax2=MaxSubSum(a,i+1,right);intsum1=0,sum2=0;for(intj=i;j>=left;j--){sum1=sum1+a[j];if(sum1>sum2)sum2=sum1;}intsum3=0,sum4=0;for(j=i+1;j<=right;j++){sum3=sum3+a[j];if(sum3>sum4)sum4=sum3;}sum=sum2+sum4;if(sum<max1)sum=max1;if(sum<max2)sum=max2;returnsum;}}voidmain(){inta[m],d;cout<<"请输入元素个数"<<endl;cin>>d;cout<<"请输入元素"<<endl;for(inti=0;i<d;i++)cin>>a[i];cout<<"最大子段和为:"<<MaxSubSum(a,0,d-1)<<endl;}运行结果为：设X[0：n-1]和Y[0：n-1]为两个数组，每个数组中含有n个已排好序的数。试设计一个时间算法，找出和的2n个数的中位数。(分治法)a、基本思想：解决问题的核心：找出将大问题分割成较小规模的相同问题的切割点，并递归定义大问题与子问题之间的关系。确定切割点：对于两个数组，我们可以从他们中分别选取出一个中位数，称为x,y，并将两个数组的左右边界称之为aLeft,aRight,bLeft,bRight。对比两个中位数，如果X数组中的中位数大于Y数组中的中位数，且X数组中的元素个数为偶数个，则X数组被切割为X[aLeft,x-1]，Y被切割为Y[y,bRight]，如果X数组的元素个数不为偶数个的话，则直接将X切割为X[aLeft,x]。如果X数组的中位数小于Y数组的中位数，取值情况刚好相反。递归关系：根据上面所述，对于原问题X[aLeft,aRight],Y[bLeft,bRight]。假设切割后的子问题为X[aLeft,x-1],Y[y,bRight]。则求解X[aLeft,aRight],Y[bLeft,bRight]问题的中位数，归结于求解子问题X[aLeft,x-1],Y[y,bRight]的中位数。递归结束条件：当切割后得到的子问题的两个数组的长度都为1位时，整个递归结束。b、复杂度分析：因为数组比较的范围每次缩小一半，所以有递推公式为：T(n)=1n=1T(n)=T(n/2)+1n>1易算出时间复杂度为c、代码实现#include<iostream>usingnamespace::std;#defined10intmedian(intx[],inty[],intxLeft,intxRight,intyLeft,intyRight){if(xLeft==xRight){return(x[xLeft]+y[yLeft])/2;}intxm=(xLeft+xRight)/2;intym=(yLeft+yRight)/2;if((xLeft+xRight)%2==0){//为奇数if(x[xm]<y[ym]){median(x,y,xm,xRight,yLeft,ym);}else{median(x,y,xLeft,xm,ym,yRight);}}else{//为偶数if(x[xm]<y[ym]){median(x,y,xm+1,xRight,yLeft,ym);}else{median(x,y,xLeft,xm,ym+1,yRight);}}}intmain(){intm;inta[d],b[d];cout<<"Enterdimensionm:"<<endl;cin>>m;cout<<"Enterarraya:"<<endl;for(inti=0;i<m;i++)cin>>a[i];cout<<"Enterarrayb:"<<endl;for(intj=0;j<m;j++)cin>>b[j];intmid=median(a,b,0,m-1,0,m-1);cout<<"Themedianis:"<<mid<<endl;return0;}运行结果为：设计一个O(n*n)时间的算法,找出由n个数组成的序列最长单调递增子序列.P87页(参考P56页)（动态规划算法）a、算法思路：序列X按非递减顺序排列，形成新序列Y，问题就转变成求解X和Y的LCS。b、时间复杂度：使用快速排序，则排序过程的时间复杂度为O（nlgn），而求两个序列的LCS的时间复杂度为O（n^2）（因为X、Y长度相等），综合可知该解法的时间复杂度为O（n^2）。c、代码实现#include<iostream.h>#definem10//快速排序voidQuickSort(intR[],ints,intt){inti=s,j=t;inttmp;if(s<t){tmp=R[s];while(i!=j){while(j>i&&R[j]>=tmp)j--;R[i]=R[j];while(i<j&&R[i]<=tmp)i++;R[j]=R[i];}R[i]=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);}}//找出最长公共子序列voidLCSLength(intx[],inty[],intn,intc[m][m],intb[m][m]){inti,j;for(i=0;i<n;i++){c[0][i]=0;c[i][0]=0;}for(i=0;i<n;i++)for(j=0;j<n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,int*x,intb[m][m]){if(i<0||j<0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i]<<"";}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}voidmain(){intx[m],y[m],d;cout<<"请输入元素个数"<<endl;cin>>d;cout<<"请输入元素"<<endl;for(inti=0;i<d;i++){cin>>x[i];y[i]=x[i];}intc[m][m]={0},b[m][m]={0};QuickSort(x,0,d-1);LCSLength(x,y,d,c,b);cout<<"最长单调递增子序列为："<<endl;LCS(d-1,d-1,x,b);}结果为：7.礼物分配问题.两兄弟Alan和Bob,共同分配n个礼物.每个礼物只能分给其中的一个人,且不能分成两个.每个礼物i的价值为vi,为正整数.设a和b分别表示Alan和Bob所收到的礼物的总价值,V=,为所有礼物的总价值.为使两兄弟高兴,我们希望尽可能地均分这些礼物,即|a-b|打到最小试设计-O(n*V)时间的动态规划算法,使得|a-b|达到最小,并求出礼物的分割集合（P77页）(动态规划算法)（4.7）多处最优服务问题P131页(贪婪算法)(与十人打水的问题一样)a、算法思想：贪心策略如下：首先对所有服务先按服务时间从小到大进行排序，然后按照排序结果，选出最小的服务站点时间，依次安排服务。b、时间复杂度：程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为O(n)：而排序算法的时间复杂度为O(nlogn)。因此，综合来看算法的时间复杂度为O(nlogn)。c、代码实现：#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;usingstd::vector;doublegreedy(vector<int>x,ints){intminx;vector<int>b(s+1,0);intn=x.size();sort(x.begin(),x.end());inti,j,k;for(i=0;i<n;i++){minx=0x7fffffff;k=0;for(j=0;j<s;j++){if(minx>b[j]){minx=b[j];k=j;}}b[k]+=x[i];x[i]=b[k];}doublet=0;for(i=0;i<n;i++)t+=x[i];t/=n;returnt;}voidmain(){intn;//等待服务的顾客人数ints;//服务点的个数inti;inta;intt;//平均服务时间vector<int>x;cout<<"输入等待服务的人数:"<<endl;cin>>n;cout<<"输入服务站点数:"<<endl;cin>>s;cout<<"输入每个顾客需要等待的时间:"<<endl;for(i=1;i<=n;i++){cin>>a;x.push_back(a);}t=greedy(x,s);cout<<"最少平均等待时间是:"<<t<<endl;}运行结果为：9.键盘输入一个高精度的正整数N,去掉其中任意S个数字后剩下的数字按左右次序将组成一个新的正整数.编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小.(P133页贪婪算法)最佳调度问题。假设有个任务由个并行的机器完成。完成任务i个需要的时间为。试设计一个算法找出完成这个任务的最佳调度，使得完成全部任务的时间最早。（回溯法）11.用回溯法做第6题(时间复杂度为,请详细分析时间复杂度)12.八皇后问题选做13．最多约数问题问题描述:正整数x的约数是能整除x的正整数。正整数x的约数个数记为div(x)。例如，1，2，5，10都是正整数10的约数，且div(10)=4。设a和b是2个正整数，a≤b，找出a和b之间约数个数最多的数x。算法思想：数据规模到1000000000，较大，最一般做法会超时。可以利用n的因子数公式，如果n的素因子分解公式为：n=p1^r1*p2^r2*p3^r3*…*pn^rn，那么n的因子数公式即为Div(n)=(r1+1)*(r2+1)*……*(rn+1)。所以，先打印素数表，用公式求即可。时间复杂度分析筛选法打印素数表的时间复杂度一定小于MAXsqr（MAX),求数m的因子个数的时间复杂度小于sqr（m）c、代码实现#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAX100000intprime[MAX];boola[MAX];intcnt;//筛选法打印素数表voidInitprime(){inti,j;cnt=0;for(i=2;i<MAX;i++){if(a[i]==0){prime[cnt++]=i;for(j=2*i;j<MAX;j+=i)