西工大算法复习资料总结(最终修订版)

1、笔试部分1 简答题(40分)1. 算法的基本概念、性质及其与程序的联系与区别算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法性质：输入-有零个或者多个外部量作为算法的输入； 输出-算法产生至少一个量最为输出； 确定性：组成算法的每条指令是清晰的、无歧义的； 有限性：算法中指令的执行次数有限和执行的时间有限。 程序：是算法用某种设计语言的具体实现，程序可以不满足算法的有限性。2. 大O表示法的含义和渐进时间复杂度（要会计算复杂度）大O表示法：称一个函数g(n)是O(f(n)，当且仅当存在常数c0和n0=1，对一切nn0均有|g(n)|n) /递归结束条件 output();

2、 /相应的处理(输出结果) else am=0; /设置状态：0表示不要该物品 search(m+1); /递归搜索：继续确定下一个物品 am=1; /设置状态：1表示要该物品 search(m+1); /递归搜索：继续确定下一个物品 搜索排列树的一般模式： void search(int m) if(mn) /递归结束条件 output(); /相应的处理(输出结果) else for(i=m;ib then return -1else beginm=(a+b)div 2;if x=Lm then return (m)else if xLmthen return BinarySearch(L

3、,m+1,b,x); else return BinarySearch(L,a,m-1,x); end; end;2. 请采用快速排序算法为下列数字排序，并写出最终结果（21 25 49 25* 16 08）快速排序的基本思想:选定一个基准值元素，对带排序的序列进行分割，分割之后的序列一部分小于基准值元素，另一部分大于基准值元素，再对这两个分割好的子序列进行上述的过程。void swap(int a,int b)int t;t =a ;a =b ;b =t ; int Partition(int arr,int low,int high) int pivot=arrlow;/采用子序列的第一个

4、元素作为基准元素 while (low high) /从后往前在后半部分中寻找第一个小于基准元素的元素 while (low = pivot) -high; /将这个比枢纽元素小的元素交换到前半部分 swap(arrlow, arrhigh); /从前往后在前半部分中寻找第一个大于基准元素的元素 while (low high &arr low =pivot ) +low ; /将这个基准元素大的元素交换到后半部分 swap (arr low ,arr high ); return low ;/返回基准元素所在的位置 void QuickSort(int a,int low,int high)

5、 if (low =high)/每个子列表中剩下一个元素时停止return; /将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右边子列表else int mid=(low+high)/2; MergeSort(low,mid);/递归划分子列表MergeSort(mid+1,high);/递归划分子列表/新建一个数组b用于存放归并的元素int b=new inthigh-low+1;/两个子列表进行排序归并，直到两个子列表中的一个结束for(int i=low,j=mid+1,k=low;i=mid&j=high;k+) if(arri=arrj)bk=arri;i+;els

6、ebk=arrj;j+;for(;j=high;j+,k+)/如果第二个子列表中仍然有元素，则追加到新列表bk=arrj;for(;i=mid;i+,k+)/如果第一个子列表中仍然有元素，则追加到新列表bk=arri;for(int z=0;zhigh-low+1;z+)/将排序的数组b的所有元素复制到原始数组arr中arrz=bz; 4. 装载问题问题关键在于：首先将第一艘船尽可能装满且c1最大值max，然后将剩余的部分装上第二艘船c2，若:总重量-c1c2则能装入两艘船。关键代码：int c1,c2,n,w10;int weight=0,max=0;void search(int m) i

7、f(m=n) if(weightmax) max=weight; else if(weight+=wm=n)checkmax(); else am=0; search(m+1); am=1; search(m+1) void checkmax() int i; int weight=0,value=0; for(i=0;in;i+) if(ai=1)weight+=wi;value+=vi;if(weightmax) max=value; 6. 循环赛日程表(递归与分治)设计思想：按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用

8、这种一分为二的策略对选手进行分割，直至只剩下两个选手时，比赛日程表的指定就很简单了。核心代码：int N = 1; void UpRightCopy(int n, int array) for(int i = 0; i n; i+) for(int j = n; j 2 * n;j+) arrayN * i + j = 2 * n + 1 -arrayN * i + 2 * n - 1 - j; void DownRightCopy(int n, int array) for(int i = n; i 2 * n; i+) for (int j = n; j 2 * n;j+) arrayN

9、* i + j = arrayN * (i - n) + j - n; void LeftDownCopy(int n, int array) for (int i = n; i 2 * n; i+) for (int j = 0; j n;j+) arrayN * i + j = arrayN * (i - n) + j + n; void turn(int n, int array) if(n = 1) array0 = 1; else turn(n / 2, array); DownRightCopy(n / 2, array); UpRightCopy(n / 2, array); L

10、eftDownCopy(n / 2, array); 7. 最长公共子序列核心代码： char a201,b201; int n1,n2; void search() int List201201;for(int i=0;i=n1;i+) Listi0=0;for(int j=0;j=n2;j+) List0j=0;for(int i=1;i=n1;i+)for(int j=1;jListij-1) Listij=Listi-1j; else Listij=Listij-1; 8. 矩阵连乘问题核心代码：int n;int p11;void search()int a1111,temp;for

11、(int i=1;i=n;i+)aii=0; for(int d=1;d=n-1;d+) for(int i;i=n-d;i+)int j=i+d;aij=0+ai+1j+pi-1*pi*pj;for(int k=i+1;kj;k+)temp=aik+ak+1j+pi-1*pk*pj;if(tempaij)aij=temp; 9. 用备忘录算法实现计算Fibonacci数列核心代码：int Fib(int n)int resultn=0,0,.,0;int f1,f2;if(n1)8. returnFibonacci(n-1)+Fibonacci(n-2);9. else10. return-

12、1;11. Version2(效率其次)1. longFibonacci2(intn)2. 3. if(n=0)4. return0;5. elseif(n=1)6. return1;7. elseif(n1)8. 9. 10. if(tempResultn!=0)11. returntempResultn;12. else13. 14. tempResultn=Fibonacci2(n-1)+Fibonacci2(n-2);15. returntempResultn;16. 17. 18. Version 3(效率最高-放弃递归用循环实现)1. longFibonacci3(intn)2.

13、3. long*temp=newlongn+1;4. 5. temp0=0;6. 7. if(n0)8. temp1=1;9. 10. for(inti=2;i=f2或s2=f1时，活动1与活动2相容。（区间表示的是活动的起始时间s和结束时间f）核心代码：struct actionint begin;int end;a1000;int n;/n表示活动的总数int sum=0;/sum表示能参加的活动的数量void search()sum=1;int temp=a0.end;/temp表示第一个活动结束的时间for(int i=1;i=temp)sum+;temp=ai.end;void se

14、lection_sort()for(int i=0;in;i+)int k=i;for(int j=i+1;jn;j+)if(aj.endak.end)k=j; struct action temp=ai; ai=ak; ak=temp;11. 最优服务次序问题思路是最短服务时间优先，先将服务时间排序，然后注意后面的等待服务时间既包括等待部分，也包括服务部分。贪心策略：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T。新问题和原问题相同，只是问题规模由n减小为n-1。基于此种选择策略，对新问题T，选

15、择n-1顾客中选择服务时间最短的先进行服务，如此进行下去，直至所有服务都完成为止。每个客户需要的等待时间为: T(1)=t(1); T(2)=t(1)+t(2); . T(n)=t(1)+t(2)+.+t(n);总等待时间为：T=n*t(1)+(n-1)*t(2)+(n-2)*t(3)+.+(n+1-i)*t(i)+.+2*t(n-1)+1*t(n)注：st是服务数组，stj为第j个队列上的某一个顾客的等待时间；su是求和数组，suj的值为第j个队列上所有顾客的等待时间；第一种代码：1. doublegreedy(vectorx,ints)2. 3. vectorst(s+1,0);4. ve

16、ctorsu(s+1,0);5. intn=x.size();6. sort(x.begin(),x.end();7. inti=0,j=0;8. while(in)9. stj+=xi;10. suj+=stj;11. i+;12. j+;13. if(j=s)j=0;14. 15. doublet=0;16. for(i=0;in;6. inttemp;7. for(intj=0;jn;j+)8. 9. scanf(%d,&xj);10. 11. sort(x,x+n);12. for(inti=1;in;i+)13. xi+=xi-1;14. doublet=0;15. for(inti

17、=0;in;i+)16. t+=xi;17. t/=n;18. cout.setf(ios:fixed);19. coutsetprecision(2)tendl;20. system(pause);21. return0;22. 12. 最短路径问题Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra

18、算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。Dijkstra算法可描述如下，其中输入带权有向图是G=(V,E)，V=1,2,，n，顶点v是源。c是一个二维数组，cij表示边(i,j)的权。当(i,j)不属于E时，cij是一个大数。disti表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i，则这种路的最

19、短长度是distu+cui。如果distu+cuidisti，则需要更新disti的值。步骤如下： (1) 用带权的邻接矩阵c来表示带权有向图, cij表示弧上的权值。设S为已知最短路径的终点的集合,它的初始状态为空集。从源点v经过S到图上其余各点vi的当前最短路径长度的初值为：disti=cvi, vi属于V. (2) 选择vu, 使得distu=Mindisti | vi属于V-S,vj就是长度最短的最短路径的终点。令S=S U u. (3) 修改从v到集合V-S上任一顶点vi的当前最短路径长度:如果 distu+cuj distj 则修改 distj= distu+cuj. (4) 重复

20、操作(2),(3)共n-1次.1. constintN=5;2. constintM=1000;3. template4. voidDijkstra(intn,intv,Typedist,intprev,TypecN+1);5. voidTraceback(intv,inti,intprev);/输出最短路径v源点，i终点6. intmain()7. 8. intv=1;/源点为19. intdistN+1,prevN+1,cN+1N+1;10. 11. cout有向图权的矩阵为：endl;12. for(inti=1;i=N;i+)13. 14. for(intj=1;jcij;17. co

21、utcij;18. 19. coutendl;20. 21. Dijkstra(N,v,dist,prev,c);22. for(inti=2;i=N;i+)23. 24. cout源点1到点i的最短路径长度为:disti，其路径为;25. Traceback(1,i,prev);26. coutendl;27. 28. 29. return0;30. 31. template32. voidDijkstra(intn,intv,Typedist,intprev,TypecN+1)33. 34. boolsN+1;35. for(inti=1;i=n;i+)36. 37. disti=cvi;

22、/disti表示当前从源到顶点i的最短特殊路径长度38. si=false;39. if(disti=M)40. 41. previ=0;/记录从源到顶点i的最短路径i的前一个顶点42. 43. else44. 45. previ=v;46. 47. 48. distv=0;49. sv=true;50. for(inti=1;in;i+)51. 52. inttemp=M;53. intu=v;/上一顶点54. /取出V-S中具有最短特殊路径长度的顶点u55. for(intj=1;j=n;j+)56. 57. if(!sj)&(distjtemp)58. 59. u=j;60. temp=

23、distj;61. 62. 63. su=true;64. /根据作出的贪心选择更新Dist值65. for(intj=1;j=n;j+)66. 67. if(!sj)&(cujM)68. 69. Typenewdist=distu+cuj;70. if(newdistdistj)71. 72. distj=newdist;73. prevj=u;74. 75. 76. 77. 78. 79. /输出最短路径v源点，i终点80. voidTraceback(intv,inti,intprev)81. 82. if(v=i)83. 84. couti;85. return;86. 87. Tra

24、ceback(v,previ,prev);88. couti;89. 13. 霍夫曼编码问题（要求画出霍夫曼树）哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下： (1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 (2)算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 (3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的

25、合并后，优先队列中只剩下一棵树，即所要求的树T。构造过程如图所示：算法中用到的类定义：1. template2. classHuffman3. 4. friendBinaryTreeHuffmanTree(Type,int);5. public:6. operatorType()const7. 8. returnweight;9. 10. /private:11. BinaryTreetree;12. Typeweight;13. ;算法HuffmanTree描述如下：1. template2. BinaryTreeHuffmanTree(Typef,intn)3. 4. /生成单节点树5.

26、Huffman*w=newHuffmann+1;6. BinaryTreez,zero;7. 8. for(inti=1;i=n;i+)9. 10. z.MakeTree(i,zero,zero);11. wi.weight=fi;12. wi.tree=z;13. 14. /建优先队列15. MinHeapHuffmanQ(n);16. for(inti=1;i=n;i+)Q.Insert(wi);17. /反复合并最小频率树18. Huffmanx,y;19. for(inti=1;in;i+)20. 21. x=Q.RemoveMin();22. y=Q.RemoveMin();23.

27、z.MakeTree(0,x.tree,y.tree);24. x.weight+=y.weight;25. x.tree=z;26. Q.Insert(x);27. 28. x=Q.RemoveMin();29. deletew;30. returnx.tree;31. 32.14. 用贪心算法解决搬桌子问题关键思想：把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。算法代码：#includeint main()structint start;int end;a100;int i,j;int n,m,min,num,temp,used100=0;scanf(%d%d,&m,&n);for(i=0;in;i+)scanf(%d%d,&ai.start,&ai.end);/sort(a,n); /按start从小到大对数组a排序min=0;num=0;while(numn)temp=0;for(i=0;i=temp)temp=ai.end;usedi=1;num+;min+;printf(%d,min);15. 八数码难题核