書名：培養與鍛鍊程式設計的邏輯腦：程式設計大賽的128個進階技巧(使用Python) 作者：Christoph Dürr, Jill-Jênn Vie 出版社：博碩 出版日期：4/29/2019 條碼：9789864343836 內容簡介 APCS，CPE最佳參考用書 演算法不僅要用得好，更要用得準 本書介紹多種解決經典問題的演算法技術，描述了問題出現的場景，並用Python提出簡單的解決方案。要正確實作演算法往往不是一件簡單的事情，總需要避開陷阱，也需要應用一些技巧來確保演算法能夠在規定時間內實現。本書在說明演算法實作時也附帶了重要的細節，以幫助讀者能夠詳加理解。 最近幾十年，不同等級的程式設計競賽在世界各地展開，推廣了演算法文化。競賽中所考究的問題一般都是經典問題的變形，使解答隱藏在難以破解的謎面背後，而讓參賽者一籌莫展，因此本書是這方面的絕佳參考書目。書中所使用的是目前最多人使用的程式語言Python，在應用與理解上更加便利！ 本書特色： ✤詳細解說如何增進演算法效率並加以實作 ✤內容由淺入深，幫助讀者快速掌握技巧 ✤以主題導向收錄128種演算法，應試更有效率 ✤使用可讀性及易用性皆優秀的程式語言Python ✤參加程式設計比賽或考試的最佳參考書目 本書相關資源：tryalgo.org/code/ 作者介紹 作者簡介 Christoph Dürr 法國國家科學研究院研究員，巴黎皮埃爾－瑪麗．居里大學研究院研究員，巴黎皮埃爾－瑪麗．居里大學博士生導師，Operation Research科研組研究主任。 Jill-Jênn Vie 法國高等電力學院博士、演算法講師、擔任法國高等師範學院Paris-Saclay團隊在ACM競賽中的演算法導師。曾任法國國際程式設計大賽Prologin主席，並於2014年獲得Google RISE Award。 譯者簡介 史世強 網名jetwaves。畢業於華中科技大學，法國特魯瓦技術大學碩士，全端工程師。曾在法國Aerow SAS擔任技術負責人，花果山水果品牌聯合創始人。從國中起開始參加資訊學奧林匹克競賽，熱衷於軟體架構、軟體工程和傳統行業資訊化建設。目前著重於人工智慧領域。白雲黃鶴幽默版版主，平時活躍於知乎，同時也是野戰遊戲和健身運動愛好者。 目錄 Chapter1 引言 1-1 程式設計競賽 1-2 我們的選擇：Python 1-3 輸入輸出 1-4 複雜度 1-5 抽象類別和基本資料結構 1-6 技術 1-7 建議 1-8 走得更遠 Chapter2 字串 2-1 易位構詞 2-2 T9： 9 個按鍵上的文字 2-3 使用字典樹進行拼寫糾正 2-4 KMP（Knuth-Morris-Pratt）模式匹配演算法 2-5 最大邊的KMP 演算法 2-6 字串的冪次 2-7 模式匹配演算法：Rabin-Karp 演算法 2-8 字串的最長迴文子串：Manacher 演算法 Chapter3 序列 3-1 網格中的最短路徑 3-2 編輯距離（列文斯登距離） 3-3 最長公共子序列 3-4 升序最長子序列 3-5 兩位玩家遊戲中的必勝策略 Chapter4 陣列 4-1 合併已排序串列 4-2 區間的總和 4-3 區間內的重複內容 4-4 區間的最大總和 4-5 查詢區間中的最小值：線段樹 4-6 計算區間的總和：樹狀陣列（Fenwick 樹） 4-7 有k 個獨立元素的窗口 Chapter5 區間 5-1 區間樹（線段樹） 5-2 區間的聯集 5-3 區間的覆蓋 Chapter6 圖 6-1 使用 Python 對圖編碼 6-2 使用 C++ 或 Java 對圖編碼 6-3 隱式圖 6-4 深度優先巡訪：深度優先演算法 6-5 廣度優先巡訪：廣度優先演算法 6-6 連通分量 6-7 雙連通分量 6-8 拓撲排序 6-9 強連通分量 6-10 可滿足性 Chapter7 圖中的環 7-1 歐拉路徑 7-2 中國郵差問題 7-3 最小長度上的比率權重環：Karp 演算法 7-4 單位時間成本最小比率環 7-5 旅行推銷員問題 Chapter8 最短路徑 8-1 組合的屬性 8-2 權重為 0 或 1 的圖 8-3 權重為正值或空值的圖：Dijkstra 演算法 8-4 隨機權重的圖：Bellman-Ford 演算法 8-5 所有源點─目標頂點對：Floyd-Warshall 演算法 8-6 網格 8-7 變形問題 Chapter9 耦合性與流 9-1 二分圖最大匹配 9-2 最大權重的完美匹配：Kuhn-Munkres 演算法 9-3 無交叉平面匹配 9-4 穩定的婚姻：Gale-Shapley 演算法 9-5 Ford-Fulkerson 最大流演算法 9-6 Edmonds-Karp 演算法的最大流 9-7 Dinic 最大流算法 9-8 s-t 最小割 9-9 平面圖的 s-t 最小割 9-10 運輸問題 9-11 在流和匹配之間化簡 9-12 偏序的寬度：Dilworth 演算法 Chapter10 樹 10-1 霍夫曼編碼 10-2 最近的共同祖先 10-3 樹中的最長路徑 10-4 最小權重生成樹：Kruskal 演算法 Chapter11 集合 11-1 背包問題 11-2 找零問題 11-3 給定總和值的子集 11-4 k 個整數之和 Chapter12 點和多邊形 12-1 凸包問題 12-2 多邊形的測量 12-3 最近點對 12-4 簡單直線多邊形 Chapter13 長方形 13-1 組成長方形 13-2 網格中的最大正方形 13-3 長條圖中的最大長方形 13-4 網格中的最大長方形 13-5 合併長方形 13-6 不相交長方形的合併 Chapter14 計算 14-1 最大公因數 14-2 貝祖等式 14-3 二項式係數 14-4 快速求冪 14-5 質數 14-6 計算算術運算式 14-7 線性方程組 14-8 矩陣序列相乘 Chapter15 窮舉 15-1 鐳射路徑 15-2 精確覆蓋 15-3 數獨 15-4 排列枚舉 15-5 正確計算 除錯工具 參考文獻