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

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

2、earch(m+1);am=1;search(m+1);搜索排列树的一般模式：void search(i nt m)/递归结束条件/相应的处理（输出结果）/设置状态：0表示不要该物品/递归搜索：继续确定下一个物品/设置状态：1表示要该物品/递归搜索：继续确定下一个物品if(mn)/递归结束条件output。；/相应的处理(输出结果)elsefor(i=m;ib the n retur n -1else begi nm=(a+b)div 2;if x=Lm the n retur n (m)else if xLmthe n return Bin arySearch(L,m+1,b,x);else

3、return Bin arySearch(L,a,m-1,x); en d;en d;2请采用快速排序算法为下列数字排序，并写出最终结果(21 25 49 25* 16 08)快速排序的基本思想：选定一个基准值元素，对带排序的序列进行分割，分割之后的序 列一部分小于基准值元素，另一部分大于基准值元素，再对这两个分割好的子序列进行上述 的过程。void swap(i nt a,i nt b) int t;t =a ;a =b ;b =t ;int Partiti on (i nt arr,i nt low,i nt high)in t 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(i nt a,i nt low,i nt high)if (low =high)每个子

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

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

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

8、下两个选手时，比赛日程表的指定就很简单了。核心代码：int N = 1;void UpRightCopy(i nt n, int array)for(i nt i = 0; i n; i+)for(i nt j = n; j 2 * n ;j+)arrayN * i + j = 2 * n + 1 -arrayN * i + 2 * n - 1 - j;void Down RightCopy(i nt n, int array)for(i nt i = n; i 2 * n; i+)for (int j = n; j 2 * n ;j+)arrayN * i + j = arrayN * (i

9、 - n) + j - n;void LeftDow nCopy(i nt n, int array)for (i nt i = n; i 2 * n; i+)for (int j = 0; j n ;j+)arrayN * i + j = arrayN * (i - n) + j + n;void turn (i nt n, int array)if(n = 1)array0 = 1;elseturn(n / 2, array);Dow nRightCopy( n / 2, array);UpRightCopy(n / 2, array);LeftDow nCopy (n / 2, arra

10、y);7最长公共子序列核心代码：char a201,b201;int n1, n2;void search()int List201201;for(i nt i=0;i=n 1;i+)ListiO=O;for(i nt j=O;j=n 2;j+)ListOj=O;for(i nt i=1;i=n 1;i+)for(i nt j=1;jListij-1)Listi j=Listi-1j;elseListi j=Listi j-1;8矩阵连乘问题核心代码：int n;in t p11;void a1111,temp;for(i nt i=1;i=n ;i+)aii=O；for

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

12、ion2(效率其次)1. long Fibonacci2( int n)2. 3. if (n = 0)4. return 0;5. else if (n =1)6. return 1;7. else if (n 1)8. 9.9. if (tempResultn !=0)10. return tempResultn;11. else12. 13. tempResultn = Fibonacci2 (n -1) + Fibonacci2 (n -15.return tempResultn;16.17.18.Version 3（效率最高-放弃递归用循环实现）1.long Fibonacci3(

13、int n)2.3.long * temp = new long n + 1;4.5.temp 0 = 0;6.7.if (n 0)8.temp 1 = 1;9.10.for (int i = 2; i =f2或s2=f1时，活动1与活动2相容。（区间表示的是活 动的起始时间s和结束时间f）核心代码：struct actio nint begi n;int en d;a1000;int n;/n表示活动的总数int sum=0;/sum表示能参加的活动的数量void search。sum=1;int temp=aO.e nd;/temp 表示第一个活动结束的时间 for(i nt i=1;i=

14、temp)sum+;temp=ai.e nd;void selecti on _sort()for(i nt i=0;i n;i+)int k=i;for(i nt j=i+1;j n ;j+)if(a j.endak.end)k=j;struct actio n temp=ai;ai=ak;ak=temp;11. 最优服务次序问题思路是最短服务时间优先，先将服务时间排序，然后注意后面的等待服务时间既包括等 待部分，也包括服务部分。贪心策略：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T。新问题和

15、原问题相同，只是问题规模由n减小为n-1。基于此种选择策略，对新问题T，选择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. double gr

16、eedy(vectorx, int s)2. 3. vectorst(s+1,0);文案大全标准实用4.vectorv int su(s+1,0);5.int n=x.size();6.sort(x.begi n( ),x.e nd();7.int i=0,j=0;8.while (in)9.st j+=xi;10.suj+=stj;11.i+;12.j+;13.if (j=s)j=0;14.15.double t=0;16.for (i=0;i n;6.int temp;7.for (int j = 0; j n; j+)8.9.scanf( %d，&xj);10.11.sort(x,x+

17、n);12.for (int i = 1; i n; i+)13.xi+=xi-1;14.double t = 0;15.for (int i = 0; i n; i+)16.t+=xi;17.t/=n;18.cout.setf(ios:fixed);19.cout setprecisi on(2) t en dl;20.system( pause);21.return 0;22. 12. 最短路径问题Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。

18、设u是G的某一个顶点，把 从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从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的最短特殊路径长度。 在Dijkstr

19、a算法中做贪心选择时， 实际上是考虑 当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点 i,则这种路的最短长度是 distu+cui。 如果distu+cuidisti，则需要更新 disti的值。步骤如下：(1)用带权的邻接矩阵 c来表示带权有向图，cij表示弧上的权值。设S为已 知最短路径的终点的集合，它的初始状态为空集。从源点 v经过S到图上其余各点vi的当前 最短路径长度的初值为：disti=cvi, vi 属于V.(2) 选择vu,使得distu=Mindisti | vi 属于V-S,vj就是长度最短的最短路径

20、的终点。 令 S=S U u.(3) 修改从v到集合V-S上任一顶点vi的当前最短路径长度：如果distu+cuj distj 则修改 distj= distu+cuj.(4) 重复操作(2),(3)共n-1次.1. con st int N = 5;2. const int M = 1000;3. template class Type4. void Dijkstra( int n, int v,Type dist, int prev,Type cN+1);5. void Traceback( int v,int i,int prev); / 输出最短路径 v 源点，i 终点6. int m

21、ain()7. 8. int v = 1; / 源点为 19. int distN+1,prevN+1,cN+1N+1;10.10. cout有向图权的矩阵为：e ndl;11. for (int i=1; i=N; i+)12. 13. for (int j=1; jcij;16. coutcij;17. 18. coute ndl;19. 20. Dijkstra(N,v,dist,prev,c);21. for (int i=2; i=N; i+)23.24.cout 源点1到点i 的最短路径长度为：disti，其路径为”；25.Traceback(1,i,prev);26.coute

22、ndl;27.28.29.return 0;30.31.template 32.void Dijkstra( int n, int v,Type dist, int prev,Type cN+1)33.34.bool sN+1;35.for (int i=1; i=n; i+)36.37.disti = cvi;disti表示当前从源到顶点i的最短特殊路径长度38.si = false ;39.if (disti = M)40.41.previ = 0;/记录从源到顶点i的最短路径i的前一个顶点42.43.else44.文案大全标准实用4

23、.4.65.66.文案大全previ = v;distv = 0;sv = true ;for (int i=1; in; i+)int temp = M;int u = v; / 上一顶点/取出V-S中具有最短特殊路径长度的顶点ufor (int j=1; j=n; j+)if (!s j) & (dist jtemp)u = j;temp = distj;su = true ;/根据作出的贪心选择更新Dist值for (int j=1; j=n; j+)标准实用

24、8.文案大全Type n ewdist = distu + cuj;if (n ewdist distj)dist j = n ewdist;prevj = u;/输出最短路径v源点，i终点void Traceback( int v,int i,int prev)if (v = i)couti;return ;Traceback(v,previ,prev);cout i;标准实用89. 13. 霍夫曼编码问题(要求画出霍夫曼树)哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤 如下:(1) 哈夫曼算法以自底向

25、上的方式构造表示最优前缀码的二叉树T。(2) 算法以|C|个叶结点开始，执行|C| 1次的“合并”运算后产生最终所要求的树T。(3) 假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列 Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n 1次的合并后，优先队列中只剩下一棵树，即所要求的树To构造过程如图所示:文案大全算法中用到的类定义:1. template class Type2. class Huffman3. 4. friendBinaryTree H

26、uffmanTree(Type,int );5. public :6. operator Type()const7. 8. return weight;9. 10. /private:11. BinaryTree tree;12. Type weight;13. ;算法HuffmanTree 描述如下：1. template 2. BinaryTree HuffmanTree(Type f,int n)3. 4. /生成单节点树5. Huffman *w = new Huffmann+1;6. BinaryTree z,zero;6.17.18

27、.8.29.for (int i=1; i=n; i+)乙M akeTree(i,zero,zero);wi.weight = fi;wi.tree = z;/建优先队列MinH eapHuffma n Q(n);for (int i=1; i=n; i+) Q.lnsert(wi);/反复合并最小频率树Huffma n x,y;for (int i=1; in; i+)x = Q.RemoveMi n();y = Q.RemoveMi n();z.MakeTree(O,x.tree,y.tree);x.weight += y.weigh

28、t;x.tree = z;Q.l nsert(x);x = Q.RemoveMi n();delete w;30. return x.tree;31. 32.14. 用贪心算法解决搬桌子问题关键思想：把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。算法代码：#in cludeint mai n()structint start;int end;a100;int i,j;int n,m,min,nu m,temp,used100=0;scan f(%d%d,&m,&n);for(i=0;i n;i+)scan f(%d%d,&ai.start,&ai.e nd);/ sort(a,n)

29、;/按start从小到大对数组 a排序mi n=0;num=0;while( numn)temp=O;for(i=0;i =temp)temp=ai.e nd;usedi=1;nu m+;mi n+;prin tf(%d,mi n);15.八数码难题核心代码：1 #in clude 2 #in clude9种状态3 #define len 362888/状态共有 362880 种，数组稍微开大点4 #define le 9/ 每种状态有9个数据，也可看为每种状态下又有5 typedef int statele;/状态：表示九个格子6 state stlen,goal;/st为状态数组 goal

30、为目标数组/dis为每7 int dislen,factle,headlen,vislen,der42= -1,0,1,0,0,-1,0,1;8种状态的已走的步骤 /der为方向：上，下，左，右9 void encode()/ 编码10int i;1 for (i=fact0=1; ile; i+)1 facti=facti-1*i;12 int decode( int s)/ 解码13 int i,j,code,cnt;1 for (i=code=0; ile; i+)4 1 for (cnt=O,j=i+1; jstsj)1 cn t+;6 code+=cnt*fact8-i;1 7 if

31、 (viscode)1 return 0;8 else1 retur n viscode=1;9 2int bfs()0 2 int front=1,rear=2,i,x,y,z,nx,ny,nz;1 en code();2 while (frontrear)2 2 state & s=stfro nt;3 if (memcmp (s,goal, sizeof (s)=0)/ 对 front 状态和目标状态进行比较2 return fron t;4 for (i=0; ile; i+)/找到为0的元素，即空的那个格子，这里选取空2的那个格子是应为相对于1,2,3,8这样的数据，0作为判断依据简

32、单于用数据作为判断5依据2 if (si=0) break ;6 x=i/3;2 y=i%3;7 z=i;/记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右2从上到下依次递增8 for (i=0; i=0&n x=0&n y3)3 2 state & t=strear;3 memcpy (&t,&s, sizeof (s);/记录此时的状态即九个格子的数值3 tz=s nz;3 tn z=sz;4 disrear=disfr on t+1;3 if (decode(rear)/判断strear这种状态是否已经出现过5 rear+;3 6 3 fron t+;7 3 return 0

33、;8 3int main( void )4 int i,oj;0 for (i=0; ile; i+)scanf (”d，&st1i);/按从左到右从上到下的顺序存储数据for (i=0; ile; i+)scanf (%d，&goali);oj=bfs();if (oj)printf (%dn ,disoj);elseputs (Impossible );4142434445464748495051return 0;文案大全52535455565758596061626364656667686916.图的M着色问题考虑所有的图，讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。用m种颜色为无向图 G=(V,E)着色，其中，V的顶点个数为n,可以用一个n元组 x=(x1,x2,xn)来描述图的一种可能着色，其中， xi 1,2,m , (1 i =1 )层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。1. #i nclude