1.数论算法 5 E; w: S! D0 G `: Z/ v4 D
求两数的最大公约数 $ `! I4 y6 \# K7 d* Z. R
function gcd(a,b:integer):integer; 8 K) H5 i0 t7 B8 S
begin 8 Y1 s$ W! N d3 c
if b=0 then gcd:=a ! J+ }% {- `1 l2 ]
else gcd:=gcd (b,a mod b); 3 }! d# v0 T) T
end ; 6 o( t- u$ k1 r
2 Y* Z; Y; I( _. y j
求两数的最小公倍数 & r f$ H. Z2 `0 r
function lcm(a,b:integer):integer; 8 o. J. f7 |+ X" r& abegin , `8 q: S1 |7 U( C0 g8 N2 N1 i
if a< b then swap(a,b); . ~; P% N+ I9 c9 h
lcm:=a; 1 x; x, Y5 t4 ?3 mwhile lcm mod b >0 do inc(lcm,a); % J* P* Y) D2 b, c# H5 Mend; . a5 h# u4 k' ]9 U7 w! E0 g$ `
- |: ?, o* d! W( e% E; O素数的求法 , D( X( s% m. A% r8 H1 E; e5 T
A.小范围内判断一个数是否为质数: 8 y! P, g7 p$ ]% T' L: Y
function prime (n: integer): Boolean; ' M0 c1 V) T, S1 l: V% }
var I: integer; + h/ \" i3 T% x9 `% ?+ A( i1 E& ubegin & L" d; p- e' ?% t: E8 I( Wfor I:=2 to trunc(sqrt(n)) do 9 s6 U2 C) t6 F" b w& g* wif n mod I=0 then 6 @# ^% S: Q; E$ J! s5 y2 N/ m
begin 9 h8 q: ]1 _5 s* d: i( ]
prime:=false; exit; 6 r( W3 e+ x. Z8 P6 b
end; 1 x. @' C1 i+ @. {0 F' iprime:=true; ! f9 x' X1 p5 C" v7 G5 D* P- d7 ~
end; . n6 _4 g c# f' Y
5 E, x" o: w: \( SB.判断longint范围内的数是否为素数(包含求50000以内的素数表): 9 F2 x3 a8 \5 N B
procedure getprime; ) A: ?6 F* w9 K: [" W" J R+ K
var " q# s. R7 W! R8 C4 z; o
i,j:longint; . }- W ~) \- M8 ]( X9 a9 u$ A3 B
p:array[1..50000] of boolean; ( y5 _3 ]. p2 k$ H# O; ?) ]2 t
begin % W% U9 j: ?0 v3 ^9 B8 ^. n6 A8 j
fillchar(p,sizeof(p),true); ) _2 j% o R) {: Y ~# R0 c0 D
p[1]:=false; & K# K; r, o5 v2 O) R: t5 fi:=2; . Y5 f9 v8 T, i, Ewhile i< 50000 do 0 Q5 B! b) L; ^8 Lbegin 8 c7 I5 x9 @. I3 d# mif p then / L0 j& C* K* K
begin , y1 ?1 X# l; e+ G
j:=i*2; + L [6 w7 w, i. | q9 zwhile j< 50000 do + P" P$ `" _5 k( I& M' _
begin . f6 Q! r2 I( ^0 F& s% }
p[j]:=false; 7 ~3 e. V; G2 k! yinc(j,i); . l" m! f8 b4 {- p% ?6 cend; 6 V$ k+ W+ j8 w- }4 F9 Z
end; 1 Q( C5 i6 P5 F4 h: minc(i); ' i# p* |* i1 w7 A& q+ z$ I- A
end; ! m* \$ U. c5 J: Fl:=0; 7 x8 O8 S) J8 X; [
for i:=1 to 50000 do ) x: `3 Y" C* _ U. W+ G% C/ j* E
if p then 1 S1 n) G- m5 l O8 Ubegin : `' S. P9 u+ }
inc(l);' b4 `( o9 q5 A2 d5 W
pr[l]:=i; 9 y9 ~5 {% C" u9 M9 p- L" nend; . G' k2 s0 c2 F" y" q8 F9 Cend;{getprime} % H7 h: q* g. t5 j- z; Kfunction prime(x:longint):integer; % a- v; {( R* o/ F3 q6 ? p' g7 e
var i:integer; 1 m7 @0 _, B) w9 d9 U
begin 4 R9 @$ g o* U
prime:=false; 7 J: d" E- ~8 z- `
for i:=1 to l do 1 v( R& T( L6 i# r# sif pr >=x then break ' M6 d5 z# I: |- S& y
else if x mod pr=0 then exit; + F8 I( [4 ~' b0 h# [ m8 h
prime:=true; / l$ Y) x' D# G8 Iend;{prime} & \ {+ j- D: b; `6 u. m0 @3 p8 ]0 t# G
2. 7 X+ _5 ]7 ?& L/ S/ G# e/ m9 g/ m
$ Z. e% j; j1 p! B7 G8 K$ b' m3. 7 x; z# _- c! k: W' J4 X7 J$ j! O9 \! ` a
4.求最小生成树 9 o; i d. J' p% V- P& m9 b3 |
A.Prim算法: ' G- y7 L% P/ T9 U& z, kprocedure prim(v0:integer); ' y S: C6 U2 N/ E" svar 2 V6 w6 z& F: ^
lowcost,closest:array[1..maxn] of integer; , o) Y7 z1 a$ y' m- M/ ^- Wi,j,k,min:integer; ( [! W3 W) g, C& k# P+ N* bbegin $ a1 n6 h2 d3 v; o# b6 S) `3 L( efor i:=1 to n do 2 M$ v: V5 A8 F! r8 Gbegin / m2 t l- s% m, u, g! t6 slowcost:=cost[v0,i]; 8 k* }2 T, d2 Y0 M4 k
closest:=v0; # F, u" ^6 m5 f. V6 `2 L
end; 3 f/ G* a6 d- Bfor i:=1 to n-1 do - a! m9 s% R2 G2 L3 t# e
begin - [6 }: D# w- i" P
{寻找离生成树最近的未加入顶点k} ) t/ k/ \! X0 f' F: ^+ Dmin:=maxlongint; ! m1 X) p7 t, C4 u% Q4 J/ N/ K
for j:=1 to n do + ~& {7 q' s" p9 ]) |( T8 o
if (lowcost[j]< min) and (lowcost[j]< >0) then 0 c2 P! `4 e1 u
begin 5 U2 D& u/ B+ mmin:=lowcost[j]; 4 m* Z/ V/ f% N2 |$ `# ^1 y. y G
k:=j; 6 \! y2 s" M3 |, q1 ~$ |0 ?
end; 3 r' _' M3 Y0 E/ S0 t& A
lowcost[k]:=0; {将顶点k加入生成树} * s8 q, F! A3 T8 ^' d; G( k{生成树中增加一条新的边k到closest[k]} 8 }: K$ f! I8 n" L) ~% C* j
{修正各点的lowcost和closest值} " a, ^) z" A. [
for j:=1 to n do # X+ @) L b8 T7 V* G0 m; p" ~if cost[k,j]< lwocost[j] then " I% L N$ ?! i: D8 U+ V+ Jbegin : c7 j& ], A0 Z2 ^3 [
lowcost[j]:=cost[k,j]; / u Z- P; s8 B4 g. d: aclosest[j]:=k; ]7 p" F4 M4 Send; / F1 P6 e0 F; d7 I
end; $ { _4 B! ?1 j( H# A* y1 j2 x# x
end;{prim} 9 X( Y% |( S% y0 _) O! HB.Kruskal算法:(贪心) * R: s; J( g1 K" |. W
按权值递增顺序删去图中的边,若不形成回路则将此边加入最小生成树。 * s" w j, p& mfunction find(v:integer):integer; {返回顶点v所在的集合} ( G/ o2 O( W5 l/ b
var i:integer; 0 l& @; a: }% T; Q; \& R, s
begin , `/ Z& t* A3 m4 b* j/ l
i:=1; $ s+ y W1 C9 `$ D+ t0 M
while (i< =n) and (not v in vset) do inc(i); ! Y+ r5 n0 C n5 S7 Lif i< =n then find:=i 1 k* P' S4 m$ m8 L
else find:=0; + [: j2 T+ ?5 O0 h4 L4 d# V# c
end; : p; V6 t) _' ^4 Hprocedure kruskal; ) }! j1 ~) g) ~9 v7 hvar 4 T6 v# e; v! m& i2 o, g% Ytot,i,j:integer; % o+ ? W: i- P, D/ ~8 k; Tbegin ' G8 t. A; t: ^- ^* Ifor i:=1 to n do vset:=;{初始化定义n个集合,第I个集合包含一个元素I} " s3 M( l2 Y( _* K% ?: vp:=n-1; q:=1; tot:=0; {p为尚待加入的边数,q为边集指针} ! r9 U. e5 o# ^/ @+ B# [1 ysort; ! W3 a. y/ M3 m; S
{对所有边按权值递增排序,存于e[I]中,e[I].v1与e[I].v2为边I所连接的两个顶点的序号,e[I].len为第I条边的长度} 7 m( t. J0 X: X7 F
while p >0 do ) T9 d, Q/ i% b: A, Mbegin 4 l; ?$ |9 W4 }+ i3 m
i:=find(e[q].v1);j:=find(e[q].v2); 1 z- f/ P; ~# O) U9 t7 J6 lif i< >j then . ?) b. k" s8 Z' dbegin . }& ]4 a, h! K# l4 vinc(tot,e[q].len); 8 L$ ]8 I6 o$ ^, v
vset:=vset+vset[j];vset[j]:=[]; ' k/ `* K: s1 C3 l4 p, Z+ z+ ldec(p); / a; B, X9 a9 q" b; _
end; : f; V8 R+ e3 Y' K8 ^ `inc(q); : x* u- T6 w4 t! q/ \! {5 l5 lend; 1 J8 [8 d0 {: S ], `writeln(tot); , O: Y0 k0 J2 q$ v7 e& M' D$ `end; ! d$ } N3 }. @) w9 q; {
: u, P1 S$ D( X7 I9 x
5.最短路径 & @& E% L( g5 Z# z) u7 bA.标号法求解单源点最短路径: 9 e- t5 {$ W% j8 D7 \% C0 Kvar # T$ J/ Q* |& R) ?
a:array[1..maxn,1..maxn] of integer; 0 y; I/ ^* u" f! J4 R# x, J
b:array[1..maxn] of integer; {b指顶点i到源点的最短路径} ' O9 j+ l% t) @0 {8 ^
mark:array[1..maxn] of boolean; 2 Y5 e8 N+ Q; {/ P0 G - b+ _3 D' s$ }+ [/ T8 Pprocedure bhf; ! U! {2 \8 j7 o$ f9 L; E- i) f
var * m1 J3 J% J9 A# X2 @3 r
best,best_j:integer; 3 ]# @) ?0 R( Z( p- P9 b
begin ; V- n3 R" n# Y7 U. b/ U9 p, w! b9 Lfillchar(mark,sizeof(mark),false); " ^ V$ D# q$ u$ @& h M" H
mark[1]:=true; b[1]:=0;{1为源点} ( K7 }' F6 g; M( a
repeat 5 o$ w+ f+ p, x* o
best:=0; 8 l4 D) l/ _8 J# f& @, K
for i:=1 to n do : ]3 A( y7 _. \If mark then {对每一个已计算出最短路径的点} 0 p g# m" U6 d$ V" c1 j% sfor j:=1 to n do - H) \3 R j s! X4 ^- L: mif (not mark[j]) and (a[i,j] >0) then 0 n: x- C6 D+ F- s7 Q* S5 a
if (best=0) or (b+a[i,j]< best) then 1 L. a' }& M) q" tbegin ) v/ v% }4 m4 X. n) l2 `best:=b+a[i,j]; best_j:=j; 1 P* ^' N. H! P1 Q% L3 Eend; + }( W' u# r6 v1 D0 [& Y6 V
if best >0 then ' L! e* A- O6 f* W9 T6 L# A {+ U
begin ) k( l1 n$ M4 @) R6 Wb[best_j]:=best;mark[best_j]:=true; 1 P! M! }7 @- Z B) D: N; r
end; ; |1 I/ O2 G' B7 P. q2 Nuntil best=0; 6 T6 H$ B4 t# F# A1 K1 Qend;{bhf} * J# c C' m4 p$ e/ Q5 S$ A% ?: j7 |" I) \4 l: \5 T4 W
B.Floyed算法求解所有顶点对之间的最短路径: ; k3 U9 U' f( m7 ?; kprocedure floyed; * v8 X0 j* z2 P$ y/ Xbegin # Q6 Y d1 D7 u/ \# i. Kfor I:=1 to n do 5 P! s* n$ s( Y, z7 tfor j:=1 to n do ' D2 p( j8 i+ f' y0 ?! wif a[I,j] >0 then p[I,j]:=I else p[I,j]:=0; + ^3 B: r; s9 w* ?0 n6 r X( E
{p[I,j]表示I到j的最短路径上j的前驱结点} ) N$ g, I ]) t. Z" D2 V, x
for k:=1 to n do {枚举中间结点} ( f' E5 G2 n0 H6 k/ mfor i:=1 to n do # _3 A- B& ^5 m |' l \! mfor j:=1 to n do ; I G% c% r# \: a8 ]5 I, P
if a[i,k]+a[j,k]< a[i,j] then 9 W9 B3 O: `, c- L! q# fbegin " _4 O& k- ?9 b/ g3 f4 I: L
a[i,j]:=a[i,k]+a[k,j]; : H8 ]( j+ ` z, X$ x# f
p[I,j]:=p[k,j]; 7 e8 V( f$ Z9 j2 `& [- U
end; 1 v, S# B/ P* g5 B
end; 3 Z, g1 ^ Z! J+ n* }: [; o6 ZC. Dijkstra 算法: ; |0 l2 V* X. z7 a [' H类似标号法,本质为贪心算法。 2 p4 e) q! Z6 M; d; R2 ~0 y
var 5 p2 H9 f$ u" A. M9 x F) [a:array[1..maxn,1..maxn] of integer; . C0 m' V. e1 W/ K
b,pre:array[1..maxn] of integer; {pre指最短路径上I的前驱结点} ) w3 y* C, l# W' ~; V, H( i$ v' Vmark:array[1..maxn] of boolean; ; B: a& |0 y2 L8 S6 X
procedure dijkstra(v0:integer); - L$ @7 V4 a& w7 I k7 [# ^begin 3 F$ _: |6 e' Y# O/ K9 S' j
fillchar(mark,sizeof(mark),false); 4 f0 y7 n" E2 i' B/ B) e
for i:=1 to n do & B8 ^ }& D9 ^0 n3 P v9 z
begin & P2 [) ^- p R8 y# Z7 ^
d:=a[v0,i]; 5 Y! P& a4 q4 k0 D% R
if d< >0 then pre:=v0 else pre:=0; 4 I+ j- N+ N6 T3 H1 T2 _end; 9 Z; G2 t& W+ T7 c7 x/ E Y5 zmark[v0]:=true; $ t# W( S" K3 nrepeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数} , F1 j" m* }. M% A! |4 jmin:=maxint; u:=0; {u记录离1集合最近的结点} 1 S; d/ e0 }2 q$ efor i:=1 to n do 7 n6 R4 x* Y. i9 @: f! Q% N
if (not mark) and (d< min) then ~" Z% Y- _* p+ ibegin + I3 K( G. I& F$ e8 L
u:=i; min:=d; ! X6 M5 k$ B: a+ u" F$ [' {7 Kend; ) F6 G/ n( c8 x- _" W+ h
if u< >0 then , w4 ~5 c4 _6 q0 h: h h' Obegin : G$ ~3 Y3 Z% c$ i% `; y, u
mark:=true; " G) |* u8 U) C+ S) i
for i:=1 to n do : X4 O O6 p& I$ mif (not mark) and (a[u,i]+d< d) then ' S; l- X; e( N' T% `+ k
begin + R' S/ p9 Y9 }$ t" N2 Od:=a[u,i]+d; 1 R+ T5 i% K( }. Y* H7 Wpre:=u; 9 `3 a, F. j& R$ e$ T
end; - k8 R) O* W: V) K! G" l
end; & s# K( D+ I2 y( s- r# suntil u=0; : _2 X. [* K( u. j% |7 kend; 7 h5 }. i7 ]: I6 g1 o- Y9 P
D.计算图的传递闭包 ! W! L0 L0 k" L0 I
Procedure Longlink; ; }# _- d b; H0 r5 Q6 G) q8 _
Var 1 \' A; n. C. q3 \( h
T:array[1..maxn,1..maxn] of boolean; , }% P( E) _- sBegin $ f/ P- n# h1 _% A- z
Fillchar(t,sizeof(t),false); 6 R2 ~ ^+ d% t( s/ @% z! C
For k:=1 to n do 9 y1 X. L5 d4 D. w, O8 _2 {
For I:=1 to n do ! s b/ Q. t) Q' \+ ^
For j:=1 to n do 8 e' n8 s, E! z7 J( u; ET[I,j]:=t[I,j] or (t[I,k] and t[k,j]); * }' }3 o6 ]" |( B& S
End; 0 b1 B5 {: p& G6 } x; |3 Z8 Q3 b) ^2 }