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

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.素?cái)?shù)的求法A.小范圍內(nèi)判斷一個(gè)數(shù)是否為質(zhì)數(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ù)是否為素?cái)?shù)（包含求50000以內(nèi)的素?cá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尋找離生成樹最近的未加入頂點(diǎn)kmin:=maxlongint;forj:=1tondoif(lowcostjmin)and(lowcostj0)thenbeginmin:=lowcostj;k:=j;end;lowcostk:=0;將頂點(diǎn)k加入生成樹生成樹中增加一條新的邊k到closestk修正各點(diǎn)的low

4、cost和closest值forj:=1tondoifcostk,jlwocostjthenbeginlowcostj:=costk,j;closestj:=k;end;end;end;primB.Kruskal算法：（貪心）按權(quán)值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。functionfind(v:integer):integer;返回頂點(diǎn)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.標(biāo)號(hào)法求解單源點(diǎn)最短路徑:vara:array1.maxn,1.maxnofinteger;b:array1.maxnofinteger;bi指頂點(diǎn)i到源點(diǎn)的最短路徑mark:array1.maxnofboolean;procedurebhf;varbest,best_j:integer;beginfillchar(mark,sizeof(mark),false);mark1:=true;b1:=0;1為源點(diǎn)repea

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

7、o枚舉中間結(jié)點(diǎn)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的前驅(qū)結(jié)點(diǎn)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)一次加入一個(gè)離1集合最近的結(jié)點(diǎn)并調(diào)整其他結(jié)點(diǎn)的參數(shù)min:=maxint;u:=0;u記錄離1集合最近的結(jié)點(diǎn)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.計(jì)算圖的傳遞閉包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對(duì)結(jié)點(diǎn)I染色ci:=color;dfs(I,color);end;end;B寬度優(yōu)先(種子染色法)5.關(guān)鍵路徑幾個(gè)定義：頂點(diǎn)1為源點(diǎn)，n

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

11、任意連續(xù)p項(xiàng)之和為正，任意q項(xiàng)之和為負(fù)，若不存在則輸出NO.7.回路問題Euler回路(DFS)定義：經(jīng)過圖的每條邊僅一次的回路。(充要條件：圖連同且無奇點(diǎn))Hamilton回路定義：經(jīng)過圖的每個(gè)頂點(diǎn)僅一次的回路。一筆畫充要條件：圖連通且奇點(diǎn)個(gè)數(shù)為0個(gè)或2個(gè)。9.判斷圖中是否有負(fù)權(quán)回路Bellman-ford算法xI,yI,tI分別表示第I條邊的起點(diǎn)，終點(diǎn)和權(quán)。共n個(gè)結(jié)點(diǎ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最短路徑的基礎(chǔ)上求解。color=#0000FF三、背包問題/color數(shù)據(jù)結(jié)構(gòu)：wi:第i個(gè)背包的重量；pi：第i個(gè)背包的價(jià)值；1.0-1背包：每個(gè)背包只能使用一次或有限次(可轉(zhuǎn)化為一次)：A.求最多可放入的重量。NOIP2001裝箱問題有一個(gè)箱子容量為v(正整數(shù)，ovv20000)

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

14、=j0thenifj+now=ntheninc(cj+now,aj);a:=c;end;邊界:f0,0:=true.2.可重復(fù)背包A求最多可放入的重量。FI,j為前i個(gè)物品中選擇若干個(gè)放入使其體積正好為j的標(biāo)志，為布爾型。狀態(tài)轉(zhuǎn)移方程為fI,j=fI-1,j-wI*k(k=1.jdivwI)B.求可以放入的最大價(jià)值。USACO1.2ScoreInflation進(jìn)行一次競賽，總時(shí)間T固定，有若干種可選擇的題目，每種題目可選入的數(shù)量不限，每種題目有一個(gè)ti(解答此題所需的時(shí)間)和一個(gè)si(解答此題所得的分?jǐn)?shù))，現(xiàn)要選擇若干題目，使解這些題的總時(shí)間在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本質(zhì)不同的質(zhì)數(shù)和的表達(dá)式的數(shù)目。思路一，生成每個(gè)質(zhì)數(shù)的系數(shù)的排列，在一一測試，這是通法。proceduretry(dep:integer);vari,j:integer;begincal;此過程計(jì)算當(dāng)前系數(shù)的計(jì)算結(jié)果，now為結(jié)果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);讀入第一個(gè)物品的重量i:=0;ai為背包容量為i時(shí)的放法總數(shù)whilei=ndobeginai:=

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

18、i,r);end;sortB.插入排序：思路：當(dāng)前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);每次比較相鄰元素的關(guān)系end;E.堆排序：proceduresift(i,m:

19、integer);調(diào)整以i為根的子樹成為堆，m為結(jié)點(diǎn)總數(shù)vark:integer;begina0:=ai;k:=2*i;在完全二叉樹中結(jié)點(diǎn)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)滿足取左邊序列當(dāng)前元素的要求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ù)排序思想：對(duì)每個(gè)元素按從低位到高位對(duì)每一位進(jìn)行一次排序五、高精度計(jì)算高精度數(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;進(jìn)位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處理最高位的進(jìn)位clen+1:=clendiv10;clen:=clenmod10;dodec(len);若不需進(jìn)位則調(diào)整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結(jié)束后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結(jié)束后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;七進(jìn)制轉(zhuǎn)換1.任意正整數(shù)進(jìn)制間的互化除n取余2.實(shí)數(shù)任意正整數(shù)進(jìn)制間的互化乘n取整3.負(fù)數(shù)進(jìn)制:八全排列與組合的生成設(shè)計(jì)一個(gè)程序，讀入一個(gè)十進(jìn)制數(shù)的基數(shù)和一個(gè)負(fù)進(jìn)制數(shù)的基數(shù)，并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下白數(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個(gè)數(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.樹形查找二叉排序樹：每個(gè)結(jié)點(diǎn)的值都大于其左子樹任一結(jié)點(diǎn)的值而小于其右子樹任一結(jié)點(diǎn)的值。查找functiontreesrh(k:keytype):pointer;varq:pointer;beginq:=root;while(qnil)and(qA.keyk)doifkqA.keythenq:=qA.leftelseq:=qA.right;treesrh:=q;end;十、貪心*會(huì)議問題(1)n個(gè)活動(dòng)每個(gè)活動(dòng)有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間，任一時(shí)刻僅一項(xiàng)活動(dòng)進(jìn)行，求滿足活動(dòng)數(shù)最多的情況。解：按每項(xiàng)活動(dòng)的結(jié)束時(shí)間進(jìn)行排序，排在前面的優(yōu)先滿足。(2)會(huì)議室空閑時(shí)間最少。(3)

34、每個(gè)客戶有一個(gè)愿付的租金，求最大利潤。(4)共R間會(huì)議室，第i個(gè)客戶需使用i間會(huì)議室，費(fè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個(gè)柱上，給定目標(biāo)柱goalh1.3,0.n存放三個(gè)柱的狀態(tài)，now與nowp存最大的不到位的銅片的柱號(hào)和編號(hào)，hI,0存第I個(gè)柱上的個(gè)數(shù)。Proceduremove(k,goal:integer);將最大不到位的k移至目標(biāo)柱goal上BeginIfk=0thenexit;ForI:=1to3doForj:=1tohanI,0doIfhI,j=kthenbeg