算法分析考试题

1.)(nT给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1]中的元素的最大值和次大值.(算法分析与设计习题2.16)（分治法）a、算法思想用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。b、复杂度分析：把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算：有递推公式为：T(n)=1n=1T(n)=2T(n/2)+1n1所以，分治算法的时间复杂度是n+[logn]-2，当n为奇数时，logn取上线，当n为偶数时，logn取下线。//不知道为什么会-2！C、代码实现：#includestdio.hinta[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(lmaxrmax)if(lcmaxrmax){max=lmax;cmax=lcmax;}else{max=lmax;cmax=rmax;}elseif(rcmaxlmax){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;in;i++){scanf(%d,&a[i]);}maxcmax(0,n-1,max,cmax);printf(最大数为%d\n,max);printf(次大数为%d\n,cmax);return0;}C、运行结果为2.求数列的最大子段和(要求时间复杂为nlogn)(算法设计与分析吕国英清华大学出版社135页4..3.3二分法变异)（分治法）（也可用动态规划算法参看递归王晓东计算机算法设计与分析第三版p61页）a、基本思想：用分治法求最大子段和首先将问题划分，即将一直序列划分成长度相等的两个序列，这时会出现3种情况，即①最大子段和在第一个序列，②最大子段和在第二个序列和③最大子段和在第一个序列与第二个序列之间。然后，将3种情况的最大子段和合并，取三者之中的最大值为问题的解。b、复杂度分析：对应划分得到的情况①和②，需要分别递归求解，对应情况③，两个并列的for循环的时间复杂度是O(n)，所以有递推公式为：T(n)=1n=1T(n)=2T(n/2)+n-1n1所以，分治算法的时间复杂度是O(nlogn)c、代码实现#includeiostream.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(sum1sum2)sum2=sum1;}intsum3=0,sum4=0;for(j=i+1;j=right;j++){sum3=sum3+a[j];if(sum3sum4)sum4=sum3;}sum=sum2+sum4;if(summax1)sum=max1;if(summax2)sum=max2;returnsum;}}voidmain(){inta[m],d;cout请输入元素个数endl;cind;cout请输入元素endl;for(inti=0;id;i++)cina[i];cout最大子段和为:MaxSubSum(a,0,d-1)endl;}运行结果为：3.设X[0：n-1]和Y[0：n-1]为两个数组，每个数组中含有n个已排好序的数。试设计一个)(lognO时间算法，找出X和Y的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)+1n1易算出时间复杂度为)(lognOc、代码实现#includeiostreamusingnamespace::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];coutEnterdimensionm:endl;cinm;coutEnterarraya:endl;for(inti=0;im;i++)cina[i];coutEnterarrayb:endl;for(intj=0;jm;j++)cinb[j];intmid=median(a,b,0,m-1,0,m-1);coutThemedianis:midendl;return0;}运行结果为：4.设计一个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、代码实现#includeiostream.h#definem10//快速排序voidQuickSort(intR[],ints,intt){inti=s,j=t;inttmp;if(st){tmp=R[s];while(i!=j){while(ji&&R[j]=tmp)j--;R[i]=R[j];while(ij&&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;in;i++){c[0][i]=0;c[i][0]=0;}for(i=0;in;i++)for(j=0;jn;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(i0||j0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[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;cind;cout请输入元素endl;for(inti=0;id;i++){cinx[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=baVnii1,为所有礼物的总价值.为使两兄弟高兴,我们希望尽可能地均分这些礼物,即|a-b|打到最小试设计-O(n*V)时间的动态规划算法,使得|a-b|达到最小,并求出礼物的分割集合（P77页）(动态规划算法)8.（4.7）多处最优服务问题P131页(贪婪算法)(与十人打水的问题一样)a、算法思想：贪心策略如下：首先对所有服务先按服务时间从小到大进行排序，然后按照排序结果，选出最小的服务站点时间，依次安排服务。b、时间复杂度：程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为O(n)：而排序算法的时间复杂度为O(nlogn)。因此，综合来看算法的时间复杂度为O(nlogn)。c、代码实现：#includeiostream#includevector#includealgorithmusingnamespacestd;usingstd::vector;doublegreedy(vectorintx,ints){intminx;vectorintb(s+1,0);intn=x.size();sort(x.begin(),x.end());inti,j,k;for(i=0;in;i++){minx=0x7fffffff;k=0;for(j=0;js;j++){