演算法全部

① 計算幾何的全部演算法

1. 矢量減法

設二維矢量 P = （x1,y1） ，Q = (x2,y2)
則矢量減法定義為： P - Q = ( x1 - x2 , y1 - y2 )
顯然有性質 P - Q = - ( Q - P )
如不加說明，下面所有的點都看作矢量，兩點的減法就是矢量相減；

2.矢量叉積

設矢量P = （x1,y1） ，Q = (x2,y2)
則矢量叉積定義為： P × Q = x1*y2 - x2*y1 得到的是一個標量
顯然有性質 P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q )
如不加說明，下面所有的點都看作矢量，點的乘法看作矢量叉積；

叉乘的重要性質：

> 若 P × Q > 0 , 則P 在Q的順時針方向
> 若 P × Q < 0 , 則P 在Q的逆時針方向
> 若 P × Q = 0 , 則P 與Q共線，但可能同向也可能反向

3.判斷點在線段上

設點為Q，線段為P1P2 ，判斷點Q在該線段上的依據是：

( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2為對角頂點的矩形內

4.判斷兩線段是否相交

我們分兩步確定兩條線段是否相交：

(1)． 快速排斥試驗

設以線段 P1P2 為對角線的矩形為R， 設以線段 Q1Q2 為對角線的矩形為T，如果
R和T不相交，顯然兩線段不會相交；

(2)． 跨立試驗

如果兩線段相交，則兩線段必然相互跨立對方，如圖1所示。在圖1中，P1P2跨立
Q1Q2 ，則矢量 ( P1 - Q1 ) 和( P2 - Q1 )位於矢量( Q2 - Q1 ) 的兩側，即
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改寫成
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
當( P1 - Q1 ) × ( Q2 - Q1 ) = 0 時，說明( P1 - Q1 ) 和 ( Q2 - Q1 )共線，
但是因為已經通過快速排斥試驗，所以 P1 一定在線段 Q1Q2上；同理，
( Q2 - Q1 ) ×( P2 - Q1 ) = 0 說明 P2 一定在線段 Q1Q2上。

所以判斷P1P2跨立Q1Q2的依據是：

( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0

同理判斷Q1Q2跨立P1P2的依據是：

( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0

至此已經完全解決判斷線段是否相交的問題。

5.判斷線段和直線是否相交

如果線段 P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：

( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0

6.判斷矩形是否包含點

只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下邊之間。

6.判斷線段、折線、多邊形是否在矩形中

因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了。

7.判斷矩形是否在矩形中

只要比較左右邊界和上下邊界就可以了。

8.判斷圓是否在矩形中

圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小於等於圓心到矩形四邊的距
離的最小值。

9.判斷點是否在多邊形中

以點P為端點，向左方作射線L，由於多邊形是有界的，所以射線L的左端一定在多
邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的
時候，進入到了多邊形的內部，遇到第二個交點的時候，離開了多邊形，……所
以很容易看出當L和多邊形的交點數目C是奇數的時候，P在多邊形內，是偶數的話
P在多邊形外。

但是有些特殊情況要加以考慮。如果L和多邊形的頂點相交，有些情況下交點只能
計算一個，有些情況下交點不應被計算（自己畫個圖就明白了）；如果L和多邊形
的一條邊重合，這條邊應該被忽略不計。為了統一起見，我們在計算射線L和多邊
形的交點的時候，1。對於多邊形的水平邊不作考慮；2。對於多邊形的頂點和L相
交的情況，如果該頂點是其所屬的邊上縱坐標較大的頂點，則計數，否則忽略；
3。對於P在多邊形邊上的情形，直接可判斷P屬於多邊行。由此得出演算法的偽代碼
如下：

1. count ← 0;
2. 以P為端點，作從右向左的射線L;
3. for 多邊形的每條邊s
4. do if P在邊s上
5. then return true;
6. if s不是水平的
7. then if s的一個端點在L上且該端點是s兩端點中縱坐標較大的端點
9. then count ← count+1
10. else if s和L相交
11. then count ← count+1;
12. if count mod 2 = 1
13. then return true
14. else return false;

其中做射線L的方法是：設P'的縱坐標和P相同，橫坐標為正無窮大（很大的一個正
數），則P和P'就確定了射線L。這個演算法的復雜度為O(n)。

10.判斷線段是否在多邊形內

線段在多邊形內的一個必要條件是線段的兩個端點都在多邊形內；

如果線段和多邊形的某條邊內交（兩線段內交是指兩線段相交且交點不在兩線段的
端點），因為多邊形的邊的左右兩側分屬多邊形內外不同部分，所以線段一定會有
一部分在多邊形外。於是我們得到線段在多邊形內的第二個必要條件：線段和多邊
形的所有邊都不內交；

線段和多邊形交於線段的兩端點並不會影響線段是否在多邊形內；但是如果多邊形
的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含與多邊形內部。
因此我們可以先求出所有和線段相交的多邊形的頂點，然後按照X-Y坐標排序，這樣
相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形內，
則該線段一定在多邊形內。證明如下：

命題1：

如果線段和多邊形的兩相鄰交點P1 ，P2的中點P' 也在多邊形內，則P1, P2之間的
所有點都在多邊形內。

證明：

假設P1,P2之間含有不在多邊形內的點，不妨設該點為Q，在P1, P'之間，因為多邊
形是閉合曲線，所以其內外部之間有界，而P1屬於多邊行內部，Q屬於多邊性外部，
P'屬於多邊性內部，P1-Q-P'完全連續，所以P1Q和QP'一定跨越多邊形的邊界，因此
在P1,P'之間至少還有兩個該線段和多邊形的交點，這和P1P2是相鄰兩交點矛盾，故
命題成立。證畢

由命題1直接可得出推論：

推論2：

設多邊形和線段PQ的交點依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點，線段
PQ在多邊形內的充要條件是：P，Q在多邊形內且對於i =1, 2,……, n-1，Pi ,Pi+1
的中點也在多邊形內。

在實際編程中，沒有必要計算所有的交點，首先應判斷線段和多邊形的邊是否內交
，倘若線段和多邊形的某條邊內交則線段一定在多邊形外；如果線段和多邊形的每
一條邊都不內交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只
要判斷點是否在線段上就可以了。

至此我們得出演算法如下：

1. if 線端PQ的端點不都在多邊形內
2. then return false;
3. 點集pointSet初始化為空;
4. for 多邊形的每條邊s
5. do if 線段的某個端點在s上
6. then 將該端點加入pointSet;
7. else if s的某個端點在線段PQ上
8. then 將該端點加入pointSet;
9. else if s和線段PQ相交 // 這時候可以肯定是內交
10. then return false;
11. 將pointSet中的點按照X-Y坐標排序，X坐標小的排在前面，
對於X坐標相同的點，Y坐標小的排在前面；
12. for pointSet中每兩個相鄰點 pointSet[i] , pointSet[ i+1]
13. do if pointSet[i] , pointSet[ i+1] 的中點不在多邊形中
14. then return false;
15. return true;

這個演算法的復雜度也是O(n)。其中的排序因為交點數目肯定遠小於多邊形的頂點數
目n，所以最多是常數級的復雜度，幾乎可以忽略不計。

11.判斷折線在多邊形內

只要判斷折線的每條線段是否都在多邊形內即可。設折線有m條線段，多邊形有n個
頂點，則復雜度為O(m*n)。

12.判斷多邊形是否在多邊形內

只要判斷多邊形的每條邊是否都在多邊形內即可。判斷一個有m個頂點的多邊形是
否在一個有n個頂點的多邊形內復雜度為O(m*n)。

13.判斷矩形是否在多邊形內

將矩形轉化為多邊形，然後再判斷是否在多邊形內。

14.判斷圓是否在多邊形內

只要計算圓心到多邊形的每條邊的最短距離，如果該距離大於等於圓半徑則該圓在
多邊形內。計算圓心到多邊形每條邊最短距離的演算法在後文闡述。

15.判斷點是否在圓內

計算圓心到該點的距離，如果小於等於半徑則該點在圓內。

16.判斷線段、折線、矩形、多邊形是否在圓內

因為圓是凸集，所以只要判斷是否每個頂點都在圓內即可。

17.判斷圓是否在圓內

設兩圓為O1,O2，半徑分別為r1, r2，要判斷O2是否在O1內。先比較r1，r2的大小
，如果r1<r2則O2不可能在O1內；否則如果兩圓心的距離大於r1 - r2 ，則O2不在
O1內；否則O2在O1內。

18.計算點到線段的最近點

如果該線段平行於X軸（Y軸），則過點point作該線段所在直線的垂線，垂足很容
易求得，然後計算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端
點；

如果該線段不平行於X軸也不平行於Y軸，則斜率存在且不為0。設線段的兩端點為
pt1和pt2，斜率為：
k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );
該直線方程為：
y = k* ( x - pt1.x) + pt1.y
其垂線的斜率為 - 1 / k，
垂線方程為：
y = (-1/k) * (x - point.x) + point.y
聯立兩直線方程解得：
x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x - pt1.x) + pt1.y;

然後再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計算兩端點
到垂足的距離，選擇距離垂足較近的端點返回。

19.計算點到折線、矩形、多邊形的最近點

只要分別計算點到每條線段的最近點，記錄最近距離，取其中最近距離最小的點即
可。

20.計算點到圓的最近距離

如果該點在圓心，則返回UNDEFINED
連接點P和圓心O，如果PO平行於X軸，則根據P在O的左邊還是右邊計算出最近點的
橫坐標為centerPoint.x - radius 或 centerPoint.x + radius， 如圖4 (a)所示；
如果PO平行於Y軸，則根據P在O的上邊還是下邊計算出最近點的縱坐標為
centerPoint.y + radius 或 centerPoint.y - radius， 如圖4 (b)所示。

如果PO不平行於X軸和Y軸，則PO的斜率存在且不為0，如圖4(c)所示。這時直線PO
斜率為
k = （ P.y - O.y ）/ ( P.x - O.x )
直線PO的方程為：
y = k * ( x - P.x) + P.y
設圓方程為:
(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，
聯立兩方程組可以解出直線PO和圓的交點，取其中離P點較近的交點即可。

21.計算兩條共線的線段的交點

對於兩條共線的線段，它們之間的位置關系有圖5所示的幾種情況。
圖5(a)中兩條線段沒有交點；圖5 (b) 和 (d) 中兩條線段有無窮焦點；圖5 (c)
中兩條線段有一個交點。設line1是兩條線段中較長的一條，line2是較短的一條，
如果line1包含了line2的兩個端點，則是圖5(d)的情況，兩線段有無窮交點；如
果line1隻包含line2的一個端點，那麼如果line1的某個端點等於被line1包含的
line2的那個端點，則是圖5(c)的情況，這時兩線段只有一個交點，否則就是
圖5(c)的情況，兩線段也是有無窮的交點；如果line1不包含line2的任何端點，
則是圖5(a)的情況，這時兩線段沒有交點。

22.計算線段或直線與線段的交點

設一條線段為L0 = P1P2，另一條線段或直線為L1 = Q1Q2 ，要計算的就是L0和L1
的交點。

1.首先判斷L0和L1是否相交（方法已在前文討論過），如果不相交則沒有交點，
否則說明L0和L1一定有交點，下面就將L0和L1都看作直線來考慮。

2.如果P1和P2橫坐標相同，即L0平行於Y軸
a)若L1也平行於Y軸，
i.若P1的縱坐標和Q1的縱坐標相同，說明L0和L1共線，假如L1是直線的話他們有
無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的演算法求他們
的交點（該方法在前文已討論過）；
ii.否則說明L0和L1平行，他們沒有交點；
b)若L1不平行於Y軸，則交點橫坐標為P1的橫坐標，代入到L1的直線方程中可以計
算出交點縱坐標；
3.如果P1和P2橫坐標不同，但是Q1和Q2橫坐標相同，即L1平行於Y軸，則交點橫
坐標為Q1的橫坐標，代入到L0的直線方程中可以計算出交點縱坐標；
4.如果P1和P2縱坐標相同，即L0平行於X軸
a)若L1也平行於X軸，
i.若P1的橫坐標和Q1的橫坐標相同，說明L0和L1共線，假如L1是直線的話他們
有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的演算法求
他們的交點（該方法在前文已討論過）；
ii.否則說明L0和L1平行，他們沒有交點；

b)若L1不平行於X軸，則交點縱坐標為P1的縱坐標，代入到L1的直線方程中可以計
算出交點橫坐標；
5.如果P1和P2縱坐標不同，但是Q1和Q2縱坐標相同，即L1平行於X軸，則交點縱坐標
為Q1的縱坐標，代入到L0的直線方程中可以計算出交點橫坐標；
6.剩下的情況就是L1和L0的斜率均存在且不為0的情況
a)計算出L0的斜率K0，L1的斜率K1 ；
b)如果K1 = K2
i.如果Q1在L0上，則說明L0和L1共線，假如L1是直線的話有無窮交點，假如L1
是線段的話可用"計算兩條共線線段的交點"的演算法求他們的交點（該方法在
前文已討論過）；
ii.如果Q1不在L0上，則說明L0和L1平行，他們沒有交點。
c)聯立兩直線的方程組可以解出交點來

說明：這個演算法並不復雜，但是要分情況討論清楚，尤其是當兩條線段共線的情況
需要單獨考慮，所以在前文將求兩條共線線段的演算法單獨寫出來。另外，一開始就
先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結果是相交，那麼在後
面就可以將線段全部看作直線來考慮。

23.求線段或直線與折線、矩形、多邊形的交點

分別求與每條邊的交點即可。

24.求線段或直線與圓的交點

設圓心為O，圓半徑為r，直線（或線段）L上的兩點為P1,P2。
1.如果L是線段且P1，P2都包含在圓O內，則沒有交點；否則進行下一步
2.如果L平行於Y軸，
a)計算圓心到L的距離dis
b)如果dis > r 則L和圓沒有交點；
c)利用勾股定理，可以求出兩交點坐標，如圖6(a)所示；但要注意考慮L和圓的相
切情況
3.如果L平行於X軸，做法與L平行於Y軸的情況類似；
4.如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然後列出L的點斜式方程
，和圓方程聯立即可求解出L和圓的兩個交點；
5.如果L是線段，對於2，3，4中求出的交點還要分別判斷是否屬於該線段的范圍內。

② 演算法的方法

程序調用自身的編程技巧稱為遞歸（recursion）。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。 貪心演算法是一種對某些求最優解問題的更簡單、更迅速的設計技術。
用貪心法設計演算法的特點是一步一步地進行，常以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它採用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題, 通過每一步貪心選擇,可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪婪法不要回溯。
貪婪演算法是一種改進了的分級處理方法，其核心是根據題意選取一種量度標准，然後將這多個輸入排成這種量度標准所要求的順序，按這種順序一次輸入一個量，如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能產生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪演算法。
對於一個給定的問題，往往可能有好幾種量度標准。初看起來，這些量度標准似乎都是可取的，但實際上，用其中的大多數量度標准作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。因此，選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心。
一般情況下，要選出最優量度標准並不是一件容易的事，但對某問題能選擇出最優量度標准後，用貪婪演算法求解則特別有效。 分治法是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。
分治法所能解決的問題一般具有以下幾個特徵：
(1) 該問題的規模縮小到一定的程度就可以容易地解決；
(2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
(3) 利用該問題分解出的子問題的解可以合並為該問題的解；
(4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。 動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。
動態規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊演算法。不象前面所述的那些搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對一種最優化問題，由於各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃演算法，可以解決各類最優化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想像力去建立模型，用創造性的技巧去求解。 分枝界限法是一個用途十分廣泛的演算法，運用這種演算法的技巧性很強，不同類型的問題解法也各不相同。
分支定界法的基本思想是對有約束條件的最優化問題的所有可行解（數目有限）空間進行搜索。該演算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），並為每個子集內的解的值計算一個下界或上界（稱為定界）。在每次分支後，對凡是界限超出已知可行解值那些子集不再做進一步分支，這樣，解的許多子集（即搜索樹上的許多結點）就可以不予考慮了，從而縮小了搜索范圍。這一過程一直進行到找出可行解為止，該可行解的值不大於任何子集的界限。因此這種演算法一般可以求得最優解。
與貪心演算法一樣，這種方法也是用來為組合優化問題設計求解演算法的，所不同的是它在問題的整個可能解空間搜索，所設計出來的演算法雖其時間復雜度比貪婪演算法高，但它的優點是與窮舉法類似，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優解的子空間進一步搜索（類似於人工智慧中的剪枝），故它比窮舉法效率更高。 回溯法（探索與回溯法）是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
其基本思想是，在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索演算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。

③ 排序演算法有多少種

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在演算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸並排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
插入排序
插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
冒泡排序
冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演算法，它不改變序列中相同元素之間的相對位置關系。
選擇排序
選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重復進行「最小元素」的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素「5」會和元素「3」交換，那麼原序列中的兩個相同元素「5」之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演算法，它在計算過程中會破壞穩定性。
快速排序
快速排序的基本思想是:通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
歸並排序
歸並排序演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸並排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合並得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重復操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

④ VB共有哪些演算法（所有）

所謂演算法，就是你解決一個問題所運算的方法，VB（或者其它程序語言）只提供基本語句，例如加減乘除、平方根、反切、冪、正餘弦等等，演算法是靠你自己去編寫的，所以說演算法是無窮無盡的！

⑤ 簡述演算法的各種表示形式

一、什麼是演算法

演算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。演算法常常含有重復的步驟和一些比較或邏輯判斷。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。時間復雜度用「O（數量級）」來表示，稱為「階」。常見的時間復雜度有： O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。

演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。

二、演算法設計的方法

1.遞推法

遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。設要求問題規模為N的解，當N=1時，解或為已知，或能非常方便地得到解。能採用遞推法構造演算法的問題有重要的遞推性質，即當得到問題規模為i-1的解後，由問題的遞推性質，能從已求得的規模為1，2，…，i-1的一系列解，構造出問題規模為I的解。這樣，程序可從i=0或i=1出發，重復地，由已知至i-1規模的解，通過遞推，獲得規模為i的解，直至得到規模為N的解。

【問題】 階乘計算

問題描述：編寫程序，對給定的n（n≤100），計算並輸出k的階乘k！（k=1，2，…，n）的全部有效數字。

由於要求的整數可能大大超出一般整數的位數，程序用一維數組存儲長整數，存儲長整數數組的每個元素只存儲長整數的一位數字。如有m位成整數N用數組a[ ]存儲：

N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100

並用a[0]存儲長整數N的位數m，即a[0]=m。按上述約定，數組的每個元素存儲k的階乘k！的一位數字，並從低位到高位依次存於數組的第二個元素、第三個元素……。例如，5！=120，在數組中的存儲形式為：

3 0 2 1 ……

首元素3表示長整數是一個3位數，接著是低位到高位依次是0、2、1，表示成整數120。

計算階乘k！可採用對已求得的階乘(k-1)！連續累加k-1次後求得。例如，已知4！=24，計算5！，可對原來的24累加4次24後得到120。細節見以下程序。

# include <stdio.h>

# include <malloc.h>

# define MAXN 1000

void pnext(int a[ ],int k)

{ int *b,m=a[0],i,j,r,carry;

b=(int * ) malloc(sizeof(int)* (m+1));

for ( i=1;i<=m;i++) b[i]=a[i];

for ( j=1;j<=k;j++)

{ for ( carry=0,i=1;i<=m;i++)

{ r=(i<a[0]?a[i]+b[i]:a[i])+carry;

a[i]=r%10;

carry=r/10;

}

if (carry) a[++m]=carry;

}

free(b);

a[0]=m;

}

void write(int *a,int k)

{ int i;

printf(「%4d！=」,k);

for (i=a[0];i>0;i--)

printf(「%d」,a[i]);

printf(「\n\n」);

}

void main()

{ int a[MAXN],n,k;

printf(「Enter the number n: 「);

scanf(「%d」,&n);

a[0]=1;

a[1]=1;

write(a,1);

for (k=2;k<=n;k++)

{ pnext(a,k);

write(a,k);

getchar();

}

}

2.遞歸

遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。

能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。

【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。

斐波那契數列為：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) （當n>1時）。

寫成遞歸函數有：

int fib(int n)

{ if (n==0) return 0;

if (n==1) return 1;

if (n>1) return fib(n-1)+fib(n-2);

}

遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。

在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。

在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。

由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。

【問題】 組合問題

問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為： （1）5、4、3 （2）5、4、2 （3）5、4、1

（4）5、3、2 （5）5、3、1 （6）5、2、1

（7）4、3、2 （8）4、3、1 （9）4、2、1

（10）3、2、1

分析所列的10個組合，可以採用這樣的遞歸思想來考慮求組合函數的演算法。設函數為void comb(int m,int k)為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其後的數字是從餘下的m-1個數中取k-1數的組合。這就將求m個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出後，才將a[ ]中的一個組合輸出。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組後，有兩種可能的選擇，因還未去頂組合的其餘元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數comb。

【程序】

# include <stdio.h>

# define MAXN 100

int a[MAXN];

void comb(int m,int k)

{ int i,j;

for (i=m;i>=k;i--)

{ a[k]=i;

if (k>1)

comb(i-1,k-1);

else

{ for (j=a[0];j>0;j--)

printf(「%4d」,a[j]);

printf(「\n」);

}

}

}

void main()

{ a[0]=3;

comb(5,3);

}

3.回溯法

回溯法也稱為試探法，該方法首先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

【問題】 組合問題

問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。

採用回溯法找問題的解，將找到的組合以從小到大順序存於a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：

（1） a[i+1]>a[i]，後一個數字比前一個大；

（2） a[i]-i<=n-r+1。

按回溯法的思想，找解過程可以敘述如下：

首先放棄組合數個數為r的條件，候選組合從只有一個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，並使其滿足上述條件（1），候選組合改為1，2。繼續這一過程，得到候選組合1，2，3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4，以及以後調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由於對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，並向前試探，得到解1，3，4。重復上述向前試探和向後回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程序如下：

【程序】

# define MAXN 100

int a[MAXN];

void comb(int m,int r)

{ int i,j;

i=0;

a[i]=1;

do {

if (a[i]-i<=m-r+1

{ if (i==r-1)

{ for (j=0;j<r;j++)

printf(「%4d」,a[j]);

printf(「\n」);

}

a[i]++;

continue;

}

else

{ if (i==0)

return;

a[--i]++;

}

} while (1)

}

main()

{ comb(5,3);

}

4.貪婪法

貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

例如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪演算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。

【問題】 裝箱問題

問題描述：裝箱問題可簡述如下：設有編號為0、1、…、n-1的n種物品，體積分別為v0、v1、…、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過V，即對於0≤i＜n，有0＜vi≤V。不同的裝箱方案所需要的箱子數目可能不同。裝箱問題要求使裝盡這n種物品的箱子數要少。

若考察將n種物品的集合分劃成n個或小於n個物品的所有子集，最優解就可以找到。但所有可能劃分的總數太大。對適當大的n，找出所有可能的劃分要花費的時間是無法承受的。為此，對裝箱問題採用非常簡單的近似演算法，即貪婪法。該演算法依次將物品放到它第一個能放進去的箱子中，該演算法雖不能保證找到最優解，但還是能找到非常好的解。不失一般性，設n件物品的體積是按從大到小排好序的，即有v0≥v1≥…≥vn-1。如不滿足上述要求，只要先對這n件物品按它們的體積從大到小排序，然後按排序結果對物品重新編號即可。裝箱演算法簡單描述如下：

{ 輸入箱子的容積；

輸入物品種數n；

按體積從大到小順序，輸入各物品的體積；

預置已用箱子鏈為空；

預置已用箱子計數器box_count為0；

for (i=0;i<n;i++)

{ 從已用的第一隻箱子開始順序尋找能放入物品i 的箱子j；

if （已用箱子都不能再放物品i）

{ 另用一個箱子，並將物品i放入該箱子；

box_count++；

}

else

將物品i放入箱子j；

}

}

上述演算法能求出需要的箱子數box_count，並能求出各箱子所裝物品。下面的例子說明該演算法不一定能找到最優解，設有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個單位體積。按上述演算法計算，需三隻箱子，各箱子所裝物品分別為：第一隻箱子裝物品1、3；第二隻箱子裝物品2、4、5；第三隻箱子裝物品6。而最優解為兩只箱子，分別裝物品1、4、5和2、3、6。

若每隻箱子所裝物品用鏈表來表示，鏈表首結點指針存於一個結構中，結構記錄尚剩餘的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構成鏈表。以下是按以上演算法編寫的程序。

【程序】

# include <stdio.h>

# include <stdlib.h>

typedef struct ele

{ int vno;

struct ele *link;

} ELE;

typedef struct hnode

{ int remainder;

ELE *head;

Struct hnode *next;

} HNODE;

void main()

{ int n, i, box_count, box_volume, *a;

HNODE *box_h, *box_t, *j;

ELE *p, *q;

Printf(「輸入箱子容積\n」);

Scanf(「%d」,&box_volume);

Printf(「輸入物品種數\n」);

Scanf(「%d」,&n);

A=(int *)malloc(sizeof(int)*n);

Printf(「請按體積從大到小順序輸入各物品的體積：」);

For (i=0;i<n;i++) scanf(「%d」,a+i);

Box_h=box_t=NULL;

Box_count=0;

For (i=0;i<n;i++)

{ p=(ELE *)malloc(sizeof(ELE));

p->vno=i;

for (j=box_h;j!=NULL;j=j->next)

if (j->remainder>=a[i]) break;

if (j==NULL)

{ j=(HNODE *)malloc(sizeof(HNODE));

j->remainder=box_volume-a[i];

j->head=NULL;

if (box_h==NULL) box_h=box_t=j;

else box_t=boix_t->next=j;

j->next=NULL;

box_count++;

}

else j->remainder-=a[i];

for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);

if (q==NULL)

{ p->link=j->head;

j->head=p;

}

else

{ p->link=NULL;

q->link=p;

}

}

printf(「共使用了%d只箱子」，box_count);

printf(「各箱子裝物品情況如下：」);

for (j=box_h,i=1;j!=NULL;j=j->next,i++)

{ printf(「第%2d只箱子，還剩餘容積%4d，所裝物品有；\n」,I,j->remainder);

for (p=j->head;p!=NULL;p=p->link)

printf(「%4d」,p->vno+1);

printf(「\n」);

}

}

5.分治法

任何一個可以用計算機求解的問題所需的計算時間都與其規模N有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

如果原問題可分割成k個子問題（1<k≤n），且這些子問題都可解，並可利用這些子問題的解求出原問題的解，那麼這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在演算法設計之中，並由此產生許多高效演算法。

分治法所能解決的問題一般具有以下幾個特徵：

（1）該問題的規模縮小到一定的程度就可以容易地解決；

（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；

（3）利用該問題分解出的子問題的解可以合並為該問題的解；

（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

上述的第一條特徵是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特徵是應用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；第三條特徵是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮貪心法或動態規劃法。第四條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。

分治法在每一層遞歸上都有三個步驟：

（1）分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；

（2）解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；

（3）合並：將各個子問題的解合並為原問題的解。

6.動態規劃法

經常會遇到復雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地採用把大問題分解成子問題，並綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規模呈冪級數增加。

為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存於該數組中，這就是動態規劃法所採用的基本方法。以下先用實例說明動態規劃方法的使用。

【問題】 求兩字元序列的最長公共字元子序列

問題描述：字元序列的子序列是指從給定字元序列中隨意地（不一定連續）去掉若干個字元（可能一個也不去掉）後所形成的字元序列。令給定的字元序列X=「x0，x1，…，xm-1」，序列Y=「y0，y1，…，yk-1」是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=「ABCBDAB」，Y=「BCDB」是X的一個子序列。

考慮最長公共子序列問題如何分解成子問題，設A=「a0，a1，…，am-1」，B=「b0，b1，…，bm-1」，並Z=「z0，z1，…，zk-1」為它們的最長公共子序列。不難證明有以下性質：

（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且「z0，z1，…，zk-2」是「a0，a1，…，am-2」和「b0，b1，…，bn-2」的一個最長公共子序列；

（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列；

（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列。

這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找「a0，a1，…，am-2」和「b0，b1，…，bm-2」的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列和找出「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。

代碼如下：

# include <stdio.h>

# include <string.h>

# define N 100

char a[N],b[N],str[N];

int lcs_len(char *a, char *b, int c[ ][ N])

{ int m=strlen(a), n=strlen(b), i,j;

for (i=0;i<=m;i++) c[i][0]=0;

for (i=0;i<=n;i++) c[0][i]=0;

for (i=1;i<=m;i++)

for (j=1;j<=m;j++)

if (a[i-1]==b[j-1])

c[i][j]=c[i-1][j-1]+1;

else if (c[i-1][j]>=c[i][j-1])

c[i][j]=c[i-1][j];

else

c[i][j]=c[i][j-1];

return c[m][n];

}

char *buile_lcs(char s[ ],char *a, char *b)

{ int k, i=strlen(a), j=strlen(b);

k=lcs_len(a,b,c);

s[k]=』\0』;

while (k>0)

if (c[i][j]==c[i-1][j]) i--;

else if (c[i][j]==c[i][j-1]) j--;

else { s[--k]=a[i-1];

i--; j--;

}

return s;

}

void main()

{ printf (「Enter two string（<%d）!\n」,N);

scanf(「%s%s」,a,b);

printf(「LCS=%s\n」,build_lcs(str,a,b));

}

7.迭代法

迭代法是用於求方程或方程組近似根的一種常用的演算法設計方法。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x)，然後按以下步驟執行：

（1） 選一個方程的近似根，賦給變數x0；

（2） 將x0的值保存於變數x1，然後計算g(x1)，並將結果存於變數x0；

（3） 當x0與x1的差的絕對值還小於指定的精度要求時，重復步驟（2）的計算。

若方程有根，並且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述演算法用C程序的形式表示為：

程序如下：

【演算法】迭代法求方程組的根

{ for (i=0;i<n;i++)

x[i]=初始近似根;

do {

for (i=0;i<n;i++)

y[i] = x[i];

for (i=0;i<n;i++)

x[i] = gi(X);

for (delta=0.0,i=0;i<n;i++)

if (fabs(y[i]-x[i])>delta) delta=fabs(y[i]-x[i])； } while (delta>Epsilon)；

for (i=0;i<n;i++)

printf(「變數x[%d]的近似根是 %f」，I，x[i])；

printf(「\n」)；

} 具體使用迭代法求根時應注意以下兩種可能發生的情況：

（1）如果方程無解，演算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代演算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制；

（2）方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。

8.窮舉搜索法

窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。

【問題】 將A、B、C、D、E、F這六個變數排成如圖所示的三角形，這六個變數分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變數之和相等的全部解。如圖就是一個解。

程序引入變數a、b、c、d、e、f，並讓它們分別順序取1至6的整數，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變數之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變數取盡所有的組合後，程序就可得到全部可能的解。程序如下：

# include <stdio.h>

void main()

{ int a,b,c,d,e,f;

for (a=1;a<=6;a++) {

for (b=1;b<=6;b++) {

if (b==a) continue;

for (c=1;c<=6;c++) {

if (c==a)||(c==b) continue;

for (d=1;d<=6;d++) {

if (d==a)||(d==b)||(d==c) continue;

for (e=1;e<=6;e++) {

if (e==a)||(e==b)||(e==c)||(e==d) continue;

f = 21-(a+b+c+d+e);

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {

printf(「%6d,a);

printf(「%4d%4d」,b,f);

printf(「%2d%4d%4d」,c,d,e);

scanf(「%*c」);

}

}

}

}

}

}}

按窮舉法編寫的程序通常不能適應變化的情況。如問題改成有9個變數排成三角形，每條邊有4個變數的情況，程序的循環重數就要相應改變。

⑥ 所有的數學演算法，全部告訴我啊

是離散問題么？
最近做了許多離散演算法
基於節約演算法的企業配送路線優化.sql
基於掃描演算法的企業配送路線優化.sql
基於最近插入法的企業配送路線優化.sql
里程節約演算法：節約演算法的核心思想是將運輸問題中存在的兩個迴路（0，… ，i，0）和（0，j，… ，0）合並成一個迴路（0，… ，i，j，…，0）。在上面的合並操作中，整個運輸問題的總運輸距離會發生變化，如果變化後總運輸距離下降，則稱節約了運輸距離。相應的變化值，叫做節約距離 ，如下面公式所示。
區域掃描演算法：掃描演算法是一種「先分組後路線」的演算法。所謂分組，即指派給每輛車一組點。一種簡單的分組方法是將以配送中心為原點的坐標平面劃分為多個扇形區域，並初步將每個扇形區域的點分派給一輛車，然後擴充路線。如果在進行了一次「分組-路線」的路線構造後，還存在未分配點，則再進行「分組-路線」程序。如此反復，直到所有的點均已分配為止。
間距最近插入演算法：最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用於解決TSP(旅行商)問題的演算法。最近插入法由四步完成：
（1）找到 最小的節點 ，形成一個子迴路（subtour）， 。
（2）在剩下的節點中，尋找一個離子迴路中某一節點最近的節點 。
（3)在子迴路中找到一條弧（i，j）,使得 + - 最小，然後將節點 插入到節點 ， 之間，用兩條新的弧(i，k)，（k，j）代替原來的弧（i，j），並將節點 加入到子迴路中。
（4）重復步驟（2）、（3），直到所有的節點都加入到子迴路中。
這樣，子迴路就演變為了一個TSP的解。
由於最近插入法解決的是單迴路運輸問題，故在此方法基礎上進行改進和修正，加上里程限制和負載限制，能使其解決多迴路運輸VRP問題。

⑦ 求全部演算法

電路上電流為2A，兩電阻兩端的電壓均為10V，因此右側電壓為0V，兩電阻中間電壓為10V。

⑧ 求編程領域上一些經典演算法同時也是程序員必須掌握的演算法

這是我在一個論壇里看到的，你也參考參考吧。C++的虛函數
======================
C++使用虛函數實現了其對象的多態，C++對象的開始四個位元組是指向虛函數表的指針，其初始化順序是先基類後派生類，所以該虛函數表永遠指向最後一個派生類，從而實現了相同函數在不同對象中的不同行為，使得對象既有共性，又有其個性。

內存池分配、回收之夥伴演算法
=======================
夥伴演算法是空閑鏈表法的一個增強演算法，依次建立2^0\2^1\2^2\2^3...2^n大小的 內存塊空閑鏈表，利用相鄰內存塊的夥伴性質，很容易將互為夥伴的內存塊進行合並移到相應的空閑鏈表或將一塊內存拆分成兩塊夥伴內存，一塊分配出去，另一塊掛入相應空閑鏈表，使得內存的分配和回收變得高效。

AVL樹
=======================
AVL樹是一個平衡二叉樹，其中序遍歷是從小到大排序的，該結構插入節點和檢索非常高效，被廣泛應用

快速排序
=======================
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。效率非常高

密碼學之非對稱加密協議（公鑰、私鑰加密協議）
======================
非對稱加密演算法需要兩個密鑰，用其中一個加密產生的密文，只能通過另外一個密鑰解密，密鑰持有者A可以將其中一個公開，稱為公用密鑰，另外一個秘密保存稱為私鑰，這樣當某人B想給A傳一封秘信時，只要將密信使用A的公鑰加密後，就可以放心使用各種信道將迷信傳給A了，因為該密信只有A可以解密，第三者截取因為無法解密而毫無意義。
該演算法很好地解決了密鑰的安全傳遞的問題，因為公鑰和加密演算法都是公開的，私鑰不需要傳輸。

密碼學之數字簽名協議（身份鑒別、防抵賴）
======================
數字簽名也是建立在非對稱加密基礎之上的，如果A君用它的私鑰將文件加密後在發布，A君就無法抵賴該文件是其發布的，因為其他人能通過A君的公鑰將文件解密就說明，如果演算法可靠，該文件一定是A君用其私鑰加密的。
由於非對稱加密演算法的加密和解密很慢，現在的數字簽名並非是將其要發布的信息用其私鑰加密，而是先用一個單項散列演算法如（MD5）產生一個該信息的比較短的指紋（hash值），對其指紋用其私鑰加密後和信息一並發布，同樣達到了防抵賴的作用。

無回溯字元串模式匹配-kmp演算法
======================
他是根據子串的特徵，當匹配失敗時，不需要回溯，而是直接將字串向後滑動若干個位元組，繼續匹配，極大提高了匹配速度。該演算法被廣泛使用。詳細請參考數據結構教程。

最小路徑選路-迪傑斯特拉演算法、弗洛伊德演算法
======================
學習數據結構的時候，印象最深的就要算kmp演算法和最小路徑演算法了，因為理解他們比較費腦子，我是不可能發明這些演算法了，發明他們的都是天才，呵呵。
使用最短路徑的演算法曾經幫人寫過一個小東西，還是很有效的，記得是使用的弗洛伊德演算法的一個變種，要詳細了解的朋友可以查找相關資料，想將他們使用在你的項目中，代碼直接從教科書上抄就可以了，不需要理解。

tcp協議之-nagle演算法
======================
tcp、ip中令人叫絕的想法很多，印象最深的要算nagle演算法了。
tcp出於效率和流量控制的考慮，發送端的數據不是產生多少就馬上發送多少，一般是等到數據集聚到發送緩沖區長度的一半或者數據達到最大tcp數據包數據部分長度（好像是65515）才啟動發送，而且還要看接受端可用緩沖區的大小，如果接受端產生一個回應報文通知發送端沒有接受空間了，發送端哪怕緩沖區已經滿了，也不會啟動發送，直到接受端通告發送端其已經有了接受數據的空間了。
這樣就有一個問題，假如發送端就是要發送一個小報文（比如10個位元組），然後等待對方的回應。按照上面的方案，tcp會一直等數據收集到一定量才發送，於是矛盾就產生了。應用層不再發數據，tcp等不到足夠的數據不會將10個字的數據發送到網卡，接收端應用層收不到數據就不會回應發送端。
你也可能說，可以讓修改發送端發送條件，不一定要等到足夠的數據再發送，為了效率考慮，可以考慮延時一定的時間，比如說1秒，如果上層還沒有數據到來，就將發送緩沖中的數據發出去。當然這樣也是可行的，盡管應用端白白等了1秒鍾啥也沒干，呵呵。
其實nagle演算法很好解決了該問題，它的做發是鏈接建立後的第一次發送不用等待，直接將數據組裝成tcp報文發送出去，以後要麼等到數據量足夠多、要麼是等到接受方的確認報文，演算法及其簡單，而且很好解決了上面的矛盾。

socket之io模型設計
======================
windows下socket有兩種工作方式：
1）同步方式
2）非同步方式

同步socket又有兩種工作模式：
1）阻塞模式
2）非阻塞模式

阻塞模式是最簡單的工作模式，以tcp的發送數據為例，如果發送緩沖區沒有空間，send調用就不會返回，一直要等到能夠發出一點數據為止，哪怕是一個位元組，但是send返回並不表示我要發送的數據已經全部提交給了tcp，所以send返回時要檢查這次發送的數量，調整發送緩沖指針，繼續發送，直到所有數據都提交給了系統。
由於其阻塞的特性，會阻塞發送線程，所以單線程的程序是不適合使用阻塞模式通信的，一般使用一個連接一個線程的方法，但是這種方式對於要維護多個連接的程序，是個不好的選擇，線程越多，開銷越大。

同步非阻塞模式的socket不會阻塞通信線程，如果發送緩沖區滿，send調用也是立刻返回，接受緩沖區空，recv也不會阻塞，所以通信線程要反復調用send或recv嘗試發送或接收數據，對cpu是很大的浪費。
針對非阻塞的尷尬，介面開發人員發明了三種io模型來解決該問題：
1）選擇模型（select）
2）非同步選擇模型（AsyncSelect）
3）事件選擇模型（EventSeselect）
其思想是根據io類型，預先查看1個或n個socket是否能讀、寫等。
其select本身來說，select是阻塞的，可以同時監視多個socket，只要所監視的其中一個socket可以讀、寫，secect調用才返回
非同步選擇模型其select是非同步的（非同步是不會阻塞的），是將監視任務委託給系統，系統在socket可讀、寫時通過消息通知應用程序。有一點需要說明，假如應用程序已經有很多數據需要發送，當收到可寫通知時，一定要盡量多地發送數據，直到發送失敗，lasterror提示「將要阻塞」，將來才可能有新的可寫通知到來，否則永遠也不會有。
事件選擇模型也是將監視socket狀態的工作委託給系統，系統在適當的時候通過事件通知應用程序socket可以的操作。

除了同步工作方式外，還有一種叫非同步工作方式
非同步工作方式是不會阻塞的，因為是將io操作本身委託給系統，系統在io操作完成後通過回調常式或事件或完成包通知應用程序
非同步工作方式有兩種io模型和其對應，其實這兩種模型是window是非同步io的實現：
1）重疊模型
2）完成埠

重疊模型通過事件或回調常式通知應用程序io已經完成
完成埠模型比較復雜，完成埠本身其實是一個io完成包隊列。
應用程序一般創建若干個線程用來監視完成埠，這些線程試圖從完成埠移除一個完成包，如果有，移除成功，應用程序處理該完成包，否則應用程序監視完成埠的線程被阻塞。

select模型是從UNIX上的Berkeley Software Distribution(BSD)版本的套接字就實現了的，其它四種io模型windows發明的，在windows中完成埠和非同步選擇模型是使用比較廣泛的，一般分別用於服務端和客戶端開發。
這五種io模型設計還是比較巧妙的：三種選擇模型很好解決了「同步非阻塞」模式編程的不足；重疊模型和完成埠是windows非同步io的經典實現，不局限於網路io，對文件io同樣適用。

說點題外話，socket的send完成僅僅是將數據（可能是部分）提交給系統，而不是已經發送到了網卡上，更不是已經發送到了接收端。所以要知道你的數據已經發送到了對方的應用層的唯一方法是，讓對方給你發送一個應對包。
發送數據要注意，對應tcp，要防止發送和接收的亂序，對於發送，一般應該為每一個鏈接建立一個發送隊列，採用類似nagle的演算法啟動數據發送。
一次發送可能是你提交數據的一部分，一定要當心，否則出問題沒處找去。

⑨ 99乘91的簡便演算法(全部)

99×91
十位相同，個位和為10
速演算法：十位數乘比它大小的數積為前兩位，個位的積為後兩位，不足兩位，十位補0。
9×10=90
9×1=9
99×91=9009

⑩ 幾種常用的演算法簡介

1、窮舉法窮舉法是最基本的演算法設計策略，其思想是列舉出問題所有的可能解，逐一進行判別，找出滿足條件的解。
窮舉法的運用關鍵在於解決兩個問題：
在運用窮舉法時，容易出現的問題是可能解過多，導致演算法效率很低，這就需要對列舉可能解的方法進行優化。
以題1041--純素數問題為例，從1000到9999都可以看作是可能解，可以通過對所有這些可能解逐一進行判別，找出其中的純素數，但只要稍作分析，就會發現其實可以大幅度地降低可能解的范圍。根據題意易知，個位只可能是3、5、7，再根據題意可知，可以在3、5、7的基礎上，先找出所有的二位純素數，再在二位純素數基礎上找出三位純素數，最後在三位純素數的基礎上找出所有的四位純素數。
2、分治法分治法也是應用非常廣泛的一種演算法設計策略，其思想是將問題分解為若乾子問題，從而可以遞歸地求解各子問題，再綜合出問題的解。
分治法的運用關鍵在於解決三個問題：
我們熟知的如漢諾塔問題、折半查找演算法、快速排序演算法等都是分治法運用的典型案例。
以題1045--Square
Coins為例，先對題意進行分析，可設一個函數f(m,
n)等於用面值不超過n2的貨幣構成總值為m的方案數，則容易推導出：
f(m,
n)
=
f(m-0*n*n,
n-1)+f(m-1*n*n,
n-1)+f(m-2*n*n,
n-1)+...+f(m-k*n*n,
n-1)
這里的k是幣值為n2的貨幣最多可以用多少枚，即k=m/(n*n)。
也很容易分析出，f(m,
1)
=
f(1,
n)
=
1
對於這樣的題目，一旦分析出了遞推公式，程序就非常好寫了。所以在動手開始寫程序之前，分析工作做得越徹底，邏輯描述越准確、簡潔，寫起程序來就會越容易。
3、動態規劃法
動態規劃法多用來計算最優問題，動態規劃法與分治法的基本思想是一致的，但處理的手法不同。動態規劃法在運用時，要先對問題的分治規律進行分析，找出終結子問題，以及子問題向父問題歸納的規則，而演算法則直接從終結子問題開始求解，逐層向上歸納，直到歸納出原問題的解。
動態規劃法多用於在分治過程中，子問題可能重復出現的情況，在這種情況下，如果按照常規的分治法，自上向下分治求解，則重復出現的子問題就會被重復地求解，從而增大了冗餘計算量，降低了求解效率。而採用動態規劃法，自底向上求解，每個子問題只計算一次，就可以避免這種重復的求解了。
動態規劃法還有另外一種實現形式，即備忘錄法。備忘錄的基本思想是設立一個稱為備忘錄的容器，記錄已經求得解的子問題及其解。仍然採用與分治法相同的自上向下分治求解的策略，只是對每一個分解出的子問題，先在備忘錄中查找該子問題，如果備忘錄中已經存在該子問題，則不須再求解，可以從備忘錄中直接得到解，否則，對子問題遞歸求解，且每求得一個子問題的解，都將子問題及解存入備忘錄中。
例如，在題1045--Square
Coins中，可以採用分治法求解，也可以採用動態規劃法求解，即從f(m,
1)和f(1,
n)出發，逐層向上計算，直到求得f(m,
n)。
在競賽中，動態規劃和備忘錄的思想還可以有另一種用法。有些題目中的可能問題數是有限的，而在一次運行中可能需要計算多個測試用例，可以採用備忘錄的方法，預先將所有的問題的解記錄下來，然後輸入一個測試用例，就查備忘錄，直接找到答案輸出。這在各問題之間存在父子關系的情況下，會更有效。例如，在題1045--Square
Coins中，題目中已經指出了最大的目標幣值不超過300，也就是說問題數只有300個，而且各問題的計算中存在重疊的子問題，可以採用動態規劃法，將所有問題的解先全部計算出來，再依次輸入測試用例數據，並直接輸出答案。
4、回溯法回溯法是基於問題狀態樹搜索的求解法，其可適用范圍很廣。從某種角度上說，可以把回溯法看作是優化了的窮舉法。回溯法的基本思想是逐步構造問題的可能解，一邊構造，一邊用約束條件進行判別，一旦發現已經不可能構造出滿足條件的解了，則退回上一步構造過程，重新進行構造。這個退回的過程，就稱之為回溯。
回溯法在運用時，要解決的關鍵問題在於：
回溯法的經典案例也很多，例如全排列問題、N後問題等。
5、貪心法貪心法也是求解最優問題的常用演算法策略，利用貪心法策略所設計的演算法，通常效率較高，演算法簡單。貪心法的基本思想是對問題做出目前看來最好的選擇，即貪心選擇，並使問題轉化為規模更小的子問題。如此迭代，直到子問題可以直接求解。
基於貪心法的經典演算法例如：哈夫曼演算法、最小生成樹演算法、最短路徑演算法等。