1. 在java中，用遞歸方法計算n的階乘。
用Java求鍵盤輸入的數的階乘n。（遞歸演算法）packagejiecheng; importjava.util.*; //導入java.util包中的所有類classrep{ publiclongrep(intn){ longi=0; if(n==0||n==1) i=1;
elsi=n*rep(n-1) returni; } } publicclassJie{ publicstaticvoidmain(String[]args){ intn; //此處定義要輸入的數Scanners= newScanner(System.in); //以下三行用於n的值得輸入System.out.print( "請輸入一個整數："); n=s.nextInt(); repf= newrep(); System.out.println(n+"!="+f.rep(n)); } }
一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序n個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(nlogn)演算法更快，因為它的內部循環（innerloop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divideandconquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。
演算法步驟：
1從數列中挑出一個元素，稱為「基準」（pivot），
2重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
3遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
二：堆排序演算法
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。
堆排序的平均時間復雜度為Ο(nlogn) 。
創建一個堆H[0..n-1]
把堆首（最大值）和堆尾互換
3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
4.重復步驟2，直到堆的尺寸為1
三：歸並排序
歸並排序（Mergesort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（DivideandConquer）的一個非常典型的應用。
1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3.比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
4.重復步驟3直到某一指針達到序列尾
5.將另一序列剩下的所有元素直接復制到合並序列尾
四：二分查找演算法
二分查找演算法是一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半，時間復雜度為Ο(logn) 。
五：BFPRT(線性查找演算法)
BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間復雜度，五位演算法作者做了精妙的處理。
1.將n個元素每5個一組，分成n/5(上界)組。
2.取出每一組的中位數，任意排序方法，比如插入排序。
3.遞歸的調用selection演算法查找上一步中所有中位數的中位數，設為x，偶數個中位數的情況下設定為選取中間小的一個。
4.用x來分割數組，設小於等於x的個數為k，大於x的個數即為n-k。
5.若i==k，返回x；若i<k，在小於x的元素中遞歸查找第i小的元素；若i>k，在大於x的元素中遞歸查找第i-k小的元素。
終止條件：n=1時，返回的即是i小元素。
六：DFS（深度優先搜索）
深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。
深度優先遍歷圖演算法步驟：
1.訪問頂點v；
2.依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
3.若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。
上述描述可能比較抽象，舉個實例：
DFS在訪問圖中某一起始頂點v後，由v出發，訪問它的任一鄰接頂點w1；再從w1出發，訪問與w1鄰接但還沒有訪問過的頂點w2；然後再從w2出發，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。
接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。
七：BFS(廣度優先搜索)
廣度優先搜索演算法（Breadth-First-Search），是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。
BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。
1.首先將根節點放入隊列中。
2.從隊列中取出第一個節點，並檢驗它是否為目標。
如果找到目標，則結束搜尋並回傳結果。
否則將它所有尚未檢驗過的直接子節點加入隊列中。
3.若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。
4.重復步驟2。
八：Dijkstra演算法
戴克斯特拉演算法（Dijkstra』salgorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。
該演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E表示G中所有邊的集合，而邊的權重則由權重函數w:E→[0,∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。
1.初始時令S=,T=，T中頂點對應的距離值
若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值
若不存在<V0,Vi>，d(V0,Vi)為∞
2.從T中選取一個其距離值為最小的頂點W且不在S中，加入S
3.對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止
九：動態規劃演算法
動態規劃（Dynamicprogramming）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。
動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。
關於動態規劃最經典的問題當屬背包問題。
1.最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動態規劃演算法解決問題提供了重要線索。
2.子問題重疊性質。子問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。
十：樸素貝葉斯分類演算法
樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單概率分類演算法。貝葉斯分類的基礎是概率推理，就是在各種條件的存在不確定，僅知其出現概率的情況下，如何完成推理和決策任務。概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。
樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換言樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。
盡管是帶著這些樸素思想和過於簡單化的假設，但樸素貝葉斯分類器在很多復雜的現實情形中仍能夠取得相當好的效果。
通過掌握以上演算法，能夠幫你迅速提高編程能力，成為一名優秀的程序員。
3. 遞歸的原理解釋
遞歸的原理解釋：
遞歸，是函數實現的一個很重要的環節，很多程序中都或多或少的使用了遞歸函數。遞歸的意思就是函數自己調用自己本身，或者在自己函數調用的下級函數中調用自己。
遞歸之所以能實現，是因為函數的每個執行過程都在棧中有自己的形參和局部變數的拷貝，這些拷貝和函數的其他執行過程毫不相干。這種機制是當代大多數程序設計語言實現子程序結構的基礎，是使得遞歸成為可能。假定某個調用函數調用了一個被調用函數，再假定被調用函數又反過來調用了調用函數。這第二個調用就被稱為調用函數的遞歸，因為它發生在調用函數的當前執行過程運行完畢之前。而且，因為這個原先的調用函數、現在的被調用函數在棧中較低的位置有它獨立的一組參數和自變數，原先的參數和變數將不受影響，所以遞歸能正常工作。程序遍歷執行這些函數的過程就被稱為遞歸下降。
程序員需保證遞歸函數不會隨意改變靜態變數和全局變數的值，以避免在遞歸下降過程中的上層函數出錯。程序員還必須確保有一個終止條件來結束遞歸下降過程，並且返回到頂層。
4. 演算法和軟體的關系，程序員應該學習哪些演算法
一.基本演算法:
枚舉. (poj1753,poj2965)
貪心(poj1328,poj2109,poj2586)
遞歸和分治法.
遞推.
構造法.(poj3295)
模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
圖的深度優先遍歷和廣度優先遍歷.
最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)
二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
串 (poj1035,poj3080,poj1936)
排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
簡單並查集的應用.
哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)
堆
trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
背包問題. (poj1837,poj1276)
型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
幾何公式.
叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)
中級（校賽壓軸及省賽中等難度）:
一.基本演算法:
C++的標准模版庫的應用. (poj3096,poj3007)
較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
差分約束系統的建立和求解. (poj1201,poj2983)
最小費用最大流(poj2516,poj2516,poj2195)
雙連通分量(poj2942)
強連通分支及其縮點.(poj2186)
圖的割邊和割點(poj3352)
最小割模型、網路流規約(poj3308)
5. 程序員必須掌握哪些演算法
一.基本演算法:
枚舉. (poj1753,poj2965)
貪心(poj1328,poj2109,poj2586)
遞歸和分治法.
遞推.
構造法.(poj3295)
模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
圖的深度優先遍歷和廣度優先遍歷.
最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)
二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
串 (poj1035,poj3080,poj1936)
排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
簡單並查集的應用.
哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)
堆
trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
背包問題. (poj1837,poj1276)
型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
幾何公式.
叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)
中級（校賽壓軸及省賽中等難度）:
一.基本演算法:
C++的標准模版庫的應用. (poj3096,poj3007)
較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
差分約束系統的建立和求解. (poj1201,poj2983)
最小費用最大流(poj2516,poj2516,poj2195)
雙連通分量(poj2942)
強連通分支及其縮點.(poj2186)
圖的割邊和割點(poj3352)
最小割模型、網路流規約(poj3308)
三.數據結構.
線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
靜態二叉檢索樹. (poj2482,poj2352)
樹狀樹組(poj1195,poj3321)
RMQ. (poj3264,poj3368)
並查集的高級應用. (poj1703,2492)
KMP演算法. (poj1961,poj2406)
四.搜索
最優化剪枝和可行性剪枝
搜索的技巧和優化 (poj3411,poj1724)
記憶化搜索(poj3373,poj1691)
五.動態規劃
較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
坐標離散化.
掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)
幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級（regional中等難度）:
一.基本演算法要求:
代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保證正確性和高效性. poj3434
二.圖演算法:
度限制最小生成樹和第K最短路. (poj1639)
最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)
最小樹形圖(poj3164)
次小生成樹.
無向圖、有向圖的最小環
三.數據結構.
trie圖的建立和應用. (poj2778)
LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).
後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索
較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.
較難的狀態DP(poj3133)
六.數學
組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
半平面求交(poj3384,poj2540)
可視圖的建立(poj2966)
點集最小圓覆蓋.
對踵點(poj2079)
6. 求編程領域上一些經典演算法同時也是程序員必須掌握的演算法
這是我在一個論壇里看到的，你也參考參考吧。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的演算法啟動數據發送。
一次發送可能是你提交數據的一部分，一定要當心，否則出問題沒處找去。
7. C語言的遞歸好難理解，誰能詳細解釋下
<可以自由轉載，但請註明以下內容，謝謝合作！>
<作者：Enoch Wang 引用自：http://chinawangquan.spaces.live.com>
所謂遞歸，簡而言之就是應用程序自身調用自身，以實現層次數據結構的查詢和訪問。 遞歸的使用可以使代碼更簡潔清晰，可讀性更好（對於初學者到不見得），但由於遞歸需要系統堆棧，所以空間消耗要比非遞歸代碼要大很多，而且，如果遞歸深度太大，可能系統資源會不夠用。
往往有這樣的觀點：能不用遞歸就不用遞歸，遞歸都可以用迭代來代替。
誠然，在理論上，遞歸和迭代在時間復雜度方面是等價的（在不考慮函數調用開銷和函數調用產生的堆棧開銷），但實際上遞歸確實效率比迭代低，既然這樣，遞歸沒有任何優勢，那麼是不是就，沒有使用遞歸的必要了，那遞歸的存在有何意義呢？
萬物的存在是需要時間的檢驗的，遞歸沒有被歷史所埋沒，即有存在的理由。從理論上說，所有的遞歸函數都可以轉換為迭代函數，反之亦然，然而代價通常都是比較高的。但從演算法結構來說，遞歸聲明的結構並不總能夠轉換為迭代結構，原因在於結構的引申本身屬於遞歸的概念，用迭代的方法在設計初期根本無法實現，這就像動多態的東西並不總是可以用靜多態的方法實現一樣。這也是為什麼在結構設計時，通常採用遞歸的方式而不是採用迭代的方式的原因，一個極典型的例子類似於鏈表，使用遞歸定義及其簡單，但對於內存定義(數組方式)其定義及調用處理說明就變得很晦澀，尤其是在遇到環鏈、圖、網格等問題時，使用迭代方式從描述到實現上都變得不現實。 因而可以從實際上說，所有的迭代可以轉換為遞歸，但遞歸不一定可以轉換為迭代。
採用遞歸演算法需要的前提條件是，當且僅當一個存在預期的收斂時，才可採用遞歸演算法，否則，就不能使用遞歸演算法。
遞歸其實是方便了程序員難為了機器，遞歸可以通過數學公式很方便的轉換為程序。其優點就是易理解，容易編程。但遞歸是用棧機制實現的，每深入一層，都要佔去一塊棧數據區域，對嵌套層數深的一些演算法，遞歸會力不從心，空間上會以內存崩潰而告終，而且遞歸也帶來了大量的函數調用，這也有許多額外的時間開銷。所以在深度大時，它的時空性就不好了。
而迭代雖然效率高，運行時間只因循環次數增加而增加，沒什麼額外開銷，空間上也沒有什麼增加，但缺點就是不容易理解，編寫復雜問題時困難。
因而，「能不用遞歸就不用遞歸，遞歸都可以用迭代來代替」這樣的理解，Enoch不敢苟同，還是辯證的來看待，不可一棍子打死。
參考資料：http://chinawangquan.spaces.live.com/blog/cns!9CF795352E94BF70!787.entry
8. C語言遞歸演算法
本人學c++，c的語法已經淡忘了，但是遞歸不管什麼語言都是一個原理
其實簡單一點來說就像數學裡面的數列的通項公式：
例如一個數列是2，4，6，8，10......
很容易就可以得到通項公式是a[n]=2*n n是大於0的整數
你肯定學過這個數列的另外一種表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大於1的整數
其實這就是一個遞歸的形式，只要你知道初始項的值，未知項和前幾項之間的關系就可以知道整個數列。
程序例子：比如你要得到第x項的值
普通循環：
for(int i=1; i<=n; i++)
if (i == x)
cout << 2*i; /*cout 相當於 c裡面的printf,就是輸出.*/
遞歸：
int a(int x) {
if (x = 1)
return 2; /* 第一項那肯定是2了，這個也是遞歸的終止條件！ */
else return a(x-1)+2; /* 函數自身調用自身是遞歸的一個特色 */
比如x=4,那麼用數學表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2
其實遞歸方法最接近自然，也是最好思考的一個方法，難點就是把對象建模成遞歸形式，但是好多問題本身就是以遞歸形式出現的。
普通遞歸就是數據結構上的堆棧，先進後出。
例如上面x=4,把a(4)放入棧底，然後放入a(3),然後a(2),a(1),a(1)的值已知，出棧，a(1)=2,a(2)出棧a(2)=a(1)+2=2+2=4,a(3)出棧a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出棧a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8
再比如樓上的階乘例子，當n=0 或 1時,0!=1,1!=1,這個是階乘的初始值，也是遞歸的終止條件。然後我們知道n!=n*(n-1)!,當n>1時,這樣我們又有了遞歸形式，又可以以遞歸演算法設計程序了。（樓上已給出譚老的程序，我就不寫了）。
我給出一種優化的遞歸演算法---尾遞歸。
從我給出的第一演算法可以看出，先進棧再出棧，遞歸的效率是很低的。速度上完全比不上迭代（循環）。但是尾遞歸引入了一個新的函數參數，用這個新的函數參數來記錄中間值.
普通遞歸階乘fac(x),就1個x而已，尾遞歸用2個參數fac(x,y),y存放階乘值。
所以譚老的程序就變成
// zysable's tail recursive algorithm of factorial.
int fac(int x, int y) {
if (x == 1)
return y;
else return fac(x-1, y*x);}
int ff(int x) {
if (x == 0)
return 1;
else return fac(x,1);}
對於這個程序我們先看函數ff，函數ff其實是對fac的一個封裝函數，純粹是為了輸入方便設計的，通過調用ff(x)來調用fac(x,1),這里常數1就是當x=1的時候階乘值了，我通過走一遍當x=3時的值即為3!來說明一下。
首先ff(3),x!=0,執行fac(3,1).第一次調用fac，x=3,y=1,x!=1,調用fac(x-1,y*x),新的x=2,y=3*1=3,這里可以看到，y已經累計了一次階乘值了，然後x還是!=1,繼續第三次調用fac(x-1,y*x),新的x=1,y=2*3=6,然後x=1了，返回y的值是6，也就是3！.你會發現這個遞歸更類似於迭代了。事實上我們用了y記錄了普通遞歸時候，出棧的乘積，所以減少了出棧後的步驟，而且現在世界上很多程序員都在倡議用尾遞歸取消循環，因為有些在很多解釋器上尾遞歸比迭代稍微效率一點.
基本所有普通遞歸的問題都可以用尾遞歸來解決。
一個問題以遞歸來解決重要的是你能抽象出問題的遞歸公式，只要遞歸公式有了，你就可以放心大膽的在程序中使用，另外一個重點就是遞歸的終止條件；
其實這個終止條件也是包含在遞歸公式裡面的，就是初始值的定義。英文叫define initial value. 用普通遞歸的時候不要刻意讓自己去人工追蹤程序，查看運行過程，有些時候你會發現你越看越不明白，只要遞歸公式轉化成程序語言正確了，結果必然是正確的。學遞歸的初學者總是想用追蹤程序運行來讓自己來了解遞歸，結果越弄越糊塗。
如果想很清楚的了解遞歸，有種計算機語言叫scheme,完全遞歸的語言，因為沒有循環語句和賦值語句。但是國內人知道的很少，大部分知道是的lisp。
好了，就給你說到這里了，希望你能學好遞歸。
PS:遞歸不要濫用，否則程序極其無效率，要用也用尾遞歸。by 一名在美國的中國程序員zysable。
9. 作為一個程序員，有哪些常用的演算法
常用的演算法有：遞推法、貪心法、列舉法、遞歸法、分治法和模擬法
原則：1. 扎實的基礎。數據結構、離散數學、編譯原理，這些是所有計算機科學的基礎，如果不掌握他們，很難寫出高水平的程序。據我的觀察，學計算機專業的人比學其他專業的人更能寫出高質量的軟體。程序人人都會寫，但當你發現寫到一定程度很難再提高的時候，就應該想想是不是要回過頭來學學這些最基本的理論。不要一開始就去學OOP，即使你再精通OOP，遇到一些基本演算法的時候可能也會束手無策。
2. 豐富的想像力。不要拘泥於固定的思維方式，遇到問題的時候要多想幾種解決問題的方案，試試別人從沒想過的方法。豐富的想像力是建立在豐富的知識的基礎上，除計算機以外，多涉獵其他的學科，比如天文、物理、數學等等。另外，多看科幻電影也是一個很好的途徑。
3. 最簡單的是最好的。這也許是所有科學都遵循的一條准則，如此復雜的質能互換原理在愛因斯坦眼裡不過是一個簡單得不能再簡單的公式：E=mc2。簡單的方法更容易被人理解，更容易實現，也更容易維護。遇到問題時要優先考慮最簡單的方案，只有簡單方案不能滿足要求時再考慮復雜的方案。
4. 不鑽牛角尖。當你遇到障礙的時候，不妨暫時遠離電腦，看看窗外的風景，聽聽輕音樂，和朋友聊聊天。當我遇到難題的時候會去玩游戲，而且是那種極暴力的打鬥類游戲，當負責游戲的那部分大腦細胞極度亢奮的時候，負責編程的那部分大腦細胞就得到了充分的休息。當重新開始工作的時候，我會發現那些難題現在竟然可以迎刃而解。
5. 對答案的渴求。人類自然科學的發展史就是一個渴求得到答案的過程，即使只能知道答案的一小部分也值得我們去付出。只要你堅定信念，一定要找到問題的答案，你才會付出精力去探索，即使最後沒有得到答案，在過程中你也會學到很多東西。
6. 多與別人交流。三人行必有我師，也許在一次和別人不經意的談話中，就可以迸出靈感的火花。多上上網，看看別人對同一問題的看法，會給你很大的啟發。
7. 良好的編程風格。注意養成良好的習慣，代碼的縮進編排，變數的命名規則要始終保持一致。大家都知道如何排除代碼中錯誤，卻往往忽視了對注釋的排錯。注釋是程序的一個重要組成部分，它可以使你的代碼更容易理解，而如果代碼已經清楚地表達了你的思想，就不必再加註釋了，如果注釋和代碼不一致，那就更加糟糕。
8. 韌性和毅力。這也許是"高手"和一般程序員最大的區別。A good programming is 99 weat and 1 ffee。高手們並不是天才，他們是在無數個日日夜夜中磨練出來的。成功能給我們帶來無比的喜悅，但過程卻是無比的枯燥乏味。你不妨做個測試，找個10000以內的素數表，把它們全都抄下來，然後再檢查三遍，如果能夠不間斷地完成這一工作，你就可以滿足這一條。
希望對你有幫助