基本算法（用 PASCAL 描述）  
［作者：sortmail    轉貼自：Delphibbs.com    點擊數(shù)：462    更新時間：2005-1-22    文章錄入：aleyn］ 
 
基本算法（用 PASCAL 描述）

1.數(shù)論算法 
求兩數(shù)的最大公約數(shù) 
function gcd(a,b:integer):integer; 
begin 
if b=0 then gcd:=a 
else gcd:=gcd (b,a mod B); 
end;  

求兩數(shù)的最小公倍數(shù) 
function lcm(a,b:integer):integer; 
begin 
if a< b then swap(a,B); 
lcm:=a; 
while lcm mod b >0 do inc(lcm,a); 
end; 

素數(shù)的求法 
A.小范圍內判斷一個數(shù)是否為質數(shù)： 
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.判斷l(xiāng)ongint范圍內的數(shù)是否為素數(shù)（包含求50000以內的素數(shù)表）： 
procedure getprime; 
var 
i,j:longint; 
p:array[1..50000] of boolean; 
begin 
fillchar(p,sizeof(p),true); 
p[1]:=false; 
i:=2; 
while i< 50000 do begin 
if p[i] then begin 
j:=i*2; 
while j< 50000 do begin 
p[j]:=false; 
inc(j,i); 
end; 
end; 
inc(i); 
end; 
l:=0; 
for i:=1 to 50000 do 
if p[i] 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 do 
if pr[i] >=x then break 
else if x mod pr[i]=0 then exit; 
prime:=true; 
end;{prime} 

2． 

3． 


4.求最小生成樹 
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 begin 
lowcost[i]:=cost[v0,i]; 
closest[i]:=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; 
begin 
i:=1; 
while (i< =n) and (not v in vset[i]) do inc(i); 
if i< =n then find:=i else find:=0; 
end; 

procedure kruskal; 
var 
tot,i,j:integer; 
begin 
for i:=1 to n do vset[i]:=[i];{初始化定義n個集合，第I個集合包含一個元素I} 
p:=n-1; q:=1; tot:=0; {p為尚待加入的邊數(shù)，q為邊集指針} 
sort; 
{對所有邊按權值遞增排序，存于e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個頂點的序號，e[I].len為第I條邊的長度} 
while p >0 do begin 
i:=find(e[q].v1);j:=find(e[q].v2); 
if i< >j then begin 
inc(tot,e[q].len); 
vset[i]:=vset[i]+vset[j];vset[j]:=[]; 
dec(p); 
end; 
inc(q); 
end; 
writeln(tot); 
end; 


5.最短路徑 
A.標號法求解單源點最短路徑： 
var 
a:array[1..maxn,1..maxn] of integer; 
b:array[1..maxn] of integer; {b[i]指頂點i到源點的最短路徑} 
mark:array[1..maxn] of boolean; 

procedure bhf; 
var 
best,best_j:integer; 
begin 
fillchar(mark,sizeof(mark),false); 
mark[1]:=true; b[1]:=0;{1為源點} 
repeat 
best:=0; 
for i:=1 to n do 
If mark[i] then {對每一個已計算出最短路徑的點} 
for j:=1 to n do 
if (not mark[j]) and (a[i,j] >0) then 
if (best=0) or (b[i]+a[i,j]< best) then begin 
best:=b[i]+a[i,j]; best_j:=j; 
end; 
if best >0 then begin 
b[best_j]:=best；mark[best_j]:=true; 
end; 
until best=0; 
end;{bhf} 

B.Floyed算法求解所有頂點對之間的最短路徑： 
procedure floyed; 
begin 
for I:=1 to n do 
for j:=1 to n do 
if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路徑上j的前驅結點} 
for k:=1 to n do {枚舉中間結點} 
for i:=1 to n do 
for j:=1 to n do 
if a[i,k]+a[j,k]< a[i,j] then begin 
a[i,j]:=a[i,k]+a[k,j]; 
p[I,j]:=p[k,j]; 
end; 
end; 

C. Dijkstra 算法： 
類似標號法，本質為貪心算法。 
var 
a:array[1..maxn,1..maxn] of integer; 
b,pre:array[1..maxn] of integer; {pre[i]指最短路徑上I的前驅結點} 
mark:array[1..maxn] of boolean; 
procedure dijkstra(v0:integer); 
begin 
fillchar(mark,sizeof(mark),false); 
for i:=1 to n do begin 
d[i]:=a[v0,i]; 
if d[i]< >0 then pre[i]:=v0 else pre[i]:=0; 
end; 
mark[v0]:=true; 
repeat {每循環(huán)一次加入一個離1集合最近的結點并調整其他結點的參數(shù)} 
min:=maxint; u:=0; {u記錄離1集合最近的結點} 
for i:=1 to n do 
if (not mark[i]) and (d[i]< min) then begin 
u:=i; min:=d[i]; 
end; 
if u< >0 then begin 
mark[u]:=true; 
for i:=1 to n do 
if (not mark[i]) and (a[u,i]+d[u]< d[i]) then begin 
d[i]:=a[u,i]+d[u]; 
pre[i]:=u; 
end; 
end; 
until u=0; 
end; 

D.計算圖的傳遞閉包 
Procedure Longlink; 
Var 
T:array[1..maxn,1..maxn] of boolean; 
Begin 
Fillchar(t,sizeof(t),false); 
For k:=1 to n do 
For I:=1 to n do 
For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and t[k,j]); 
End; 


6.0-1背包問題（部分背包問題可有貪心法求解：計算Pi/Wi) 
數(shù)據結構： 
w[i]:第i個背包的重量； 
p[i]:第i個背包的價值； 
(1)0-1背包： 每個背包只能使用一次或有限次(可轉化為一次)： 
A.求最多可放入的重量。 
NOIP2001 裝箱問題 
有一個箱子容量為v(正整數(shù)，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積 (正整數(shù))。要求從 n 個物品中，任取若千個裝入箱內，使箱子的剩余空間為最小。 
l 搜索方法 
procedure search(k,v:integer); {搜索第k個物品，剩余空間為v} 
var i,j:integer; 
begin 
if v< best then best:=v; 
if v-(s[n]-s[k-1]) >=best then exit; {s[n]為前n個物品的重量和} 
if k< =n then begin 
if v >w[k] then search(k+1,v-w[k]); 
search(k+1,v); 
end; 
end; 

l DP 
F[I,j]為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。 
實現(xiàn):將最優(yōu)化問題轉化為判定性問題 
F[I,j]=f[i-1,j-w[i]] (w[I]< =j< =v) 邊界：f[0,0]:=true. 
For I:=1 to n do 
For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]]; 
優(yōu)化：當前狀態(tài)只與前一階段狀態(tài)有關，可降至一維。 
F[0]:=true; 
For I:=1 to n do begin 
F1:=f; 
For j:=w[I] to v do 
If f[j-w[I]] then f1[j]:=true; 
F:=f1; 
End; 

B.求可以放入的最大價值。 
F[I,j]= 


C.求恰好裝滿的情況數(shù)。 

　

(2)每個背包可使用任意次： 
A.求最多可放入的重量。 
狀態(tài)轉移方程為 
f[I,j]=max{f[i-w[j] 

　


B.求可以放入的最大價值。 
USACO 1.2 Score Inflation 
進行一次競賽，總時間T固定，有若干種可選擇的題目，每種題目可選入的數(shù)量不限，每種題目有一個ti（解答此題所需的時間）和一個si（解答此題所得的分數(shù)），現(xiàn)要選擇若干題目，使解這些題的總時間在T以內的前提下，所得的總分最大，求最大的得分。 
*易想到： 
f[i,j] = max { f [i- k*w[j], j-1] + k*v[j] } (0< =k< = i div w[j]) 
其中f[i,j]表示容量為i時取前j種背包所能達到的最大值。 
*優(yōu)化： 
Begin 
FillChar(problem,SizeOf(problem),0); 
Assign(Input,'inflate.in'); 
Reset(Input); 
Readln(M,N); 
For i:=1 To N Do 
With problem[i] Do 
Readln(point,time); 
Close(Input); 

FillChar(f,SizeOf(f),0); 
For i:=1 To M Do 
For j:=1 To N Do 
If i-problem[j].time >=0 Then 
Begin 
t:=problem[j].point+f[i-problem[j].time]; 
If t >f[i] Then f[i]:=t; 
End; 

Assign(Output,'inflate.out'); 
Rewrite(Output); 
Writeln(f[M]); 
Close(Output); 
End. 
C.求恰好裝滿的情況數(shù)。 
Ahoi2001 Problem2 
求自然數(shù)n本質不同的質數(shù)和的表達式的數(shù)目。 
思路一，生成每個質數(shù)的系數(shù)的排列，在一一測試，這是通法。 
procedure try(dep:integer); 
var i,j:integer; 
begin 
cal; {此過程計算當前系數(shù)的計算結果，now為結果} 
if now >n then exit; {剪枝} 
if dep=l+1 then begin {生成所有系數(shù)} 
cal; 
if now=n then inc(tot); 
exit; 
end; 
for i:=0 to n div pr[dep] do begin 
xs[dep]:=i; 
try(dep+1); 
xs[dep]:=0; 
end; 
end; 

思路二，遞歸搜索效率較高 
procedure try(dep,rest:integer); 
var i,j,x:integer; 
begin 
if (rest< =0) or (dep=l+1) then begin 
if rest=0 then inc(tot); 
exit; 
end; 
for i:=0 to rest div pr[dep] do 
try(dep+1,rest-pr[dep]*i); 
end; 

思路三：可使用動態(tài)規(guī)劃求解 
USACO1.2 money system 
V個物品，背包容量為n，求放法總數(shù)。 
轉移方程： 

Procedure update; 
var j,k:integer; 
begin 
c:=a; 
for j:=0 to n do 
if a[j] >0 then 
for k:=1 to n div now do 
if j+now*k< =n then inc(c[j+now*k],a[j]); 
a:=c; 
end; 
{main} 
begin 
read(now); {讀入第一個物品的重量} 
i:=0; {a[i]為背包容量為i時的放法總數(shù)} 
while i< =n do begin 
a[i]:=1; inc(i,now); end; {定義第一個物品重的整數(shù)倍的重量a值為1，作為初值} 
for i:=2 to v do 
begin 
read(now); 
update; {動態(tài)更新} 
end; 
writeln(a[n]);

7.排序算法 
A.快速排序： 
procedure sort(l,r:integer); 
var i,j,mid:integer; 
begin 
i:=l;j:=r; mid:=a[(l+r) div 2]; {將當前序列在中間位置的數(shù)定義為中間數(shù)} 
repeat 
while a[i]< mid do inc(i); {在左半部分尋找比中間數(shù)大的數(shù)} 
while mid< a[j] do dec(j);{在右半部分尋找比中間數(shù)小的數(shù)} 
if i< =j then begin {若找到一組與排序目標不一致的數(shù)對則交換它們} 
swap(a[i],a[j]); 
inc(i);dec(j); {繼續(xù)找} 
end; 
until i >j; 
if l< j then sort(l,j); {若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間} 
if i< r then sort(i,r);