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

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

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

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

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

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

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

十、貪心
*會議問題
（1） n個活動每個活動有一個開始時(shí)間和一個結(jié)束時(shí)間，任一時(shí)刻僅一項(xiàng)活動進(jìn)行，求滿足活動數(shù)最多的情況。
解：按每項(xiàng)活動的結(jié)束時(shí)間進(jìn)行排序，排在前面的優(yōu)先滿足。
（2）會議室空閑時(shí)間最少。
（3）每個客戶有一個愿付的租金，求最大利潤。
（4）共R間會議室，第i個客戶需使用i間會議室，費(fè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é)點(diǎn)q）
5．雙鏈表的刪除操作

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