Python算法設計、實現、優化與應用（微課版·在線學習軟件版）

董付國，山東工商學院計算機學院副教授，山東省一流本科課程“Python應用開發”負責人。先後出版17本Python系列教材，多次獲得校級教學優秀效果獎一等獎和教學質量獎，開發過多套大型系統和軟件，發表教研、科研論文40余篇，EI收錄近30篇，擁有國家發明專利1項、軟件著作權1項，主持和參與多項縱向課題。長期維護微信公眾號“Python小屋”，免費分享超過1000篇原創技術文章和500節微課視頻。

目 錄

 

第1篇

 

常用算法的原理、實現與優化

 

 

 

第1章 算法分析與設計基礎 ...................................002

 

1.1 基本概念 ...................................................002

 

1.2 算法復雜度指標 ..............................................003

 

1.2.1 時間復雜度 ...........................................003

 

1.2.2 測量程序運行時間和空間使用情況 ........................005

 

1.3 算法優化常用思路 ............................................008

 

1.3.1 算法層面優化 .........................................008

 

1.3.2 代碼層面優化 .........................................010

 

習題 ............................................................013

 

第2章 枚舉算法 ............................................017

 

2.1 數學類問題算法設計與應用 .....................................017

 

2.2 其他類問題算法設計與應用 .....................................031

 

習題 ............................................................037

 

第3章 解析算法 ............................................039

 

3.1 數學類問題算法設計與應用 .....................................039

 

3.2 物理類問題算法設計與應用 .....................................048

 

3.3 其他類問題算法設計與應用 .....................................053

 

習題 ............................................................061

 

第4章 遞推與疊代算法 ......................................063

 

4.1 數學類問題算法設計與應用 .....................................063

 

4.2 其他類問題算法設計與應用 .....................................085

 

習題 ............................................................098

 

 

 

第5章 遞歸與回溯算法 ......................................101

 

5.1 數學類問題算法設計與應用 .....................................102

 

5.2 其他類問題算法設計與應用 .....................................105

 

5.3 尾遞歸優化 .................................................120

 

習題 ............................................................122

 

第6章 排序算法 ............................................124

 

6.1 排序算法的原理與實現 ........................................124

 

6.1.1 冒泡排序算法 .........................................124

 

6.1.2 選擇排序算法 .........................................126

 

6.1.3 插入排序算法 .........................................128

 

6.1.4 侏儒排序算法 .........................................129

 

6.1.5 希爾排序算法 .........................................129

 

6.1.6 堆排序算法 ...........................................130

 

6.1.7 歸並排序算法 .........................................131

 

6.1.8 快速排序算法 .........................................133

 

6.1.9 基數排序算法 .........................................134

 

6.1.10 計數排序算法 ........................................135

 

6.2 排序算法高級應用 ............................................138

 

習題 ............................................................147

 

第7章 查找算法 ............................................150

 

7.1 線性查找算法 ................................................150

 

7.2 二分法查找 .................................................159

 

習題 ............................................................162

 

第8章 貪心算法 ............................................164

 

8.1 找零錢問題 .................................................164

 

8.2 幼兒園加餐吃面包問題 ........................................165

 

8.3 汽車加油問題 ................................................166

 

8.4 區間合並問題 ................................................167

 

8.5 分數分解問題 ................................................167

 

8.6 若幹數字中前後元素最大差問題 .................................169

 

8.7 活動安排問題 ................................................169

 

 

 

8.8 哈夫曼編碼與解碼 ............................................171

 

習題 ............................................................174

 

第9章 分治法 ..............................................176

 

9.1 方程近似根 .................................................176

 

9.2 任意數列的逆序數 ............................................177

 

9.3 大自然數相乘 ................................................180

 

9.4 若幹整數的第k大元素 ........................................181

 

9.5 元素之和最大的連續子序列 .....................................186

 

9.6 二維平面距離最近的兩個點 .....................................188

 

習題 ............................................................192

 

第10章 動態規劃算法 .......................................193

 

10.1 斐波那契數列第n個數 .......................................194

 

10.2 找零錢問題 ................................................194

 

10.3 獎品收集問題 ...............................................197

 

10.4 0-1背包問題 ...............................................200

 

10.5 最長非遞減子序列 ...........................................206

 

10.6 最長公共子序列 .............................................210

 

習題 ............................................................214

 

第2篇

 

算法在不同學科中的應用

 

 

 

第11章 數論算法 ...........................................216

 

11.1 進制轉換 ..................................................216

 

11.2 最大公約數 ................................................217

 

11.3 素性檢測 ..................................................219

 

11.4 大數乘法與多項式乘法 .......................................229

 

11.5 乘模逆、擴展歐幾裏得算法 ....................................234

 

11.6 中國剩余定理 ...............................................237

 

11.7 快速冪模算法 ...............................................239

 

11.8 水仙花數 ..................................................244

 

11.9 平方數與自守數 .............................................249

 

 

 

11.10 整數分解 .................................................251

 

習題 ............................................................259

 

第12章 線性代數算法 .......................................261

 

12.1 向量基本運算 ...............................................261

 

12.2 矩陣基本運算 ...............................................265

 

12.3 矩陣行列式、代數余子式、逆矩陣 ..............................269

 

習題 ............................................................275

 

第13章 概率論與隨機過程算法 ................................277

 

13.1 概率論的基本概念 ...........................................277

 

13.2 算法應用案例解析 ...........................................279

 

習題 ............................................................288

 

第14章 益智遊戲類算法 .....................................289

 

14.1 24點遊戲 ..................................................289

 

14.2 蒙蒂霍爾悖論遊戲 ...........................................290

 

14.3 尋寶遊戲 ..................................................292

 

14.4 模擬發紅包 ................................................297

 

14.5 聰明的尼姆遊戲 .............................................298

 

14.6 抓狐貍遊戲 ................................................299

 

14.7 確定旅遊目的地 .............................................301

 

14.8 制作漂亮手鏈 ...............................................303

 

14.9 數字可達遊戲 ...............................................304

 

14.10 電影院選座位問題 ..........................................307

 

14.11 數獨遊戲盤面生成與自動求解 .................................308

 

14.12 推理遊戲 .................................................313

 

14.13 迷宮自動尋找最短路徑 ......................................315

 

習題 ............................................................318

 

第15章 圖論算法 ...........................................320

 

15.1 圖的概念、表示、應用與可視化 ................................320

 

15.1.1 基本概念與應用場景 .................................320

 

15.1.2 圖的表示方式 .......................................321

 

 

 

15.1.3 圖的可視化 .........................................325

 

15.1.4 尋找人群中的明星 ...................................326

 

15.2 二叉樹與多叉樹節點遍歷 ......................................326

 

15.3 通路、回路、最短路徑 .......................................331

 

15.4 拓撲排序 ..................................................340

 

15.5 圖著色問題 ................................................341

 

15.6 最小生成樹 ................................................344

 

15.7 完美匹配 ..................................................346

 

15.8 最大流 ....................................................347

 

習題 ............................................................352

 

第16章 機器學習算法 .......................................353

 

16.1 線性回歸算法原理與應用 ......................................353

 

16.1.1 線性回歸算法原理 ...................................353

 

16.1.2 使用線性回歸模型預測兒童身高 ........................355

 

16.2 協同過濾算法原理與電影推薦 ..................................357

 

16.3 樸素貝葉斯算法原理與應用 ....................................358

 

16.3.1 分類算法基本原理 ...................................358

 

16.3.2 使用樸素貝葉斯算法進行垃圾郵件分類 ...................359

 

16.4 分類算法與聚類算法 .........................................363

 

16.4.1 使用KNN算法判斷交通工具類型 ........................363

 

16.4.2 使用K-Means算法壓縮圖像顏色 ........................365

 

16.4.3 DBSCAN算法原理與應用 ..............................368

 

16.5 關聯規則分析算法原理與應用 ..................................370

 

16.5.1 基本概念與算法原理 .................................371

 

16.5.2 使用關聯規則分析算法分析和預測演員關系 ...............371

 

習題 ............................................................375

 

第17章 計算機圖形學算法 ....................................376

 

17.1 Bresenham直線生成算法 .....................................376

 

17.2 二維平面直線裁剪算法 .......................................379

 

17.2.1 Cohen-Sutherland裁剪算法 ..........................380

 

17.2.2 Liang-BarSky裁剪算法 ..............................384

 

17.3 求解點集的凸包 .............................................388

 

習題 ............................................................392

 

 

 

第18章 密碼學算法 .........................................394

 

18.1 安全哈希算法 ...............................................394

 

18.2 對稱密鑰密碼算法DES和AES ..................................395

 

18.3 非對稱密鑰密碼算法RSA與數字簽名算法DSA .....................397

 

18.3.1 RSA算法 ...........................................397

 

18.3.2 DSA算法 ...........................................400

 

習題 ............................................................401

 

參考文獻 ...................................................402