定 價:38.6 元
叢書名:大學(xué)生創(chuàng)意·創(chuàng)新·創(chuàng)業(yè)教育與實踐系列教材
- 作者:梁冰,馮林主編
- 出版時間:2018/4/1
- ISBN:9787040491920
- 出 版 社:高等教育出版社
- 中圖法分類:TP301.6
- 頁碼:284頁
- 紙張:膠版紙
- 版次:1
- 開本:16K
本書共分11章,第1章介紹Linux操作系統(tǒng)與C++編程環(huán)境,第2章簡單介紹初級算法,第3章介紹基礎(chǔ)數(shù)據(jù)結(jié)構(gòu),第4章介紹枚舉、遞推、遞歸、貪心、分治、哈希和二分等基礎(chǔ)算法設(shè)計,第5章介紹簡單排序算法,第6章介紹圖論的相關(guān)知識,第7章介紹并查集和線段樹兩種高級數(shù)據(jù)結(jié)構(gòu),第8章介紹KMP、字典樹、Z算法和馬拉車算法等處理字符串的數(shù)據(jù)結(jié)構(gòu),第9章介紹深度優(yōu)先搜索、寬度優(yōu)先搜索、雙向?qū)挾葍?yōu)先搜索、A*搜索和一些剪枝常用的策略,第10章介紹初等數(shù)論,第11章介紹動態(tài)規(guī)劃,重點講述背包問題。
這是一本關(guān)于算法的教材。算法是一系列解決問題的清晰指令,可以說是程序設(shè)計的靈魂。同一問題可用不同算法解決,而一個算法的質(zhì)量優(yōu)劣將影響程序的執(zhí)行效率。算法分析的目的在于選擇合適算法和改進算法。評價一個算法的好壞主要是通過算法運行的時間長短和占用空間的大小來考慮。對于計算機相關(guān)專業(yè)的學(xué)生或者愛好計算機的學(xué)生來說,無論是學(xué)習(xí)還是工作,或多或少都會應(yīng)用到一些算法的知識。而目前國內(nèi)外大型互聯(lián)網(wǎng)公司招聘時的筆試和面試都以算法為主,可見算法的重要性是不言而喻的。ACMICPC(ACM International Collegiate Programming Contest,ACM國際大學(xué)生程序設(shè)計競賽)是一項由美國計算機協(xié)會主辦的旨在展示大學(xué)生創(chuàng)新能力、團隊精神,以及在壓力下編寫程序、分析和解決問題能力的年度競賽。ACM程序設(shè)計競賽的題目強調(diào)算法的高效性與正確性。參賽選手只有編寫出能夠在規(guī)定時間內(nèi)運行完成若干組嚴(yán)格的測試數(shù)據(jù)且結(jié)果全部正確的程序,才能得到分?jǐn)?shù)。本教程將以ACM程序設(shè)計競賽的題目為基礎(chǔ),介紹一些比較初級的算法。
本書是面向初學(xué)者的一本算法教材。即使是從未接觸過算法,甚至還沒有接觸過編程語言,都可以將本書當(dāng)作算法入門的讀物。本書旨在將更多對計算機和算法感興趣,但又苦于無從入手的同學(xué)帶進算法的大門。本書依次介紹了一些包括排序算法在內(nèi)的、基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計。相信當(dāng)讀者掌握了這些內(nèi)容之后,會對算法和程序設(shè)計有一個新層次的認(rèn)識并產(chǎn)生濃厚的興趣;之后重點介紹并查集、線段樹和一些字符串處理方面的高級數(shù)據(jù)結(jié)構(gòu),還將介紹搜索、圖論、動態(tài)規(guī)劃和數(shù)論等程序設(shè)計競賽中常用到的算法。對于每個算法,本書都有圖文并茂的翔實講解;每章節(jié)的后面都有針對該節(jié)知識點的例題講解,每道例題都是國內(nèi)外著名程序在線判題系統(tǒng)中的原題,而且對每道例題,都會從理解題意開始,詳細(xì)講解解題的思路,并附有完整的可以正確通過測試樣例的代碼,供讀者研究學(xué)習(xí)。除了例題,每一章的最后還有一些練習(xí)題供讀者鞏固本節(jié)中學(xué)到的知識,如果讀者對這些習(xí)題仍感覺無從下手,可以參考每道練習(xí)題后附帶的思路分析來幫助整理解題思路。
本書共分11章,第1章介紹Linux操作系統(tǒng)與C++編程環(huán)境;第2章簡單介紹初級算法;第3章介紹基礎(chǔ)數(shù)據(jù)結(jié)構(gòu);第4章介紹枚舉、遞推、遞歸、貪心、分治、哈希和二分等基礎(chǔ)算法設(shè)計;第5章介紹簡單排序算法;第6章介紹圖論的相關(guān)知識,包括最短路徑問題和最小生成樹問題的一些經(jīng)典算法;第7章介紹并查集和線段樹兩種高級數(shù)據(jù)結(jié)構(gòu);第8章介紹KMP、字典樹、Z算法和馬拉車算法等處理字符串的數(shù)據(jù)結(jié)構(gòu);第9章介紹搜索的相關(guān)算法,包括深度優(yōu)先搜索、寬度優(yōu)先搜索、雙向?qū)挾葍?yōu)先搜索、A*搜索和一些剪枝常用的策略;第10章介紹初等數(shù)論;第11章介紹動態(tài)規(guī)劃,重點介紹背包問題。本書的例題代碼都是集訓(xùn)隊成員測試提交通過的正確代碼。
梁冰,工程師,博士,大連理工大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院教師,主要從事創(chuàng)新創(chuàng)業(yè)教育、數(shù)據(jù)融合、數(shù)據(jù)挖掘等教學(xué)和科學(xué)研究工作。自2012年起擔(dān)任大連理工大學(xué)國際大學(xué)生程序設(shè)計競賽教練。
第1章 Linux操作系統(tǒng)與編程環(huán)境
1.1 Linux基礎(chǔ)
1.2 編譯器
1.2.1 Code::Blocks安裝
1.2.2 Code::Blocks編程環(huán)境配置
1.2.3 Code::Blocks編寫程序
1.3 編譯C++文件
1.4 ACM國際大學(xué)生程序設(shè)計競賽
1.5 自動評測系統(tǒng)
1.5.1 評測系統(tǒng)反饋
1.5.2 國內(nèi)知名評測系統(tǒng)
第2章 算法入門
2.1 快速冪取模算法
2.1.1 模運算
2.1.2 冪取模的計算
2.1.3 例題講解
2.2 算法
2.2.1 算法的定義
2.2.2 學(xué)習(xí)算法的意義
2.2.3 算法復(fù)雜度分析
第3章 基本數(shù)據(jù)結(jié)構(gòu)
3.1 基本線性數(shù)據(jù)結(jié)構(gòu)
3.1.1 線性表
3.1.2 棧
3.1.3 隊列
3.1.4 例題講解
3.2 二叉搜索樹
3,2.1 二叉搜索樹的定義
3.2.2 二叉搜索樹的實現(xiàn)
3.3 CH標(biāo)準(zhǔn)模板庫
3.3.1 VeCtOr
3.3.2 Set
3.3.3 map
3.3.4 priority_queue
3.3.5 例題講解
3.4 練習(xí)題
第4章 基本算法設(shè)計
4.1 枚舉
4.1.1 枚舉算法的定義
4.1.2 枚舉算法的解題過程
4.1.3 枚舉算法的特點
4.1.4 例題講解
4.2 遞推
4.2.1 遞推的概念
4.2.2 遞推與數(shù)列
4.2.3 斐波那契數(shù)列
4.2.4 遞推的兩種順序
4.2.5 例題講解
4.3 遞歸
4.3.1 遞歸的定義
4.3.2 遞歸的要求
4.3.3 遞歸與遞推
4.3.4 例題講解
4.4 貪心算法
4.4.1 貪心算法的概念
4.4.2 貪心算法的原理
4.4.3 例題講解
4.5 分治算法
4.5.1 分治的基本思想
4.5.2 分治的一般解題步驟
4.5.3 分治的特點
4.5.4 歸并排序
4.5.5 例題講解
4.6 模擬
4.6.1 高精度計算
4.6.2 矩陣運算
4.6.3 例題講解
4.7 哈希
4.7.1 直接尋址表
4.7.2 哈希表
4.7.3 例題講解
4.8 二分法
4.8.1 二分查找
4.8.2 二分逼近
4.8.3 求解性問題的二分策略
4.8.4 例題講解
4.9 練習(xí)題
第5章 排序算法
5.1 基于比較的排序算法
5.1.1 簡單排序
5.1.2 快速排序
5.1.3 限制和優(yōu)勢
5.2 基于統(tǒng)計的排序算法
5.2.1 計數(shù)排序
5.2.2 基數(shù)排序
5.3 例題講解
5.4 練習(xí)題
第6章 圖的基本算法
6.1 圖的定義及存儲方法
6.1.1 圖的定義
6.1.2 有向圖和無向圖
6.1.3 路徑與連通
6.1.4 圖的存儲結(jié)構(gòu)
6.2 圖的遍歷及拓?fù)渑判?/span>
6.2.1 圖的深度優(yōu)先遍歷
6.2.2 圖的寬度優(yōu)先遍歷
6.2.3 圖的拓?fù)渑判?/span>
6.2.4 例題講解
6.3 最小生成樹
6.3.1 Kruskal算法
6.3.2 Prim算法
6.4 單源最短路徑
6.4.1 Dijkstra算法
6.4.2 Bellman-Ford算法
6.4.3 SPFA算法
6.4.4 差分約束系統(tǒng)
6.4.5 例題講解
6.5 每對頂點的最短路徑
6.5.1 最短路徑和矩陣乘法
6.5.2 Floyd算法
6.5.3 例題講解
6.6 練習(xí)題
第7章 并查集和線段樹
7.1 并查集
7.1.1 并查集的基本概念
7.1.2 并查集的操作
7.1.3 例題講解
7.2 線段樹
7.2.1 線段樹的概念與性質(zhì)
7.2.2 線段樹的基本操作
7.2.3 例題講解
7.3 練習(xí)題
第8章 字符串問題
8.1 Trie樹
8.1.1 Trie樹的基本概念
8.1.2 Trie樹的操作
8.1.3 例題講解
8.2 KMP算法
……
第9章 搜索
第10章 初等數(shù)論
第11章 動態(tài)規(guī)劃入門
參考文獻(xiàn)