出版時間:2012-7 出版社:王曉云、 陳業(yè)綱 科學出版社 (2012-07出版) 作者:王曉云,陳業(yè)綱 著 頁數:360
內容概要
算法設計、分析與實現是計算機軟件開發(fā)人員應掌握的基本要素,在大型程序開發(fā)中越來越受到重視?!队嬎銠C算法設計、分析與實現》將典型的經典問題和算法設計技術巧妙地進行結合,系統(tǒng)地論述算法設計技術及其在經典問題中的應用。全書共14章,第1章介紹算法的基本概念和算法分析相關的數學問題,第2~13章分別介紹遞歸的應用、迭代算法、常見排序算法、動態(tài)規(guī)劃法、回溯法、貪心算法、分治算法、概率算法、近似算法、分支限界法、遺傳算法、蟻群算法等算法設計技術,第14章介紹查找。書中所有算法均在VC6.0環(huán)境下調試通過,并截圖顯示其運行過程?! 队嬎銠C算法設計、分析與實現》內容豐富,深入淺出,圖例豐富,可作為計算機專業(yè)本科高年級學生和研究生學習算法的教材,也可供工程技術人員、軟件設計師和自學者參考。
書籍目錄
前言 第1章與算法相關的數學問題 1.1復雜性分析初步 1.1.1空間復雜度 1.1.2時間復雜度 1.2復雜性的計量 1.3數學歸納法 1.3.1第一數學歸納法 1.3.2第二數學歸納法 1.3.3結構歸納法 1.4生成函數 1.4.1基本性質 1.4.2生成函數的計算 1.5遞歸方程求解 1.5.1遞推法 1.5.2公式解法 1.5.3母函數法 1.6 NP問題 思考題 第2章遞歸的應用 2.1第1類遞歸 2.2二叉樹的遞歸遍歷 2.3圖的遍歷 2.3.1圖的深度優(yōu)先搜尋法 2.3.2圖的廣度優(yōu)先算法 2.4遞歸與非遞歸的轉換 思考題 第3章迭代算法 3.1常見的迭代 3.2求方程的根 3.2.1牛頓迭代法 3.2.2二分法 3.2.3實例 3.3雅可比迭代法與高斯一塞德爾迭代法 3.3.1雅可比迭代法 3.3.2高斯一塞德爾迭代法 3.3.3迭代收斂的充分條件 思考題 第4章常見排序算法 4.1常見的內排序 4.1.1插入排序法 4.1.2交換排序 4.1.3選擇排序 4.1.4基數排序 4.1.5歸并排序 4.1.6計數排序 4.2算法性能分析 思考題 第5章動態(tài)規(guī)劃法 5.1最短路徑問題 5.1.1 Dijkstra算法 5.1.2 Bellman—Ford算法 5.1.3 Floyd算法 5.2最長公共子序列 5.3 01背包問題 5.4計算矩陣連乘積 5.5 Bitonic旅行路線問題 思考題 第6章回溯法 6.1 4皇后問題 6.2排列組合問題 6.3 01背包問題 6.4任務分配問題 6.5數碼串珠 6.6橋本分數式 思考題 第7章貪心算法 7.1 01背包 7.2哈夫曼編碼 7.3拓撲排序 7.4最小生成樹 7.4.1 Kruskal算法 7.4.2 Prim算法 7.5汽車加油問題 思考題 第8章分治算法 8.1二分查找 8.2大整數的乘法 8.3棋盤覆蓋問題 8.4循環(huán)賽日程表 8.5全排列 8.6矩陣乘法 思考題 第9章概率算法 9.1數值概率算法 9.1.1隨機數 9.1.2用隨機投點法計算pi值 9.1.3計算定積分 9.2舍伍德算法 9.3拉斯維加斯算法 9.4蒙特卡羅算法 思考題 第10章近似算法 10.1旅行售貨員問題 10.2裝箱問題 10.3集合覆蓋問題 10.4子集和問題 思考題 第11章分支限界法 11.1 01背包 11.2最短路徑 11.3裝載問題 11.4旅行售貨員問題 11.5布線問題 思考題 第12章遺傳算法 12.1遺傳算法的基本原理 12.1.1全局優(yōu)化問題 12.1.2遺傳編碼 12.1.3群體設定 12.1.4適應度函數 12.1.5遺傳算子 12.1.6循環(huán)終止條件 12.1.7控制參數 12.2 01背包問題 12.3旅行家問題 思考題 第13章蟻群算法 13.1蟻群算法簡介 13.2 TSP問題 思考題 第14章查找 14.1查找的基本概念 14.1.1查找表和查找 14.1.2查找表的數據結構表示 14.1.3平均查找長度ASL 14.2順序查找 14.2.1順序查找方法適用于線性表的順序存儲結構 14.2.2順序查找的平均查找長度 14.2.3該算法的優(yōu)缺點 14.3二分查找 14.3.1基本思想 14.3.2查找算法 14.3.3平均查找長度 14.3.4二分查找的優(yōu)點和缺點 14.4分塊查找 14.4.1存儲結構 14.4.2基本思想 14.4.3算法分析 14.4.4分塊查找的優(yōu)缺點 14.5二叉排序樹的查找 14.6哈希查找 思考題 主要參考文獻
章節(jié)摘錄
版權頁: 插圖: 第8章分治算法 分治法顧名思義“分而治之”,就是把一個復雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最后子問題可以簡單地直接求解,原問題的解即子問題解的合并。這個技巧是很多高效算法的基礎,如排序算法(快速排序、歸并排序)、傅里葉變換(快速傅里葉變換)、……,任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。問題的規(guī)模越小,越容易直接求解,解題所需的計算時間也越少。例如,對于n個元素的排序問題,當n=1時,不需任何計算;當n=2時,只要作一次比較即可排好序;當n=3時,只要作3次比較即可,……;當咒較大時,問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題,有時是相當困難的。對于一個規(guī)模為n的問題,若該問題可以容易地解決(n較?。﹦t直接解決,否則將其分解為k個規(guī)模較小的子問題,這些子問題互相獨立且與原問題形式相同,遞歸地解這些子問題,然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。 分治法的設計思想是:將一個難以直接解決的大問題分割成一些規(guī)模較小的相同問題,以便各個擊破,分而治之。 分治策略是:對于一個規(guī)模為n的問題,若該問題可以容易地解決(比如說規(guī)模,2較?。﹦t直接解決;否則,將其分解為k個規(guī)模較小的子問題,這些子問題互相獨立且與原問題形式相同,遞歸地解這些子問題,然后將各子問題的解合并得到原問題的解。 如果原問題可分割成k個子問題(1
編輯推薦
《計算機算法設計分析與實現》內容豐富,深入淺出,圖例豐富,可作為計算機專業(yè)本科高年級學生和研究生學習算法的教材,也可供工程技術人員、軟件設計師和自學者參考。
圖書封面
評論、評分、閱讀與下載