計算機算法與程序設(shè)計實踐

前言

　　教育部計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會在《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn) 略研究報告暨專業(yè)規(guī)范（試行）》提出“加強學(xué)生實踐和動手能力的培養(yǎng)”。接著，在《高等學(xué)校 計算機科學(xué)與技術(shù)專業(yè)實踐教學(xué)體系與規(guī)范》中提出計算機專業(yè)高級人才的基本學(xué)科能力 包括：計算思維能力、算法設(shè)計與分析能力、程序設(shè)計與實現(xiàn)能力和系統(tǒng)分析、開發(fā)和應(yīng)用能 力。其中，計算思維能力主要包括形式化、模型化、抽象化能力和邏輯推演能力?！　〗o定一個問題，能夠?qū)⑵溥M(jìn)行抽象，建立模型；然后，綜合運用各種知識，設(shè)計出求解問 題的有效算法；最后，通過程序設(shè)計實現(xiàn)算法，以求解問題。這在當(dāng)前計算學(xué)科教學(xué)環(huán)節(jié)中， 越來越受到重視。為了強化學(xué)生對學(xué)科基本知識、基本方法、問題求解基本思想的掌握，需要 通過實踐教學(xué)，讓學(xué)生親身體驗，在實踐中理解并運用。通過實踐，不僅可以培養(yǎng)運用各種知 識解決實際問題的能力，而且還可以引導(dǎo)學(xué)生對未知進(jìn)行探索，培養(yǎng)創(chuàng)新能力。在我們的教 學(xué)實踐中，通過設(shè)置“問題求解與程序設(shè)計”、“信息學(xué)競賽”、“算法分析與設(shè)計”等課程，通過 鼓勵和組織學(xué)生參加ACM國際大學(xué)生程序設(shè)計競賽（ACM／ICPC），以圖提高學(xué)生基本學(xué) 科能力和動手實踐能力?！　cM／ICPC是世界上公認(rèn)的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計競賽。競賽充 分展示了大學(xué)生程序設(shè)計與問題求解能力，是一種行之有效的實踐教學(xué)形式。作為一種全新 的發(fā)現(xiàn)和培養(yǎng)計算學(xué)科頂尖學(xué)生的方式，AcM／IcPC得到全世界各大學(xué)的積極響應(yīng)。在 2008年第33屆ACM／ICPc亞洲區(qū)預(yù)選賽中，168所高校的1190支隊伍參加了杭州賽區(qū)的 網(wǎng)絡(luò)預(yù)選賽；137所高校的803支隊伍參加了合肥賽區(qū)的網(wǎng)絡(luò)預(yù)選賽；138所高校的905支 隊伍參加了北京賽區(qū)的網(wǎng)絡(luò)預(yù)選賽；151所高校的838支隊伍參加了成都賽區(qū)的網(wǎng)絡(luò)預(yù)選 賽；152所高校的1145支隊伍參加了哈爾濱賽區(qū)的網(wǎng)絡(luò)預(yù)選賽。　　本書主要目的是服務(wù)于計算學(xué)科相關(guān)專業(yè)的實踐教學(xué)環(huán)節(jié)，專注于問題求解。其特色在 于：面向?qū)嵺`、面向過程、面向?qū)嵱谩Ｑ刂皢栴}一建立模型一設(shè)計算法一程序設(shè)計一測試與 調(diào)試”的線索，綜合應(yīng)用各門課程知識?！　∪珪卜?3章。第1章介紹算法與程序、算法復(fù)雜性分析及ACM／ICPC題目特點、解 題原則等內(nèi)容；第2章至第13章分別介紹數(shù)據(jù)結(jié)構(gòu)、字符串、模擬、高精度計算、遞歸與分 治、遞推、貪心、動態(tài)規(guī)劃、搜索、圖論、數(shù)學(xué)和計算幾何的基本知識，針對若干相應(yīng)問題分析 和設(shè)計算法并編程求解，給出相關(guān)訓(xùn)練題集。

內(nèi)容概要

　　《計算機算法與程序設(shè)計實踐》專注于綜合應(yīng)用各種算法思想進(jìn)行程序設(shè)計以實現(xiàn)問題求解，其特色在于：面向?qū)嵺`、面向過程、面向?qū)嵱谩Ｔ陲L(fēng)格上追求簡單明快，并力圖展示問題求解過程，而不僅僅是給出結(jié)果。書中不僅分析題目、設(shè)計算法，還按照統(tǒng)一的程序設(shè)計風(fēng)格編程實現(xiàn)算法?！　∪珪卜?3章。第1章介紹算法與程序、算法復(fù)雜性分析及AcM／ICPC題目特點、解題原則等內(nèi)容；第2章至第13章分別介紹數(shù)據(jù)結(jié)構(gòu)、字符串、模擬、高精度計算、遞歸與分治、遞推、貪心、動態(tài)規(guī)劃、搜索、圖論、數(shù)學(xué)和計算幾何的基本知識，針對若干相應(yīng)問題分析和設(shè)計算法并編程求解。

書籍目錄

第1章 基本知識1.1 算法與程序1.2 算法復(fù)雜性分析1.3 ACM／ICPC問題求解1.3.1 競賽的特點1.3.2 常見問題類型1.3.3 解題的幾點原則1.3.4 解題的幾點權(quán)衡第2章 數(shù)據(jù)結(jié)構(gòu)2.1 知識概述2.1.1 線性表2.1.2 棧2.1.3 隊列2.1.4 集合2.1.5 樹2.1.6 圖2.1.7 查找2.1.8 排序2.2 例題解析2.2.1 TheMostFrequentNumbei2.2.2 BooleanExpressions2.2.3 PrinterQueue2.2.4 IsItATree2.2.5 FindingNemo2.2.6 TOYS2.2.7 Babelfish2.2.8 TheSuspects2.2.9 Atlantis2.2.10 Stars2.2.11 WordPuzzles2.3 訓(xùn)練集第3章 字符串操作3.1 知識概述3.2 例題解析3.2.1 VerticalHistogram3.2.2 InstruensFabulam3.2.3 English-NumberTranslatot3.2.4 References3.3 訓(xùn)練集第4章 模擬4.1 知識概述4.2 例題解析4.2.1 ALessSimpleTaskinWindows4.2.2 TheSameGame4.2.3 Robocode4.2.4 TempusetmobiliusTimeandmotion4.3 訓(xùn)練集第5章 高精度計算5.1 知識概述5.2 例題解析5.2.1 ContinuousFractions5.2.2 Exponentiation5.2.3 Heritage5.3 訓(xùn)練集第6章 遞歸與分治6.1 知識概述6.2 例題解析6.2.1 RedandBlack6.2.2 FractaI6.2.3 SticksProblem6.3 訓(xùn)練集第7章 遞推7.1 知識概述7.2 例題解析7.2.1 Tiling7.2.2 WorldCupNoise7.2.3 ComputerTransformation7.2.4 ParallelExpectations7.3 訓(xùn)練集第8章 貪心8.1 知識概述8.2 例題解析8.2.1 RadarInstallation8.2.2 GoneFishing8.2.3 Supermarket8.3 訓(xùn)練集第9章 動態(tài)規(guī)劃9.1 知識概述9.2 例題解析9.2.1 Bridgingsignals9.2.2 HumanGeneFunctions9.2.3 WashingClothes9.2.4 TotheMax9.2.5 AppleTree9.2.6 Coloredstones9.3 訓(xùn)練集第10章 搜索10.1 枚舉10.1.1 知識概述10.1.2 例題解析10.1.3 訓(xùn)練集10.2 廣度優(yōu)先搜索10.2.1 知識概述10.2.2 例題解析10.2.3 訓(xùn)練集10.3 深度優(yōu)先搜索10.3.1 知識概述10.3.2 例題解析10.3.3 訓(xùn)練集10.4 啟發(fā)式搜索10.4.1 知識概述10.4.2 例題解析10.4.3 訓(xùn)練集第11章 圖論11.1 知識概述11.2 例題解析11.2.1 StockbrokerGrapevine11.2.2 PicnicPlanning11.2.3 SortingItAllOut11.2.4 SPF11.2.5 PowerNetwork11.2.6 PurifyingMachine11.2.7 PlayonWords11.2.8 ChannelAllocation11.3 訓(xùn)練集第12章 數(shù)學(xué)12.1 知識概述12.2 例題解析12.2.1 PrimeDistance12.2.2 SumofFactorials12.2.3 Biorhythms12.2.4 IDCodes12.2.5 GameofConnections12.2.6 NecklaceofBeads12.2.7 BacktoMotherShip12.2.8 RandomWalk12.2.9 CalendarGame12.3 訓(xùn)練集第13章 計算幾何13.1 知識概述13.2 例題解析13.2.1 TheDoors13.2.2 ThatNiceEulerCircuit13.2.3 ARoundPeginaGroundHole13.2.4 Splitconvexpolygon13.2.5 Area13.2.6 ArtGallery13.2.7 SurroundtheTrees13.2.8 VivaConfetti13.2.9 CenterofSymmetry13.3 訓(xùn)練集附錄A ACM／ICPC簡介附錄B OnlineJudge簡介附錄C 程序編碼風(fēng)格附錄D 例題來源參考文獻(xiàn)

章節(jié)摘錄

　　12.計算幾何　　指主要使用計算幾何相關(guān)知識設(shè)計算法求解的題目。包括位置關(guān)系相關(guān)問題（如點與多邊形的位置關(guān)系、線段與線段的位置關(guān)系和多邊形與多邊形的位置關(guān)系等）、周長與面積問題（如多邊形并或交的周長與面積等）、凸包問題（如平面點集的凸包）、多邊形的可見核問題和三角剖分問題等?！　?3.特殊問題　　指需要創(chuàng)造新算法進(jìn)行求解的題目。這類題目一般難度較大。　　1.3.3 解題的幾點原則　　制定一些合理原則，并遵照這些原則求解問題，可以大大提高解題效率。下面，介紹幾點基本原則。　　1.評估題目難易程度　　給定題目，應(yīng)養(yǎng)成首先對題目難易程度進(jìn)行評估的習(xí)慣，切忌看到一個感覺順手的題目就馬上開始編程求解。這個習(xí)慣在競賽中尤為重要，因為競賽的總時間是一定的，根據(jù)競賽排名規(guī)則，最好的策略就是先做最簡單的題目，并用最短的時間、最少的提交次數(shù)正確求解。這樣，才能有利于良好心態(tài)的保持，才能爭取更多有效時間求解其余題目。　　2.警惕思維定勢　　作一些思維方面的準(zhǔn)備是非常有必要的，但務(wù)必盡量保持清醒靈活的頭腦，切忌思維定勢。對于一個題目，要嚴(yán)格按照步驟分析設(shè)計算法，使其在給定時空限制下求解問題，并考慮是否有更簡捷的算法。切忌想到一個貌似可行的方法就急著編程求解，這在大多數(shù)情況下將導(dǎo)致錯誤的結(jié)果。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計算機算法與程序設(shè)計實踐 PDF格式下載

---