 |
-- 會員 / 註冊 --
|
 |
|
|
|
算法設計與問題求解——編程實踐 ( 簡體 字) |
| 作者：李清勇 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：電子工業出版社 |  3dWoo書號： 36369
詢問書籍請說出此書號！【缺書】
NT售價： 175 元 |
| 出版日：6/1/2013 |
| 頁數：248 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787121203275 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：2006年3月， 美國卡內基-梅隆大學計算機科學系主任周以真（Jeannette M. Wing）教授在美國計算機權威期刊《Communications of the ACM》雜志上首先提出了計算思維（Computational Thinking）的概念。周教授認為： 計算思維是運用計算機科學的基礎概念進行問題求解、 系統設計、 以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。計算思維是每個人的基本技能， 不僅僅屬于計算機科學家。我們應當使每個學生在培養解析能力時不僅掌握閱讀、 寫作和算術（Reading， wRiting and aRithmetic， 3R）， 還要學會計算思維。正如印刷出版促進了3R的普及， 計算和計算機也以類似的正反饋促進了計算思維的傳播， 計算機逐漸成為了當今問題求解的最重要工具。
1.計算機與問題求解
在20世紀40年代， 為了求解軍事領域復雜的炮彈彈道計算問題， 科學家發明了第一臺電子計算機“埃尼阿克”（Electronic Numerical Integrator And Computer， ENIAC）。隨著計算機計算能力的增強， 計算機被廣泛應用到了社會生活的各個領域。大到宇宙探測、 基因圖譜繪制， 小到日常工作、 生活娛樂， 無不需要計算機的支持。
作為“問題求解的一個有力工具”， 計算機盡管沒有思維， 只能機械地執行指令， 但它運算速度快、 存儲容量大、 計算精度高。如果能夠設計有效的算法和程序， 充分利用這些優點， 計算機就能成為問題求解的一個利器。
運算速度快是計算機最重要的特點之一。很多問題盡管比較復雜， 但仍然存在求解的方法， 只是這些方法往往計算量比較大， 計算過程較為繁瑣， 人們難以在可以接受的時間內手工求解。
【例】 用1， 2， 3， 4， 5， 6， 7， 8， 9九個數字拼成一個九位數， 每個數字使用一次且僅用一次， 要求得到的九位數的前三位、 中間三位和最后三位構成的三位數的比值為123。例如192384576就是一個符合該要求的數， 因為192384576=123。
對于這樣的問題， 很容易想到的一個求解方案是： 列舉所有可能的九位數123456789， …， 987654321， 并逐個驗證是否符合比值要求。理論上， 這是一個可行的辦法， 可是幾乎沒有人愿意這樣做。因為這樣的九位數總共有9!＝362880個， 即使每秒驗證一個數（對于人工驗證， 這已經是很快的速度了！）， 也需要100多個小時。
但是， 計算機實現同樣的“笨方法”效果就大不一樣。考慮用一個數組d保存九位數的各位數字， x， y， z分別代表前三位數、 中間三位數和最后三位數， 用STL中的函數next_permutation計算九個數字的下一個排列。當某個排列（即一個九位數）滿足比例要求x y z=123時， 則輸出該九位數。下面是解決此問題的C++代碼， 在普通的PC機上運行該程序， 需要的時間還不到0.1秒。 void NineNumber() {
int x ， y ， z;
int d[9]= {1 ， 2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8 ， 9};
do{
x=d [0] * 100+d [1] * 10+d [2];
y=d [3] * 100+d [4] * 10+d [5];
z=d [6] * 100+d [7] * 10+d [8];
if(y == x * 2 ＆＆ z == x * 3)
cout ＜＜ x ＜＜ y ＜＜ z ＜＜ endl ;
} while (next_permutation(d ， d+9)); // STL中的函數， 得到下一個排列
}
存儲容量大是計算機的另一個重要特點。人們很容易記住10以內的兩個數的乘積， 也就是小學數學中的“九九乘法表”。但如果要求人們記住100以內的任意兩個數的乘積， 普通人可能會覺得“記憶”不夠。但對于計算機來說， 這真是“小菜一碟”， 一個100×100的二維數組就可以把“百百乘法表”保存下來。
人們常說的內存、 硬盤、 光盤、 U盤等都是存儲器， 可以通俗地理解為計算機的記憶部件。容量的基本單位是字節（Byte）， 記為B。其他單位有KB（1KB=1024B）、 MB（1MB=1024KB）、 GB（1GB=1024MB）等。容量越大， 可以存儲的數據就越多， 其“記憶力”就越強。“百百乘法表”如果用一個100×100的二維int型整數（假設一個int型整數占2字節）數組保存， 它僅僅需要占用20 000字節（少于20KB）的空間。相比現在計算機動輒數GB的內存容量來說， “百百乘法表”的存儲開銷微不足道。
需要特別指出的是， 運算速度快、 存儲容量大僅僅是計算機硬件系統的兩個突出特點。在實際問題求解過程中， 只有硬件平臺還遠遠不夠， 人們需要針對問題設計不同的算法， 并把算法轉化為計算機可以運行的程序。
2.計算機問題求解的知識體系
計算機問題求解的本質是把特定領域中特定問題的求解過程轉換為計算機可以執行的程序。在這個轉換過程中， 除了必要的專業知識外， 問題求解者還需要掌握計算機算法設計方面的知識， 主要包括： 高級程序設計語言、 數據結構和算法。這些知識構成了計算機問題求解的核心知識體系。
在計算機教學體系中， 高級程序設計語言、 數據結構、 算法是相互承接的課程系列。從計算機問題求解的角度看， 這三門課程的知識相互交叉、 相互支撐。高級程序設計語言和數據結構是算法設計的基礎， 高效的算法和數據結構需要用某種高級程序設計語言去實現； 一個好程序不僅需要“編程小技巧”， 更需要合理的數據結構和高效的算法。
程序設計語言是問題求解的基本工具。隨著計算機技術的發展， 程序設計語言經歷了一個從低級程序設計語言到高級程序設計語言的發展歷程。機器語言和匯編語言等面向特定的體系結構和指令系統， 在計算機發展的早期應用較多。隨著形式語言理論、 編譯技術的發展， 與目標機器無關的高級程序設計語言（如C/C++， Java等）逐漸成為程序設計的主流。本書約定的程序設計語言是C/C++。需要注意的是， 程序設計語言并不等于程序設計， 程序設計的目的是表達程序設計者的思想， 按照計算機所能理解的方式描述需要讓計算機完成的工作， 而程序設計語言只是表達這種思想的工具。程序設計的關鍵之處在于明確數據在計算機中的表達形式， 以及確定如何將輸入轉化為輸出的一系列計算步驟， 而這些都需要數據結構和算法理論的指導。
數據結構是問題求解的基礎要素。數據是信息的載體， 無論是待求解問題的輸入/輸出， 還是問題求解過程中產生的中間量； 無論是簡單的量， 比如單個數值， 還是復雜的對象， 它們在計算機中都是以數據的形式存儲。在問題求解時， 為滿足數據存儲的結構化要求并提高程序執行效率， 人們首先面臨的問題是怎樣合理地組織、 存儲和加工這些數據。常用的數據結構有線性表、 棧、 隊列、 樹、 二叉樹、 圖、 哈希表（散列表）等。數據結構的設計和應用不是一個教條化的生搬硬套過程， 同一個問題也許可以運用不同的數據結構求解， 而且它們求解的效率往往不盡相同。另外， 有些問題可能沒有現成的數據結構直接套用， 需要人們綜合運用基本數據結構組合成新的數據結構。無論是已有數據結構的選擇還是新數據結構的設計， 人們都需要應用算法設計與分析方面的知識。
算法設計是問題求解的關鍵要素。簡單地說， 算法可以理解為把將問題輸入轉化為問題答案的一系列計算步驟。算法必須滿足正確性與復雜性要求。首先， 算法執行結果必須正確， 它能正確無誤地把每一個問題實例的正確答案求解出來。其次， 算法的復雜度要適中。計算機系統的資源（包括運行時間和存儲空間）是有限的， 因此算法必須在有限的資源條件下正確地求解問題。同樣的問題， 某些算法執行結果可能不正確， 某些算法執行結果正確無誤。即使執行結果都正確的不同算法， 它們的執行效率可能也不盡相同， 如有些算法需要幾個小時， 甚至幾天， 有些算法卻僅僅需要幾秒鐘或幾分鐘。算法設計是一個靈活的、 創造性的過程， 甚至可以認為是一個藝術創造過程。有些算法是現實生活中人們解決問題時所用辦法的升華和抽象； 有些算法是數學理論和數學模型的體現和具體化。人們需要掌握經典的算法思想及其應用技巧， 也要學會怎樣針對特定問題設計和創造新算法。
3.本書的內容和結構
本書是一本講述怎樣綜合運用算法設計理論和技術進行問題求解的實踐教材， 主要講述算法設計原理和方法， 對運用算法求解問題時涉及的C/C++程序設計細節， 尤其是影響算法準確性和復雜性的編程要點和技巧也進行了詳細闡述。數據結構往往是算法設計和實現的基礎， 特別是一些高級數據結構， 其本身就體現了很強的算法思維， 因此本書不僅僅單獨設立一章講述數據結構， 在討論具體算法時也會交叉討論相應的數據結構知識。本書包括7章， 組織如下：
第1章介紹問題求解和算法的基本概念， 然后著重闡述了算法復雜度分析的基本理論和方法。
第2章介紹程序設計和數據結構相關內容， 程序設計和數據結構是算法設計的重要支撐， 本章重點介紹了程序設計的三個盲點， 以及常用的基本數據結構及其用法。
第3章介紹枚舉算法。“大道至簡”， 枚舉算法是一種最樸素最簡單的算法思想， 但在具有卓越運算速度的計算機系統中， 它卻是常常被忽視的問題求解利器。本章重點闡述了怎樣直接和間接運用枚舉算法求解問題。
第4章介紹遞歸和分治算法。“凡治眾如治寡， 分數是也”， 分治策略是分析和解決復雜問題最常用的策略之一。本章根據分治算法的求解步驟把分治策略歸納為三類， 并結合具體實例闡述每類策略的設計思想、 適用范圍及實現要點。
第5章介紹動態規劃算法。動態規劃算法是最具有創造性的一種算法， 歸約、 分治等思維方法都在動態規劃算法框架中得到了很好的體現。本章重點討論基于“劃分”和“約簡”策略的動態規劃算法原理和運用技巧。
第6章介紹貪心算法。這種類似于“瞎子爬山”的策略， 如果運用適當， 能夠快速地產生最優解。本章給出了一些典型的貪心算法問題， 并探討了貪心算法的適用范圍。
第7章介紹搜索算法。搜索是求解一些難解問題的常用策略， 它把問題求解轉換為狀態空間圖中的路徑探索過程， 究其本質， 搜索是一種枚舉和優化策略的綜合算法。“運用之妙， 存乎一心”， 本章以典型問題為例闡述五種經典搜索策略的原理、 適用范圍以及實現要點。
為便于教學和讀者自學， 本教材提供有適用于理論教學的課件以及實踐學習的配套平臺——“北京交通大學在線程序評測系統”（http： //acm.bjtu.edu.cn/OnlineJudge ， 簡稱BOJ）。BOJ是一個公益性質的計算機問題求解實踐平臺， 也是本書的配套網站。本書的例題和習題都以專題的形式加入BOJ題庫中， 讀者在學習本書時， 可登錄該系統進行編程求解和自我評測。 |
內容簡介：本書是北京市精品教材立項項目，是大學生創新實踐課程“算法設計與實踐”課程教材。本書以問題求解為目標，以高級程序設計語言C/C++為工具，討論怎樣綜合運用算法（包括數據結構）知識去分析問題和解決問題。問題驅動，高級語言程序設計、數據結構以及算法設計與分析知識交叉融合是本書的特點。配套理論教學的電子課件；實踐教學用“在線程序評測系統”。包括問題求解與算法分析概述、基本數據結構、高級數據結構、枚舉算法、遞歸與分治、 動態規劃、貪心算法、搜索算法、圖算法、算法分析的實用公式、在線程序評測系統簡介等。 |
目錄：第1章 計算機問題求解概述
1.1 問題與問題實例
1.2 計算機問題求解周期
1.3 算法與程序
1.4 算法復雜性分析
1.4.1 空間復雜性
1.4.2 時間復雜性
1.4.2.1 時間復雜性的表示
1.4.2.2 漸近時間復雜性及其階
1.4.2.3 時間復雜性漸近階的意義
1.4.2.4 算法時間復雜性分析
習題1
第2章 程序設計語言與數據結構
2.1 程序設計語言的“盲點”
2.1.1 long不夠長
2.1.1.1 數據類型的值域
2.1.1.2 大整數相加算法
2.1.2 double不夠準
2.1.2.1 浮點數的存儲格式
2.1.2.2 浮點數的有效數字
2.1.2.3 高精度浮點數處理實例
2.1.3 遞歸不夠快
2.2 基本數據結構
2.2.1 線性表
2.2.1.1 線性表的順序存儲結構
2.2.1.2 線性表的鏈式存儲結構
2.2.2 棧和隊列
2.2.2.1 棧
2.2.2.2 隊列
2.2.3 樹和二叉樹
2.2.3.1 樹
2.2.3.2 二叉樹
2.2.4 優先隊列和堆
2.2.4.1 優先隊列
2.2.4.2 二叉堆
2.2.5 圖
2.2.5.1 鄰接矩陣
2.2.5.2 鄰接表
2.3 標準模板庫
2.3.1 模板的基本概念
2.3.2 標準模板庫概述
2.3.2.1 算法
2.3.2.2 容器
2.3.2.3 迭代器
2.3.3 標準模板庫應用
2.3.3.1 向量(vector)
2.3.3.2 集合和多重集合（set和multiset）
2.3.3.3 映射和多重映射（map 和multimap）
2.3.3.4 堆（heap）
2.3.3.5 排序算法
習題2
第3章 枚舉算法
3.1 枚舉的基本思想
3.2 模糊數字
3.3 m錢買n雞
3.4 真假銀幣
習題3
第4章 遞歸與分治
4.1 遞歸程序
4.2 分治策略的基本原理
4.3 合并排序
4.4 逆序對問題
4.5 快速排序
4.6 最接近點對問題
4.7 指數運算
4.8 二分查找
習題4
第5章 動態規劃
5.1 動態規劃的基本思想
5.1.1 動態規劃的基本要素
5.1.2 動態規劃的求解步驟
5.2 矩陣連乘
5.3 最優二叉搜索樹
5.4 多段圖最短路徑
5.5 最長公共子序列
5.6 0拟1背包問題
5.7 最大上升子序列
習題5
第6章 貪心算法
6.1 貪心算法的基本要素
6.2 活動安排問題
6.3 小數背包問題
6.4 最優前綴碼
6.5 單源最短路徑
6.6 最小生成樹
6.6.1 Prim算法
6.6.2 Kruskal算法
6.7 貪心算法與動態規劃、 分治算法的比較
習題6
第7章 搜索技術
7.1 問題的狀態空間表示
7.2 深度優先搜索
7.3 廣度優先搜索
7.4 回溯算法
7.4.1 回溯算法的基本原理和框架程序
7.4.2 裝載問題的回溯算法
7.4.3 圓排列問題
7.5 分支限界
7.5.1 分支限界法的基本原理
7.5.2 裝載問題的分支限界法
7.6 啟發式搜索
7.6.1 啟發式搜索基本原理
7.6.2 裝載問題的啟發式搜索
習題7
附錄A 復雜性分析的數學基礎
附錄B 常用C語言和STL函數
附錄C 程序設計競賽和OnlineJudge介紹
參考文獻 |
| 序： |
|
