c算法大全常用c語言算法,包括數(shù)論算法,圖論算法排序算法高精度計算樹的遍歷算法等等

1、一、數(shù)論算法1.求兩數(shù)的最大公約數(shù)functiongcd(a,b:integer):integer;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;2.求兩數(shù)的最小公倍數(shù)functionlcm(a,b:integer):integer;beginifa0doinc(lcm,a);end;3.素數(shù)的求法A.小范圍內(nèi)判斷一個數(shù)是否為質數(shù)：functionprime(n:integer):Boolean;varI:integer;beginforI:=2totrunc(sqrt(n)doifnmodI=0thenbeginprime:=false;exit

2、;end;prime:=true;end;B,判斷l(xiāng)ongint范圍內(nèi)的數(shù)是否為素數(shù)（包含求50000以內(nèi)的素數(shù)表）：proceduregetprime;vari,j:longint;p:array1.,50000ofboolean;beginfillchar(p,sizeof(p),true);p1:=false;i:=2;whilei50000dobeginifpithenbeginj:=i*2;whilej=xthenbreakelseifxmodpri=0thenexit;prime:=true;end;prime、圖論算法1.最小生成樹A.Prim算法:procedureprim(v

3、0:integer);varlowcost,closest:array1.maxnofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcosti:=costv0,i;closesti:=v0;end;fori:=1ton-1dobegin尋找離生成樹最近的未加入頂點kmin:=maxlongint;forj:=1tondoif(lowcostjmin)and(lowcostj0)thenbeginmin:=lowcostj;k:=j;end;lowcostk:=0;將頂點k加入生成樹生成樹中增加一條新的邊k到closestk修正各點的low

4、cost和closest值forj:=1tondoifcostk,jlwocostjthenbeginlowcostj:=costk,j;closestj:=k;end;end;end;primB.Kruskal算法：（貪心）按權值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。functionfind(v:integer):integer;返回頂點v所在的集合vari:integer;begini:=1;while(i=n)and(notvinvseti)doinc(i);ifi0dobegini:=find(eq.v1);j:=find(eq.v2);ifijthenbegini

5、nc(tot,eq.len);vseti:=vseti+vsetj;vsetj:=;dec(p);end;inc(q);end;writeln(tot);end;2.最短路徑A.標號法求解單源點最短路徑:vara:array1.maxn,1.maxnofinteger;b:array1.maxnofinteger;bi指頂點i到源點的最短路徑mark:array1.maxnofboolean;procedurebhf;varbest,best_j:integer;beginfillchar(mark,sizeof(mark),false);mark1:=true;b1:=0;1為源點repea

6、tbest:=0;fori:=1tondoIfmarkithen對每一個已計算出最短路徑的點forj:=1tondoif(notmarkj)and(ai,j0)thenif(best=0)or(bi+ai,j0thenbeginbbest_j:=best；markbest_j:=true;end;untilbest=0;end;bhfB.Floyed算法求解所有頂點對之間的最短路徑：procedurefloyed;beginforI:=1tondoforj:=1tondoifaI,j0thenpI,j:=IelsepI,j:=0;pI,j表示I到j的最短路徑上j的前驅結點fork:=1tond

7、o枚舉中間結點fori:=1tondoforj:=1tondoifai,k+aj,kai,jthenbeginai,j:=ai,k+ak,j;pI,j:=pk,j;end;end;C.Dijkstra算法：varb,pre:array1.maxnofinteger;prei指最短路徑上I的前驅結點mark:array1.maxnofboolean;a:array1.maxn,1.maxnofinteger;proceduredijkstra(v0:integer);beginfillchar(mark,sizeof(mark),false);fori:=1tondobegindi:=av0,i

8、;ifdi0thenprei:=v0elseprei:=0;end;markv0:=true;repeat每循環(huán)一次加入一個離1集合最近的結點并調整其他結點的參數(shù)min:=maxint;u:=0;u記錄離1集合最近的結點fori:=1tondoif(notmarki)and(dimin)thenbeginu:=i;min:=di;end;ifu0thenbeginmarku:=true;fori:=1tondoif(notmarki)and(au,i+dudi)thenbegindi:=au,i+du;prei:=u;end;end;untilu=0;end;3.計算圖的傳遞閉包Procedu

9、reLonglink;VarT:array1.maxn,1.maxnofboolean;BeginFillchar(t,sizeof(t),false);Fork:=1tondoForI:=1tondoForj:=1tondoTI,j:=tI,jor(tI,kandtk,j);End;4.無向圖的連通分量A.深度優(yōu)先proceduredfs(now,color:integer);beginfori:=1tondoifanow,iandci=0thenbegin對結點I染色ci:=color;dfs(I,color);end;end;B寬度優(yōu)先(種子染色法)5.關鍵路徑幾個定義：頂點1為源點，n

10、為匯點。a.頂點事件最早發(fā)生時間Vej,Vej=maxVej+wI,j,其中Ve(1)=0;b.頂點事件最晚發(fā)生時間Vlj,Vlj=minVlj-wI,j,其中Vl(n)=Ve(n);c.邊活動最早開始時間EeI,若邊I由j,k表示，則EeI=Vej;d.邊活動最晚開始時間曰I,若邊I由j,k表示，則曰I=Vlk-wj,k;若Eej=Elj,則活動j為關鍵活動，由關鍵活動組成的路徑為關鍵路徑。求解方法：a.從源點起topsort,判斷是否有回路并計算Ve;b.從匯點起topsort,求Vl;c.算Ee和El;6.拓撲排序找入度為0的點，刪去與其相連的所有邊，不斷重復這一過程。例尋找一數(shù)列，其中

11、任意連續(xù)p項之和為正，任意q項之和為負，若不存在則輸出NO.7.回路問題Euler回路(DFS)定義：經(jīng)過圖的每條邊僅一次的回路。(充要條件：圖連同且無奇點)Hamilton回路定義：經(jīng)過圖的每個頂點僅一次的回路。一筆畫充要條件：圖連通且奇點個數(shù)為0個或2個。9.判斷圖中是否有負權回路Bellman-ford算法xI,yI,tI分別表示第I條邊的起點，終點和權。共n個結點和m條邊。procedurebellman-fordbeginforI:=0ton-1dodI:=+infinitive;d0:=0;forI:=1ton-1doforj:=1tomdo枚舉每一條邊ifdxj+tjdyjthe

12、ndyj:=dxj+tj;forI:=1tomdoifdxj+tjdyjthenreturnfalseelsereturntrue;end;10.第n最短路徑問題*第二最短路徑：每舉最短路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些路徑中最短的一條即為第二最短路徑。*同理，第n最短路徑可在求解第n-1最短路徑的基礎上求解。color=#0000FF三、背包問題/color數(shù)據(jù)結構：wi:第i個背包的重量；pi：第i個背包的價值；1.0-1背包：每個背包只能使用一次或有限次(可轉化為一次)：A.求最多可放入的重量。NOIP2001裝箱問題有一個箱子容量為v(正整數(shù)，ovv20000)

13、同時有n個物品(o玄nV30)每個物品有一個體積(正整數(shù))。要求從n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。l搜索方法proceduresearch(k,v:integer);搜索第k個物品，剩余空間為vvari,j:integer;beginifv=bestthenexit;sn為前n個物品的重量和ifkwkthensearch(k+1,v-wk);search(k+1,v);end;end;lDPFI,j為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。實現(xiàn):將最優(yōu)化問題轉化為判定性問題*部分背包問題可有貪心法求解：計算Pi/WifI,j=fi-1,j-wi(wI

14、=j0thenifj+now=ntheninc(cj+now,aj);a:=c;end;邊界:f0,0:=true.2.可重復背包A求最多可放入的重量。FI,j為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。狀態(tài)轉移方程為fI,j=fI-1,j-wI*k(k=1.jdivwI)B.求可以放入的最大價值。USACO1.2ScoreInflation進行一次競賽，總時間T固定，有若干種可選擇的題目，每種題目可選入的數(shù)量不限，每種題目有一個ti(解答此題所需的時間)和一個si(解答此題所得的分數(shù))，現(xiàn)要選擇若干題目，使解這些題的總時間在T以內(nèi)的前提下，所得的總分最大，求最大的得分。*易

15、想到：fi,j=maxfi-k*wj,j-1+k*pj(0=k=0ThenBegint:=problemj.point+fi-problemj.time;IftfiThenfi:=t;End;Writeln(fM);End.C.求恰好裝滿的情況數(shù)。Ahoi2001Problem2求自然數(shù)n本質不同的質數(shù)和的表達式的數(shù)目。思路一，生成每個質數(shù)的系數(shù)的排列，在一一測試，這是通法。proceduretry(dep:integer);vari,j:integer;begincal;此過程計算當前系數(shù)的計算結果，now為結果ifnownthenexit;剪枝ifdep=l+1thenbegin生成所有系

16、數(shù)cal;ifnow=ntheninc(tot);exit;end;fori:=0tondivprdepdobeginxsdep:=i;try(dep+1);xsdep:=0;end;end;思路二，遞歸搜索效率較高proceduretry(dep,rest:integer);vari,j,x:integer;beginif(rest0thenfork:=1tondivnowdoifj+now*k=ntheninc(cj+now*k,aj);a:=c;end;mainbeginread(now);讀入第一個物品的重量i:=0;ai為背包容量為i時的放法總數(shù)whilei=ndobeginai:=

17、1;inc(i,now);end;定義第一個物品重白整數(shù)倍的重量a值為1,作為初值fori:=2tovdobeginread(now);update;動態(tài)更新end;writeln(an);四、排序算法1.快速排序：procedureqsort(l,r:integer);vari,j,mid:integer;begini:=l;j:=r;mid:=a(l+r)div2;將當前序列在中間位置的數(shù)定義為中間數(shù)repeatwhileaimiddodec(j);在右半部分尋找比中間數(shù)小的數(shù)ifij;ifljthenqsort(l,j);若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間ifirthenqsort(

18、i,r);end;sortB.插入排序：思路：當前a1.ai-1已排好序了，現(xiàn)要插入ai使a1.ai有序。procedureinsert_sort;vari,j:integer;beginfori:=2tondobegina0:=ai;j:=i-1;whilea0ajthenswap(ai,aj);end;D.冒泡排序procedurebubble_sort;vari,j,k:integer;beginfori:=1ton-1doforj:=ndowntoi+1doifajaj-1thenswap(aj,aj-1);每次比較相鄰元素的關系end;E.堆排序：proceduresift(i,m:

19、integer);調整以i為根的子樹成為堆，m為結點總數(shù)vark:integer;begina0:=ai;k:=2*i;在完全二叉樹中結點i的左孩子為2*i,右孩子為2*i+1whilek=mdobeginif(km)and(akak+1)theninc(k);找出ak與ak+1中較大值ifa0akthenbeginai:=ak;i:=k;k:=2*i;elsek:=m+1;end;ai:=a0;將根放在合適的位置end;endprocedureheapsort;varj:integer;beginforj:=ndiv2downto1dosift(j,n);forj:=ndownto2dobe

20、ginswap(a1,aj);sift(1,j-1);end;end;F.歸并排序a為序列表，tmp為輔助數(shù)組proceduremerge(vara:listtype;p,q,r:integer);將已排序好的子序列ap.q與aq+1.r合并為有序的tmpp.rvarI,j,t:integer;tmp:listtype;begint:=p;i:=p;j:=q+1;t為tmp指針，I,j分別為左右子序列的指針while(t=r)dobeginif(ir)or(ai=aj)滿足取左邊序列當前元素的要求thenbeginendelsebegintmpt:=aj;inc(j);end;inc(t);e

21、nd;fori:=ptordoai:=tmpi;end;mergeproceduremerge_sort(vara:listtype;p,r:integer);合并并F序ap.rvarq:integer;beginifprthenbeginq:=(p+r-1)div2;merge_sort(a,p,q);merge_sort(a,q+1,r);merge(a,p,q,r);end;end;mainbeginmerge_sort(a,1,n);end.G.基數(shù)排序思想：對每個元素按從低位到高位對每一位進行一次排序五、高精度計算高精度數(shù)的定義：typehp=array1.maxlenofinteg

22、er;1.高精度加法procedureplus(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa0b0thenlen:=a0elselen:=b0;fori:=1tolendobegininc(ci,ai+bi);ifci10thenbegindec(ci,10);inc(ci+1);end;進位end;ifclen+10theninc(len);c0:=len;end;plus2.高精度減法proceduresubstract(a,b:hp;varc:hp);vari,len:integer;beginfill

23、char(c,sizeof(c),0);ifa0b0thenlen:=a0elselen:=b0;fori:=1tolendobegininc(ci,ai-bi);ifci1)and(clen=0)dodec(len);c0:=len;end;3.高精度乘以低精度proceduremultiply(a:hp;b:longint;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);len:=a0;fori:=1tolendobegininc(ci,ai*b);inc(ci+1,(ai*b)div10);ci:=cimod10;end;in

24、c(len);while(clen=10)dobegin處理最高位的進位clen+1:=clendiv10;clen:=clenmod10;dodec(len);若不需進位則調整lenc0:=len;end;multiply4.高精度乘以高精度procedurehigh_multiply(a,b:hp;varc:hpvari,j,len:integer;beginfillchar(c,sizeof(c),0);fori:=1toa0doforj:=1tob0dobegininc(ci+j-1,ai*bj);inc(ci+j,ci+j-1div10);ci+j-1:=ci+j-1mod10;en

25、d;len:=a0+b0+1;while(len1)and(clen=0)dodec(len);c0:=len;end;5.高精度除以低精度proceduredevide(a:hp;b:longint;c:=adivb;d:=amodbvari,len:integer;beginfillchar(c,sizeof(c),0);len:=a0;d:=0;fori:=lendownto1dobegind:=d*10+ai;ci:=ddivb;d:=dmodb;end;inc(len);end;while(len1)and(clen=0)varc:hp;vard:longint);while(len

26、1)and(clen=0)thendec(len);c0:=len;end;6.高精度除以高精度procedurehigh_devide(a,b:hp;varc,d:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);fillchar(d,sizeof(d),0);len:=a0;d0:=1;fori:=lendownto1dobeginmultiply(d,10,d);d1:=ai;while(compare(d,b)=0)do即d=bbeginSubtract(d,b,d);inc(ci);end;end;while(len1)and(c.s

27、len=0)dodec(len);c.len:=len;end;六、樹的遍歷1.已知前序中序求后序procedureSolve(pre,mid:string);vari:integer;beginif(pre=“)or(mid=“)thenexit;i:=pos(pre1,mid);solve(copy(pre,2,i),copy(mid,1,i-1);solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i);post:=post+pre1;加上根，遞3結束后post即為后序遍歷end;2.已知中序后序求前序procedureS

28、olve(mid,post:string);vari:integer;beginif(mid=“)or(post=“)thenexit;i:=pos(postlength(post),mid);pre:=pre+postlength(post);加上根，遞3結束后pre即為前序遍歷solve(copy(mid,1,I-1),copy(post,1,I-1);solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i);end;3.已知前序后序求中序的一種functionok(s1,s2:string):boolean;vari,l:

29、integer;p:boolean;beginok:=true;l:=length(s1);fori:=1toldobeginp:=false;forj:=1toldoifs1i=s2jthenp:=true;ifnotpthenbeginok:=false;exit;end;end;end;proceduresolve(pre,post:string);vari:integer;beginif(pre=)or(post=M)thenexit;i:=0;repeatinc(i);untilok(copy(pre,2,i),copy(post,1,i);solve(copy(pre,2,i),c

30、opy(post,1,i);midstr:=midstr+pre1;solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1);end;七進制轉換1.任意正整數(shù)進制間的互化除n取余2.實數(shù)任意正整數(shù)進制間的互化乘n取整3.負數(shù)進制:八全排列與組合的生成設計一個程序，讀入一個十進制數(shù)的基數(shù)和一個負進制數(shù)的基數(shù)，并將此十進制數(shù)轉換為此負進制下白數(shù)：-R-2,-3,-4,.-201.排列的生成：（1.n）proceduresolve(dep:integer);vari:integer;beginifdep=n+1thenbe

31、ginwriteln(s);exit;end;fori:=1tondoifnotusedithenbegins:=s+chr(i+ord(0);usedi:=true;solve(dep+1);s:=copy(s,1,length(s)-1);usedi:=false;end;end;2.組合的生成(1.n中選取k個數(shù)的所有方案)proceduresolve(dep,pre:integer);vari:integer;beginifdep=k+1thenbeginwriteln(s);exit;end;fori:=1tondoif(notusedi)and(ipre)thenbegins:=s

32、+chr(i+ord(0);usedi:=true;solve(dep+1,i);s:=copy(s,1,length(s)-1);usedi:=false;end;end;九.查找算法1.折半查找functionbinsearch(k:keytype):integer;varlow,hig,mid:integer;beginlow:=1;hig:=n;mid:=(low+hig)div2;while(amid.keyk)and(lowkthenhig:=mid-1elselow:=mid+1;mid:=(low+hig)div2;end;iflowhigthenmid:=0;binsearc

33、h:=mid;end;2.樹形查找二叉排序樹：每個結點的值都大于其左子樹任一結點的值而小于其右子樹任一結點的值。查找functiontreesrh(k:keytype):pointer;varq:pointer;beginq:=root;while(qnil)and(qA.keyk)doifkqA.keythenq:=qA.leftelseq:=qA.right;treesrh:=q;end;十、貪心*會議問題(1)n個活動每個活動有一個開始時間和一個結束時間，任一時刻僅一項活動進行，求滿足活動數(shù)最多的情況。解：按每項活動的結束時間進行排序，排在前面的優(yōu)先滿足。(2)會議室空閑時間最少。(3)

34、每個客戶有一個愿付的租金，求最大利潤。(4)共R間會議室，第i個客戶需使用i間會議室，費用相同，求最大利潤。十一、回溯法框架1.n皇后問題proceduretry(i:byte);varj:byte;beginifi=n+1thenbeginprint;exit;end;forj:=1tondoifaiandbj+iandcj-ithenbeginxi：=j；aj:=false;bj+i:=false;cj-i:=false;try(i+1);aj:=true;bi+j:=true;cj-i:=true;end;end;2.HanoiTower漢諾塔h(n)=2*h(n-1)+1h(1)=1初

35、始所有銅片都在a柱上procedurehanoi(n,a,b,c:byte);將第n塊銅片從a柱通過b柱移到c柱上beginifn=0thenexit;hanoi(n-1,a,c,b);將上面的n-1塊從a柱通過c柱移到b柱上write(n,movedm,a,c);to,hanoi(n-1,b,a,c);將b上白nn-1塊從b柱通過a柱移到c柱上end;初始銅片分布在3個柱上，給定目標柱goalh1.3,0.n存放三個柱的狀態(tài)，now與nowp存最大的不到位的銅片的柱號和編號，hI,0存第I個柱上的個數(shù)。Proceduremove(k,goal:integer);將最大不到位的k移至目標柱goal上BeginIfk=0thenexit;ForI:=1to3doForj:=1tohanI,0doIfhI,j=kthenbeg