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

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

2、put(); /相应的处理(输出结果) 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 BinarySe

3、arch(L,m+1,b,x); else return BinarySearch(L,a,m-1,x);end; end;请采用快速排序算法为如下数字排序，并写出最终结果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; /将列表划分成相等的两个子列表,假如有奇数个元素，如此在左边子列表大于右边子列表elseint 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+;el

6、sebk=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; 装载问题问题关键在于：首先将第一艘船尽可能装满且c1最大值max，然后将剩余的局部装上第二艘船c2，假如:总重量-c1c2如此能装入两艘船。关键代码：int c1,c2,n,w10;int weight=0,max=0;void search(int m)

7、 if(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; 循环赛日程表(递归与分治)设计思想：按分治策略，可以将所有选手对分为两半，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); Le

10、ftDownCopy(n / 2, array); 最长公共子序列核心代码： 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; 矩阵连乘问题核心代码：int n;int p11;void search()int a1111,temp;for(int i=

11、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; 用备忘录算法实现计算Fibonacci数列核心代码：int Fib(int n)int resultn=0,0,.,0;int f1,f2;if(n1)returnFibonacci(n-1)+Fibonacci(n-2);elsereturn-1;Version2(效率其次)long

12、Fibonacci2(intn)if(n=0)return0;elseif(n=1)return1;elseif(n1)if(tempResultn!=0)returntempResultn;elsetempResultn=Fibonacci2(n-1)+Fibonacci2(n-2);returntempResultn;Version 3(效率最高-放弃递归用循环实现)longFibonacci3(intn)long*temp=newlongn+1;temp0=0;if(n0)temp1=1;for(inti=2;i=f2或s2=f1时，活动1与活动2相容。区间表示的是活动的起始时间s和完毕

13、时间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 selection_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;最

14、优服务次序问题思路是最短服务时间优先，先将服务时间排序，然后注意后面的等待服务时间既包括等待局部，也包括服务局部。贪心策略：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进展服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T。新问题和原问题一样，只是问题规模由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

15、-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个队列上所有顾客的等待时间；第一种代码：doublegreedy(vectorx,ints)vectorst(s+1,0);vectorsu(s+1,0);intn=x.size();sort(x.begin(),x.end();inti=0,j=0;while(in)stj+=xi;suj+=stj;i+;j+;if(j=s)j=0;doublet=0;for(i=0;in;inttemp;fo

16、r(intj=0;jn;j+)scanf(%d,&xj);sort(x,x+n);for(inti=1;in;i+)xi+=xi-1;doublet=0;for(inti=0;in;i+)t+=xi;t/=n;cout.setf(ios:fixed);coutsetprecision(2)tendl;system(pause);return0;最短路径问题Dijkstra算法是解单源最短路径问题的贪心算法。其根本思想是，设置顶点集合S并不断地作贪心选择来扩大这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点

17、的路称为从源到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的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后，可能出现一条到顶点

18、的新的特殊路，如果这条新特殊路是先经过老的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就是长度最短的最短路径的终点。令S=S U u.(3) 修改从v到集合V-S上任一顶点vi的当前最短路径长

19、度:如果 distu+cuj distj 如此修改 distj= distu+cuj.(4) 重复操作(2),(3)共n-1次.constintN=5;constintM=1000;templatevoidDijkstra(intn,intv,Typedist,intprev,TypecN+1);voidTraceback(intv,inti,intprev);/输出最短路径v源点，i终点intmain()intv=1;/源点为1intdistN+1,prevN+1,cN+1N+1;cout有向图权的矩阵为：endl;for(inti=1;i=N;i+)for(intj=1;jcij;cout

20、cij;coutendl;Dijkstra(N,v,dist,prev,c);for(inti=2;i=N;i+)cout源点1到点i的最短路径长度为:disti，其路径为;Traceback(1,i,prev);coutendl;return0;templatevoidDijkstra(intn,intv,Typedist,intprev,TypecN+1)boolsN+1;for(inti=1;i=n;i+)disti=cvi;/disti表示当前从源到顶点i的最短特殊路径长度si=false;if(disti=M)previ=0;/记录从源到顶点i的最短路径i的前一个顶点elseprev

21、i=v;distv=0;sv=true;for(inti=1;in;i+)inttemp=M;intu=v;/上一顶点/取出V-S中具有最短特殊路径长度的顶点ufor(intj=1;j=n;j+)if(!sj)&(distjtemp)u=j;temp=distj;su=true;/根据作出的贪心选择更新Dist值for(intj=1;j=n;j+)if(!sj)&(cujM)Typenewdist=distu+cuj;if(newdistdistj)distj=newdist;prevj=u;/输出最短路径v源点，i终点voidTraceback(intv,inti,intprev)if(v=

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

23、合并后，优先队列中只剩下一棵树，即所要求的树T。构造过程如下列图：算法中用到的类定义：templateclassHuffmanfriendBinaryTreeHuffmanTree(Type,int);public:operatorType()constreturnweight;/private:BinaryTreetree;Typeweight;算法HuffmanTree描述如下：templateBinaryTreeHuffmanTree(Typef,intn)/生成单节点树Huffman*w=newHuffmann+1;BinaryTreez,zero;for(inti=1;i=n;i+)

24、z.MakeTree(i,zero,zero);wi.weight=fi;wi.tree=z;/建优先队列MinHeapHuffmanQ(n);for(inti=1;i=n;i+)Q.Insert(wi);/反复合并最小频率树Huffmanx,y;for(inti=1;in;i+)x=Q.RemoveMin();y=Q.RemoveMin();z.MakeTree(0,x.tree,y.tree);+=y.weight;=z;Q.Insert(x);x=Q.RemoveMin();deletew;returnx.tree;用贪心算法解决搬桌子问题关键思想：把课桌按起点从小到大排序，每次都是搬离

25、当前位置最近的课桌。算法代码：#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);八数码难题核心代码：12345678

26、9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include#define len 362888/状态共有362880种，数组稍微开大点#define le 9/每种状态有9个数据,也可看为每种状态下又有9种状态typedefintstatele;/状态：表示九个格子state stlen,goal;/st为状态数组goal为目标数组intdislen,factle,headlen

27、,vislen,der42= -1,0,1,0,0,-1,0,1;/dis为每种状态的已走的步骤/der为方向:上，下，左，右voidencode()/编码inti;for(i=fact0=1; ile; i+)facti=facti-1*i;intdecode(ints)/解码inti,j,code,t;for(i=code=0; ile; i+)for(t=0,j=i+1; jstsj)t+;code+=t*fact8-i;if(viscode)return0; elsereturnviscode=1;intbfs()intfront=1,rear=2,i,x,y,z,nx,ny,nz;e

28、ncode();while(frontrear)state& s=stfront;if(memcmp(s,goal,sizeof(s)=0)/对front状态和目标状态进展比拟returnfront;for(i=0; ile; i+)/找到为0的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,2,3,.8这样的数据，0作为判断依据简单于用数据作为判断依据if(si=0)break;x=i/3;y=i%3;z=i;/记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右从上到下依次递增for(i=0; i=0&nx=0&ny3)state& t=strear;memcpy(&t,

29、&s,sizeof(s);/记录此时的状态即九个格子的数值tz=snz;tnz=sz;disrear=disfront+1;if(decode(rear)/判断strear这种状态是否已经出现过rear+;front+;return0;intmain(void)inti,oj;for(i=0; ile; i+)scanf(%d,&st1i);/按从左到右从上到下的顺序存储数据for(i=0; i=1层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。#includestdafx.h#include#includeusingnamespacestd;constintN=5;/

30、图的顶点数constintM=3;/色彩数ifstreamfin(5d8.txt);classColorfriendintmColoring(int,int,int*);private:boolOk(intk);voidBacktrack(intt);intn,/图的顶点数m,/可用的颜色数*a,/图的邻接矩阵*x;/当前解longsum;/当前已找到的可m着色方案数;intmColoring(intn,intm,int*a);intmain()int*a=newint*N+1;for(inti=1;i=N;i+)ai=newintN+1;cout图G的邻接矩阵为:endl;for(inti=

31、1;i=N;i+)for(intj=1;jaij;coutaij;coutendl;cout图G的着色方案如下：endl;cout当m=M时，图G的可行着色方案数目为：mColoring(N,M,a)endl;for(inti=1;in)sum+;for(inti=1;i=n;i+)coutxi;coutendl;elsefor(inti=1;i=m;i+)xt=i;if(Ok(t)Backtrack(t+1);boolColor:Ok(intk)/检查颜色可用性for(intj=1;j=n;j+)if(akj=1)&(xj=xk)/相邻且颜色一样returnfalse;returntrue;intmColoring(intn,intm,int*a)ColorX;/初始化X=n;=m;=a;=0;int*p=newintn+1;for(inti=0;in如此已求得一个解输出着色方案即可；否如此，依次对顶点t着色1-m。假如t与所有其他相邻顶点无颜色冲突，如此继续为下一顶点着