c算法大全常用c语言算法,包括数论算法,图论算法、排序算法、高精度计算、树的遍历算法等等.doc

《c算法大全常用c语言算法,包括数论算法,图论算法、排序算法、高精度计算、树的遍历算法等等.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、数论算法1．求两数的最大公约数function gcd(a,b:integer):integer;begin ifb=0thengcd:=a  elsegcd:=gcd(b,amodb);end;2．求两数的最小公倍数function lcm(a,b:integer):integer;begin ifa0doinc(lcm,a);end;3．素数的求法A.小范围内判断一个数是否为质数：functionprime(n:integer):Boolean; varI:integer; begin  forI

2、:=2totrunc(sqrt(n))do   ifnmodI=0thenbegin prime:=false;exit;end;  prime:=true; end;B.判断longint范围内的数是否为素数（包含求50000以内的素数表）： proceduregetprime;  var   i,j:longint;   p:array[1..50000]ofboolean;   begin    fillchar(p,sizeof(p),true);p[1]:=false;i:=2;whilei<50000dobegin ifp[i]thenbegin  j:=i*2;  

3、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;   vari:integer;   begin    prime:=false;fori:=1toldo ifpr[i]>=xthenbreak  elseifxmodpr[i]=0thenexit;prime:

4、=true;   end;{prime}二、图论算法1．最小生成树A.Prim算法：  procedureprim(v0:integer);   var    lowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;   begin    fori:=1tondobegin lowcost[i]:=cost[v0,i]; closest[i]:=v0; end;fori:=1ton-1dobegin {寻找离生成树最近的未加入顶点k} min:=maxlongint; forj:=1tondo  if(lowcost[j

5、]0)thenbegin   min:=lowcost[j];   k:=j;  end; lowcost[k]:=0;{将顶点k加入生成树}   {生成树中增加一条新的边k到closest[k]} {修正各点的lowcost和closest值} forj:=1tondo  if cost[k,j]

6、边加入最小生成树。functionfind(v:integer):integer;{返回顶点v所在的集合}vari:integer;begin i:=1; while(i<=n)and(notvinvset[i])doinc(i); ifi<=nthenfind:=ielsefind:=0;end;procedurekruskal;var tot,i,j:integer;begin fori:=1tondovset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}p:=n-1;q:=1;tot:=0;{p为尚待加入的边数，q为边集指针}sort;{对所有边按权值递

7、增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度} 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.最短路