新編實(shí)用算法分析與程序設(shè)計(jì)

內(nèi)容概要

　　本書是一部程序設(shè)計(jì)競賽教程。書中首先講述了算法的基本概念、各種排序與解題的方法及策略，然后論述了初等數(shù)論、計(jì)算幾何學(xué)、搜索和圖論的有關(guān)算法，最后討論了動態(tài)規(guī)劃。本書不僅從教學(xué)的角度詳細(xì)講解算法理論，而且從競賽的角度對經(jīng)典習(xí)題進(jìn)行詳細(xì)解析，培養(yǎng)學(xué)生靈活運(yùn)用算法的能力?！　”緯瓤梢宰鳛榇髮Ｔ盒Ｓ?jì)算機(jī)專業(yè)算法類課程的教材，亦可以作為大中學(xué)校計(jì)算機(jī)競賽活動的培訓(xùn)教材，還可供計(jì)算機(jī)軟硬件研發(fā)人員參考。

作者簡介

　　王建德，著名的信息學(xué)奧林匹克競賽金牌教練，國務(wù)院特殊津貼專家，中學(xué)特級教師。他所輔導(dǎo)的學(xué)生在國際奧林匹克信息學(xué)競賽中獲7金，2銀，2銅的信奉異教成績。先后出版了22本關(guān)于程序設(shè)計(jì)和算法的學(xué)術(shù)專著，其中《實(shí)用算法的分析與程序設(shè)計(jì)》廣受好評，長期以來是國內(nèi)各類程序設(shè)計(jì)競賽的必備教程。吳永輝：博士，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系副教授，ACM-ICPC中國賽區(qū)指導(dǎo)委員會成員，復(fù)旦大學(xué)ACM程序設(shè)計(jì)競賽隊(duì)教練。自2001年起連續(xù)帶隊(duì)進(jìn)入ACM-ICPC世界總決賽，并取得過世界第6名的佳績。主要研究方向?yàn)閿?shù)據(jù)庫，在《計(jì)算機(jī)研究與發(fā)展》，《軟件學(xué)報(bào)》以及重大學(xué)術(shù)會議上發(fā)表多篇論文，參與譯著《數(shù)據(jù)通信與網(wǎng)絡(luò)》和《數(shù)據(jù)通信，計(jì)算機(jī)網(wǎng)絡(luò)與開放系統(tǒng)》。

書籍目錄

第1章 緒論1.1 算法的基本定義1.2 算法的空間復(fù)雜度1.2.1 壓縮存儲技術(shù)1.2.2 原地工作1.3 算法的時(shí)間復(fù)雜度1.3.1 基本運(yùn)算1.3.2 輸入規(guī)模1.3.3 輸入情況1.3.4 時(shí)間復(fù)雜度的階1.4 優(yōu)化時(shí)間效率的方法1.4.1 編程實(shí)現(xiàn)算法時(shí)注意細(xì)節(jié)優(yōu)化1.4.2 尋找解題思路時(shí)盡可能考慮最優(yōu)性1.5 實(shí)際生活中常見的算法問題第2章 排序、順序統(tǒng)計(jì)與解題的基本策略2.1 計(jì)數(shù)排序與貪心策略2.1.1 計(jì)數(shù)排序2.1.2 貪心策略2.2 “二分”思想與快速排序2.2.1 分類和分治思想2.2.2 快速排序采用二分法2.2.3 快速排序和二分法在順序統(tǒng)計(jì)問題上的應(yīng)用2.3 堆排序的思想與應(yīng)用2.3.1 在調(diào)整中保持堆性質(zhì)2.3.2 建堆2.3.3 堆排序2.4 數(shù)據(jù)有序化2.4.1 預(yù)處理階段的數(shù)據(jù)有序化2.4.2 實(shí)時(shí)處理階段的數(shù)據(jù)有序化習(xí)題第3章 初等數(shù)論的有關(guān)算法3.1 計(jì)算a和b最大公約數(shù)的歐幾里得公式gcd(a， b)3.2 計(jì)算N的最大互質(zhì)數(shù)3.3 歐幾里得公式推廣：計(jì)算最大公約數(shù)的線性組合3.4 計(jì)算同余方程ax≡b(mod n)(n＞0)3.5 求解同余式組3.6 解不定方程ax+by=c3.7 初等數(shù)論知識的應(yīng)用3.7.1 運(yùn)用反復(fù)平方法求數(shù)的冪模n3.7.2 素?cái)?shù)的測試3.7.3 整數(shù)的因子分解習(xí)題第4章 計(jì)算幾何學(xué)的有關(guān)算法4.1 線段的性質(zhì)4.2 計(jì)算兩條相交線段的交點(diǎn)4.3 判斷任意一組線段中是否存在相交情況4.4 計(jì)算線段p1p2的中垂線方程4.5 計(jì)算凸多邊形的重心位置和面積4.6 尋找最近點(diǎn)對4.7 計(jì)算包含平面所有點(diǎn)的二維凸包4.8 將凸包問題由二維拓展至三維4.8.1 計(jì)算三維凸包體積的基本思想4.8.2 計(jì)算由3個(gè)空間點(diǎn)組成的劈面三棱柱的體積V(R( i))4.8.3 計(jì)算包含點(diǎn)集p的三維凸包體積4.9 計(jì)算幾何類問題的類型和應(yīng)對的基本方法習(xí)題第5章 搜索的有關(guān)算法第6章 圖論的有關(guān)算法參考文獻(xiàn)

章節(jié)摘錄

　　第1章　緒論　　什么是算法？為什么要對算法進(jìn)行研究？相對于其他信息技術(shù)來說，算法的作用是什么？在實(shí)際生活中，算法有什么應(yīng)用價(jià)值？衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是什么？本章將圍繞這些問題展開討論?！　?.1　算法的基本定義　　簡單來說，所謂算法（algorithm）就是明確的計(jì)算過程，它取一個(gè)或一組值作為輸入，并生成一個(gè)或一組值作為輸出。亦即，算法就是一系列的計(jì)算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果，　　如圖1.1所示?！　∥覀冞€可以將算法看作是一種工具，用來解決可以抽象出計(jì)算模型的問題。在表述該問題時(shí)，必須用嚴(yán)謹(jǐn)?shù)恼Z言規(guī)定所需的輸入／輸出關(guān)系。與之對應(yīng)的算法則描述了一個(gè)特定的計(jì)算過程，用于實(shí)現(xiàn)這一輸入／輸出關(guān)系，如下所示?！　≥斎耄河蒼個(gè)數(shù)構(gòu)成的一個(gè)序列（a1，a2，…an）?！　≥敵觯狠敵鲆粋€(gè)重排的序列（a1`，a2`，…an`）。，使得a1`≤a2`≤…≤an`?！　⌒枰赋龅氖?，問題的表述方式是多樣化的，并不一定像上面例子這么抽象呆板，例如，許多試題就采用了生動趣味的故事形式。而這里所說的語言嚴(yán)謹(jǐn)，是針對抽象計(jì)算模型而言。也就是說求解的目標(biāo)是什么，給出了哪些已知信息、顯式條件或隱含條件，最后應(yīng)該用什么樣的數(shù)據(jù)形式表達(dá)計(jì)算結(jié)果，必須描述清楚，切不能模棱兩可或者產(chǎn)生歧義。同樣，與問題對應(yīng)的計(jì)算過程可以用自然語言、程序設(shè)計(jì)語言甚至硬件設(shè)計(jì)等形式來表達(dá)。不論采用哪種形式，解決問題的每一個(gè)步驟都必須準(zhǔn)確定義，這是由于我們是和計(jì)算機(jī)打交道，稍有含糊則風(fēng)馬牛不相及。自然語言傳遞的信息，從語意上來看，可能會有不明之處，但我們處理它們時(shí)可根據(jù)上下文信息或平時(shí)習(xí)慣等來推理并準(zhǔn)確地接受它，而計(jì)算機(jī)卻不能。尤其是編程時(shí)，要用程序設(shè)計(jì)的范式語言精　　確定義每一個(gè)步驟，千萬不要誤以為自己懂了計(jì)算機(jī)也會懂?！　∥覀兒饬恳粋€(gè)算法好壞的標(biāo)準(zhǔn)主要有兩個(gè)：正確性和時(shí)效性。　?。?）算法的正確性。如果一個(gè)算法使其每一個(gè)輸入實(shí)例都能在輸出正確的結(jié)果后停止，則稱它是正確的。

編輯推薦

　　作者編著的《實(shí)用算法的分析與程序設(shè)計(jì)》一書曾經(jīng)在全國信息學(xué)奧林匹克競賽產(chǎn)生了廣泛和深遠(yuǎn)的影響。本書是作者在該書基礎(chǔ)上十年磨一劍、精心編寫而成的，反映了近年來程序設(shè)計(jì)教育和競賽培訓(xùn)活動出現(xiàn)的新趨勢。全書不僅從教學(xué)的角度詳細(xì)講解算法的理論，而且從競賽的角度對經(jīng)典習(xí)題進(jìn)行詳細(xì)解析，重在培養(yǎng)學(xué)生靈活運(yùn)用算法的能力。　　本書是一部優(yōu)秀的算法參考書，更是各層次程序設(shè)計(jì)競賽培訓(xùn)不可錯過的輔導(dǎo)書?！　”緯厣骸　〔捎媒Y(jié)構(gòu)清晰、移植性強(qiáng)且貼近自然語言表述的類程序設(shè)計(jì)語言。　　各章節(jié)之間有著緊密的內(nèi)在聯(lián)系，但是彼此又相對獨(dú)立?！　±}多采用一題多解、多向求解的方法，且各章均有與其內(nèi)容相匹配的練習(xí)題?！　￠_辟專門網(wǎng)站（http：／／admis.fudan.edu.cn／publications.htm），為讀者提供大量的經(jīng)典例題和測試數(shù)據(jù)。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    新編實(shí)用算法分析與程序設(shè)計(jì) PDF格式下載

---