摘錄地址：
http://vib.hit.edu.cn/vibbbs/dispbbs.asp?boardID=25&ID=2357&page=8 1.數論算法
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
?? if b=0 then gcd:=a
?? else gcd:=gcd (b,a mod b);
end ;
求兩數的最小公倍數
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;
素數的求法
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 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為尚待加入的邊數，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;??
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 {每循環一次加入一個離1集合最近的結點并調整其他結點的參數}??
????????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;??
7.排序算法??
A.快速排序：??
procedure sort(l,r:integer);??
var i,j,mid:integer;??
begin??
????i:=l;j:=r;
????mid:=a[(l+r) div 2];??
????{將當前序列在中間位置的數定義為中間數}??
????repeat??
????while a[i]< mid do inc(i); {在左半部分尋找比中間數大的數}??
????while mid< a[j] do dec(j);{在右半部分尋找比中間數小的數}??
????if i< =j then??
????begin {若找到一組與排序目標不一致的數對則交換它們}??
?????? swap(a[i],a[j]);??
?????? inc(i);
?????? dec(j); {繼續找}??
????end;??
????until i >j;??
????if l< j then
?????? sort(l,j); {若未到兩個數的邊界，則遞歸搜索左右區間}??
????if i< r then sort(i,r);??
end;{sort}
B.插入排序：
procedure insert_sort(k,m:word); {k為當前要插入的數，m為插入位置的指針}
var i:word; p:0..1;
begin??
????p:=0;??
????for i:=m downto 1 do??
????????if k=a[i] then exit;??
????????repeat?? If k >a[m] then??
???????????????? begin??
????????????????????a[m+1]:=k; p:=1;??
???????????????? end??
???????????????? else??
???????????????? begin??
????????????????????a[m+1]:=a[m];
????????????????????dec(m);??
???????????????? end;??
????????until p=1;
end;{insert_sort}??
l 主程序中為：??
?? a[0]:=0;??
?? for I:=1 to n do insert_sort(b[i],I-1);????
C.選擇排序：??
procedure sort;??
var i,j,k:integer;??
begin??
???? for i:=1 to n-1 do??
???? begin??
???????? k:=i;??
???????? for j:=i+1 to n do??
????????????if a[j]< a[k] then
?????????????? k:=j; {找出a[i]..a[n]中最小的數與a[i]作交換}??
?????????????? if k< >i then??
?????????????? begin??
??????????????????a[0]:=a[k];
??????????????????a[k]:=a[i];
??????????????????a[i]:=a[0];??
?????????????? end;??
???? end;??
end;????
D. 冒泡排序??
procedure sort;??
var i,j,k:integer;??
begin??
????for i:=n downto 1 do??
????????for j:=1 to i-1 do??
????????????if a[j] >a[i] then??
????????????begin??
?????????????? a[0]:=a[i];
?????????????? a[i]:=a[j];
?????????????? a[j]:=a[0];??
????????????end;??
end;????
E.堆排序：??
procedure sift(i,m:integer);{調整以i為根的子樹成為堆,m為結點總數}??
var k:integer;??
begin??
????a[0]:=a[i];
????k:=2*i;{在完全二*樹中結點i的左孩子為2*i,右孩子為2*i+1}??
????while k< =m do??
????begin??
????????if (k< m) and (a[k]< a[k+1]) then inc(k);{找出a[k]與a[k+1]中較大值}??
????????if a[0]< a[k] then??
????????begin??
?????????? a[i]:=a[k];
?????????? i:=k;
?????????? k:=2*i;??
????????end??
????????else
?????????? k:=m+1;??
????????end;??
????????a[i]:=a[0]; {將根放在合適的位置}??
end;
procedure heapsort;
var j:integer;
begin??
????for j:=n div 2 downto 1 do sift(j,n);??
????????for j:=n downto 2 do??
????????begin??
????????????swap(a[1],a[j]);??
????????????sift(1,j-1);??
????????end;
end;
F. 歸并排序
{a為序列表，tmp為輔助數組}
procedure merge(var a:listtype; p,q,r:integer);
{將已排序好的子序列a[p..q]與a[q+1..r]合并為有序的tmp[p..r]}
var I,j,t:integer;
????tmp:listtype;
begin??
????t:=p;
????i:=p;
????j:=q+1;{t為tmp指針，I,j分別為左右子序列的指針}??
????while (t< =r) do??
????begin??
?????? if (i< =q){左序列有剩余} and ((j >r) or (a[i]< =a[j])) then??{滿足取左邊序列當前元素的要求}??
?????? begin??
??????????tmp[t]:=a[i]; inc(i);??
?????? end??
?????? else??
?????? begin??
??????????tmp[t]:=a[j];
??????????inc(j);??
?????? end;??
?????? inc(t);??
????end;??
????for i:=p to r do a[i]:=tmp[i];
end;{merge}
procedure merge_sort(var a:listtype; p,r: integer); {合并排序a[p..r]}
var q:integer;
begin??
????if p< >r then??
????begin??
?????? q:=(p+r-1) div 2;??
?????? merge_sort (a,p,q);??
?????? merge_sort (a,q+1,r);??
?????? merge (a,p,q,r);??
????end;
end;
{main}
begin??
????merge_sort(a,1,n);
end.
?? writeln(tot);
end;??????