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

前言

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

內(nèi)容概要

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

書籍目錄

第1章　集腋成裘——漸增型算法　　1.1　算法設(shè)計與分析　　1.2　插入排序算法　　　1.2.1　算法描述與分析　　　1.2.2　程序?qū)崿F(xiàn)　　　1.2.3　應(yīng)用——贏得舞伴　　1.3　兩個有序序列的合并算法　　　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　堆的實現(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)先隊列　　　2.6.1　算法描述與分析　　　2.6.2　程序?qū)崿F(xiàn)　　2.7　關(guān)于排序算法　　　2.7.1　比較型排序算法的時間復(fù)雜度　　　2.7.2　C/C++/Java提供的排序函數(shù)(方法)　　　2.7.3　應(yīng)用——環(huán)法自行車賽　　2.8　小結(jié)　第3章　記表備查——動態(tài)規(guī)劃算法　　3.1　矩陣鏈乘法　　　3.1.1　算法描述與分析　　　3.1.2　程序?qū)崿F(xiàn)　　　3.1.3　應(yīng)用——牛牛玩牌　　3.2　最長公共子序列　　　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)有向圖中任意兩點間的最短路徑　　　3.4.1　算法描述與分析　　　3.4.2　程序?qū)崿F(xiàn)　　　3.4.3　應(yīng)用——牛牛聚會　　3.5　小結(jié)　第4章　高效的選擇——貪婪算法　　4.1　活動選擇問題　　　4.1.1　算法描述與分析　　　4.1.2　程序?qū)崿F(xiàn)　　　4.1.3　貪婪算法與動態(tài)規(guī)劃　　　4.1.4　應(yīng)用——海岸雷達　　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章　圖形學基礎(chǔ)——計算幾何　附錄　參考文獻　

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---