算法分析考试题.doc

精选1. 给定数组a0:n-1,试设计一个算法,在最坏情况下用n+logn-2次比较找出a0:n-1 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) （分治法）a、 算法思想用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。 b、复杂度分析：把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算：有递推公式为：T(n)=1 n=1 T(n)= 2T(n/2)+1 n1 所以，分治算法的时间复杂度是n+logn-2，当n为奇数时，logn取上线，当n为偶数时，logn取下线。/不知道为什么会-2！C、代码实现：#include int a100;void maxcmax(int i,int j,int &max,int &cmax) int lmax,lcmax,rmax,rcmax;int mid;if (i=j)max=ai;cmax=ai;else if (i=j-1)if (airmax)if(lcmaxrmax)max=lmax;cmax=lcmax;elsemax=lmax;cmax=rmax;elseif(rcmaxlmax)if(rmax=rcmax) max=rmax; cmax=lmax;else max=rmax; cmax=rcmax;elsemax=rmax;cmax=lmax;int main()int n;int max,cmax;printf(输入数组长度);scanf(%d,&n); printf(输入数组:n);for(int i=0;i1 所以，分治算法的时间复杂度是O(nlogn)c、代码实现#include#define m 10int MaxSubSum(int a,int left,int right)int sum=0;if(left=right) sum=aleft0?aleft:0;elseint i=(left+right)/2;int max1=MaxSubSum(a,left,i);int max2=MaxSubSum(a,i+1,right);int sum1=0,sum2=0;for(int j=i;j=left;j-)sum1=sum1+aj;if(sum1sum2)sum2=sum1;int sum3=0,sum4=0;for(j=i+1;jsum4)sum4=sum3;sum=sum2+sum4;if(summax1)sum=max1;if(summax2)sum=max2;return sum;void main()int am,d;cout请输入元素个数d;cout请输入元素endl;for(int i=0;iai;cout最大子段和为:MaxSubSum(a,0,d-1)1易算出时间复杂度为 c、代码实现#includeusing namespace:std;#define d 10int median(int x,int y,int xLeft,int xRight,int yLeft,int yRight) if(xLeft=xRight) return (xxLeft+yyLeft)/2; int xm=(xLeft+xRight)/2; int ym=(yLeft+yRight)/2; if(xLeft+xRight)%2=0) /为奇数 if(xxmyym) median(x,y,xm,xRight,yLeft,ym); else median(x,y,xLeft,xm,ym,yRight); else /为偶数 if(xxmyym) median(x,y,xm+1,xRight,yLeft,ym); else median(x,y,xLeft,xm,ym+1,yRight); int main()int m;int ad,bd;coutEnter dimension m:m;coutEnter array a:endl;for(int i=0;iai;coutEnter array b:endl;for(int j=0;jbj;int mid=median(a,b,0,m-1,0,m-1);coutThe median is:midendl;return 0;运行结果为：4. 设计一个O(n*n)时间的算法,找出由n个数组成的序列最长单调递增子序列. P87页(参考P56页) （动态规划算法）a、算法思路：序列X按非递减顺序排列，形成新序列Y，问题就转变成求解X和Y的LCS。b、时间复杂度：使用快速排序，则排序过程的时间复杂度为O（nlgn），而求两个序列的LCS的时间复杂度为O（n2）（因为X、Y长度相等），综合可知该解法的时间复杂度为O（n2）。c、代码实现#include#define m 10/快速排序void QuickSort(int R,int s,int t)int i=s,j=t;int tmp;if(si&Rj=tmp)j-;Ri=Rj;while(ij&Ri=tmp)i+;Rj=Ri;Ri=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);/找出最长公共子序列void LCSLength(int x,int y,int n,int cmm,int bmm)int i,j;for(i=0;in;i+)c0i=0;ci0=0;for(i=0;in;i+)for(j=0;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;void LCS(int i,int j,int *x,int bmm)if(i0|j0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi ;else if(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);void main()int xm,ym,d;cout请输入元素个数d;cout请输入元素endl;for(int i=0;ixi;yi=xi;int cmm=0,bmm=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页）(动态规划算法) 8. （4.7）多处最优服务问题 P131页 (贪婪算法) (与十人打水的问题一样)a、算法思想：贪心策略如下：首先对所有服务先按服务时间从小到大进行排序，然后按照排序结果，选出最小的服务站点时间，依次安排服务。b、时间复杂度：程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为O(n)：而排序算法的时间复杂度为O(nlogn)。因此，综合来看算法的时间复杂度为O(nlogn)。c、代码实现：#include #include #include using namespace std; using std:vector; double greedy(vectorx,int s) int minx;vectorb(s+1,0);int n=x.size(); sort(x.begin(),x.end(); int i,j,k; for(i=0;in;i+)minx=0x7fffffff;k=0;for(j=0;jbj)minx=bj;k=j;bk+=xi;xi=bk; double t=0; for(i=0;in;i+) t+=xi; t/=n; return t; void main() int n;/等待服务的顾客人数int s;/服务点的个数int i; int a; int t;/平均服务时间vectorx; cout输入等待服务的人数:n; cout输入服务站点数:s; cout输入每个顾客需要等待的时间:endl; for(i=1;ia;x.push_back(a); t=greedy(x, s); cout最少平均等待时间是:tendl; 运行结果为：9. 键盘输入一个高精度的正整数N, 去掉其中任意S个数字后剩下的数字按左右次序将组成一个新的正整数.编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小. (P133页 贪婪算法)10. 最佳调度问题。假设有个任务由个并行的机器完成。完成任务i个需要的时间为。 试设计一个算法找出完成这个任务的最佳调度，使得完成全部任务的时间最早。（回溯法）11.用回溯法做第6题 ( 时间复杂度为,请详细分析时间复杂度) 12.八皇后问题选做13最多约数问题问题描述:正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如，1，2，5，10 都是正整数10 的约数，且div(10)=4。设a 和b 是2 个正整数，ab，找出a和b之间约数个数最多的数x。a、 算法思想：数据规模到1000000000，较大，最一般做法会超时。可以利用n的因子数公式，如果n的素因子分解公式为：n = p1r1 * p2r2 * p3r3 * * pnrn，那么n的因子数公式即为Div(n) = (r1+1)*(r2+1)*(rn+1)。所以，先打印素数表，用公式求即可。b、 时间复杂度分析筛选法打印素数表的时间复杂度一定小于MAXsqr（MAX),求数m的因子个数的时间复杂度小于sqr（m）c、代码实现#include#include#include#define MAX 100000int primeMAX;bool aMAX;int cnt;/筛选法打印素数表void Initprime() int i, j; cnt = 0; for( i=2; iMAX; i+ ) if( ai = 0 ) primecnt+ = i; for( j=2*i; jMAX; j+=i ) aj = 1; /求数m的因子个数int Div( int m ) int tmp,ret=1; if( m100000 & am=0 ) return 2; for( int i=0; primei*primei=m & icnt; i+ ) if( m % primei = 0 ) tmp = 0; while( m % primei = 0 ) tmp +; m /= primei; ret = ret * ( tmp+1 ); if( m !=