一、數(shù)論算法
1．求兩數(shù)的最大公約數(shù)
2．求兩數(shù)的最小公倍數(shù)
3．素數(shù)的求法
A.小范圍內(nèi)判斷一個數(shù)是否為質(zhì)數(shù)：
B.判斷longint范圍內(nèi)的數(shù)是否為素數(shù)（包含求50000以內(nèi)的素數(shù)表）：

二、圖論算法
1．最小生成樹
A.Prim算法：
B.Kruskal算法：(貪心)
按權(quán)值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。
2.最短路徑
A.標號法求解單源點最短路徑：
B.Floyed算法求解所有頂點對之間的最短路徑：
C. Dijkstra 算法：
3.計算圖的傳遞閉包
4．無向圖的連通分量
A.深度優(yōu)先
B 寬度優(yōu)先（種子染色法）
5．關(guān)鍵路徑
幾個定義： 頂點1為源點，n為匯點。
a. 頂點事件最早發(fā)生時間Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 頂點事件最晚發(fā)生時間 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 邊活動最早開始時間 Ee[I], 若邊I由<j,k>表示，則Ee[I] = Ve[j];
d. 邊活動最晚開始時間 El[I], 若邊I由<j,k>表示，則El[I] = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，則活動j為關(guān)鍵活動，由關(guān)鍵活動組成的路徑為關(guān)鍵路徑。
求解方法：
a. 從源點起topsort,判斷是否有回路并計算Ve;
b. 從匯點起topsort,求Vl;
c. 算Ee 和 El;
6．拓撲排序
找入度為0的點，刪去與其相連的所有邊，不斷重復(fù)這一過程。
例 尋找一數(shù)列，其中任意連續(xù)p項之和為正，任意q 項之和為負，若不存在則輸出NO.
7.回路問題
Euler回路(DFS)
定義：經(jīng)過圖的每條邊僅一次的回路。（充要條件：圖連同且無奇點）
Hamilton回路
定義：經(jīng)過圖的每個頂點僅一次的回路。
一筆畫
充要條件：圖連通且奇點個數(shù)為0個或2個。
9．判斷圖中是否有負權(quán)回路 Bellman-ford 算法
x[I],y[I],t[I]分別表示第I條邊的起點，終點和權(quán)。共n個結(jié)點和m條邊。
10．第n最短路徑問題
*第二最短路徑：每舉最短路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些路徑中最短的一條即為第二最短路徑。
*同理，第n最短路徑可在求解第n-1最短路徑的基礎(chǔ)上求解。

三、背包問題
*部分背包問題可有貪心法求解：計算Pi/Wi
數(shù)據(jù)結(jié)構(gòu)：
w[i]:第i個背包的重量；
p[i]:第i個背包的價值；
1．0-1背包： 每個背包只能使用一次或有限次(可轉(zhuǎn)化為一次)：
A.求最多可放入的重量。
B.求可以放入的最大價值。
F[I,j] 為容量為I時取前j個背包所能獲得的最大價值。
F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }
C.求恰好裝滿的情況數(shù)。
2．可重復(fù)背包
A求最多可放入的重量。
F[I,j]為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。
狀態(tài)轉(zhuǎn)移方程為
f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])
B.求可以放入的最大價值。
f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])
其中f[i,j]表示容量為i時取前j種背包所能達到的最大值。
C.求恰好裝滿的情況數(shù)。
Ahoi2001 Problem2
求自然數(shù)n本質(zhì)不同的質(zhì)數(shù)和的表達式的數(shù)目。
思路一，生成每個質(zhì)數(shù)的系數(shù)的排列，在一一測試，這是通法。
思路二，遞歸搜索效率較高

思路三：可使用動態(tài)規(guī)劃求解
四、排序算法
1.快速排序：
B.插入排序：
思路：當前a[1]..a[i-1]已排好序了，現(xiàn)要插入a[i]使a[1]..a[i]有序。
C.選擇排序：
D. 冒泡排序
E.堆排序：
F. 歸并排序
G.基數(shù)排序
思想：對每個元素按從低位到高位對每一位進行一次排序
五、高精度計算
高精度數(shù)的定義：
1．高精度加法
2．高精度減法
3．高精度乘以低精度
4．高精度乘以高精度
5．高精度除以低精度
6．高精度除以高精度

六、 樹的遍歷
1．已知前序中序求后序
2．已知中序后序求前序
3．已知前序后序求中序的一種

七 進制轉(zhuǎn)換
1任意正整數(shù)進制間的互化
除n取余
2實數(shù)任意正整數(shù)進制間的互化
乘n取整
3負數(shù)進制：
設(shè)計一個程序，讀入一個十進制數(shù)的基數(shù)和一個負進制數(shù)的基數(shù)，并將此十進制數(shù)轉(zhuǎn)換為此負 進制下的數(shù)：-R∈{-2，-3，-4,....-20}
八 全排列與組合的生成
1排列的生成：（1..n）
2組合的生成(1..n中選取k個數(shù)的所有方案)

九.查找算法
1折半查找
2樹形查找
二叉排序樹：每個結(jié)點的值都大于其左子樹任一結(jié)點的值而小于其右子樹任一結(jié)點的值。
查找

十、貪心
*會議問題
（1） n個活動每個活動有一個開始時間和一個結(jié)束時間，任一時刻僅一項活動進行，求滿足活動數(shù)最多的情況。
解：按每項活動的結(jié)束時間進行排序，排在前面的優(yōu)先滿足。
（2）會議室空閑時間最少。
（3）每個客戶有一個愿付的租金，求最大利潤。
（4）共R間會議室，第i個客戶需使用i間會議室，費用相同，求最大利潤。
十一、回溯法框架
1. n皇后問題
2.Hanoi Tower h(n)=2*h(n-1)+1 h(1)=1

十二、DFS框架

十三、BFS框架

十五、數(shù)據(jù)結(jié)構(gòu)相關(guān)算法
1．鏈表的定位函數(shù)

2．單鏈表的插入操作
3．單鏈表的刪除操作
4．雙鏈表的插入操作（插入新結(jié)點q）
5．雙鏈表的刪除操作

原文鏈接：http://old.blog.edu.cn/user3/Hailer/archives/2006/1545396.shtml