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


	想要提升程式設計的功力，除了熟悉程式的語法外，演算法與邏輯思考是關鍵，正確的邏輯思維和活用演算法技巧，如此才能解決現實世界中的各種問題，並將它轉化為電腦中的程式語法，進而利用電腦運算出解決的方案。　　本書就是一本結合了程式設計基礎、演算法與國際程式競賽解題分析和經驗分享的參考書籍，書中有上百題實例，淡化理論，注重學習方法和實作技巧，並分享解題經驗，對於想要學習或提升程式設計能力，並想參加像IOI國際奧林匹克資訊競賽，ACM/ICPC國際大專程式設計競賽，這本書是很好的入門參考。　　多數初學者在學習程式設計與演算法時，都需要詳細的程式碼才能透徹地鍛練思考邏輯與理解演算法，但只從看程式碼來瞭解演算法原理和步驟是遠遠不夠的。請注意，程式設計不是看會的，也不是聽會的，而是練會的，程式設計需要大量的練習，只看只聽是不夠的，本書的目標很明確——提供演算法競賽入門所必需的一切「看」的藍本，接下來有效的「練」還要靠讀者自己實際上機練習。　　本書作者曾參加ACM/ICPC國際大專程式設計競賽，在亞洲賽區獲得冠軍，並在世界總決賽中獲得銀牌。作者也曾擔任ACM/ICPC亞洲賽區的命題總監和裁判，並在北京、上海、吉隆坡等多地著名高中教授講課，對於程式設計與國際競賽有相當豐富的經驗。　　作者將其豐富的知識和經驗編寫成書，全書共11章，內容包括程式設計基礎概念和重點、迴圈結構程式設計、陣列和字串、函數和遞迴、基礎題型題選、資料結構基礎、暴力求解法、高效演算法設計、動態規劃初步、數學概念與方法、圖論模型與演算法，包含了演算法程式競賽入門所需的主要知識，書中的程式碼規範、簡潔、易懂，不僅能解說演算法的原理，還能教會讀者很多實用的程式設計技巧，另外書中包含的各種開發、測試和除錯技巧也是在傳統的語言、演算法類型的書籍中難以見到的，是一本學習演算法、邏輯思考及程式設計技巧的好用參考書。


	目錄 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　開發環境與方法掌握命令列模式的使用掌握 Linux 和 Windows 下各種常用的命令語法掌握 Windows 下的批次檔腳本編寫掌握 Linux 下 Bash 腳本的編寫掌握 gcc 的安裝與測試掌握 gcc 的編譯基本理解 gdb 的基本淺談 IDE 環境的使用