 |
-- 會員 / 註冊 --
|
 |
|
|
|
算法基礎——打開程序設計之門 ( 簡體 字) |
| 作者：梁冰,馮林,劉勝藍 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：電子工業出版社 |  3dWoo書號： 50762
詢問書籍請說出此書號！【缺書】
NT售價： 345 元 |
| 出版日：3/1/2019 |
| 頁數：280 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787121358685 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：這是一本關于算法的教程。算法是一系列解決問題的清晰指令，可以說它是程序設計的靈魂。同一問題可用不同的算法解決，而一個算法的質量優劣將影響程序的執行效率。算法分析的目的在于選擇合適算法和改進算法。評價一個算法的好壞主要是通過算法運行的時間長短和占用空間的大小來評估的。對于計算機專業或者愛好計算機的人士來說，無論學習還是工作，或多或少都會應用一些算法的知識。而目前國內外大型互聯網公司在招聘時的筆試和面試都以算法為主。可見，算法的重要性是不言而喻的。
ACM/ICPC（ACM International Collegiate Programming Contest）是一項由美國計算機協會主辦的，旨在展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。ACM程序設計競賽的題目強調算法的高效性與正確性。參賽選手只有編寫出能夠在規定時間內運行完成若干組數嚴格的測試數據，并且結果全部正確的程序才能得到分數。本書將以ACM程序設計競賽的題目為基礎，介紹一些經典的算法。
本書的目的是將更多對計算機和算法感興趣，但又苦于無從入手的讀者帶進算法的大門，讓剛邁入大學校門的學生學會使用C++語言解決簡單的問題。本書會依次介紹一些包括高級數據結構、字符串、動態規劃、圖論、組合數學方面的經典算法，相信當讀者掌握了這些內容之后，會對算法和程序設計有一個新層次的認識，并會產生濃厚的興趣。對于每個算法，本書都有圖文并茂的講解；在每章節的最后，都有針對該部分知識點的例題講解，每道例題都是國內外著名程序在線判題系統中的原題，而且對于每道例題，都會從理解題意開始，詳細講解解題的思路，并附有完整的可以正確通過測試樣例的代碼，供讀者研究學習。除了例題，在每章的最后還有一些練習題供讀者鞏固學到的知識，如果讀者對這些習題仍感覺無從下手，可以參考每道練習題后附帶的思路分析來幫助整理解題思路。
大連理工大學是在全國高校中較早倡導并開展創新創業教育的學校。自1984年以來，學校大力開展以突出創新創業實踐為特色的創新創業教育。1995年，在全國率先成立以學生創新創業教育為主體的教學改革示范區—創新教育實踐中心，開展創新創業教育課程體系、教學內容、教學方法、教學模式等方面的改革，探索與之配套的管理運行機制，將創造性思維與創新方法融入教學實踐中，在課堂教學中樹立“CDIO工程教育”新理念，倡導“做中學”，在實踐環節構建了“個性化、雙渠道、三結合、四層次、多模式”的創新教育實踐教學新體系，取得了一系列成果，在全國高校產生了很大的影響。“創造性思維與創新方法”和“創新教育基礎與實踐（系列）”課程分別被評為國家級精品資源開放課程。“大學生程序設計競賽初級教材”是“創新教育基礎與實踐”系列課程的核心課程，是面向大連理工大學ACM創新實踐班的學生開設的。
此外，本書在撰寫過程中，除了參考文獻和正文中標出的引用來源，還參考了國內外的相關研究成果和網站資源，但沒有一一列出，在此感謝所涉及的所有單位、專家和研究人員。
因編者水平有限，書中的錯誤和不足之處在所難免，歡迎廣大讀者來信批評指正，提出寶貴意見，幫助我們不斷地完善本書。
編 者
2018年12月 |
內容簡介：算法是一系列解決問題的清晰指令，是程序設計的靈魂。同一問題可采用不同的算法解決，而一個算法的優劣將直接影響程序的執行效率。本書以ACM程序設計競賽的題目為基礎，詳細介紹一些常用的算法以及相關的理論知識，主要內容包括高級數據結構、字符串、動態規劃進階算法、圖論高級算法、經典算法問題、組合數學、計算幾何、組合游戲論。 |
目錄：第1章 高級數據結構 （1）
1.1 堆 （1）
1.1.1 堆的定義 （1）
1.1.2 建堆 （1）
1.1.3 堆排序算法 （2）
1.2 樹狀數組 （3）
1.2.1 樹狀數組的定義 （4）
1.2.2 樹狀數組的實現和使用 （4）
1.2.3 例題講解 （5）
1.3 左傾堆 （7）
1.3.1 左傾堆相關定義和性質 （7）
1.3.2 左傾堆的操作 （7）
1.3.3 例題講解 （8）
1.4 平衡二叉樹 （10）
1.4.1 Treap （11）
1.4.2 Splay樹 （13）
1.4.3 例題講解 （18）
1.5 練習題 （22）
第2章 字符串 （24）
2.1 Trie樹 （24）
2.1.1 Trie樹的原理 （24）
2.1.2 Trie樹的實現 （25）
2.1.3 例題講解 （26）
2.2 KMP算法 （29）
2.2.1 KMP算法的原理 （29）
2.2.2 KMP算法的實現 （31）
2.2.3 例題講解 （32）
2.3 Aho-Corasick自動機 （35）
2.3.1 Aho-Corasick自動機原理 （35）
2.3.2 Aho-Corasick自動機算法的實現 （37）
2.3.3 例題講解 （39）
2.4 后綴數組 （43）
2.4.1 后綴數組基本原理 （43）
2.4.2 后綴數組的應用 （46）
2.4.3 例題講解 （49）
2.5 練習題 （54）
第3章 動態規劃進階算法 （57）
3.1 樹狀DP （57）
3.1.1 樹狀DP的定義 （57）
3.1.2 樹狀DP解題方法 （58）
3.1.3 例題講解 （58）
3.2 狀態壓縮DP （62）
3.2.1 集合的整數表示 （62）
3.2.2 例題講解 （63）
3.3 動態規劃的優化方法 （66）
3.3.1 單調隊列優化的動態規劃 （66）
3.3.2 例題講解 （66）
3.3.3 斜率優化的動態規劃 （68）
3.3.4 例題講解 （68）
3.3.5 四邊形不等式優化的動態規劃 （71）
3.3.6 例題講解 （71）
3.4 練習題 （73）
第4章 圖論高級算法 （76）
4.1 最大流 （76）
4.1.1 最大流的定義 （76）
4.1.2 增廣路算法涉及的三個重要概念 （77）
4.1.3 Edmonds-Karp算法 （79）
4.1.4 Dinic算法 （82）
4.1.5 ISAP算法 （84）
4.1.6 網絡流的建圖 （89）
4.1.7 例題講解 （91）
4.2 最小費用流 （99）
4.2.1 最小費用流算法 （99）
4.2.2 例題講解 （100）
4.3 二分圖匹配 （109）
4.3.1 二分圖的定義 （109）
4.3.2 二分圖的最大匹配 （109）
4.3.3 二分圖的性質與應用 （114）
4.3.4 例題講解 （115）
4.4 練習題 （118）
第5章 經典算法問題 （121）
5.1 多項式與快速傅里葉變換 （121）
5.1.1 多項式 （121）
5.1.2 多項式的表示與多項式乘法 （121）
5.1.3 DFT和FFT的實現 （123）
5.1.4 例題講解 （124）
5.2 NP完全性 （127）
5.2.1 NP問題簡介 （127）
5.2.2 哈密頓回路 （127）
5.2.3 例題講解 （128）
5.3 對偶圖問題 （135）
5.3.1 基本概念 （135）
5.3.2 平面圖轉化為對偶圖 （137）
5.3.3 對偶圖的應用 （140）
5.4 RMQ問題 （144）
5.4.1 RMQ問題的簡單求解方法 （145）
5.4.2 ST（Sparse Table）算法 （145）
5.4.3 例題講解 （146）
5.5 LCA問題 （151）
5.5.1 LCA問題的簡單求解方法 （151）
5.5.2 基于倍增的雙親存儲法 （152）
5.5.3 高效的LCA算法 （152）
5.5.4 例題講解 （154）
5.6 練習題 （158）
第6章 組合數學 （161）
6.1 排列組合 （161）
6.1.1 基本計數原則 （161）
6.1.2 排列 （161）
6.1.3 組合 （162）
6.1.4 例題講解 （163）
6.2 母函數 （164）
6.2.1 母函數基礎 （165）
6.2.2 母函數的兩類具體應用 （165）
6.2.3 例題講解 （166）
6.3 整數劃分 （169）
6.3.1 從動態規劃到母函數 （169）
6.3.2 例題講解 （170）
6.4 Stirling數和Catalan數 （172）
6.4.1 第一類Stirling數 （172）
6.4.2 第二類Stirling數 （173）
6.4.3 Catalan數 （173）
6.4.4 例題講解 （174）
6.5 容斥原理與反演 （179）
6.5.1 容斥原理 （179）
6.5.2 反演理論 （180）
6.5.3 Mobius反演 （181）
6.5.4 例題講解 （184）
6.6 群論與Polya定理 （187）
6.6.1 群的基本性質 （187）
6.6.2 置換群 （188）
6.6.3 Burnside定理及Polya定理 （189）
6.6.4 例題講解 （190）
6.7 練習題 （192）
第7章 計算幾何 （195）
7.1 多邊形上的數據結構表示 （195）
7.1.1 點 （195）
7.1.2 線段 （197）
7.1.3 多邊形類 （198）
7.1.4 例題講解 （199）
7.2 多邊形相交問題 （202）
7.2.1 線段相交 （202）
7.2.2 多邊形相交問題的討論 （203）
7.2.3 例題講解 （204）
7.3 多邊形求面積 （207）
7.3.1 計算多邊形的面積 （207）
7.3.2 格點數 （208）
7.3.3 例題講解 （209）
7.4 凸包 （210）
7.4.1 凸多邊形 （210）
7.4.2 凸多邊形的性質 （215）
7.4.3 構造凸包 （215）
7.4.4 例題講解 （219）
7.5 相交問題 （230）
7.5.1 半平面交 （230）
7.5.2 凸多邊形交 （232）
7.5.3 例題講解 （232）
7.6 圓 （240）
7.6.1 圓與線段的交 （240）
7.6.2 圓與多邊形的交的面積 （241）
7.6.3 圓與圓的交的面積 （241）
7.6.4 圓與圓的并的面積 （245）
7.7 練習題 （249）
第8章 組合游戲論 （252）
8.1 組合游戲論中的游戲 （252）
8.1.1 組合游戲論的定義 （252）
8.1.2 博弈樹模型 （253）
8.1.3 巴什博弈 （253）
8.1.4 威佐夫博弈 （254）
8.1.5 例題講解 （255）
8.2 NIM游戲和SG函數 （256）
8.2.1 NIM游戲的定義 （256）
8.2.2 NIM游戲中的性質 （256）
8.2.3 Sprague-Grundy函數的價值 （257）
8.2.4 SG函數的應用 （258）
8.2.5 例題講解 （259）
8.3 NIM游戲的變形 （262）
8.3.1 ANTI-NIM問題 （262）
8.3.2 Staircase NIM （264）
8.3.3 例題講解 （265）
8.4 練習題 （267）
參考文獻 （269） |
| 序： |
|
