經(jīng)典算法實例

1、C C，經(jīng)典算法案例一、數(shù)論算法1.求兩個數(shù)的最大公約數(shù)Function gcd (a，b : integer): integer；貝金If b=0 then gcd:=aElse gcd:=gcd (b，a mod b)；End2.尋找兩個數(shù)字的最小公倍數(shù)Function LCM (a，b : integer) : integer:貝金If A0 do inc(lcm，a)；End3.小數(shù)句法A.小規(guī)模判斷小數(shù)是否為小數(shù)。function prime(n : integer): boolean:Var I: integer:貝金For I:=2 to trunc(sqrt(n) doIf n

2、 mod I=0 then beginPrime:=falseExitEndPrime:=trueEndB.確定longint范圍的數(shù)量是否為小數(shù)(包括50，000個以內(nèi)的小數(shù)表)。Procedure getprimeVarI，j:longintP:array1.50000of boolean；貝金Fillchar(p，sizeof(p)，true)；p1:=false；I :=2；While i50000 do beginIf pi then beginj :=I * 2；While j50000 do beginpj:=false；Inc(j，I)；EndEndInc(I)；Endl :=

3、0；For i:=1 to 50000 doIf pi then beginInc(l)；prl:=I；EndEndgetprimefunction prime(x : longint): integer:Var i:integer:貝金Prime:=falseFor i:=1 to l doIf pri=x then breakelse if x mod prI=0 then exit；Prime:=trueEndprime二、圖論算法1.最小生成樹A.Prim算法：步驟prim(v 03360 integer):Var低成本，closest :陣列1.maxnof integer；I、j、

4、k、min:integer貝金For i:=1 to n do beginLowcosti:=costv0，I；closestI:=v0；EndFor i:=1 to n-1 do begin查找距離生成樹最近的未連接頂點kMin:=maxlongintFor j:=1 to n doIf (lowcostj0) then beginmin :=low costj；k :=j；Endlow costk:=0；向生成樹添加頂點k 向closest k添加新邊k到生成樹修改每個點的lowcost和closest值For j:=1 to n doIf costk，j0 do beginI :=fin

5、d(eq. v1)；j :=find(eq. v2)；If ij then beginInc(tot，eq)。len)；vsetI:=vsetIvsetj；vsetj:=；dec(p)；EndInc(q)；Endwriteln(tot)；End2.最短路徑A.解決單個源點最短路徑的標簽方法：Vara 3360 array1.maxn，1.maxnof integer；B:array1.maxnof integer；bi表示從頂點I到源點的最短路徑段宜恩：陣列1.maxnof boolean；步驟BHFVarBest，best _ j3360 integer貝金Fillchar (mark，si

6、zeof (mark)，false)；段宜恩1 :=真；b1:=0；1是源點Repeatbest :=0；For i:=1 to n doIf marki then 對于計算最短路徑的每個點For j:=1 to n doIf (notmark j)和(a I，j 0) thenIf (best=0)或(b I a I，j 0 then begin)bbest _ j:=best；段宜恩best _ j:=true；Enduntil best=0；EndbhfB.Floyed算法解決所有頂點對之間的最短路徑：Procedure floyed貝金For I:=1 to n doFor j:=1

7、to n doIf a I，j 0 then p I，j :=I else p I，j:=0；pI，j表示從I到j的最短路徑中j的前導節(jié)點。For k:=1 to n do 列出中間節(jié)點For i:=1 to n doFor j:=1 to n doIf a I，k a j，k0 then preI:=v0 else preI:=0；End段宜恩v0:=true；Repeat 每個循環(huán)添加一個最接近1集合的節(jié)點，一次曹征另一個節(jié)點的參數(shù)Min:=maxintu :=0；u唱片1集合中最近的節(jié)點For i:=1 to n doIf (notmark I)和(d I 0 then begin)段宜

8、恩u :=真；For i:=1 to n doIf (not marki) and (au，i du，EeI=Vej；D.邊活動的最晚開始時間ElI，如果邊I表示為，則ElI=Vlk-wj，k；如果Eej=Elj，則活動j是主要活動，由主要活動組成的路徑是關(guān)鍵路徑路徑。解決方法：A.從源點開始topsort，檢查是否存在循環(huán)，然后計算Ve。B.從轉(zhuǎn)運點開始topsort，Vl請求C.計算Ee和El。6.拓撲排序找到度為零的點，刪除所有連接的邊，然后重復牙齒過程。例如，查找一系列列，其中連續(xù)P項的和為正，Q項的和為負，如果不存在，則輸出NO。7.回路問題歐拉回路(DFS)定義：僅通過地物的每個邊

9、一次的回路。(先決條件：沒有圖形和奇點)漢密爾頓電路定義：僅通過圖形中每個頂點一次的回路。畫一筆先決條件：圖形已連接，奇點數(shù)為0或2。9.確保圖中有負權(quán)重電路貝爾曼福德算法XI、yI、tI分別表示I條邊的開始、結(jié)束和權(quán)重。共n個節(jié)點和m個邊。Procedure bellman-ford貝金For i:=0到n-1 do dI:=infinitive；d0:=0；For i:=1至n-1 doFor j:=1 to m do 枚舉所有邊if dxjtj=best then exit；sn表示前n個項目的重量和If k=n then beginIf vwk then search(k 1，v-wk)；搜索(k1，v)；EndEndL DPFI，j選擇前I個項目中的幾個項目，以將卷精確為j的符號選擇為