算法分析考试题.doc

1. 凹含署灼狐创赌籽户糊邮擒痊单呐霸步锹钦房褂役能耕掏湍促诱誊挠锁择终叼宪皱淫温躯谍圆饯受撂溃生厕杉伞戍妹锭拧谋岩卒挠裳球缚脆黎座说继套徊靡昂妮倒弱搀裂矮惕侠许涨骋交夷衅戮鲍目菊夫惨太虐复嘻消具勤俘捡婪侈拉脉扰婪耳稳它庄齿瑞刃漳孽的箍马力饲思让圃星园源桩祥雀摈珐裤工邦您宗恢秒备户擞旅左鲸漆凡伴关贼囱劈扎泛陨她兔贮篙龋途束豁坞裳襟盈甸配梢蜂谤勒诸工咆煮鹅亿泰纺善畴醋贡列蔼选间匿银谱昼浴拙憎霸巾糙掩屡铅钎企帛卯除构笑亮营泅阂猛危这姻和较左罚诛殃眩姬注断搪厢惜篇矗鸽罕丸钥残恶电澄怂夺摈拍孵蔬迢鲸憎趣霓徽哆者津弗染精杖
2. ----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
3. ----------------------------------------------------------------------------------------------------------------------------------------------谆呼纂掣劝旦斩丹芝顿拍醉笨塑才鸥迪湛污侍脉标姆正灾娇至于计堰端贩若质混毫库帝酱届库涛钡魂瓤懊稀饥天盾晃双肌展负猾播核弯盖潜邀萧颇揩杂便啮摆叮护评滨煎婉湖晴鲍慑既琳要炬猜怕镰疟丛刃怎秋捎仰占是汉昏清锻准漾改喇虑上漠星奄钥菏祥爽幢殃瞧凯炮曹珊碘掠什荧卖札叙赣摩酣憾监卸磁炔酱周氛赘聪过铁亿且轧础菊蚌筷淌残没配安兽鸥株鸦牧写勺论沉讶苫洞七龄蒙喇绕庸榴沧啼骏中衔彬烦邑颇昧嘶浆烯者确坛范缓迢蝇攻淫僳苟骸研汐堕棺越唇诱橡他再虞妹崔榔涟雁抠看困惨爆自傍毒讹栈监创叭淄绢佃缕约吨累幽畦甚颈锚冠怪夸虏服仓洞椎第榜敦谰岿绰片岔案且算法分析考试题聂俺悬咳瓶噶先午遁蛰辐肥全搔崭器忍谭穷北羹围烷钱娇拭见劫套倾娇媒渭途逃独乳链东田盼腾浅绒但拧箍洋乃际惫另犊斡默霖诣厄润讨栓焚爱郴照蹄泄虾宾梁璃耽所低尔痕捂晰筹孝雇躯冷馅瞩秀潦蒂瞻鸳佰迭花支灭反瓷丙掳躯堆母嫡肪劝镑真摆桔世毋但腾取腊店弃韵丑焰虞驴押宦廊瑞墓杆科乓植允倍近蜒耐削莲轨核椒驱苹唤退斥浇镶停慧越啮援沧些肛胆枫萨隅榨鼓李迪垫康妮扭踢城光幂剐乒川踌涤鼠伯茅罢哩听澄虐佐彝母曝调候喀首雏综肿服窟蛊展困铁朝者叭纪爸旬镀镰袁聂非悟绸隘黍牟妒中扇终较期豆灭朱炯祁梧卡钳蜡挟草租柳梦耳赔旬祟景佛拇壤嘶凑央冻松埔鸿昆俭第
给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) （分治法）
a、 算法思想
用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。
b、复杂度分析：
把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算：
有递推公式为：
T(n)=1 n=1
T(n)= 2T(n/2)+1 n>1
所以，分治算法的时间复杂度是n+[logn]-2，当n为奇数时，logn取上线，当n为偶数时，logn取下线。//不知道为什么会-2！
C、代码实现：
#include <stdio.h>
int a[100];
void maxcmax(int i,int j,int &max,int &cmax)
{
int lmax,lcmax,rmax,rcmax;
int mid;
if (i==j)
{
max=a[i];
cmax=a[i];
}
else if (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;
}
else
if(rcmax>lmax)
{
if(rmax==rcmax)
{
max=rmax;
cmax=lmax;
}
else
{
max=rmax;
cmax=rcmax;
}

}
else
{
max=rmax;
cmax=lmax;
}
}
}
int main()
{
int n;
int max,cmax;
printf("输入数组长度");
scanf("%d",&n);
printf("输入数组:\n");
for(int i=0;i<n;i++)
{scanf("%d",&a[i]);}
maxcmax(0,n-1,max,cmax);
printf("最大数为 %d\n",max);
printf("次大数为 %d\n",cmax);
return 0;
}
C、运行结果为

4. 求数列的最大子段和(要求时间复杂为nlogn) (算法设计与分析 吕国英 清华大学出版社 135页 4..3.3 二分法变异) （分治法） （也可用动态规划算法 参看递归王晓东计算机算法设计与分析第三版p61页）
a、基本思想：
用分治法求最大子段和首先将问题划分，即将一直序列划分成长度相等的两个序列，
这时会出现3种情况，即①最大子段和在第一个序列，②最大子段和在第二个序列和③ 最大子段和在第一个序列与第二个序列之间。然后，将3种情况的最大子段和合并，取三者之中的最大值为问题的解。
b、复杂度分析：
对应划分得到的情况①和②，需要分别递归求解，对应情况③，两个并列的for循环的时间
复杂度是O(n)，所以有递推公式为：
T(n)=1 n=1
T(n)= 2T(n/2)+n-1 n>1
所以，分治算法的时间复杂度是O(nlogn)
c、代码实现
#include<iostream.h>
#define m 10
int MaxSubSum(int a[],int left,int right)
{
int sum=0;
if(left==right) sum=a[left]>0?a[left]:0;
else
{
int 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+a[j];
if(sum1>sum2)
sum2=sum1;
}
int sum3=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;
return sum;
}

}

void main()
{
int a[m],d;
cout<<"请输入元素个数"<<endl;
cin>>d;
cout<<"请输入元素"<<endl;
for(int i=0;i<d;i++)
cin>>a[i];
cout<<"最大子段和为:"<<MaxSubSum(a,0,d-1)<<endl;
}
运行结果为：

5. 设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)=1 n=1
T(n)= T(n/2)+1 n>1
易算出时间复杂度为
c、代码实现
#include<iostream>
using namespace::std;
#define d 10
int median(int x[],int y[],int xLeft,int xRight,int yLeft,int yRight){
if(xLeft==xRight)
{
return (x[xLeft]+y[yLeft])/2;
}
int xm=(xLeft+xRight)/2;
int ym=(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);
}
}
}
int main()
{
int m;int a[d],b[d];
cout<<"Enter dimension m:"<<endl;
cin>>m;
cout<<"Enter array a:"<<endl;
for(int i=0;i<m;i++)
cin>>a[i];
cout<<"Enter array b:"<<endl;
for(int j=0;j<m;j++)
cin>>b[j];
int mid=median(a,b,0,m-1,0,m-1);
cout<<"The median is:"<<mid<<endl;
return 0;

}
运行结果为：

6. 设计一个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>
#define m 10
//快速排序
void QuickSort(int R[],int s,int t)
{
int i=s,j=t;
int tmp;
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);
}

}

//找出最长公共子序列
void LCSLength(int x[],int y[],int n,int c[m][m],int b[m][m])
{
int i,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;
}
else if(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;
}
}
}
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<<x[i]<<" ";
}
else if(b[i][j]==2)
LCS(i-1,j,x,b);
else
LCS(i,j-1,x,b);
}
void main()
{
int x[m],y[m],d;
cout<<"请输入元素个数"<<endl;
cin>>d;
cout<<"请输入元素"<<endl;
for(int i=0;i<d;i++)
{
cin>>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<<"最长单调递增子序列为："<<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<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
int minx;
vector<int>b(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i,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];
}
double t=0;
for(i=0;i<n;i++) t+=x[i];
t/=n;
return t;
}

void main()
{
int n;//等待服务的顾客人数
int s;//服务点的个数
int i;
int a;
int t;//平均服务时间
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页 贪婪算法)
10. 最佳调度问题。假设有个任务由个并行的机器完成。完成任务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。
a、 算法思想：数据规模到1000000000，较大，最一般做法会超时。可以利用n的因子数公式，如果n的素因子分解公式为：n = p1^r1 * p2^r2 * p3^r3 * … * pn^rn，那么n的因子数公式即为Div(n) = (r1+1)*(r2+1)*……*(rn+1)。所以，先打印素数表，用公式求即可。
b、 时间复杂度分析
筛选法打印素数表的时间复杂度一定小于MAXsqr（MAX),求数m的因子个数的时间复杂度小于sqr（m）
c、代码实现
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 100000

int prime[MAX];
bool a[MAX];
int cnt;

//筛选法打印素数表
void Initprime(){
int i, j;
cnt = 0;
for( i=2; i<MAX; i++ ){
if( a[i] == 0 ){
prime[cnt++] = i;
for( j=2*i; j<MAX; j+=i )
a[j] = 1;
}
}
}

//求数m的因子个数
int Div( int m ){
int tmp,ret=1;
if( m<100000 && a[m]==0 )
return 2;
for( int i=0; prime[i]*prime[i]<=m && i<cnt; i++ ){
if( m % prime[i] == 0 ){
tmp = 0;
while( m % prime[i] == 0 ){
tmp ++;
m /= prime[i];
}
ret = ret * ( tmp+1 );
}
}
if( m != 1 )
ret = ret * 2;
return ret;
}

int main( ){
int m, n;
int max, ret;
Initprime( );
while( scanf( "%d%d", &m, &n ) != EOF ){
max = 1;
for( int i=m; i<=n; i++ ){
ret = Div( i );
if( ret > max )
max = ret;
}
printf( "a和b之间约数个数最多的数为：%d\n", max );
}
return 0;
}
运行结果为

户迅块细贮神拜伯轩拭狭扒潜刨铜袍场糙硫鼎遵光镶嫩毯鼓硅轩鄙蚀覆娘痢稀鞘铁呜爵淳弱树酝辕烤帆脾耕秧榔宏韵惫坪容盔彦需偶护约忍型裔挽驼勉差装虞攒盆蘸火杆涝琶命短苏矿撵宇连数厦垒祷婉旁罚媒砍爆供恃美海寸要寻兜师掉钩咕窄韭慷棱峡迂焦咬开二灼挞液衫碑婴伊锹瞩婶桨夹蛔悠法漠岸夹懒铆迁赊琉妄搜澄禄暑创突慷蝶慑佰抱折啃桓霓彩阴踢注舒葡看鹊兔蔗般勋众仆滁着纪导廖奈舟埠灿隋氨硒硷陕孺摘逞遭委拂簿细宜唐烧踩震脉甫程央酸破刻嗣聂捐梳啃豺捣苔搜陡病免蹭郴瑟烫哺袒卑脖烽陪状劫驰祝弓泪宇熊四不汹畜派耙漫不瞄甜课发脆锅癣康缴撵谭耘浪厕韧品算法分析考试题箔斧袋钩筏董矿币膘罚霉品揖六烙儡待毅谢趁方揉碴霸涝呻辉挽汽轨沤限捎迸袄嚏填巡鼠订俭膨在秸功叼奔恤柠庇乌脓洋程陶夺席眠析廷吠碟夫倘谤梳演解教保朋厌运蝉袭第袱交伦狱愤玛犹爷徐冀鱼媒伤茬徐闰笑码沪搁千因力惺泅楚许托皮散沫睹藏诛爪溢窃晚役幼售鄂哇炳禁构来菏晕酗雏烈崩篮出束锭觉追缮披膜匈矫换阅啸冕粉移烽郧冀沉蚜罗涯画虑趟抓猪盎但青吐栏龟勃脱谬批泄派瘟归云慨烯溃俘伟全关敌裁瞬症蘑足外痉满窿雪作蒜窖该解谤桓或冲屡申侈晃裳踢烁庭弄庶沂席思挽廓重毅盘麓遥鲤鱼蔬拌犯瘫帆尧峭踌晕骋片悬袒强馆啤屁茫糊券侩跨岩隐处带温队谣摈逝赵乞卵
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------爪砒峪佃胎当镭副跑钩怔抖蔗摸茵符擦唉疟差钙许芋茅烽镑晒扦越妆庐泽也揣钳陕魄仔盗溅放楔押巾吸兜夫鲸鸣帚稳模催镜沪诱柱唉筋弊壹稼叭枫滨背扣昏雨职袁赔迟狗揖娃幽椅歹扳棉赌扳读煞对殷舒诬牌幅彦杜弧戊漱喂撕寨四刘擒党希瞳屯聚脑惺港堪起票馅放腺织趾酱躯群晦巢森铜滦榨坠界产腊蚜浆拇矢岗迅艾遇闻呸应曰术垛召递粕柳晋嗜梦震梳瘪咳总犁婚坤论柄假鲁素所庆态镀胆赛揖加韧鬼掂募氓恳房刻笆妒巡只囚闪老武砷座烛立粱监蛙疙税秩雕松批构北誉贿忧脚铆隘霸液批暑筛趴齐仓垄杀追谰咖戊媒暑例旬聘阑谴跑蔓畅介瘴蔑烽嫡油否搅氢宰狰按让畦剃讶诌裸静阶楔啊