提升程式設計的邏輯思考力：國際程式設計競賽之演算法原理、題型、解題技巧與重點解析

Part I　語言篇
Chapter 01　程式設計入門
熟悉 C 語言程式的編譯和執行
學會程式設計的運算並輸出常見的算術運算式之結果
掌握整數和浮點數的含義和輸出方法
掌握數學函數的使用方法
初步瞭解變數的含義
掌握整數和浮點數變數的宣告方法
掌握整數和浮點數變數的讀入方法
掌握變數交換的三變數法
理解演算法競賽中的程式三步曲：輸入、計算、輸出
記住演算法競賽的目標及其對程式的要求

Chapter 02　迴圈結構程式設計
掌握 for 迴圈的使用方法
掌握 while 迴圈的使用方法
學會使用計數器和累加器
學會用輸出中間結果的方法除錯
學會用計時函數測試程式效率
學會用重新導向的方式讀寫檔案
學會用 fopen 的方式讀寫檔案
瞭解演算法競賽對檔案讀寫方式和命名的嚴格規範
記住變數在指定值之前的值是不確定的
學會使用條件編譯指示建構本機執行環境

Chapter 03　陣列和字串
掌握一維陣列的宣告和使用方法
掌握二維陣列的宣告和使用方法
掌握字串的宣告、指定值、比較和連接方法
熟悉字元的 ASCII碼和 ctype.h中的字元函數
正確認識 ++、+= 等能修改變數的運算子
學會用編譯選項 -Wall 獲得更多的警告資訊
掌握 fgetc 和 getchar 的使用方法
瞭解不同作業系統中分行符號的表示方法
掌握 fgets 的使用方法並瞭解 gets 的「緩衝區溢位」漏洞
理解預處理和迭代式開發的技巧

Chapter 04　函數和遞迴
掌握多參數、單返回值的數學函數之定義和使用方法
學會用 typedef 定義結構體
學會用 assert 巨集幫忙除錯
理解函數呼叫時使用實參（Argument）為形參（Parameter）指定值的過程
學會定義區域變數和全域變數
理解呼叫堆疊和堆疊框架（Stack frame），學會用 gdb 查看呼叫堆疊並選擇堆疊框架
理解位址和指標
理解遞迴定義和遞迴函數
理解可執行檔中的正文段、資料段和 BSS 段
熟悉堆疊段，瞭解堆疊溢出的常見原因


Part II　演算法篇
Chapter 05　演算法基礎題型與解題技巧
學會用常數表簡化程式碼
學會用狀態變數輔助字串讀入
學會用結構體定義高精度整數，並設計建構函數、複製建構函數和輸入輸出方法
學會為結構體定義「小於」運算子，並用它定義其他比較運算子
熟練掌握泡泡排序和循序檢索
熟練掌握用 qsort 函數幫整數和字串排序的方法
熟練掌握小規模質數表的建構方法
熟練掌握質因數分解的方法
熟練掌握三角形有向面積的意義和計算方法
完成一定數量的程式設計練習

Chapter 06　資料結構的基礎
熟練掌握堆疊和佇列及其實作
瞭解雙向鏈結串列及其實作
掌握對比測試的方法
掌握亂數生成方法
掌握完全二元樹的陣列實作
瞭解動態記憶體分配和釋放方法及其注意事項
掌握二元樹的鏈式標記法
掌握二元樹的先序、後序、中序走訪和層次走訪
掌握圖的 DFS 及連通塊計數
掌握圖的 BFS 及最短路徑的輸出
掌握拓撲排序演算法
掌握尤拉迴路演算法

Chapter 07　暴力求解法
掌握整數、子串等簡單的列舉方法
熟練掌握排列生成的遞迴方法
熟練掌握用「下一個排列」列舉全排列的方法
理解解答樹，並能估算典型解答樹的節點數目
熟練掌握子集生成的增量法、位元向量法和二進位法
熟練掌握回溯法框架，並能理解為什麼它往往比生成-測試法有效率
熟練掌握解答樹的寬度優先搜尋和反覆運算加深搜尋
理解倒水問題的狀態圖與八皇后問題的解答樹的本質區別
熟練掌握數字拼圖問題的 BFS 實作
熟練掌握集合的兩種典型實作 —— Hash 表和 STL 集合

Chapter 08　高效演算法設計
理解「基本運算」、漸進時間複雜度的概念和大 O記號的含義
掌握「最大連續和」問題的各種演算法及其時間複雜度分析
正確認識演算法分析的優點和局限性，能正確使用分析結果
掌握歸併排序和逆序對統計的分治演算法
理解快速排序和快速選擇演算法
熟練掌握二分搜尋演算法，包括找上下界的演算法
能用遞迴的方式思考和求解問題
熟練掌握用二分法求解非線性方程式的方法
熟練掌握用二分法把優化問題轉化為判定問題的方法
熟悉能用貪心法求解的各類經典問題


Part III　競賽篇
Chapter 09　動態規劃初步
理解狀態和狀態轉移方程式
理解最優子結構和重疊子問題
熟練運用遞推法和記憶化搜尋求解數字三角形問題
熟悉 DAG 上動態規劃的常見邏輯思考方式
掌握記憶化搜尋在實作方面的注意事項
掌握記憶化搜尋和遞推中輸出方案的方法
掌握遞推中滾動陣列的使用方法
實作常見動態規劃問題
掌握集合上動態規劃的基本思考方式和方法
理解並靈活運用增加維度的方法

Chapter 10　數學概念與方法
熟練掌握擴展歐幾里德演算法和它的時間複雜度
熟練掌握用篩法建構質數表，瞭解質數定理
學會求二元線性不定方程式的整數解
熟練掌握模（mod）運算規則、快速冪取模演算法和模線性方程式的解法
熟悉楊輝三角、二項式定理和組合數的基本性質
學會推導約數個數公式和尤拉函數公式
熟練掌握可重集全排列的編碼和解碼演算法
理解樣本空間、事件和機率，學會用組合計數的方法計算離散機率
熟悉常見計數序列，如 Fibonacci 數列、Catalan 數列等
熟悉建立遞推關係的基本方法、常見錯誤和實作技巧

Chapter 11　圖論模型與演算法
掌握無根樹的常用儲存法和轉化為有根樹的方法
掌握由運算式建構運算式樹的演算法
掌握 Kruskal 演算法及其正確性證明，且用並查集來實作
掌握基於優先佇列的 Dijkstra 演算法實作
掌握基於 FIFO 佇列的 Bellman-Ford 演算法實作
掌握 Floyd 演算法和遞移閉包（Transitive Closure）的求法
理解最大流量問題的概念、流量的 3 個條件、殘量網路的概念和求法
理解增廣路徑定理與最小分割最大流量定理的證明方法，會實作 Edmonds-Karp 演算法
理解最小費用最大流量問題的概念，以及平行邊和反向弧可能造成的問題
實作以 Bellman-Ford 為基礎的最小費用路徑演算法


Appendix A　開發環境與方法
掌握

Part I　語言篇
Chapter 01　程式設計入門
熟悉 C 語言程式的編譯和執行
學會程式設計的運算並輸出常見的算術運算式之結果
掌握整數和浮點數的含義和輸出方法
掌握數學函數的使用方法
初步瞭解變數的含義
掌握整數和浮點數變數的宣告方法
掌握整數和浮點數變數的讀入方法
掌握變數交換的三變數法
理解演算法競賽中的程式三步曲：輸入、計算、輸出
記住演算法競賽的目標及其對程式的要求

Chapter 02　迴圈結構程式設計
掌握 for 迴圈的使用方...