1、自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！ ！ 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺【數據結構】算法集錦數論算法1.求兩數的最大公約數function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end2.求兩數的最小公倍數function lcm(a,b:integer):integer; begin if a<b then swap(a,b); lcm:=a

2、; while lcm mod b>0do inc(lcm,a); nd; 3 .素數的求法 A.小范圍內判斷一個數是否為質數：function prime (n: integer): Boolean; var I:integer; begin for I:=2 to trunc(sqrt(n) do if n mod I=0 then beginprime:=false; exit; end; prime:=true; end;B.判斷longint范圍內的數是否為素數(包含求50000以內的素數表)：procedure getprime; var i,j:longint;p:arra

3、y1.50000 of boolean; begin fillchar(p,sizeof(p),true); p1:=false; i:=2; while i<50000 do begin if pi then begin j:=i*2; while j<50000 do begin pj:=false; inc(j,i); end; end; inc(i); end; l:=0; for i:=1 to 50000 do if pi then begin inc(l);prl:=i; end; end;getprime function prime(x:longint):inte

4、ger; var i:integer; begin prime:=false; for i:=1 to l do if pri>=x then break else if x mod pri=0 then exit; prime:=true; end;prime二、圖論算法1 .最小生成樹 A.Prim 算法： procedure prim(v0:integer); var lowcost,closest:array1.maxn of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcosti:=costv0,i;

5、closesti:=v0; end; for i:=1 to n-1 do begin 尋找 離生成樹最近的未加入頂點k min:=maxlongint; for j:=1 to n do if (lowcostj<min) and (lowcostj<>0) then beginmin:=lowcostj; k:=j; end; lowcostk:=0; 將頂點k加入生成樹 生成樹中增加一條新的邊k到closestk 修正各點的 lowcost 和 closest值 for j:=1 to n do if costk,j<lwocostj then begin low

6、costj:=costk,j; closestj:=k; end; end; end;primB.Kruskal算法：(貪心)按權值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。functionfind(v:integer):integer; 返回頂點 v 所在的集合 var i:integer; begin i:=1; while (i<=n) and (not v in vseti) do inc(i); if i<=n then find:=i else find:=0; end; procedure kruskal; var tot,i,j:integer; b

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

8、nc(q); end; writeln(tot); end; 2. 最短路徑 A.標號法求解單源點最短 路徑： var a:array1.maxn,1.maxn of integer; b:array1.maxn of integer; bi 指頂點 i 至U源點的最短路徑 mark:array1.maxn of boolean; procedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark1:=true; b1:=0;1 為源點 repeat best:=0; for i:=1 to

9、 n do If marki then 對每一個已計算出最短路徑的點for j:=1 to n do if (not markj) and (ai,j>0) then if (best=0) or (bi+ai,j<best) then begin best:=bi+ai,j; best_j:=j; end; if best>0 then begin bbest_j:=best ； markbest_j:=true; end; until best=0; end;bhf B.Floyed算法求解所有頂點對之間的最短路徑：procedure floyed; begin for

10、I:=1 to n do for j:=1 to n do if aI,j>0 then pI,j:=I else pI,j:=0;pI,j表示I至叮 的最短路徑上j的前驅結點 for k:=1 to n do 枚舉中間結點 for i:=1 to n do for j:=1 to n do if ai,k+aj,k<ai,j then begin ai,j:=ai,k+ak,j; pI,j:=pk,j; end; end; C. Dijkstra算法： vara:array1.maxn,1.maxn of integer; b,pre:array1.maxn of integer

11、; prei 指最短路徑上 I 的前驅結點 mark:array1.maxn of boolean; procedure dijkstra(v0:integer); begin fillchar(mark,sizeof(mark),false); for i:=1 to n do begin di:=av0,i; if di<>0 then prei:=v0 else prei:=0; end; markv0:=true; repeat 每循環一次加入一個離1 集合最近的結點并調整其他結點的參數 min:=maxint; u:=0; u 記錄離1集合最近的結點 for i:=1 t

12、o n do if (not marki) and (di<min) then begin u:=i; min:=di; end; if u<>0 then begin marku:=true; for i:=1 to n do if (not marki) and (au,i+du<di) then begin di:=au,i+du; prei:=u; end; end; until u=0; end; 3. 計算圖的傳遞閉包 Procedure Longlink; Var T:array1.maxn,1.maxn of boolean; Begin Fillcha

13、r(t,sizeof(t),false); For k:=1 to n do For I:=1 to n do For j:=1 to n do TI,j:=tI,j or (tI,k and tk,j); End;4. 無向圖的連通分量A.深度優先 procedure dfs ( now,color: integer); begin for i:=1 to n do if anow,i and ci=0 then begin 對結點 I 染色 ci:=color; dfs(I,color); end; end;5. 關鍵路徑 幾個定義：頂點1為源點，n為匯點。a.頂點事件最早發生時間Vej,

14、 Ve j = max Ve j +wI,j ,其中 Ve (1) = 0; b.頂點事件最晚發生時間Vlj, Vl j = min Vlj -wI,j ,其中 Vl(n) = Ve(n); c.邊活自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！ ！ 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺動最早開始時間Eel,若邊I由j,k表示，則Eel = Vej; d.邊活動最晚開始時間Ell,若邊I由j,k表示，則Ell = Vlk-wj,k;若Eej = Elj，則活動j為關鍵活動，由關鍵活

15、動組成的路徑為關鍵路徑。求解方法：a.從源點起topsort,判斷是否有回路并計算Ve; b.從匯點起topsort,求Vl; c.算Ee和El;例尋找一數列，其中任意連續6拓撲排序 找入度為0的點，刪去與其相連的所有邊，不斷重復這一過程。 p項之和為正，任意q項之和為負，若不存在則輸出 NO.7.回路問題Euler回路（DFS）定義：經過圖的每條邊僅一次的回路。（充要條件：圖連同且無奇點）Hamilton回路 定義：經過圖的每個頂點僅一次的回路。一筆畫 充要條件：圖連通且奇點個數為 0個或2個。9判斷圖中是否有負權回路 Bellman-ford算法xl,yl,tl分別表示第I條邊的起點，終點和權。共 n個結點和m條 邊。 procedure bellman-ford begin for l:=0 to n-1 do dl:=+infinitive; d0:=0; for l:=1 t