算法设计与分析复习题

1、算法设计与分析复习题1一个算法应有哪些主要特征？另附资料2分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？另附资料3试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。另附资料4编写一个递归算法求解Hanoi 塔问题。Void Hanoi(int n,int first,int second,int third) If(n=1)Move(first,third);Else Hanoi(n-1,first,third,second);Move(first,third);Hanoi(n-1,second,first,second

2、);5求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。6求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。7求解方程T(n)=aT(n/b)+n，T(1)=1，设n=2k。另附资料8编写一个Quick Sorting 算法，并分析时间复杂性。9利用Quick Sorting的原理，编写一个查找第k小元素的算法。10编写一个Heap Sorting算法，并分析时间复杂性。另附资料上有部分具体实现代码：11证明O(nlogn)是“比较”排序算法时间复杂性的下界。证明O(nlogn)是“比较”排序算法时间复杂性的下界。为了证明只用到比较的排序算法最低时间复杂度是O

3、(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)l

4、ogn-n/2=O(nlogn)所以只用到比较的排序算法最低时间复杂度是O(nlogn)。赞12编写一个Radix算法对n个相同长度的整数排序。int maxbit(int data,int n) /辅助函数，求数据的最大位数 int d = 1; /保存最大的位数 int p =10; for(int i = 0;i = p) p *= 10; +d; return d; void radixsort(int data,int n) /基数排序 int d = maxbit(data,n); int * tmp = new intn; int * count = new int10; /计数

5、器 int i,j,k; int radix = 1; for(i = 1; i= d;i+) /进行d次排序 for(j = 0;j 10;j+) countj = 0; /每次分配前清空计数器 for(j = 0;j n; j+) k = (dataj/radix)%10; /统计每个桶中的记录数 countk+; for(j = 1;j = 0;j-) /将所有桶中记录依次收集到tmp中 k = (dataj/radix)%10; tmpcountk-1 = dataj; countk-; for(j = 0;j n;j+) /将临时数组的内容复制到data中 dataj = tmpj;

6、 radix = radix*10; delete tmp; delete count; 13编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。14如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是找最大的回文子串呢？15设n个不同的整数排好序后存在数组T1：n中。若存在一个下标i，使得Ti=i，设计一个有效的算法找到该下标。要求时间复杂性是O(logn)。16编写一个采用KMP的算法查找T的子串P，并判断匹配失败的字符是否在P中，以此确定可滑动的最大距离。17编写一个算法找出2个正文中的最长公共子序列，若要找出3个正文中的最长公共子序列，应如何编

7、写算法。18编写一个求解8后问题的算法，并作出时间复杂性分析。19试分析回溯法与分支定界法的异同之处。20采用分支定界法编写一个求解货郎担问题的算法，并作出算法时间复杂性分析。21假设有k种不同面值的硬币（以元为单位，每种的个数不限）。编写一个用最少的硬币数找出n元钱的算法，并分析算法的时间复杂性。#include int main()int change;coutchange;cout找给顾客的五角硬币个数为：change/50endl;change=change%50;cout找给顾客的壹角硬币个数为：change/10endl;change=change%10;cout找给顾客的伍分硬币

8、个数为：change/5endl;change=change%5;cout找给顾客的贰分硬币个数为：change/2endl;change=change%2;cout找给顾客的壹分硬币个数为：changeendl;return 0;22考虑一个“模糊”的算法查找T的子串P，先快速找到与P相似的子串，再进一步确认之。23设计一个算法确定K个矩阵相乘的最优次序，并分析该算法的时间复杂性。方法一：动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有

9、用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 本实验的算法思路是： 1、计算最优值算法MatrixChain()：建立两张表（即程序中的*m和*s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2、输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程

10、Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、实验源程序 建立一个矩阵的类Matrix。 Matrix.h代码#ifndef MATRIX_H #define MATRIX_H class Matrix public: Matrix(); /构造函数 Matrix(); /析构函数 bool Run(); /运行接口函数 private: int W; /记录矩阵的个数 int *m; /存放最优值，即最小运算量 i

11、nt *s; /断开位置 int *p; /存放 bool Input(); /处理输入 bool MatrixChain();/计算最优值算法 void Traceback(int i,int j,int *s); /输出矩阵加括号的方式 ; #endif Matrix.cpp代码#define N 50 #include #include #include Matrix.h /构造函数，作变量初始化工作，为指针分配内存空间 Matrix:Matrix() W=0; m = new int*N; s = new int*N; for(int i=0; iN ; i+) mi = new in

12、tN; si = new intN; p = new intN; /析构函数，释放内存 Matrix:Matrix() for(int i=0; iN ; i+) delete mi; delete si; delete m; delete s; delete p; /处理键盘输入 bool Matrix:Input() int w; coutw; W = w; cout输入矩阵A1维数p0p1; for(int i=2 ; i=W ; i+) int m = pi-1; cout输入矩阵Aipi-1pi; if(pi-1 != m) coutendl维数不对，矩阵不可乘！endl; exit

13、(1); /coutendl; if(p!=NULL) return true; else return false; /计算最优值算法 bool Matrix:MatrixChain() if(NULL = p) return false; for(int i=1;i=W;i+) mii=0; for(int r=2;r=W;r+) for(int i=1;i=W-r+1;i+) int j=i+r-1; mij = mi+1j + pi-1*pi*pj; sij = i; for(int k=i+1;kj;k+) int t = mik + mk+1j + pi-1*pk*pj; if(t

14、mij) mij = t; sij = k; return true; /输出矩阵结合方式，加括号 void Matrix:Traceback(int i,int j,int *s) if(i = j) coutAi; else if(i+1 = j) cout(AiAj); else cout(; Traceback(i,sij,s); Traceback(sij+1,j,s); cout); bool Matrix:Run() if(Matrix:Input() if(Matrix:MatrixChain() Matrix:Traceback(1,W,s); cout=j) return

15、i; else return j;int Min(int i,int j)if(i=j)return j;else return i;struct point fun1(int offset,int end,int n)/传入参数为查找下限，上限，注意上限下标不在查找范围内struct point temp, temp1,temp2;if(n=2) temp.max=Max(arrayoffset,arrayend-1);temp.min=Min(arrayoffset,arrayend-1);return temp;elsetemp1=fun1(offset,(offset+end)/2,n

16、/2);/每次规模减半temp2=fun1(offset+end)/2,end,n/2); temp.max=Max(temp1.max,temp2.max);temp.min=Min(temp1.min,temp2.min);return temp;void main() struct point a1,a2;int i,n;for(i=0;i50;i+) arrayi=0;printf(Input the total n=:n);scanf(%d,&n);printf(Input the numbers:n);for(i=0;in;i+)scanf(%d,&arrayi);a1=fun1(

17、0,n,n);printf(Max=%dnMin=%dn,a1.max,a1.min);方法二：25用分治法一个算法从数A1：n中同时找出最大元素，分析算法的时间复杂性，并思考为什么是这样的结果。同上26在一个数组中出现次数最多的元素称为“众数”，编写一个找出众数的算法，并分析算法时间复杂性。int most(int a,int length) /length数组长度int i,j,k;int max,value;int num100100;num00=a0;num01=1;j=0;for(i=1;ilength;i+)for(k=0;kj)j+;numj0=ai;numj1=1;max=0;

18、for(k=;kmax)max=numk1;value=numk0;return value; /出现次数最多的数字27设计一个使用Hash法的算法在数组中找出“众数”，并分析时间复杂性。#include #include #define N 100010 using namespace std; int aN; int main() int test; scanf(%d,&test); while(test-) int n; scanf(%d,&n); int i,t; for(i=0;iN;i+) ai=0; for(i=0;in;i+) scanf(%d,&t); at+; int p,

19、ans=0; for(i=0;ians) p=i; ans=ai; printf(%d %dn,p,ans); return 0; 28设计一个时间复杂性不超过O(n2)的算法，找出n个数组成的序列中最长的单调递增序列。【设计原理】将数组a复制到数组x,先用排序算法将数组x排序，在调用查找最长公共子序列的算法求出数组a和数组x中的最长公共子序列，因为数组x是单调递增的，所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。【概要设计】数据：N：数组元素个数。aN：用于存放数组。XN：复制数组aN，并排序。cij：存储a和x的最长公共子序列的长度。bij：记录cij的值是由哪一个资问题

20、的解得到的。函数：int Partition(int a,int p,int t,int x);/数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。void Swap(int &x,int &y);/交换元素x和yvoid QuickSort(int a,int p,int r);/快速排序。void LCSL(int m,int n,int *x,int *y,int *c,int *b);/计算最长公共子序列长度。void LCS(int i,int j,int *x,int *b);根据bij的内容打印a,x数组的最长公共子序列。【详细设计】#include#include

21、using namespace std; #define N 10void LCSL(int m,int n,int *x,int *y,int *c,int *b);/计算最长公共子序列长度。void LCS(int i,int j,int *x,int *b);/根据bij的内容打印a,x数组的最长公共子序列。void QuickSort(int a,int p,int r);/快速排序。int Partition(int a,int p,int t);/数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。void Swap(int &x,int &y);/交换元素x和y。/计

22、算最长公共子序列长度void LCSL(int m,int n,int *x,int *y,int cN,int bN)c00=0;int i,j;for(i=1;i=m;i+) ci0=0;for(i=1;i=n;i+) c0i=0; for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; coutcmmendl;/根据bij的内容打印a,x数组的最长公共子序列void LCS(int i,int j,int *x,int bN) if(i=0|j=0) return; if(bij=1) LCS(i

23、-1,j-1,x,b); for(int y=1;yi;y+) if(xy=xi) return; coutxi ;else if(bij=2) LCS(i-1,j,x,b);else LCS(i,j-1,x,b);void QuickSort(int a,int p,int r)if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序int Partition(int a,int p,int r)int i=p, j=r+1;int x=ap;/将x的元素交换到右边区域while(

24、true) while(a-jx); while(ij)&a+i=j)break; Swap(ai,aj);ap=aj; aj=x; return j;void Swap(int &x,int &y)int t;t=x;x=y;y=t; void main(void) int *a,*x; a=new intN; x=new intN; int bNN; int cNN; cout请输入十个数：endl; for(int i=1;iai; xi=ai; QuickSort(x,1,N-1); LCSL(N-1,N-1,a,x,c,b); LCS(N-1,N-1,a,b);此方法的算法复杂性应为

25、O(nlogn)29从1，2，n中找出所有质数，设计一个较优的算法。方法一：由于一个合数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，那么剩下的就是质数了。例如要查找100以内的质数，首先2是质数，把2的倍数去掉；此时3没有被去掉，可认为是质数，所以把3的倍数去掉；再到5，再到7，7之后呢，因为8，9，10刚才都被去掉了，而100以内的任意合数肯定都有一个因子小于10（100的开方），所以，去掉，2，3，5，7的倍数后剩下的都是质数了。用程序可以这样解决，引入布尔类型数组ai，如果i是质数，ai=true，否则ai=false。那么划掉i可以表示成ai=false。 /找出n以内质数void Sieve(int n) boo