大连理工大学算法分析与设计算法总结

一，马步程序简要算法描述：算法从1号节点作为当前节点开始进行搜索。从小到大深度优先尝试所有相连的节点，并把它作为下一次搜索的当前节点，如果最终能够回到起始点，并且每个节点经过且仅经过一次，则存在一条哈密顿回路。否则不存在哈密顿回路。优化：1，如果走一步之后发现，存在度数小于2的未走过的节点，则没有必要继续搜索，只能尝试其他节点。2，如果发现，当前存在大于等于两个度数为2的节点，则直接回溯到上一层节点，没有必要继续搜索。3，回溯到第一个节点后，如果没找到哈密顿回路则直接退出，没有必要尝试其他走法，因为另一条路径与当前遍历过的路径是对称的。#include #include #include usingnamespacestd;constintMaxn=10000;intdirx=-1,-2,-2,-1,1,2,2,1;intdiry=-2,-1,1,2,2,1,-1,-2;intn1,n2,n;boolusedMaxn;intansMaxn;intdegreeMaxn,degMaxn;intgraphMaxn8;boolvalid(intx,inty)returnx=0&x=0&yn2;voidgetGraph()for(inti=0;i n;+i)introw=i/n2;intcol=i%n2;degreei=0;for(intj=0;j8;+j)intx=row+dirxj;inty=col+diryj;if(!valid(x,y)continue;graphidegreei+=x*n2+y;degi=degreei;voidresume(intcur)for(inti=0;idegreecur;+i)intnext=graphcuri;if(usednext)continue;degnext+;boolupdate(intcur)boolret=true;for(inti=0;idegreecur;+i)intnext=graphcuri;if(usednext)continue;degnext-;if(degnext2&next!=graph01)ret=false;if(!ret)resume(cur);returnfalse;returntrue;booldfs(intstep,intcur) /递归版ansstep=cur;if(step=n-1)if(graph01!=cur)returnfalse;for(inti=0;i n;+i)printf(%d ,ansi);puts();returntrue;for(inti=0;idegreecur;+i)if(cur=0&i)break;intnext=graphcuri;if(usednext)continue;usednext=true;if(!update(cur)usednext=false;continue;if(dfs(step+1,next)returntrue;resume(cur);usednext=false;returnfalse;boolcheck()/ goto 版intwMaxn=0;memset(used,false,sizeof(used);intcur=0,next;used0=true;inti,step=0;l0:i=-1,ansstep=cur;if(step=n-1)if(graph01!=cur)gotol2;for(inti=0;i=degreecur)gotol2;next=graphcuri;if(usednext)gotol1;usednext=true;if(!update(cur)usednext=false;gotol1;step+;cur=next;gotol0;l2:cur=ans-step;resume(cur);next=graphcurwstep;usednext=false;if(step0)i=wstep;gotol1;returnfalse;intmain()while(scanf(%d %d,&n1,&n2)!=EOF)coutcas n1 n2endl;n=n1*n2;getGraph();if(!check()coutNo Answer!endl;return0;二，归并排序 & 快速排序归并排序：主要思想是分而治之合并已经排序好的两个数组。这样按照块大小从小到大的顺序，处理完所有元素之后，就用O(nlogn)的时间复杂度完成排序.优化：见程序注释快速排序: 主要思想仍然是分而治之，但他与归并排序处理数据的顺序正好相反，按照块大小从大到小的顺序处理，每次选取一个参考元素x，将比x小的放在左边，其他的放在右边，然后用同样的方法处理每个子块。平均时间复杂度为O（nlogn）,最坏时间复杂度为O(n2).#include iostream#include cstring#include cstdio#include algorithmusingnamespacestd;constintMaxn=1000000;templatestructInsertSortvoidstaticsort(T*a,intn)for(inti=1;i=0;-j)if(tmpaj)aj+1=aj;elsebreak;aj+1=tmp;/与插入相结合 不递归 不回写/如果想实现无逆序会使得各个块的大小不相同因此必须新加一个数组记录各个块的起始位置，这样做得不偿失 所以暂时无法加入无逆序的优化templatestructMergeSortTtmpMaxn;voidsort(T*arr,intn)for(inti=0;i n;i+=16)/小于16 采用插入排序InsertSort:sort(arr+i,min(n-i,16);for(inti=16;i n;i=1)/归并的单个块大小/s表示第一块归并起点，a表示第一个块处理完的大小， b表示第二个块处理完的大小 s+i 表示第二块归并起点ints,a,b;/两块有序集合进行合并 奇数次归并 从左向右for(a=0,b=0,s=0; s n; s+=(i1),a=0,b=0)/第一块起始位置intla=min(s+i,n)-s;intlb=min(s+i+i,n)-(s+i);intcnt=0;while(ala| blb)/归并while(a=lb|!(arrs+i+barra+s)tmps+(cnt+)=arr(a+)+s;while(b=la|arrb+s+iarra+s)tmps+(cnt+)=arr(b+)+s+i;i=n)for(intj=0;j=0; s-=(i1),a=0,b=0)intla=s-max(s-i,-1);intlb=s-i-max(s-i-i,-1);intcnt=a;while(ala| blb)while(b=la|!(tmps-i-btmps-a)/由于从右向左 所以找大的arrs-(cnt+)=tmps-i-(b+);while(a=lb|tmps-i-btmps-a)arrs-(cnt+)=tmps-(a+);/优化：1，非递归/ 2，与插入相结合 templatestructQuickSortpairstack100;/logn 的大小 快排额外空间大小为logninttop;intpartion(T*arr,intn)/获取pivotintmid=n/2;if(arrmidarr0)swap(arrmid,arr0);if(arrn-1arrmid)swap(arrmid,arrn-1);if(arrmidarr0)swap(arrmid,arr0);Ttmp=arrmid;arrmid=arr0;/快排inta,b;for(a=0,b=n-1;aa&!(arrba)arra+=arrb;while(a b&!(tmparra)a+;if(a=0)pairseg=stack-top;if(seg.second=16)InsertSort:sort(arr+seg.first,seg.second);elseintmid=partion(arr+seg.first,seg.second);if(1mid)stacktop+=make_pair(seg.first,mid);if(mid+1+1seg.second)stacktop+=make_pair(seg.first+mid+1,seg.second-(mid+1);MergeSortMerge;QuickSortQuick;intaMaxn;intmain()intn;cinn;for(inti=0;iai;Merge.sort(a,n);for(inti=0;i n;+i)coutai ;coutendl;random_shuffle(a,a+n);Quick.sort(a,n);for(inti=0;i n;+i)coutai ;cout=0;i-) Heap_Adjust(a,i,len); for(i=len-1;i0;i-) inttemp; temp=a0; a0=ai; ai=temp; Heap_Adjust(a,0,i); voidHeap_Adjust(inta,inti,intlen)/调整堆 intchild; /保存父亲节点 inttemp; for(temp=ai;2*i+1len;i=child) /左孩子坐标 child=2*i+1; /找到较大的孩子 if(child+1len&achildtemp) ai=achild; achild=temp; else break; 四，红黑树利用AVL树中的左旋与右旋操作达到调节红黑树黑节点高度一致的问题.1,红黑红红：将根节点变为红色，两个孩子变为黑色 最终变为黑红黑红2,黑红红：变色，移跟变方向（旋转根节节点为孩子节点）。#include #include #include #include usingnamespacestd;constintMaxn=1000000;classRedBlackTreeprivate:structNode intlc,rc,key; boolred; voidclear(intk) lc=rc=0; key=k; red=true; nodeMaxn;intsize,root;voidinit() size=1; root=0; node0.clear(0); node0.red=false;voidrotateL(int&cur)/ rotate left direction intc=cur; cur=nodec.rc; nodec.rc=nodecur.lc; nodecur.lc=c;voidrotateR(int&cur)/ rotate right direction intc=cur; cur=nodec.lc; nodec.lc=nodecur.rc; nodecur.rc=c;voidinsert(int&cur,intkey) if(cur=0)/ insert at leaf node cur=size+; nodecur.clear(key); return; intlc=nodecur.lc,rc=nodecur.rc; if(keyout) intcur=queout+; coutid = cur, key = nodecur.key colour = (nodecur.red?red:black), left child = nodecur.lc, right child = nodecur.rcendl; if(nodecur.lc) quein+=nodecur.lc; if(nodecur.rc) quein+=nodecur.rc; assert(nodecur.red&nodenodecur.lc.red)=false); assert(nodecur.red&nodenodecur.rc.red)=false); tree;intmain()for(inti=0;i20000;+i) tree.insert(rand();tree.out();return0;五，Prim & Dijikstra & Kruscal & floydPrim & Dijikstra：主要思想是采用贪心算法，贪心的选取最小代价的节点放入目标集合中，之后用已选节点更新所有其他未选节点，如此循环，直到所有点均放入目标集合中，程序结束。如果采用堆进行优化可以将复杂度从O(n2 + m)降到O(nlogn + m).Kruscal: 算法从原理上仍然属于贪心算法，只不过是按照边从小到大进行贪心的。因此kruscal首先要对所有边进行排序，之后遍历每条边，如果不形成环则选用此边，否则放弃此边。验证是否存在环可以采用可并堆（并查集）来实现，复杂度O(mlogm)。当原图为完全图时，kruscal算法比prim慢，相当于O(n2*log(n2)。Floyd ：三层for循环，寻找多源多汇最短路径，复杂度O(n3)。#include #include #include #include #include usingnamespacestd;constintMaxn=1000,INF=0x3f3f3f3f;intgraphMaxnMaxn;intn,m;intprim()boolusedMaxn;intret=0;intcostMaxn;memset(used,false,sizeof(used);cost1=0;used1=true;for(inti=2;i=n;+i)costi=graph1i;for(inti=0;i n-1;+i)/找最小值intminCost=INF,minID;for(intj=1;jcostj)minCost=costj;minID=j;ret+=minCost;if(minCost=INF)break;usedminID=true;/更新节点for(intj=1;j=n;+j)if(usedj)continue;costj=min(costj,graphminIDj);returnret;intdijikstra(ints=1,intt=n)/s为起点 t为终点boolusedMaxn;intcostMaxn;memset(used,false,sizeof(used);useds=true;for(inti=1;i=n;+i)costi=graphsi;for(inti=0;i n-1;+i)/找最小值intminCost=INF,minID;for(intj=1;jcostj)minCost=costj;minID=j;if(minCost=INF)break;usedminID=true;/更新节点for(intj=1;j=n;+j)if(usedj)continue;costj=min(costj,graphminIDj+costminID);returncostt;voidfloyd(int(*dist)Maxn) for(inti=1;i=n;+i) for(intj=1;j=n;+j) if(i=j)distij=0; elsedistij=graphij; for(intk=1;k=n;+k) for(inti=1;i=n;+i) for(intj=1;j=n;+j) distij=min(distij,distik+distkj);structEdgeintx,y,v;booloperator (constEdge&e)constreturnv=0)/找根ret=rootret;while(x!=ret)/优化 将所有节点变为树根的孩子inty=rootx;rootx=ret;x=y;returnret;intkruscal()sort(edge,edge+m);memset(root,-1,sizeof(root);intret=0;for(inti=0;im;+i)intx=edgei.x,y=edgei.y;intrx=getRoot(x),ry=getRoot(y);if(rx=ry)continue;/在同一集合内ret+=edgei.v;if(rootrx rootry) /小树根指向大树根rootrx += rootry;rootry = rx;if(rootrx=-n)break;else rootry+=rootrx;rootrx=ry;if(rootry=-n)break;/ 已找到生成树returnret;intmain()scanf(%d %d,&n,&m);memset(graph,INF,sizeof(graph);/graph 置0for(inti=1;i=n;+i)graphii=0;for(inti=0;i=1&x=1&y=n);/保证顶点号满足1, ngraphxy=graphyx=v;edgei.x=x,edgei.y=y,edgei.v=v;coutprim = prim() dijikstra = dijikstra()endl;coutkruscal = kruscal()=visitx)isCutx=true;min0=min(min0,lowne);cnt+;if(last=-1)/根节点的情况isCutx=(cnt 1);lowx=min0;if(lowx=visitx)/找到一个连通分支coutgroup : endl;while(true)inttmp=