算法设计与分析复习题

算法设计与分析复习题1、一个算法应有哪些主要特征？有限性、确定性、输入、输出、可行性2、分治法（DivideandConquer）与动态规划（DynamicProgramming）有什么不同？分治法是将一个问题划分成一系列独立的子问题，分别处理后将结果组合以得到原问题的答案。动态规划同样将一个问题划分成一系列子问题进行处理，但当子问题不是互相独立而是互有联系时，动态规划不会重复计算子问题间联系的问题，是更高效的解决办法。3、试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。贪心算法的思想是通过选择局部最优以求得最优解，但某些最优解问题无法由局部最优推出，如0-1knapsackproblem（背包问题，一个能装20斤的背包装入一定商品，要求价值最高）4、编写一个递归算法求解Hanoi塔问题。#includestdio.hvoidmove(charx,chary){printf(%c----%c\n,x,y);}voidhanoi(intn,charx,chary,charz){if(n==1)move(x,z);else{hanoi(n-1,x,z,y);move(x,z);hanoi(n-1,y,x,z);}}intmain(){intn;printf(entern:);scanf(%d,&n);hanoi(n,'A','B','C');return0;}5、求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。X^2=X+1解得X1=(1+√5)/2,，X2=(1-√5)/2。则F(n)=C1*X1^n+C2*X2^n。∵F⑴=F⑵=1。∴C1*X1+C2*X2。C1*X1^2+C2*X2^2。解得C1=√5/5，C2=-√5/5。∴F(n)=（√5/5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}（√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、编写一个QuickSorting算法，并分析时间复杂性。#includeiostream#defineM100000usingnamespacestd;intpartition(doublea[],intp,intr);voidquicksort(doublea[],intp,intr);intmain(){doublea[M];srand(time(0));printf(Thearrayis:\n);for(inti=0;iM;i++){a[i]=rand()-5000;a[i]+=rand()/10000.0;if(i%10==0)printf(%.6lf\n,a[i]);elseprintf(%.6lf\t,a[i]);}quicksort(a,0,M-1);coutendl排序结束:endl;for(inti=0;iM;i++){if(i%10==0)printf(%.6lf\n,a[i]);elseprintf(%.6lf\t,a[i]);}return0;}voidquicksort(doublea[],intp,intr){intq;if(pr){q=partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);}}intpartition(doublea[],intp,intr){doublex=a[r];inti=p-1;for(intj=p;j=r-1;j++){if(a[j]=x){i++;doubletemp=a[i];//将比最后一个数大的数交换到后面去a[i]=a[j];a[j]=temp;}}doubletemp=a[i+1];//将作为基准的最后一个数交换到合适位置a[i+1]=a[r];a[r]=temp;returni+1;}最坏时间复杂度为O(n^2)（每次选中的中间元素为序列的最小或最大元T(n)=T(n-1)+T(0)+O(n)）最好时间复杂度为O(nlogn)（每次选中的中间元素为序列的正中元素T(n)=2T(n/2)+O(n)）平均时间复杂度为O(nlogn)（不会分析……）9、利用QuickSorting的原理，编写一个查找第k小元素的算法。doublequicksortk(doublea[],intp,intr,intk){intq;q=partition(a,p,r);if((q+1)==k){coutRightendl;returna[q];}elseif((q+1)k)returnquicksortk(a,p,q-1,k);elsereturnquicksortk(a,q+1,r,k);}10、编写一个HeapSorting算法，并分析时间复杂性。intheapsize=0;intalength=M-1;intleft(inti).//返回左节点{return2*i;}intright(inti)//返回右节点;{return2*i+1;}intiparent(inti){returni/2;}voidheapify(doublea[],inti){intl=left(i);intr=right(i);intlargest;if(l=heapsize&&a[l]a[i])largest=l;elselargest=i;if(r=heapsize&&a[r]a[largest])largest=r;if(largest!=i){doubletemp=a[i];a[i]=a[largest];a[largest]=temp;heapify(a,largest);}}voidbuild_heap(doublea[]){heapsize=alength;for(inti=alength/2;i=1;i--)heapify(a,i);//调整大头堆};voidheapsort(doublea[]){build_heap(a);//建立大头堆intk=0;coutendl排序结束:endl;for(inti=alength;i=2;i--){printf(%.6lf\t,a[1]);;k++;if(k%10==0)coutendl;doubletemp=a[1];a[1]=a[i];a[i]=temp;heapsize--;heapify(a,1);}}intmain(){doublea[M];srand(time(0));printf(Thearrayis:\n);for(inti=1;iM;i++){a[i]=rand()-5000;a[i]+=rand()/10000.0;if(i%10==0)printf(%.6lf\n,a[i]);elseprintf(%.6lf\t,a[i]);}heapsort(a);return0;}时间复杂度为O(nlogn)，heapify()的时间复杂度为O(logn)11、证明O(nlogn)是“比较”排序算法时间复杂性的下界。这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。具有L片树叶的二叉树的深度至少是logL。所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。而log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1=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个相同长度的整数排序。#includeiostream#includequeue#defineM10usingnamespacestd;queueintm;queueintr[10];intradixsort(queueintm,intn){for(inti=0;in;i++){while(m.size()!=0){inttemp=m.front();m.pop();/*if(i==0)r[temp%10].push(temp);elser[temp/(i*10)%10].push(temp);*/inttemp2=1;for(intk=0;ki;k++)temp2*=10;r[temp/(temp2)%10].push(temp);}for(intj=0;j10;j++){while(r[j].size()!=0){inttemp=r[j].front();r[j].pop();m.push(temp);}}}coutendloutcome;while(m.size()!=0){inttemp=m.front();m.pop();couttempendl;}return0;}intmain(){inta[M];//srand(time(0));printf(Thearrayis:\n);for(inti=0;iM;i++){a[i]=(int)rand()-5000;a[i]=(a[i]+120000)%100000;m.push(a[i]);if(i%10==0)printf(%.6d\n,a[i]);elseprintf(%.6d\t,a[i]);}radixsort(m,5);return0;}13、编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。intfun(char*A,intn){inti,j;i=0,j=n-1;while(i=j){if(A[i]!=A[j])break;i++;j--;}if(i=j)return0;elsereturn1;}14、如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是找最大的回文子串呢？intjudge(char*A,intn0,intn1){inti,j;i=n0;j=n1;while(i=j){if(A[i]!=A[j])break;i++;j--;}if(i=j)return0;elsereturn1;}intfun(char*A,intn){inti,j,k;for(i=1,i=n-1;i--){for(j=0;jn-i;j++){if(judge(&A,j,j+i)==1){output(&A,j,j+i);return1;}}}return0;}如果找最大回文则需更改为；intfun(char*A,intn){inti,j,k;for(i=n-1;i=1;i--){for(j=0;j=n-i-1;j++){if(fun(&A,j,i+j)==1){output(&A,j,i+j);return1;}}}return0;}此时最先找到的即为最大回文。15、设n个不同的整数排好序后存在数组T[1：n]中。若存在一个下标i，使得T[i]=i，设计一个有效的算法找到该下标。要求时间复杂性是O(logn)。因为整数数组已排好序，可以从数组的正中元素开始寻找T[i]，当T[(n+1)/2](n+1)/2时，要求的i一定在T[1:(n+1)/2-1]中，当T[(n+1)/2](n+1)/2时，要求的i一定在T[(n+1)/2+1:n]中，递归地使用此方法。//初始Left=1Right=nintfind_i(T,Lef