熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構算法集錦

2013-11-15 15:34:29  來源: 數據結構 

  一數論算法

  求兩數的最大公約數

  function gcd(ab:integer):integer;

  begin

  if b= then gcd:=a

  else gcd:=gcd (ba mod b);

  end ;

  求兩數的最小公倍數

  function lcm(ab:integer):integer;

  begin

  if a

  lcm:=a;

  while lcm mod b> do inc(lcma);

  end;

  素數的求法

  A小范圍內判斷一個數是否為質數

  function prime (n: integer): Boolean;

  var I: integer;

  begin

  for I:= to trunc(sqrt(n)) do

  if n mod I= then begin

  prime:=false; exit;

  end;

  prime:=true;

  end;

  B判斷longint范圍內的數是否為素數(包含求以內的素數表)

  procedure getprime;

  var

  ij:longint;

  p:array[] of boolean;

  begin

  fillchar(psizeof(p)true);

  p[]:=false;

  i:=;

  while i< do begin

  if p[i] then begin

  j:=i*;

  while j< do begin

  p[j]:=false;

  inc(ji);

  end;

  end;

  inc(i);

  end;

  l:=;

  for i:= to 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:= to l do

  if pr[i]>=x then break

  else if x mod pr[i]= then exit;

  prime:=true;

  end;{prime}

  二圖論算法

  最小生成樹

  APrim算法

  procedure prim(v:integer);

  var

  lowcostclosest:array[maxn] of integer;

  ijkmin:integer;

  begin

  for i:= to n do begin

  lowcost[i]:=cost[vi];

  closest[i]:=v;

  end;

  for i:= to n do begin

  {尋找離生成樹最近的未加入頂點k}

  min:=maxlongint;

  for j:= to n do

  if (lowcost[j]) then begin

  min:=lowcost[j];

  k:=j;

  end;

  lowcost[k]:=; {將頂點k加入生成樹}

  {生成樹中增加一條新的邊k到closest[k]}

  {修正各點的lowcost和closest值}

  for j:= to n do

  if cost[kj]

  lowcost[j]:=cost[kj];

  closest[j]:=k;

  end;

  end;

  end;{prim}

  BKruskal算法(貪心)

  按權值遞增順序刪去圖中的邊若不形成回路則將此邊加入最小生成樹

  function find(v:integer):integer; {返回頂點v所在的集合}

  var i:integer;

  begin

  i:=;

  while (i<=n) and (not v in vset[i]) do inc(i);

  if i<=n then find:=i else find:=;

  end;

  procedure kruskal;

  var

  totij:integer;

  begin

  for i:= to n do vset[i]:=[i];{初始化定義n個集合第I個集合包含一個元素I}

  p:=n; q:=; tot:=; {p為尚待加入的邊數q為邊集指針}

  sort;

  {對所有邊按權值遞增排序存於e[I]中e[I]v與e[I]v為邊I所連接的兩個頂點的序號e[I]len為第I條邊的長度}

  while p> do begin

  i:=find(e[q]v);j:=find(e[q]v);

  if i<>j then begin

  inc(tote[q]len);

  vset[i]:=vset[i]+vset[j];vset[j]:=[];

  dec(p);

  end;

  inc(q);

  end;

  writeln(tot);

  end;

  最短路徑

  A標號法求解單源點最短路徑

  var

  a:array[maxnmaxn] of integer;

  b:array[maxn] of integer; {b[i]指頂點i到源點的最短路徑}

  mark:array[maxn] of boolean;

  procedure bhf;

  var

  bestbest_j:integer;

  begin

  fillchar(marksizeof(mark)false);

  mark[]:=true; b[]:=;{為源點}

  repeat

  best:=;

  for i:= to n do

  If mark[i] then {對每一個已計算出最短路徑的點}

  for j:= to n do

  if (not mark[j]) and (a[ij]>) then

  if (best=) or (b[i]+a[ij]

  best:=b[i]+a[ij]; best_j:=j;

  end;

  if best> then begin

  b[best_j]:=best;mark[best_j]:=true;

  end;

  until best=;

  end;{bhf}

  BFloyed算法求解所有頂點對之間的最短路徑

  procedure floyed;

  begin

  for I:= to n do

  for j:= to n do

  if a[Ij]> then p[Ij]:=I else p[Ij]:=; {p[Ij]表示I到j的最短路徑上j的前驅結點}

  for k:= to n do {枚舉中間結點}

  for i:= to n do

  for j:= to n do

  if a[ik]+a[jk]

  a[ij]:=a[ik]+a[kj];

  p[Ij]:=p[kj];

  end;

  end;

  C Dijkstra 算法

  var

  a:array[maxnmaxn] of integer;

  bpre:array[maxn] of integer; {pre[i]指最短路徑上I的前驅結點}

  mark:array[maxn] of boolean;

  procedure dijkstra(v:integer);

  begin

  fillchar(marksizeof(mark)false);

  for i:= to n do begin

  d[i]:=a[vi];

  if d[i]<> then pre[i]:=v else pre[i]:=;

  end;

  mark[v]:=true;

  repeat {每循環一次加入一個離集合最近的結點並調整其他結點的參數}

  min:=maxint; u:=; {u記錄離集合最近的結點}

  for i:= to n do

  if (not mark[i]) and (d[i]

  u:=i; min:=d[i];

  end;

  if u<> then begin

  mark[u]:=true;

  for i:= to n do

  if (not mark[i]) and (a[ui]+d[u]

  d[i]:=a[ui]+d[u];

  pre[i]:=u;

  end;

  end;

  until u=;

  end;

  計算圖的傳遞閉包

  Procedure Longlink;

  Var

  T:array[maxnmaxn] of boolean;

  Begin

  Fillchar(tsizeof(t)false);

  For k:= to n do

  For I:= to n do

  For j:= to n do T[Ij]:=t[Ij] or (t[Ik] and t[kj]);

  End;

  無向圖的連通分量

  A深度優先

  procedure dfs ( nowcolor: integer);

  begin

  for i:= to n do

  if a[nowi] and c[i]= then begin {對結點I染色}

  c[i]:=color;

  dfs(Icolor);

  end;

  end;

  B 寬度優先(種子染色法)

  關鍵路徑

  幾個定義 頂點為源點n為匯點

  a 頂點事件最早發生時間Ve[j] Ve [j] = max{ Ve [j] + w[Ij] }其中Ve () = ;

  b 頂點事件最晚發生時間 Vl[j] Vl [j] = min{ Vl[j] – w[Ij] }其中 Vl(n) = Ve(n);

  c 邊活動最早開始時間 Ee[I] 若邊I由表示則Ee[I] = Ve[j];

  d 邊活動最晚開始時間 El[I] 若邊I由表示則El[I] = Vl[k] – w[jk];

  若 Ee[j] = El[j] 則活動j為關鍵活動由關鍵活動組成的路徑為關鍵路徑

  求解方法

  a 從源點起topsort判斷是否有回路並計算Ve;

  b 從匯點起topsort求Vl;

  c 算Ee 和 El;

  拓撲排序

  找入度為的點刪去與其相連的所有邊不斷重復這一過程

  例 尋找一數列其中任意連續p項之和為正任意q 項之和為負若不存在則輸出NO

  回路問題

  Euler回路(DFS)

  定義經過圖的每條邊僅一次的回路(充要條件圖連同且無奇點)

  Hamilton回路

  定義經過圖的每個頂點僅一次的回路

  一筆畫

  充要條件圖連通且奇點個數為個或

  判斷圖中是否有負權回路 Bellmanford 算法

  x[I]y[I]t[I]分別表示第I條邊的起點終點和權共n個結點和m條邊

  procedure bellmanford

  begin


From:http://tw.wingwit.com/Article/program/sjjg/201311/23620.html

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.