1.数论算法 3 P3 N5 P) ^$ W5 \求两数的最大公约数 3 J+ s. N0 ^3 r* t- h- I
function gcd(a,b:integer):integer; + B! a4 n$ ^+ S: Fbegin 6 `2 e/ Q7 O: e3 h! z& Wif b=0 then gcd:=a 0 r: k1 Q1 `5 {- g% w s
else gcd:=gcd (b,a mod b); : r' A9 b1 k. p! ]9 K" j( e- Aend ; 4 t+ ]# g( W% p/ [6 \( v
* I7 D3 c! h6 K9 H6 T% n) P: v% y7 {求两数的最小公倍数 ' c% F. N8 f* y. ~, o
function lcm(a,b:integer):integer; , k5 x* U$ y' ], v: q) z' k
begin 4 T! E3 b, H. x( N ^. ?! a. J1 z
if a< b then swap(a,b); % H& s2 a" V1 i# |: Q, }
lcm:=a; % E3 V- S5 M+ M% E
while lcm mod b >0 do inc(lcm,a); S1 D+ r( L0 K7 fend; U2 Z" |4 J0 Z( O W0 ?
% C0 K% F0 u$ z8 ^素数的求法 3 y# D6 t7 [; ]8 t. }A.小范围内判断一个数是否为质数: ; W- _" K' \$ O) g' C; nfunction prime (n: integer): Boolean; $ t- b# H) Q8 `/ Y4 T
var I: integer; ; `" j& V2 @; fbegin ' W* w) q- i" q- g; ^for I:=2 to trunc(sqrt(n)) do 5 |6 ]9 {' h; a3 G7 c9 q; g0 V( ]
if n mod I=0 then 3 t. `/ }6 I0 K. c- nbegin 8 d$ \+ c5 U! T
prime:=false; exit; / ?: Y5 T! s+ h6 P# q9 O$ _end; / u N0 b, i0 x1 t2 S% u6 t
prime:=true; 5 J' a. P$ s. ^
end; ' E$ k* _5 Z: m3 I% V 2 c+ {( A" }: D% {8 c" {B.判断longint范围内的数是否为素数(包含求50000以内的素数表): 1 `2 o B: F% m% Yprocedure getprime; : ~* I# g. W5 i8 {var - M' m* q- p" ?/ Ki,j:longint; " ?9 J8 k: j& b9 q
p:array[1..50000] of boolean; 6 z! Z& ~1 \$ b$ _+ b5 Ebegin 4 g5 g8 @6 i; [9 t, E
fillchar(p,sizeof(p),true); 2 }8 z& \% h& e, fp[1]:=false; 5 {# [! P& Z( I% L: `' N" vi:=2; + a$ w5 n P1 Y; W0 hwhile i< 50000 do 0 J# T4 e9 [$ c1 E0 sbegin $ I6 p% ~1 V/ U Z& d1 f) \
if p then 5 B' [: {% i3 h1 Z h+ h; u
begin # Y7 {5 I9 }/ Q
j:=i*2; ( p- I3 r% P, E- _5 m! |while j< 50000 do R3 J$ g4 o+ t& B0 L/ A
begin ! p- G: l+ ~3 _. g7 s' i- gp[j]:=false; " N, _0 C( X. n6 {/ w! R
inc(j,i); $ s1 @& n p' |, ?7 A
end; " ]4 ?, |- |( Q) r5 Dend; 4 ^4 Q; `! u# Q: ^, P, }9 m
inc(i); 2 f _: u6 R: p+ y4 Q: l
end; 9 x g" D6 S; b( L8 S
l:=0; ! }* V2 q' k5 T. Vfor i:=1 to 50000 do 3 f2 U* q0 `9 G" ]) p# Dif p then / A$ c. K& D( O3 `+ G( qbegin - T9 @0 \9 ~3 f! i, u( z2 I4 d
inc(l);! x- I4 N* m5 o$ T
pr[l]:=i; $ e. r# R: V; s" }end; ; Q8 b! o p( o, T$ M% x% Gend;{getprime} , o- t! v% T2 pfunction prime(x:longint):integer; ! B2 w/ A5 {, Ovar i:integer; 9 I: f* n3 J, O6 e, V
begin 9 ]" z) N" v* }4 u( C1 Iprime:=false; , H, n, k9 {$ m3 v+ D1 Pfor i:=1 to l do 1 v& b% O! |8 i6 F6 p/ q6 Zif pr >=x then break 3 a3 K- H( u E8 Z' i! Nelse if x mod pr=0 then exit; - X0 k. k/ y& Y" ~' Z* g8 ^* d
prime:=true; 1 @# F0 `$ k Y3 w1 a% v
end;{prime} 3 }! m8 U/ o$ @1 @
# e, F8 h8 n* b U
2. : O) p) v6 X. U, x 1 I# [: J. H' M2 W7 d, J0 U( O3. & a; D4 K3 _- N 0 Z: Z" x( c- `/ d% X# a4.求最小生成树 [1 C# b* M; `6 p! bA.Prim算法: - m2 P+ M- b+ L' e7 G
procedure prim(v0:integer); . H$ d. q% m9 wvar 0 P* G2 O/ I% A2 C" blowcost,closest:array[1..maxn] of integer; 4 k! M* M( Y U9 v) u& U, J
i,j,k,min:integer; & V4 ^% e5 u) b) Y* g1 j
begin . c. `/ U4 ?* c6 r2 ? Gfor i:=1 to n do m9 M" K8 b; W* b1 v" J
begin 3 u9 M' w: ^: C- q' f4 mlowcost:=cost[v0,i]; 5 u. Z& s6 f3 R& u1 |8 m1 S m. Kclosest:=v0; ( _& ]( T; P) P1 n+ Oend; 6 P: W' ~1 C h( ifor i:=1 to n-1 do $ y3 U7 L% y0 _4 N- _1 Ubegin : Y7 V. t8 M/ L4 h3 G$ S8 x
{寻找离生成树最近的未加入顶点k} 2 Z' n& s2 Q2 h$ \min:=maxlongint; 2 L4 x* s3 x9 }
for j:=1 to n do $ f2 g1 x# X7 |if (lowcost[j]< min) and (lowcost[j]< >0) then 9 J* _: ~+ p* R f* j2 |, r& Vbegin # t. S6 Z$ q* k5 E! mmin:=lowcost[j]; 4 C0 o- { v3 G( n# X- G9 ?# H
k:=j; ) k b/ @, _( h" b* f
end; & Z6 M* o7 D2 i9 S* {# E8 l
lowcost[k]:=0; {将顶点k加入生成树} ' h# z# n$ A6 I2 h0 h |1 y
{生成树中增加一条新的边k到closest[k]} & i" |9 u# p" D9 }1 E3 |
{修正各点的lowcost和closest值} 2 ~' b- p% X4 i; F- {( ]9 \; l
for j:=1 to n do 7 @- {- Q8 P' e: D! P9 m( Yif cost[k,j]< lwocost[j] then ) d' _% ]* W8 o* N3 L" A. sbegin 7 w# B# M. i" F; ]1 O) J; C% T
lowcost[j]:=cost[k,j]; ' y" E7 I0 W8 C. n; zclosest[j]:=k; 8 w2 |% E; K6 ?6 Y+ o; oend; ! W- }! [6 n" Z: d- h; i: K6 ^! Y* c
end; " f6 K* ~1 z/ v+ ^9 i. \! L4 ]end;{prim} ) a) Y7 Q G* D- f- a
B.Kruskal算法:(贪心) 1 q. `% ?& }2 I) Y
按权值递增顺序删去图中的边,若不形成回路则将此边加入最小生成树。 8 T& U) I( g% o1 l ^function find(v:integer):integer; {返回顶点v所在的集合} 8 I9 o' {. D; }: |var i:integer; 9 M) W: n! L) n$ Ebegin - e" I7 ?2 T6 }% S+ h* bi:=1; $ I2 w( V0 D2 y. L! `
while (i< =n) and (not v in vset) do inc(i); " Q1 H' h; ~' U! E" k" Dif i< =n then find:=i 7 f3 |, z2 A6 y
else find:=0; & @6 t7 q4 J1 q
end; - D9 [0 |2 A3 ^0 C2 j" m* Y
procedure kruskal; ) h* d9 C0 O$ ?# Bvar 0 U1 O* E6 ?' e- z; T
tot,i,j:integer; 2 K; ^6 D: C1 {+ t$ ?- S* Lbegin * F, n" v" i1 Nfor i:=1 to n do vset:=;{初始化定义n个集合,第I个集合包含一个元素I} 6 P/ r% I0 |1 n, d( D1 e2 n
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数,q为边集指针} ( R" X# @3 c& A; Y) a w% E) q" j4 g
sort; . R. q( [: { [
{对所有边按权值递增排序,存于e[I]中,e[I].v1与e[I].v2为边I所连接的两个顶点的序号,e[I].len为第I条边的长度} ( R- Q7 d- |% k7 w5 q) d7 mwhile p >0 do % t$ J. d) J/ `+ Abegin " e3 v" r8 v; t: l5 G0 v3 N
i:=find(e[q].v1);j:=find(e[q].v2); ( X8 Z! `; ~: W5 } D: F
if i< >j then 3 G; X- E3 Y) X6 P
begin 5 Q# L L$ D* Y s4 v
inc(tot,e[q].len); * @+ d$ s; o+ E* V" B
vset:=vset+vset[j];vset[j]:=[]; ; z4 z, q; r2 b4 V6 ~6 {( Gdec(p); 0 ? F; z7 q1 K1 S
end; . `/ j1 b; g4 m; j0 A+ k3 ~
inc(q); 5 k& S0 X$ b7 F
end; 5 j8 ~8 | d5 A/ Ewriteln(tot); ( B) o. H* e9 o& d; Dend; g) r5 A, m: T: x
2 J5 _) }2 h4 H; z7 v2 @1 N5.最短路径 9 b- |: c* q; t# FA.标号法求解单源点最短路径: + ~) g1 s) H! _$ [/ xvar 4 B& r) v/ N. K, I- d
a:array[1..maxn,1..maxn] of integer; ! P' G! g/ h7 Y1 T0 Mb:array[1..maxn] of integer; {b指顶点i到源点的最短路径} " _$ J8 Y1 S! T& r7 S! h: Umark:array[1..maxn] of boolean; ; |3 z+ g' h7 v, ?4 `5 S
~# ]9 n8 t; {
procedure bhf; / G. N# \" {, O# l: ?; M3 w C
var - ]; F$ g! @7 l1 K0 u9 Fbest,best_j:integer; o, `1 ]) E. z2 q# Tbegin / |6 m j+ y" i
fillchar(mark,sizeof(mark),false); 5 u; ~! H! n, ~( I Zmark[1]:=true; b[1]:=0;{1为源点} & a! ~$ t3 [- s
repeat R5 v9 B& [' G0 y0 J, B
best:=0; " o+ [8 |! p5 j/ Ifor i:=1 to n do ; s1 y: ^; r; I! j, c5 i1 ^If mark then {对每一个已计算出最短路径的点} , X, N8 {5 L' `$ Q4 z* J9 p
for j:=1 to n do ( S3 ~" O+ L. L7 M# m
if (not mark[j]) and (a[i,j] >0) then 5 {& ~ u H6 T4 v8 Y/ Q9 ` d9 _/ I
if (best=0) or (b+a[i,j]< best) then - j6 y% d- ?1 n3 n3 M, { D& Sbegin * c$ o* t9 |7 P1 @best:=b+a[i,j]; best_j:=j; 3 f4 l& D |7 Q; v8 uend; 2 Z o6 f; \% I$ ?" ?if best >0 then * S% j9 r* V# pbegin 9 d! h8 ?: p2 N) Q; \
b[best_j]:=best;mark[best_j]:=true; 5 M! Y# D. `! }+ z) _" oend; ! v* a& }% R \+ L7 q6 l) m' l
until best=0; # ~/ ^! N" Y5 H" T* wend;{bhf} ) M: x7 H9 P4 _; J
; T3 B4 u& A! N3 v
B.Floyed算法求解所有顶点对之间的最短路径: 0 p* I. i) n/ G/ r# H- ^
procedure floyed; - { v1 u4 N; L, b( _) U" r
begin ) [7 e L; H" j4 jfor I:=1 to n do & j e; W% N, T2 m G: bfor j:=1 to n do 9 B: p+ d* J; O% S' |8 r- T3 z eif a[I,j] >0 then p[I,j]:=I else p[I,j]:=0; ! x+ h2 i& u, g6 \6 [5 I7 d% v% D
{p[I,j]表示I到j的最短路径上j的前驱结点} # t0 ^7 X! e V- G4 Tfor k:=1 to n do {枚举中间结点} $ H! i5 o- c/ q8 l$ e
for i:=1 to n do + e8 O- |5 Q) x0 ^0 I
for j:=1 to n do 3 h2 I8 d E6 t% J9 L/ O4 Y x
if a[i,k]+a[j,k]< a[i,j] then & p; P1 N; B$ U9 P. a x1 C- C0 kbegin / Q) H5 M* G6 G3 G$ o- b" A1 m
a[i,j]:=a[i,k]+a[k,j]; * d( o- n) m+ a c; X6 y
p[I,j]:=p[k,j]; 7 v- s- T8 [! A4 C' h
end; 4 W$ w9 h5 O3 ^- M: G* @( vend; & }( I: T, {0 _C. Dijkstra 算法: 7 }. W2 G# j4 `类似标号法,本质为贪心算法。 . l; o/ S$ p6 i! I/ g
var ! y& ^: L! @( i8 ]% p/ C7 a
a:array[1..maxn,1..maxn] of integer; 4 d% ~' d) Z3 z2 Bb,pre:array[1..maxn] of integer; {pre指最短路径上I的前驱结点} ) E1 J: i, Z ^" Qmark:array[1..maxn] of boolean; # I6 v& @; w5 K' F
procedure dijkstra(v0:integer); 1 f& d6 \8 k0 M( S Rbegin ' t5 s8 o* v5 E( m# ^$ o X
fillchar(mark,sizeof(mark),false); ! ~' @! ]" Q3 \* v( F( k. K
for i:=1 to n do 3 q0 E. k5 P+ o" Ubegin ( P/ L5 {& X, Z4 w3 i% ~d:=a[v0,i]; " J3 f' x; t( Y4 Jif d< >0 then pre:=v0 else pre:=0; ^/ b) f# K7 B$ vend; ; I. L$ ^. H5 J# w
mark[v0]:=true; 2 ~" P/ t, \& F, q2 u, V7 Qrepeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数} 0 u4 {% Q; O J$ W3 }
min:=maxint; u:=0; {u记录离1集合最近的结点} $ S- J" s1 y1 x# s
for i:=1 to n do ' n1 m+ N7 c/ D5 B f7 m& ]if (not mark) and (d< min) then . G" X/ p, e/ B, E+ s* G4 i5 _4 hbegin . H( ?3 Q& O+ L. P4 Q! k8 e
u:=i; min:=d; 7 R8 B1 X3 d$ s- N
end; - n$ @6 O$ ^5 ] u, \9 x$ O
if u< >0 then " j: t+ E) a& r, k; r& {8 ?: ybegin 3 V" b) r4 z; o- Z
mark:=true; y2 k7 n B5 T0 j, ^for i:=1 to n do $ J- \2 j6 H. Q, Gif (not mark) and (a[u,i]+d< d) then ! m y0 G# r4 {, Y7 d! i' P. ?begin % V+ j5 N' D3 q6 cd:=a[u,i]+d; * q9 ~1 O; ~( ]5 Q# v) h# u2 Y
pre:=u; 8 U/ o9 k, p$ }
end; ; `) n% [2 ^- v' t9 _( z+ M R
end; $ R' [* j* V3 duntil u=0; ) A l0 y- e) L: f0 \end; Z p' O* {/ O3 G( C8 z B1 Y
D.计算图的传递闭包 $ l4 i. g; V' K7 q
Procedure Longlink; * ?' ]. O- p1 |. VVar ( \5 ]6 d7 c2 |& [, B oT:array[1..maxn,1..maxn] of boolean; $ n8 r5 ~7 q, R* kBegin + K, T, B2 b C1 U; a# _Fillchar(t,sizeof(t),false); . ~, x' A2 t0 d4 e) V, j+ GFor k:=1 to n do 4 ^+ m! V$ S' |0 s
For I:=1 to n do 2 r+ H3 w% g- ~- r/ d8 ?
For j:=1 to n do 6 k- [2 T! y$ p. g3 V1 {T[I,j]:=t[I,j] or (t[I,k] and t[k,j]); 8 x; L+ [5 P2 C" V$ F( lEnd; + ]7 h' b3 t/ i) j3 M2 H & g! Y0 J6 g1 p8 H; L2 E) L