算法設(shè)計(jì)、分析與實(shí)現(xiàn)從入門到精通

前言

　　算法作為數(shù)學(xué)的一個(gè)分支已經(jīng)存在幾百年了。然而，算法真正煥發(fā)青春得到長(zhǎng)足的發(fā)展，還是發(fā)生在20世紀(jì)電子計(jì)算機(jī)發(fā)明的時(shí)代。隨著計(jì)算機(jī)技術(shù)的廣泛應(yīng)用，人們?cè)絹碓角宄卣J(rèn)識(shí)到，作為計(jì)算機(jī)科學(xué)與工程最主要的技術(shù)——程序設(shè)計(jì)，其靈魂就是解決問題的算法?！　∧芊裉峁┮槐炯饶茏審V大讀者清晰、輕松地理解算法思想，又能為讀者提供算法的程序?qū)崿F(xiàn)各種關(guān)鍵技術(shù)建議的書是作者一個(gè)很長(zhǎng)時(shí)間的思考?，F(xiàn)在擺在讀者面前的這本書，就是這一思考的結(jié)果。作者希望本書在讀者研習(xí)算法與程序設(shè)計(jì)時(shí)不僅是書桌前或是床頭邊的參考書，更多的是計(jì)算機(jī)旁的參考書?！　”緯劝此惴ㄔO(shè)計(jì)技巧分類為漸增型算法、遞歸分治算法、動(dòng)態(tài)規(guī)劃算法、貪婪算法、回溯算法和圖的搜索算法等前6章。每章對(duì)2～3個(gè)經(jīng)典問題針對(duì)一種算法設(shè)計(jì)技巧，給出解決問題的算法，并分析算法的時(shí)間復(fù)雜度。筆者認(rèn)為，對(duì)于初學(xué)者來說，按算法的設(shè)計(jì)方法劃分章節(jié)，算法思想的闡述比較集中，有利于入門。一旦具備了算法設(shè)計(jì)的基本方法，按應(yīng)用領(lǐng)域劃分專題深入學(xué)習(xí)，讀者可以應(yīng)用已學(xué)的方法綜合起來解決比較復(fù)雜的問題。第7章的線性規(guī)劃和第8章的計(jì)算幾何可以算作這部分內(nèi)容。在此基礎(chǔ)上，讀者可以更進(jìn)一步探討更前沿的隨機(jī)算法、近似算法和并行算法等現(xiàn)代算法設(shè)計(jì)方法。本書之所以按照這樣的8章編排，還有一個(gè)重要原因是它們之間有一定的前后邏輯關(guān)系：第1章漸增型算法和第2章分治算法是最基本的算法，并且在這兩章內(nèi)容展開的同時(shí)我們還介紹了后面各章所需要的數(shù)據(jù)結(jié)構(gòu)，例如第2章介紹的優(yōu)先隊(duì)列就是第4章討論貪婪算法時(shí)所需要的。建議讀者以本書的章節(jié)順序研讀，特別是實(shí)現(xiàn)的程序中也有很多是前后呼應(yīng)的代碼段?！　∷惴ɡ碚搶?duì)于程序設(shè)計(jì)實(shí)踐的指導(dǎo)意義已經(jīng)被大家所接受，但不管是在校學(xué)生還是已踏上職業(yè)征程的程序員，很多人對(duì)算法學(xué)習(xí)都有一種“枯燥繁難”的先人之見。如何有效地學(xué)習(xí)算法的設(shè)計(jì)與分析，是本書試圖與讀者一起探討的最重要的目標(biāo)之一。其實(shí)，算法都是針對(duì)具體問題的。對(duì)于要解決的問題進(jìn)行深入理解與分析，是設(shè)計(jì)出正確有效的算法的前提。然而，“深入理解與分析”似乎是個(gè)模糊概念，怎樣的“度”才能認(rèn)為是對(duì)問題深入理解了呢？計(jì)算學(xué)科提出了一個(gè)非常重要的“標(biāo)準(zhǔn)”：簡(jiǎn)單地說，能夠把一個(gè)問題輸入與輸出準(zhǔn)確地提煉并表述出來，就可以認(rèn)為是理解了這個(gè)問題。這樣對(duì)問題的描述稱為“問題的形式化描述”。一旦形式化地描述出了問題的輸入與輸出，也就能準(zhǔn)確地把握住算法解決問題所需要的條件和所要達(dá)到的目標(biāo)。換句話說，設(shè)計(jì)算法是要在問題的輸入與輸出之間架起一座通達(dá)的橋梁。本書以此為目標(biāo)，無論是對(duì)正文中討論的問題還是“動(dòng)手做”題目中的問題或者是作為應(yīng)用的ICPC問題，我們都給出其形式化描述。有了問題的輸入與輸出的數(shù)據(jù)表示，運(yùn)用人們的常識(shí)、數(shù)學(xué)知識(shí)和科學(xué)知識(shí)建立起從輸入到輸出之間的對(duì)應(yīng)關(guān)系，這就是算法?！　∷惴梢杂米匀徽Z言或是圖形等工具加以描述，但要將算法作為計(jì)算機(jī)程序的設(shè)計(jì)藍(lán)圖，則需要將其無歧義地表述出來。用偽代碼表述算法是迄今為止人們所使用的最有效的方法。計(jì)算機(jī)程序設(shè)計(jì)語言當(dāng)然也能做到無歧義地描述算法。事實(shí)上，市場(chǎng)上也有以某種具體的程序設(shè)計(jì)語言為描述工具的算法書籍，但這樣的圖書往往要面對(duì)一個(gè)兩難問題：一方面，若要使具體語言描述的算法能直接運(yùn)行，則必須做諸如變量聲明、用該語言所提供的方式表示各種復(fù)雜的數(shù)學(xué)表達(dá)式以及其他操作等各種技術(shù)細(xì)節(jié)工作。這樣就會(huì)大大降低算法描述的可讀性，妨礙讀者對(duì)算法思想本身的理解與接受。另一方面，如果為提高算法描述的可讀性而省略上述的各種技術(shù)細(xì)節(jié)，則仍然回到偽代碼描述的起點(diǎn)，讓讀者在實(shí)現(xiàn)程序時(shí)有隔靴抓癢的感覺。

內(nèi)容概要

　　本書第1章～第6章按算法設(shè)計(jì)技巧分成漸增型算法、分治算法、動(dòng)態(tài)規(guī)劃算法、貪婪算法、回溯算法和圖的搜索算法。每章針對(duì)一些經(jīng)典問題給出解決問題的算法，并分析算法的時(shí)間復(fù)雜度。這樣對(duì)于初學(xué)者來說，按照算法的設(shè)計(jì)方法劃分，算法思想的闡述比較集中，有利于快速入門理解算法的精髓所在。一旦具備了算法設(shè)計(jì)的基本方法，按應(yīng)用領(lǐng)域劃分專題深入學(xué)習(xí)，讀者可以結(jié)合已學(xué)的方法綜合起來解決比較復(fù)雜的問題。本書第7章的線性規(guī)劃和第8章的計(jì)算幾何是綜合算法部分，通過學(xué)習(xí)這些內(nèi)容，讀者將進(jìn)一步地學(xué)習(xí)更前沿的隨機(jī)算法、近似算法和并行算法等現(xiàn)代算法設(shè)計(jì)方法和實(shí)戰(zhàn)技巧。　　本書特色是按照算法之間邏輯關(guān)系編排學(xué)習(xí)順序，并對(duì)每一個(gè)經(jīng)典算法，都給出了完整的C/C++/Java三種主流編程語言的實(shí)現(xiàn)程序，是一本既能讓讀者清晰、輕松地理解算法思想，又能讓讀者編程實(shí)現(xiàn)算法的實(shí)用書籍。建議讀者對(duì)照本書在計(jì)算機(jī)上自己創(chuàng)建項(xiàng)目、文件，進(jìn)行錄入、調(diào)試程序等操作，從中體會(huì)算法思想的精髓，體驗(yàn)編程成功帶來的樂趣。

書籍目錄

第1章　集腋成裘——漸增型算法　　1.1　算法設(shè)計(jì)與分析　　1.2　插入排序算法　　　1.2.1　算法描述與分析　　　1.2.2　程序?qū)崿F(xiàn)　　　1.2.3　應(yīng)用——贏得舞伴　　1.3　兩個(gè)有序序列的合并算法　　　1.3.1　算法描述與分析　　　1.3.2　程序?qū)崿F(xiàn)　　1.4　序列的劃分　　　1.4.1　算法描述與分析　　　1.4.2　程序?qū)崿F(xiàn)　　1.5　小結(jié)　第2章　化整為零——分治算法　　2.1　Hanoi塔問題與遞歸算法　　　2.1.1　算法的描述與分析　　　2.1.2　程序?qū)崿F(xiàn)　　　2.1.3　應(yīng)用——新Hanoi塔游戲　　2.2　歸并排序算法　　　2.2.1　算法描述與分析　　　2.2.2　程序?qū)崿F(xiàn)　　　2.2.3　應(yīng)用——讓舞伴更開心　　2.3　快速排序算法　　　2.3.1　算法描述與分析　　　2.3.2　程序?qū)崿F(xiàn)　　2.4　堆的實(shí)現(xiàn)　　　2.4.1　堆的概念及其創(chuàng)建　　　2.4.2　程序?qū)崿F(xiàn)　　2.5　堆排序　　　2.5.1　算法描述與分析　　　2.5.2　程序?qū)崿F(xiàn)　　2.6　基于二叉堆的優(yōu)先隊(duì)列　　　2.6.1　算法描述與分析　　　2.6.2　程序?qū)崿F(xiàn)　　2.7　關(guān)于排序算法　　　2.7.1　比較型排序算法的時(shí)間復(fù)雜度　　　2.7.2　C/C++/Java提供的排序函數(shù)(方法)　　　2.7.3　應(yīng)用——環(huán)法自行車賽　　2.8　小結(jié)　第3章　記表備查——?jiǎng)討B(tài)規(guī)劃算法　　3.1　矩陣鏈乘法　　　3.1.1　算法描述與分析　　　3.1.2　程序?qū)崿F(xiàn)　　　3.1.3　應(yīng)用——牛牛玩牌　　3.2　最長(zhǎng)公共子序列　　　3.2.1　算法描述與分析　　　3.2.2　程序?qū)崿F(xiàn)　　　3.2.3　算法的應(yīng)用　　3.3　背包問題　　　3.3.1　算法描述與分析　　　3.3.2　程序?qū)崿F(xiàn)　　　3.3.3　算法的應(yīng)用　　3.4　帶權(quán)有向圖中任意兩點(diǎn)間的最短路徑　　　3.4.1　算法描述與分析　　　3.4.2　程序?qū)崿F(xiàn)　　　3.4.3　應(yīng)用——牛牛聚會(huì)　　3.5　小結(jié)　第4章　高效的選擇——貪婪算法　　4.1　活動(dòng)選擇問題　　　4.1.1　算法描述與分析　　　4.1.2　程序?qū)崿F(xiàn)　　　4.1.3　貪婪算法與動(dòng)態(tài)規(guī)劃　　　4.1.4　應(yīng)用——海岸雷達(dá)　　4.2　Huffman編碼　　　4.2.1　算法描述與分析　　　4.2.2　程序?qū)崿F(xiàn)　　　4.2.3　應(yīng)用——Huffman樹　　4.3　最小生成樹　　　4.3.1　算法描述與分析　　　4.3.2　程序?qū)崿F(xiàn)　　　4.3.3　應(yīng)用——北方通信網(wǎng)　　4.4　單源最短路徑問題　　　4.4.1　算法描述與分析　　　4.4.2　程序?qū)崿F(xiàn)　　　4.4.3　應(yīng)用——西氣東送　　4.5　小結(jié)　第5章　艱苦卓絕——回溯算法　第6章　圖的搜索算法　第7章　集組合優(yōu)化問題之大成——線性規(guī)劃　第8章　圖形學(xué)基礎(chǔ)——計(jì)算幾何　附錄　參考文獻(xiàn)　

章節(jié)摘錄

　　1.1 算法設(shè)計(jì)與分析　　1.什么是算法　　眾所周知，算法是程序的靈魂。只有對(duì)需要解決的計(jì)算問題有一個(gè)正確的算法，才可能編寫出解決此問題的程序。所謂算法就是解決一個(gè)計(jì)算問題的一系列計(jì)算步驟有序、合理的排列。對(duì)一個(gè)具體問題（有確定的輸入數(shù)據(jù)）依次執(zhí)行一個(gè)正確的算法中的各操作步驟，最終將得到該問題的解。算法研究有著悠久的歷史，內(nèi)容極其豐富。人們對(duì)各種典型的問題研究出了很多經(jīng)典的算法設(shè)計(jì)方法。例如，本書詳細(xì)討論的漸增型算法、分治算法、動(dòng)態(tài)規(guī)劃、貪婪策略和回溯算法等都是具有代表性的經(jīng)典算法設(shè)計(jì)方法。對(duì)這些方法的學(xué)習(xí)，可以為我們?cè)诮鉀Q各種具體問題時(shí)設(shè)計(jì)出正確、高效的算法提供有益的啟示。　　2.算法分析基本概念　　解決一個(gè)問題，算法不必是唯一的。對(duì)表示問題的數(shù)據(jù)的不同組織方式（數(shù)據(jù)結(jié)構(gòu)），解決問題的不同策略（算法思想）將導(dǎo)致不同的算法。解決同一問題的不同算法，消耗的時(shí)間和空間資源量有所不同。算法運(yùn)行所需要的計(jì)算機(jī)資源的量稱為算法的復(fù)雜性。一般來說，解決同一問題的算法，需要的資源量越少，我們認(rèn)為越優(yōu)秀。計(jì)算算法運(yùn)行所需資源量的過程稱為算法復(fù)雜性分析，簡(jiǎn)稱為算法分析。理論上，算法分析既要計(jì)算算法的時(shí)間復(fù)雜性，也要計(jì)算它的空間復(fù)雜性。然而，算法的運(yùn)行時(shí)間都是消耗在數(shù)據(jù)處理上的，從這個(gè)意義上說，算法的空間復(fù)雜性不會(huì)超過時(shí)間復(fù)雜性。出于這個(gè)原因，人們多關(guān)注于算法的時(shí)間復(fù)雜性分析。本書中除非特別說明，所說的算法分析，僅局限于對(duì)算法的時(shí)間復(fù)雜性分析。　　為客觀、科學(xué)地評(píng)估算法的時(shí)間復(fù)雜性，我們?cè)O(shè)置一臺(tái)抽象的計(jì)算機(jī)，它只用一個(gè)處理機(jī)，卻有無限量的隨機(jī)存儲(chǔ)器。它的有限個(gè)基本操作——算術(shù)運(yùn)算、邏輯運(yùn)算和數(shù)據(jù)的移動(dòng)（比如對(duì)變量的賦值）均在有限固定時(shí)間內(nèi)完成，我們進(jìn)一步假定所有這些基本操作都消耗一個(gè)時(shí)間單位。

編輯推薦

　　國(guó)內(nèi)算法界著名學(xué)者、計(jì)算理論學(xué)組組長(zhǎng)朱洪教授推薦?！　”舅惴ń滩奈墓P順暢，處理算法描述的兩難問題有自己的特點(diǎn)，且具有豐富的C、C++和Java實(shí)現(xiàn)程序，這對(duì)讀者學(xué)以致用很有幫助?！端惴ㄔO(shè)計(jì)、分析與實(shí)現(xiàn)從入門到精通：C、C++和Java》還有一個(gè)特點(diǎn)，文采甚好，如集腋成裘、化整為零、贏得舞伴等，生動(dòng)形象，易于學(xué)習(xí)和理解?！端惴ㄔO(shè)計(jì)、分析與實(shí)現(xiàn)從入門到精通：C、C++和Java》插圖也精美，如Hanoi塔圖等，都給《算法設(shè)計(jì)、分析與實(shí)現(xiàn)從入門到精通：C、C++和Java》增色很多，讓讀者在興趣中學(xué)習(xí)。此書在應(yīng)用性例題上，兼有中、英文描述題目，如環(huán)法自行車賽、牛牛玩牌、射雕英雄等例題。這些例題來自ACM／ICPC，它們富有挑戰(zhàn)性，可引起讀者的學(xué)習(xí)興趣?！　?8個(gè)經(jīng)典范例，包括漸增型算法、分治算法、動(dòng)態(tài)規(guī)劃算法、貪婪算法、回溯算法、線性規(guī)劃算法和計(jì)算幾何等算法設(shè)計(jì)和實(shí)現(xiàn)技巧?！　?6個(gè)國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽真題的詳細(xì)解析及算法的應(yīng)用?！　?種主流語言(C、C++和Java)實(shí)現(xiàn)算法范例程序。

圖書封面

圖書標(biāo)簽Tags

無

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

---

    算法設(shè)計(jì)、分析與實(shí)現(xiàn)從入門到精通 PDF格式下載

---