算法设计与分析复习题.doc

算法设计与分析复习题1、 一个算法应有哪些主要特征？有限性、确定性、输入、输出、可行性2、 分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？分治法是将一个问题划分成一系列独立的子问题，分别处理后将结果组合以得到原问题的答案。动态规划同样将一个问题划分成一系列子问题进行处理，但当子问题不是互相独立而是互有联系时，动态规划不会重复计算子问题间联系的问题，是更高效的解决办法。3、 试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。贪心算法的思想是通过选择局部最优以求得最优解，但某些最优解问题无法由局部最优推出，如0-1 knapsack problem（背包问题，一个能装20斤的背包装入一定商品，要求价值最高）4、 编写一个递归算法求解Hanoi 塔问题。#include void move(char x,char y)printf(%c-%cn,x,y);void hanoi(int n,char x,char y,char z)if(n=1)move(x,z);elsehanoi(n-1,x,z,y);move(x,z);hanoi(n-1,y,x,z);int main()int n;printf(enter n:);scanf(%d,&n);hanoi(n,A,B,C);return 0;5、 求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。X2=X+1解得X1=(1+5)/2,，X2=(1-5)/2。则F(n)=C1*X1n + C2*X2n。F=F=1。C1*X1 + C2*X2。C1*X12 + C2*X22。解得C1=5/5，C2=-5/5。F(n)=（5/5)*(1+5)/2n - (1-5)/2n（5表示根号5）。6、 求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。T(n)=2n-1;(不确定)7、 求解方程T(n)=aT(n/b)+n，T(1)=1，设n=2k。8、 编写一个Quick Sorting 算法，并分析时间复杂性。#include #define M 100000using namespace std;int partition(double a,int p,int r);void quicksort(double a,int p,int r);int main()double aM;srand(time(0);printf(The array is:n);for (int i=0;iM;i+)ai=rand()-5000;ai+=rand()/10000.0;if(i%10=0)printf(%.6lfn,ai);elseprintf(%.6lft,ai); quicksort(a,0,M-1);coutendl排序结束:endl; for (int i=0;iM;i+)if(i%10=0)printf(%.6lfn,ai);elseprintf(%.6lft,ai);return 0;void quicksort(double a,int p,int r)int q;if(pr)q=partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);int partition(double a,int p,int r)double x=ar;int i=p-1;for (int j=p;j=r-1;j+)if (aj=x) i+;double temp=ai; /将比最后一个数大的数交换到后面去ai=aj;aj=temp; doubletemp=ai+1; /将作为基准的最后一个数交换到合适位置ai+1=ar;ar=temp;return i+1;最坏时间复杂度为O(n2)（每次选中的中间元素为序列的最小或最大元T(n)=T(n-1)+T(0)+O(n)）最好时间复杂度为O(nlogn)（每次选中的中间元素为序列的正中元素T(n)=2T(n/2)+O(n)）平均时间复杂度为O(nlogn)（不会分析）9、 利用Quick Sorting的原理，编写一个查找第k小元素的算法。double quicksortk(double a,int p,int r,int k)int q;q=partition(a,p,r);if(q+1)=k)coutRightk)return quicksortk(a,p,q-1,k);elsereturn quicksortk(a,q+1,r,k);10、 编写一个Heap Sorting算法，并分析时间复杂性。int heapsize=0;int alength=M-1;int left(int i)./返回左节点return 2*i;int right(int i)/返回右节点;return 2*i+1;int iparent(int i) return i/2;void heapify(double a,int i)int l=left(i);int r=right(i);int largest;if(lai)largest=l;else largest=i;if(ralargest)largest=r;if (largest!=i)double temp=ai;ai=alargest;alargest=temp;heapify(a,largest);void build_heap(double a)heapsize=alength;for (int i=alength/2;i=1;i-)heapify(a,i);/调整大头堆;void heapsort(double a)build_heap(a);/建立大头堆int k=0;coutendl排序结束:=2;i-)printf(%.6lft,a1);k+;if(k%10=0)coutendl;double temp=a1;a1=ai;ai=temp;heapsize-;heapify(a,1);int main()double aM;srand(time(0);printf(The array is:n);for (int i=1;i=logn+log(n-1)+log(n-2)+.+log(n/2)=(n/2)log(n/2)=(n/2)logn-n/2=O(nlogn)所以只用到比较的排序算法最低时间复杂度是O(nlogn)。12、 编写一个Radix算法对n个相同长度的整数排序。#include #include #define M 10using namespace std;queue m;queue r10;intradixsort(queue m,int n)for(int i=0;in;i+)while(m.size()!=0)int temp=m.front();m.pop();/*if(i=0)rtemp%10.push(temp);elsertemp/(i*10)%10.push(temp);*/int temp2=1;for(int k=0;ki;k+)temp2*=10;rtemp/(temp2)%10.push(temp);for(int j=0;j10;j+)while(rj.size()!=0)int temp=rj.front();rj.pop();m.push(temp);coutendloutcome;while(m.size()!=0)int temp=m.front();m.pop();couttempendl;return 0;int main()int aM;/srand(time(0);printf(The array is:n);for (int i=0;iM;i+)ai=(int)rand()-5000;ai=(ai+120000)%100000;m.push(ai);if(i%10=0)printf(%.6dn,ai);elseprintf(%.6dt,ai);radixsort(m,5);return 0;13、 编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。int fun(char *A,int n) int i ,j; i=0,j=n-1; while(i=j) if(Ai!=Aj)break; i+;j-; if(i=j)return 0;else return 1;14、 如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是找最大的回文子串呢？int judge(char *A,int n0, int n1)int i,j;i=n0;j=n1;while(i=j) if(Ai!=Aj)break; i+;j-; if(i=j)return 0;else return 1;int fun(char *A,int n) int i,j,k; for(i=1,i=n-1;i-) for(j=0;j=1;i-) for(j=0;j(n+1)/2时，要求的i一定在T1:(n+1)/2-1中，当T(n+1)/2Right) return -1; (Left+Right)/2 if(T(Left+Right)/2(Left+Right)/2) return find_i(T, (Left+Right)/2+1, Right);if(T(Left+Right)/2(Left+Right)/2) return find_i(T, Left, (Left+Right)/2-1); else return (Left+Right)/2;16、 编写一个采用KMP的算法查找T的子串P，并判断匹配失败的字符是否在P中，以此确定可滑动的最大距离。int next100;int lenthT,lenthP;void get_next(char *P)int i,j;i=1;j=0;next1=0;while(i=lenthP)if(j=0|Pi=Pj)+i;+j;if(Pi!=Pj) nexti=j;else nexti=nextj;else j=nextj;int KMP(char *T,char *P)int i,j;i=1;j=1;get_next(P);while(i=lenthT&jlenthP)return i-lenthP;else return 0;17、 编写一个算法找出2个正文中的最长公共子序列，若要找出3个正文中的最长公共子序列，应如何编写算法。算法思想X=Y=的LCS为Z=(1)若xm=yn,则zk=xm=yn,则z是xm-1和yn-1的LCS;(2)若xm!=yn,且zk!=xm,则z是xm-1和y的LCS;(3)若xm!=yn,且zk!=yn,则z是xm和yn-1的LCS采用动态规划的思想,通过公共字串的长度以及公共字串的起始地址求出公共字串;时间复杂度为O(mn);#include #include #define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int cMAXLEN, int bMAXLEN) int i, j; for(i = 0; i = m; i+) ci0 = 0; for(j = 1; j = n; j+) c0j = 0; for(i = 1; i= m; i+) for(j = 1; j = cij-1) cij = ci-1j; bij = 1; else cij = cij-1; bij = -1; void PrintLCS(int bMAXLEN, char *x, int i, int j) if(i = 0 | j = 0) return; if(bij = 0) PrintLCS(b, x, i-1, j-1); printf(%c , xi-1); else if(bij = 1) PrintLCS(b, x, i-1, j); else PrintLCS(b, x, i, j-1);int main(int argc, char *argv) char xMAXLEN = ABCBDAB; char yMAXLEN = BDCABA; int bMAXLENMAXLEN; int cMAXLENMAXLEN; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); return 0;算法实现#include #include #include using namespace std;int main()char x100;char y100;scanf(%s,x);scanf(%s,y);/ciny;int m=strlen(x);int n=strlen(y);int len100100;int z100100;for (int i=0;im;i+)for (int j=0;jn;j+)couti=i j=jlenij-1) lenij=leni-1j; zij=zi-1j;elselenij=lenij-1;zij=zij-1;coutlenij=lenijendl;coutzij=zijendlendl;/printf(最长公共子序列为%s,x+(m-zmn) ;/printf(最长公共子序列为%s,x+m-zm-1n-1) ;printf(最长公共子序列长度:%dn,lenm-1n-1);for(int i=0,b=zm-1n-1-lenm-1n-1+1;ilenm-1n-1;i+)printf(%c,xb+i);18、 编写一个求解8后问题的算法，并作出时间复杂性分析。#include #include #include using namespace std;#define N 10int m,n;int colN+1; int vis3N*2; void search(int cur)if(cur=m)cout成功找出方案:endl;for(int i=0;im;i+)cout第i+1行放在第coli+1列endl;coutendl; elsefor(int i=0;im;i+)if(!vis0i&!vis1cur+i&!vis2cur-i+n)/满足不相互攻击的条件 /vis0 行 vis1 /对角线 vis2 对角线colcur=i;vis0i=vis1cur+i=vis2cur-i+n=1;search(cur+1);/ 搜索下一个皇后位置vis0i=vis1cur+i=vis2cur-i+n=0;/回溯,重置状态 int main() for(int i=0;i3;i+) for(int j=0;j2*N;j+) visij=0; scanf(%d,&n); m=n; n-; search(0);19、 试分析回溯法与分支定界法的异同之处。(0) 分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树种满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或者是在满足约束条件的解种找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。（1）回溯法只通过约束条件来限制搜索，而分支定界不仅通过约束条件，而且还通过目标函数来限制搜索。（2）回溯法是应用的深度优先搜索策略，而分支定界采用的是广度优先搜索策略 20、 采用分支定界法编写一个求解货郎担问题的算法，并作出算法时间复杂性分析。21、 假设有k种不同面值的硬币（以元为单位，每种的个数不限）。编写一个用最少的硬币数找出n元钱的算法，并分析算法的时间复杂性。int dynamic_coin(int a,int money,int n) /采用动态规划求解int summoney+1;sum0=0;for (int i=1;i=money;i+)sumi=-1;for (int i=1;i=money;i+)for(int j=0;j=0)if(sumi-aj=-1) /continue;if(sumi=-1)sumi=sumi-aj+1; elsesumi=(sumisumi-aj+1)?sumi-aj+1:sumi; /最优解为本身或者sumi-aj+1if(summoney=-1) return -1;else return summoney;22、 考虑一个“模糊”的算法查找T的子串P，先快速找到与P相似的子串，再进一步确认之。int new_get_index(char *T,char *P) int a,b,c; a=0;b=strlen(p);c=(a+b)/2; int k=0; while() if(Pa!=Tk+a|Pb!=Tk+b|Pc!=Tk+c)k+;continue; for(int j=0;jb;j+) if(Pj!=Tj+k)break; if(j=b)return k; 23、 设计一个算法确定K个矩阵相乘的最优次序，并分析该算法的时间复杂性。int dynamic_cross(int i,int j,int mMM,int pM3)if(i=j)mii=0;return 0; for(int k=i;kj;k+) /枚举k把矩阵乘法分为前后两半mik=dynamic_cross(i,k,m,p);mk+1j=dynamic_cross(k+1,j,m,p);int sum=mik+mk+1j+pi0*pk1*pj1;if(summij)mij=sum;return mij;24、 设计一个算法从数A1：n中同时找出最大元素和最小元素，只需要不超过15n2次比较。void divid(int abegin,int aend,double & maxd,double & mind,double a)if(aend-abegin=1) /规模足够小的时候，直接2个数比较if(aabeginmaxd)maxd=aaend;if(aabeginmind)mind=aabegin;else if(aaendmaxd) maxd=aabegin;return ; /关键 一定要退出了 因为已经是递归出口 int mid=(abegin+aend)/2; /二分处理divid(abegin,mid,maxd,mind,a);divid(mid+1,aend,maxd,mind,a);25、 用分治法一个算法从数A1：n中同时找出最大元素，分析算法的时间复杂性，并思考为什么是这样的结果。采用分治法 T（n）=2T（n/2）+2 T（2）=1解这递归方程 得 T（n）=1.5n-2 得到优化。26、 在一个数组中出现次数最多的元素称为“众数”，编写一个找出众数的算法，并分析算法时间复杂性。先排序，然后遍历一遍寻找最长的相同元素序列。算法默认出现2次及2次以上才为众数。快排时间复杂度为O(nlogn)，遍历一遍复杂度为O(n)，故算法总时间复杂度为O(nlogn)int number(Array, Len)/快排 QSort(Array, Len); max=1;num=-1;i=0;j=1 while(iLen) /遍历 找最长的相同元素序列while(jmax) max=j-i; num=Arrayi;i=j;j=i+1 return num;27、 设计一个使用Hash法的算法在数组中找出“众数”，并分析时间复杂性。Hash的方法很关键，不知道有什么简单的方法这里假设数组中数据范围为0max，max为数组中最大元素，先找到max，确定了Hash的范围，再使用一对一Hash(direct addressing)。时间复杂性为O(n)（查找最大元时间复杂度为O(n)，遍历一遍数组为O(n)，Hash的时间复杂度为O(1)，故算法时间复杂度为O(n)，当然这里使用的方法受限制极强，不是通用的解答，时间复杂度也不可能有这么好，但是代码容易编写与理解）/Hash函数 有点假hash(Brray, i) Brrayi+;/返回-1则未找到众数 默认出现2次及2次以上才为众数int number(Array, Len) /找到最大数 max=find_max(Array, Len); /新建一个数组 Brray=new intmax+1; /初始化其中数据为0 for(i=0;imax+1;i+) Brrayi=0; /Array0=5则Brray5+ 以此类推 for(i=0;iLen;i+) hash(Brray, Arrayi); /默认众数为-1 出现次数为1次 num=-1;nax=1; /在Brray中找最大数 for(i=0;inax) nax=Brrayi; num=i; /删除Brray数组 delete Brray; /返回找到的众数 return num;28、 设计一个时间复杂性不超过O(n2)的算法，找出n个数组成的序列中最长的单调递增序列。比较简单，遍历一遍数组就可以了，这里为了写代码方便默认返回数组长度为1时，不存在递增序列，可以改成0更符合逻辑。/Result为返回的序列开始指针 RLen为序列长度increase(Array, Len, &Result, &RLen) RLen=1;/从Array0开始 i记录起始位置 j用于遍历数组 i=0;j=1; while(jLen) /如果是递减或相等序列 一直后移直到变成递增序列while(jLen) &(Arrayj=Len) return;/递增序列 一直后移到其末尾i=j-1;j+;while(jArrayj-1) j+;/更新返回值 if(j-i)RLen) RLen=j-i;Result=Array+i; i=j;j+; 29、 从1，2，n中找出所有质数，设计一个较优的算法。刷选法:Int I,j,count=0;Aa0=2;For(int i=3;ilim;i+=2)For(j=1;j=count)Count+;Aacount=I;30、 编写一个无向图的深度优先搜索算法，并将其改为非递归算法。void dfs(vector graph,int beginnode)if(visitedbeginnode=0)coutbeginnodeendl;visitedbeginnode=1;for(vector:iterator it=graphbeginnode.begin();it!=graphbeginnode.end();it+)int x=*it;if(visitedx=0)s.push(x);dfs(graph,x);/s.pop();if(s.size()=0) return ;int newnode=s.top();s.pop();dfs(graph,newnode);思路：a.先输出起始结点的值，其实结点入栈。b.t指向栈顶元素的第一个邻接结点，若t指向结点未访问过，输出t指向的结点，设置t指向的结点为已经访问过，t指向的结点入栈，转到b。若t指向的结点已经访问过，t指向栈顶元素下一个邻接结点，若t指向结点未访问过，输出t指向的结点，设置t指向的结点为已经访问过，t指向的结点入栈，转到b。若栈顶所有邻接结点都已经访问过，出栈。转到b。void s_dfs(int n)/非递归函数int stack100;int top=0;/stack NULLL_NODE* t=headn;int v;printf(-%d,n);visitn=1;stacktop+=n;while(top!=0)if(t=NULL) top-;v=stacktop-1;/v必定访问过t=headv;while(t!=NULL)if(visitt-ver=0)printf(-%d,t-ver);visitt-ver=1;stacktop+=t-ver;break;t=t-link;/end while/end while31、 编写一个无向图的宽度优先搜索非递归算法。void bfs(vector graph,int beginnode)queue q;q.push(beginnode);while(q.size()!=0)int u=q.front();q.pop();coutuendl;for(vector:iterator it=graphu.begin();it!=graphu.end();it+)int x=*it;if(visitedx=0)q.push(*it);visitedu=1;/coutendl;32、 测试一个图是否连通图，可以用深度优先搜索算法或宽度优先搜索算法，在什么情况下，用哪种算法更好一些？深度优先搜索算法33、 试求图中所有点对之间的所有路径，在此基础上再改写为找出所有点对之间最短路径的算法。问题描述 在一个有向图中,确认任何两个节点有没有通路; 二、算法思想借用半环的性质,设两点之间有通路,这l(a,b)=1,否则为0,通过动态规划的方法,不断填充cijk数组; cijk数组表示从点i经过k个节点能否到达节点j;从而求出所有节点间是否有通路;算法复杂度:为了求出cijk数组,用到了三重循环,所以复杂度明显为O(N*3); 三、代码实现#include #include #include #include #define M 100using namespace std;int lMM;int cMMM;int linkMM;int main()int n;coutn;int line;coutline;vector graph20;memset(l,0,sizeof(l); for(int i=0;iline;i+)int a,b;coutb):;cina;cinb;if (a=n|b=n)cout输入节点出错: ;return 0;grapha.push_back(b);lab=1; for (int i=0;in;i+)cii0=1+lii;for(int i=0;in;i+)for(int j=0;jn;j+)if(i!=j)cij0=lij;for (int k=1;kn;k+)for(int i=0;in;i+)for(int j=0;j=1)cijk