ACM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程

前言

從1970年開(kāi)始，ACM／ICPC賽事就影響著計(jì)算機(jī)與信息專(zhuān)業(yè)的許多大學(xué)生，引導(dǎo)著他們應(yīng)用計(jì)算機(jī)技術(shù)展示自己分析問(wèn)題解決問(wèn)題的才能。哈爾濱工程大學(xué)于2005年開(kāi)始積極投身于ACM／ICPC活動(dòng)中。時(shí)至今日，令我欣慰的是，從僅有的幾名程序設(shè)計(jì)愛(ài)好者到如今上百人參與集訓(xùn)的規(guī)模，我們的校代表隊(duì)已形成了一套自己的訓(xùn)練方法。在多年的磨煉中，我看到我們的隊(duì)員走了一些彎路，也經(jīng)歷了一些波折。經(jīng)過(guò)不斷的嘗試、努力，以及與其他高校參賽選手積極的交流，他們漸漸成長(zhǎng)起來(lái)。今天，他們把自己的經(jīng)驗(yàn)編輯成為一本系統(tǒng)的教材，既是對(duì)自己多年來(lái)訓(xùn)練學(xué)習(xí)的總結(jié)，也為了使更多的ACM／ICPC愛(ài)好者有“據(jù)”可依。

內(nèi)容概要

　　《ACM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程》以循序漸進(jìn)的方式對(duì)ACM程序設(shè)計(jì)競(jìng)賽中所涉及的基本題型和知識(shí)點(diǎn)進(jìn)行了綜合的介紹。全書(shū)共分9章，包括基礎(chǔ)知識(shí)講解、典型題目分析和算法設(shè)計(jì)，每道例題均給出完整的源程序作為參考。內(nèi)容涵蓋了基礎(chǔ)算法、數(shù)據(jù)結(jié)構(gòu)、字符串、搜索、圖論、動(dòng)態(tài)規(guī)劃、組合數(shù)學(xué)和初等數(shù)論等。
　　《ACM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程》內(nèi)容全面，針對(duì)性強(qiáng)，言簡(jiǎn)意賅，講解透徹，通俗易懂，圖例豐富，所有源代碼均可進(jìn)行評(píng)測(cè)?！禔CM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程》作為ACM程序設(shè)計(jì)競(jìng)賽的培訓(xùn)教程，不僅為大學(xué)生們提供了競(jìng)賽入門(mén)的指導(dǎo)，而且對(duì)參賽學(xué)生拓展解題思路和提高訓(xùn)練水平也有很大的幫助。《ACM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程》也可供喜愛(ài)程序設(shè)計(jì)的學(xué)生以及從事算法設(shè)計(jì)的教師學(xué)習(xí)參考。

書(shū)籍目錄

第1章 基礎(chǔ)算法
1.1 分治
1.2 遞歸
1.3 枚舉
1.4 貪心
第2章 排序、查找算法
2.1 基本排序算法
2.1.1 插入排序
2.1.2 冒泡排序
2.1.3 快速排序
2.1.4 其他排序
2.2 基本查找算法
2.2.1 順序查找
2.2.2 折半查找
2.3 實(shí)例分析
2.4 小結(jié)
第3章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
3.1 常用數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介
3.1.1 線段樹(shù)簡(jiǎn)介
3.1.2 并查集簡(jiǎn)介
3.1.3 樹(shù)狀數(shù)組簡(jiǎn)介
3.2 實(shí)例分析
第4章 字符串
4.1 字符串匹配
4.1.1 樸素的字符串匹配算法
4.1.2 KMP算法
4.1.3 其他匹配算法
4.2 實(shí)例分析
4.3 小結(jié)
第5章 搜索算法
5.1 基本搜索算法
5.1.1 遞歸與迭代
5.1.2 深度優(yōu)先搜索與廣度優(yōu)先搜索
5.1.3 回溯
5.2 搜索算法的一些優(yōu)化
5.2.1 剪枝函數(shù)
5.2.2 雙向廣度搜索
5.3 實(shí)例分析
5.4 小結(jié)
第6章 圖論算法
6.1 最短路徑
6.1.1 Dijkstra算法
6.1.2 Floyd算法
6.1.3 Bellman-Ford算法
6.2 最小生成樹(shù)
6.2.1 Kruskal算法
6.2.2 Prim算法
6.3 最大匹配--匈牙利算法
6.4 最優(yōu)權(quán)匹配問(wèn)題
6.4.1 理論基礎(chǔ)
6.4.2 基本思想
6.4.3 樣例代碼
6.5 割點(diǎn)、割邊以及連通分量
6.5.1 理論基礎(chǔ)
6.5.2 求割點(diǎn)
6.5.3 求強(qiáng)連通分量
6.6 網(wǎng)絡(luò)流
6.6.1 理論基礎(chǔ)
6.6.2 最大流問(wèn)題
6.6.3 最小費(fèi)用最大流問(wèn)題
6.7 實(shí)例分析
6.8 小結(jié)
第7章 動(dòng)態(tài)規(guī)劃算法
7.1 基本思想
7.2 基本概念
7.3 基本原理
7.3.1 最優(yōu)化原理
7.3.2 無(wú)后效性
7.4 基本步驟
7.5 經(jīng)典例子
7.6 實(shí)例分析
7.7 小結(jié)
第8章 計(jì)算幾何基礎(chǔ)
8.1 矢量
8.1.1 矢量的概念
8.1.2 矢量加減法
8.1.3 矢量叉積
8.1.4 矢量叉積的應(yīng)用
8.2 包含關(guān)系
8.2.1 判斷圖形是否包含在矩形中
8.2.2 判斷圖形是否包含在多邊形中
8.2.3 判斷圖形是否包含在圓中
8.3 凸包
8.3.1 凸包的概念
8.3.2 凸包的求法
8.4 實(shí)例分析
第9章 數(shù)論
9.1 基本數(shù)學(xué)算法
9.1.1 素?cái)?shù)篩選
9.1.2 最大公約數(shù)
9.1.3 快速乘方
9.2 實(shí)例分析
附錄A 綜合訓(xùn)練題
A.1 LuckyBird
A.2 Josephusproblem
A.3 Counter Strike
A.4 Gauss Elimination
A.5 The Math Problem
A.6 Mobile phones
A.7 Japan
A.8 骨灰級(jí)玩家考證篇
A.9 括號(hào)匹配
A.10 食物鏈

章節(jié)摘錄

插圖：搜索算法是利用計(jì)算機(jī)的高性能來(lái)有目的的窮舉一個(gè)問(wèn)題的部分或所有的可能情況，從而求出問(wèn)題的解的一種方法。搜索過(guò)程實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹(shù)并尋找符合目標(biāo)狀態(tài)的結(jié)點(diǎn)的過(guò)程。所有的搜索算法從其最終的算法實(shí)現(xiàn)上來(lái)看，都可以劃分成兩個(gè)部分——控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)，而所有的算法的優(yōu)化和改進(jìn)主要都是通過(guò)修改其控制結(jié)構(gòu)來(lái)完成的。5.1 基本搜索算法5.1.1 遞歸與迭代遞歸程序設(shè)計(jì)是編程語(yǔ)言設(shè)計(jì)中的一種重要的設(shè)計(jì)方法，它使許多問(wèn)題簡(jiǎn)單化，易于求解。遞歸的特點(diǎn)：函數(shù)或過(guò)程直接的或間接的調(diào)用它自己本身。所謂迭代，就是在程序中用同一個(gè)變量存放每一次推算出的值，每一次循環(huán)都執(zhí)行同一語(yǔ)句，給同一變量賦以新值，即用一個(gè)新值代替舊值。5.1.2 深度優(yōu)先搜索與廣度優(yōu)先搜索深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對(duì)擴(kuò)展結(jié)點(diǎn)選取上。由于其保留了所有的前驅(qū)結(jié)點(diǎn)，所以在產(chǎn)生后繼結(jié)點(diǎn)時(shí)可以去掉一部分重復(fù)的結(jié)點(diǎn)，從而提高了搜索效率。

編輯推薦

《ACM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程》：教育部“高等學(xué)校教學(xué)質(zhì)量與教學(xué)改革工程”立項(xiàng)項(xiàng)目

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    ACM程序設(shè)計(jì)競(jìng)賽基礎(chǔ)教程 PDF格式下載

---