基本信息

書名:算法設計與問題求解――計算思維培養

定價

作者:李清勇 著

出版社：電子工業出版社

出版日期：2020-05-01

ISBN：9787121295157

字數：

頁碼：256

版次：1

裝幀：平裝

開本：16開

商品重量：

編輯推薦

內容提要

在信息時代，計算思維是解決復雜工程問題的重要思維方式，計算機則是求解問題的重要工具。本書以計算機經典問題求解為導向，通用算法思維和編程能力培養為目標，引入ACM國際大學生程序設計競賽素，組織教材的理論教學和編程實踐兩方面的內容。本書主要內容包括計算機問題求解的經典算法模型和設計範式，包括計算機問題求解中常用的數據結構、枚舉算法、遞歸與分治策略、動態規劃、貪心算法和搜索技術。除了強調經典的問題原型和算法原理，本書兼顧編程實踐能力，力圖使得學生面對復雜問題時既能“想到”還能“做到”。

目錄

目 錄

章 計算機問題求解概述t1
1．1 問題與問題實例t1
1．2 計算機問題求解周期t2
1．3 算法與程序t5
1．4算法復雜性分析t5
1．4．1空間復雜性t6
1．4．2 時間復雜性t7
習題1t15
第2章 程序設計語言與數據結構t16
2．1 程序設計語言的“盲點”t16
2．1．1 long不夠長t17
2．1．2 double不夠準t19
2．1．3 遞歸不夠快t25
2．2 基本數據結構t26
2．2．1 線性表t26
2．2．2 棧和隊列t30
2．2．3 樹和二叉樹t36
2．2．4 優先隊列和堆t44
2．2．5 圖t45
2．2．6 並查集t47
2．3 標準模板庫t49
2．3．1 模板的基本概念t49
2．3．2 標準模板庫概述t51
2．3．3 標準模板庫應用t52
習題2t63
第3章 枚舉算法t69
3．1 枚舉的基本思想t69
3．2 模糊數字t70
3．3 真假銀幣t72
3．4 m錢n雞t75
3．5 數字配對t77
3．6 繩子切割t79
3．7 石頭距離t81
習題3t84
第4章 遞歸與分治t90
4．1 遞歸程序t90
4．2 分治法的基本原理t94
4．3 合並排序t96
4．4 逆序對問題t100
4．5 快速排序t102
4．6 接近點對問題t106
4．7 指數運算t111
4．8 二分查找t113
習題4t114
第5章 動態規劃t122
5．1 動態規劃的基本思想t122
5．1．1 動態規劃的基本要素t124
5．1．2 動態規劃的求解步驟t125
5．2 矩陣連乘t126
5．3 二叉搜索樹t131
5．4 多段圖 短路徑t136
5．5 公共子序列t140
5．6 0-1背包問題t143
5．7 上升子序列t146
習題5t149
第6章 貪心算法t155
6．1 貪心算法的基本要素t155
6．2 活動安排問題t157
6．3 小數背包問題t161
6．4 前綴碼t164
6．5 單源 短路徑t169
6．6 小生成樹t174
6．6．1 Prim算法t175
6．6．2 Kruskal算法t178
習題6t182
第7章 搜索技術t187
7．1 問題的狀態空間表示t187
7．2 深度優先搜索t189
7．3 廣度優先搜索t191
7．4 回溯算法t193
7．4．1 回溯算法的基本原理和框架程序t193
7．4．2 裝載問題的回溯算法t199
7．4．3 圓排列問題t203
7．5 分支限界t206
7．5．1 分支限界法的基本原理t206
7．5．2 裝載問題的分支限界法t208
7．6 啟發式搜索t211
7．6．1 啟發式搜索基本原理t211
7．6．2 裝載問題的啟發式搜索t215
習題7t217
附錄A 復雜度分析的數學基礎t225
附錄B 常用C語言和STL函數t235
附錄C 程序設計競賽和OnlineJudge介紹t241
附錄D 教學資源t244
參考文獻t245

作者介紹

李清勇，北京交通大學計算機與信息技術學院教授，研究領域為人工智能和大數據，涵蓋計算機視覺、模式識別、機器學習和數據挖掘等學科方向，尤其專注於表面缺陷檢測、多媒體內容分析與檢索、低秩稀疏表示模型和聚類分析等，其研究成果應用於高速鐵路和氣像觀測等行業。獲得"北京市高校青年英纔計劃”人選，北京市教學成果獎一等獎等。

序言