基本代码.docVIP

一、数论算法1．求两数的最大公约数function gcd(a,b:integer):integer;beginif b=0 then gcd:=a??? else gcd:=gcd (b,a mod b);end ;2．求两数的最小公倍数function lcm(a,b:integer):integer;beginif ab then swap(a,b);lcm:=a;while lcm mod b0 do inc(lcm,a);end;3．素数的求法A.小范围内判断一个数是否为质数：function prime (n: integer): Boolean;var I: integer;begin??? for I:=2 to trunc(sqrt(n)) do??? if n mod I=0 then begin????? prime:=false; exit;??? end;????? prime:=true;end;B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：procedure getprime;??? var??? i,j:longint;??? p:array[1..50000] of boolean;??? begin????? fillchar(p,sizeof(p),true);p[1]:=false;i:=2;while i50000 do beginif p then begin??? j:=i*2;??? while j50000 do begin??? p[j]:=false;??? inc(j,i);??? end;end;inc(i);end;l:=0;for i:=1 to 50000 doif p then begin??? inc(l);pr[l]:=i;end;end;{getprime}function prime(x:longint):integer;??? var i:integer;??? begin????? prime:=false;for i:=1 to l doif pr=x then break??? else if x mod pr=0 then exit;prime:=true;end;{prime} 二、图论算法1．最小生成树A.Prim算法：procedure prim(v0:integer);??? var????? lowcost,closest:array[1..maxn] of integer;i,j,k,min:integer;??? begin????? for i:=1 to n do beginlowcost:=cost[v0,i];closest:=v0;end;for i:=1 to n-1 do begin{寻找离生成树最近的未加入顶点k}min:=maxlongint;for j:=1 to n do??? if (lowcost[j]min) and (lowcost[j]0) then begin??? min:=lowcost[j];??? k:=j;??? end;lowcost[k]:=0; {将顶点k加入生成树}??? {生成树中增加一条新的边k到closest[k]}{修正各点的lowcost和closest值}for j:=1 to n do??? if cost[k,j]lwocost[j] then begin??? lowcost[j]:=cost[k,j];??? closest[j]:=k;??? end;end;end;{prim}B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。function find(v:integer):integer; {返回顶点v所在的集合}var i:integer;begini:=1;while (i=n) and (not v in vset) do inc(i);if i=n then find:=i else find:=0;end;procedure kruskal;vartot,i,j:integer;beginfor i:=1 to n do vset:=;{初始化定义n个集合，第I个集合包含一个元素I}p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}sort;{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点