計算機算法與程序設計實踐

前言

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

內容概要

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

書籍目錄

第1章 基本知識1.1 算法與程序1.2 算法復雜性分析1.3 ACM／ICPC問題求解1.3.1 競賽的特點1.3.2 常見問題類型1.3.3 解題的幾點原則1.3.4 解題的幾點權衡第2章 數據結構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 訓練集第3章 字符串操作3.1 知識概述3.2 例題解析3.2.1 VerticalHistogram3.2.2 InstruensFabulam3.2.3 English-NumberTranslatot3.2.4 References3.3 訓練集第4章 模擬4.1 知識概述4.2 例題解析4.2.1 ALessSimpleTaskinWindows4.2.2 TheSameGame4.2.3 Robocode4.2.4 TempusetmobiliusTimeandmotion4.3 訓練集第5章 高精度計算5.1 知識概述5.2 例題解析5.2.1 ContinuousFractions5.2.2 Exponentiation5.2.3 Heritage5.3 訓練集第6章 遞歸與分治6.1 知識概述6.2 例題解析6.2.1 RedandBlack6.2.2 FractaI6.2.3 SticksProblem6.3 訓練集第7章 遞推7.1 知識概述7.2 例題解析7.2.1 Tiling7.2.2 WorldCupNoise7.2.3 ComputerTransformation7.2.4 ParallelExpectations7.3 訓練集第8章 貪心8.1 知識概述8.2 例題解析8.2.1 RadarInstallation8.2.2 GoneFishing8.2.3 Supermarket8.3 訓練集第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 訓練集第10章 搜索10.1 枚舉10.1.1 知識概述10.1.2 例題解析10.1.3 訓練集10.2 廣度優(yōu)先搜索10.2.1 知識概述10.2.2 例題解析10.2.3 訓練集10.3 深度優(yōu)先搜索10.3.1 知識概述10.3.2 例題解析10.3.3 訓練集10.4 啟發(fā)式搜索10.4.1 知識概述10.4.2 例題解析10.4.3 訓練集第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 訓練集第12章 數學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 訓練集第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 訓練集附錄A ACM／ICPC簡介附錄B OnlineJudge簡介附錄C 程序編碼風格附錄D 例題來源參考文獻

章節(jié)摘錄

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算機算法與程序設計實踐 PDF格式下載

---