算法分析考试题(2)

{//为奇数

if(x[xm]

median(x,y,xm,xRight,yLeft,ym); } else { median(x,y,xLeft,xm,ym,yRight); } } else

{//为偶数

if(x[xm]

median(x,y,xm+1,xRight,yLeft,ym); } else {

median(x,y,xLeft,xm,ym+1,yRight); } } }

int main() { int m;int a[d],b[d]; cout<<\ cin>>m; cout<<\ for(int i=0;i>a[i]; cout<<\ for(int j=0;j>b[j]; int mid=median(a,b,0,m-1,0,m-1); cout<<\ return 0; }

运行结果为：

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、代码实现

#include #define m 10 //快速排序

void QuickSort(int R[],int s,int t) { int i=s,j=t; int tmp; if(si&&R[j]>=tmp) j--; R[i]=R[j]; while(i

//找出最长公共子序列

void LCSLength(int x[],int y[],int n,int c[m][m],int b[m][m]) { int i,j; for(i=0;i=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; } } }

void LCS(int i,int j,int *x,int b[m][m]) { if(i<0||j<0) return; if(b[i][j]==1) { LCS(i-1,j-1,x,b); cout<

void main() { int x[m],y[m],d; cout<<\请输入元素个数\ cin>>d; cout<<\请输入元素\ for(int i=0;i>x[i]; y[i]=x[i]; } int c[m][m]={0},b[m][m]={0}; QuickSort(x,0,d-1); LCSLength(x,y,d,c,b); cout<<\最长单调递增子序列为：\ LCS(d-1,d-1,x,b); }

结果为：

7.礼物分配问题. 两兄弟Alan 和Bob, 共同分配n个礼物. 每个礼物只能分给其中的一个人,且不能分成两个.每个礼物i 的价值为vi, 为正整数.设 a 和 b 分别表示Alan 和 Bob所收到的礼物的总价值, V=

?Vi?1ni?a?b, 为所有礼物的总价值. 为使两兄弟高兴,我们希望尽

可能地均分这些礼物, 即 |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;ib[j]) { minx=b[j]; k=j; } } b[k]+=x[i]; x[i]=b[k]; } double t=0; for(i=0;i

void main() { int n;//等待服务的顾客人数 int s;//服务点的个数 int i;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析考试题(2)在线全文阅读。