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

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

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

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

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

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

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

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

十二、DFS框架

十三、BFS框架

十五、數據結構相關算法
1．鏈表的定位函數

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

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