資源描述:
《c算法大全常用c語(yǔ)言算法,包括數(shù)論算法,圖論算法、排序算法、高精度計(jì)算、樹的遍歷算法等等》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、一、數(shù)論算法1.求兩數(shù)的最大公約數(shù)function?gcd(a,b:integer):integer;begin?ifb=0thengcd:=a??elsegcd:=gcd(b,amodb);end;2.求兩數(shù)的最小公倍數(shù)function?lcm(a,b:integer):integer;begin?ifa0doinc(lcm,a);end;3.素?cái)?shù)的求法A.小范圍內(nèi)判斷一個(gè)數(shù)是否為質(zhì)數(shù):functionprime(n:integer)
2、:Boolean;?varI:integer;?begin??forI:=2totrunc(sqrt(n))do???ifnmodI=0thenbegin?prime:=false;exit;end;??prime:=true;?end;B.判斷l(xiāng)ongint范圍內(nèi)的數(shù)是否為素?cái)?shù)(包含求50000以內(nèi)的素?cái)?shù)表):?proceduregetprime;??var???i,j:longint;???p:array[1..50000]ofboolean;???begin????fillchar(p,sizeof(p)
3、,true);p[1]:=false;i:=2;whilei<50000dobegin?ifp[i]thenbegin??j:=i*2;??whilej<50000dobegin???p[j]:=false;???inc(j,i);??end;??end;??inc(i);?end;?l:=0;?fori:=1to50000do??ifp[i]thenbegin???inc(l);pr[l]:=i;?end;end;{getprime}???functionprime(x:longint):integer;??
4、?vari:integer;???begin????prime:=false;fori:=1toldo?ifpr[i]>=xthenbreak??elseifxmodpr[i]=0thenexit;prime:=true;???end;{prime}二、圖論算法1.最小生成樹A.Prim算法:??procedureprim(v0:integer);???var????lowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;???begin????for
5、i:=1tondobegin?lowcost[i]:=cost[v0,i];?closest[i]:=v0;?end;fori:=1ton-1dobegin?{尋找離生成樹最近的未加入頂點(diǎn)k}?min:=maxlongint;?forj:=1tondo??if(lowcost[j]0)thenbegin???min:=lowcost[j];???k:=j;??end;?lowcost[k]:=0;{將頂點(diǎn)k加入生成樹}???{生成樹中增加一條新的邊k到closest[k
6、]}?{修正各點(diǎn)的lowcost和closest值}?forj:=1tondo??if?cost[k,j]7、(i<=n)and(notvinvset[i])doinc(i);?ifi<=nthenfind:=ielsefind:=0;end;procedurekruskal;var?tot,i,j:integer;begin?fori:=1tondovset[i]:=[i];{初始化定義n個(gè)集合,第I個(gè)集合包含一個(gè)元素I}p:=n-1;q:=1;tot:=0;{p為尚待加入的邊數(shù),q為邊集指針}sort;{對(duì)所有邊按權(quán)值遞增排序,存于e[I]中,e[I].v1與e[I].v2為邊I所連接的兩個(gè)頂點(diǎn)的序號(hào),e[I].l
8、en為第I條邊的長(zhǎng)度}?whilep>0dobegin??i:=find(e[q].v1);j:=find(e[q].v2);??ifi<>jthenbegin???inc(tot,e[q].len);???vset[i]:=vset[i]+vset[j];vset[j]:=[];???dec(p);??end;??inc(q);?end;?writeln(tot);end;2.最短路