基本算法
<P>基本算法 <BR><BR>1.数论算法 <BR>求两数的最大公约数 <BR>function gcd(a,b:integer):integer; <BR>begin <BR>if b=0 then gcd:=a <BR>else gcd:=gcd (b,a mod b); <BR>end ; <BR><BR>求两数的最小公倍数 <BR>function lcm(a,b:integer):integer; <BR>begin <BR>if a< b then swap(a,b); <BR>lcm:=a; <BR>while lcm mod b >0 do inc(lcm,a); <BR>end; <BR><BR>素数的求法 <BR>A.小范围内判断一个数是否为质数： <BR>function prime (n: integer): Boolean; <BR>var I: integer; <BR>begin <BR>for I:=2 to trunc(sqrt(n)) do <BR>if n mod I=0 then <BR>begin <BR>prime:=false; exit; <BR>end; <BR>prime:=true; <BR>end; <BR><BR>B.判断longint范围内的数是否为素数（包含求50000以内的素数表）： <BR>procedure getprime; <BR>var <BR>i,j:longint; <BR>p:array of boolean; <BR>begin <BR>fillchar(p,sizeof(p),true); <BR>p:=false; <BR>i:=2; <BR>while i< 50000 do <BR>begin <BR>if p then <BR>begin <BR>j:=i*2; <BR>while j< 50000 do <BR>begin <BR>p:=false; <BR>inc(j,i); <BR>end; <BR>end; <BR>inc(i); <BR>end; <BR>l:=0; <BR>for i:=1 to 50000 do <BR>if p then <BR>begin <BR>inc(l);<BR>pr:=i; <BR>end; <BR>end;{getprime} </P><P>function prime(x:longint):integer; <BR>var i:integer; <BR>begin <BR>prime:=false; <BR>for i:=1 to l do <BR>if pr >=x then break <BR>else if x mod pr=0 then exit; <BR>prime:=true; <BR>end;{prime} <BR><BR>2． <BR><BR>3． <BR><BR><BR>4.求最小生成树 <BR>A.Prim算法： <BR>procedure prim(v0:integer); <BR>var <BR>lowcost,closest:array of integer; <BR>i,j,k,min:integer; <BR>begin <BR>for i:=1 to n do <BR>begin <BR>lowcost:=cost; <BR>closest:=v0; <BR>end; <BR>for i:=1 to n-1 do <BR>begin <BR>{寻找离生成树最近的未加入顶点k} <BR>min:=maxlongint; <BR>for j:=1 to n do <BR>if (lowcost< min) and (lowcost< >0) then <BR>begin <BR>min:=lowcost; <BR>k:=j; <BR>end; <BR>lowcost:=0; {将顶点k加入生成树} <BR>{生成树中增加一条新的边k到closest} <BR>{修正各点的lowcost和closest值} <BR>for j:=1 to n do <BR>if cost< lwocost then <BR>begin <BR>lowcost:=cost; <BR>closest:=k; <BR>end; <BR>end; <BR>end;{prim} </P>
<P>B.Kruskal算法：(贪心) <BR>按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。 <BR>function find(v:integer):integer; {返回顶点v所在的集合} <BR>var i:integer; <BR>begin <BR>i:=1; <BR>while (i< =n) and (not v in vset) do inc(i); <BR>if i< =n then find:=i <BR>else find:=0; <BR>end; </P>
<P>procedure kruskal; <BR>var <BR>tot,i,j:integer; <BR>begin <BR>for i:=1 to n do vset:=;{初始化定义n个集合，第I个集合包含一个元素I} <BR>p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针} <BR>sort; <BR>{对所有边按权值递增排序，存于e中，e.v1与e.v2为边I所连接的两个顶点的序号，e.len为第I条边的长度} <BR>while p >0 do <BR>begin <BR>i:=find(e.v1);j:=find(e.v2); <BR>if i< >j then <BR>begin <BR>inc(tot,e.len); <BR>vset:=vset+vset;vset:=[]; <BR>dec(p); <BR>end; <BR>inc(q); <BR>end; <BR>writeln(tot); <BR>end; <BR></P> <P>算法都是最基本的，这就能要金币吗？过２天我也弄几篇好文章来，哈．</P> 我要金币!! 啊 我顶 顶一下 多谢了大大。 我1... 不错 <p>这也为可不是个好方法！！</p>
页:
[1]
2