Python编程导论（第2版）.pdf

PDF: https://github.com/jash-git/Jash-good-idea-20200304-001

目 录
第1 章 启程 …………………………………………….. 1
第2 章 Python 简介 ………………………………… 6
2.1 Python 基本元素 ………………………………… 7
2.1.1 对象、表达式和数值类型 ………… 8
2.1.2 变量与赋值 …………………………….. 9
2.1.3 Python IDE …………………………….. 11
2.2 程序分支 ………………………………………….. 12
2.3 字符串和输入 …………………………………… 14
2.3.1 输入 ………………………………………. 15
2.3.2 杂谈字符编码 ………………………… 16
2.4 迭代 ………………………………………………… 17
第3 章 一些简单的数值程序 ………………….. 20
3.1 穷举法 ……………………………………………… 20
3.2 for 循环 …………………………………………… 22
3.3 近似解和二分查找 ……………………………. 24
3.4 关于浮点数 ………………………………………. 27
3.5 牛顿拉弗森法 …………………………………. 29
第4 章 函数、作用域与抽象 ………………….. 31
4.1 函数与作用域 …………………………………… 32
4.1.1 函数定义 ……………………………….. 32
4.1.2 关键字参数和默认值 ………………. 33
4.1.3 作用域 …………………………………… 34
4.2 规范 ………………………………………………… 37
4.3 递归 ………………………………………………… 39
4.3.1 斐波那契数列 ………………………… 40
4.3.2 回文 ………………………………………. 42
4.4 全局变量 ………………………………………….. 45
4.5 模块 ………………………………………………… 46
4.6 文件 ………………………………………………… 47
第5 章 结构化类型、可变性与
高阶函数 …………………………………….. 50
5.1 元组 ………………………………………………… 50
5.2 范围 ………………………………………………… 52
5.3 列表与可变性 …………………………………… 52
5.3.1 克隆………………………………………. 57
5.3.2 列表推导 ……………………………….. 57
5.4 函数对象 ………………………………………….. 58
5.5 字符串、元组、范围与列表 ………………. 60
5.6 字典 ………………………………………………… 61
第6 章 测试与调试 ………………………………… 65
6.1 测试 ………………………………………………… 65
6.1.1 黑盒测试 ……………………………….. 66
6.1.2 白盒测试 ……………………………….. 68
6.1.3 执行测试 ……………………………….. 69
6.2 调试 ………………………………………………… 70
6.2.1 学习调试 ……………………………….. 72
6.2.2 设计实验 ……………………………….. 72
6.2.3 遇到麻烦时 ……………………………. 75
6.2.4 找到“目标”错误之后 …………… 76
第7 章 异常与断言 ………………………………… 77
7.1 处理异常 ………………………………………….. 77
7.2 将异常用作控制流 ……………………………. 80
7.3 断言 ………………………………………………… 82
第8 章 类与面向对象编程 ……………………… 83
8.1 抽象数据类型与类 ……………………………. 83
8.1.1 使用抽象数据类型设计程序 ……. 87
8.1.2 使用类记录学生与教师 …………… 87
2 目 录
8.2 继承 ………………………………………………… 90
8.2.1 多重继承 ……………………………….. 92
8.2.2 替换原则 ……………………………….. 93
8.3 封装与信息隐藏 ……………………………….. 94
8.4 进阶示例：抵押贷款 ………………………… 99
第9 章 算法复杂度简介 ……………………….. 103
9.1 思考计算复杂度 ……………………………… 103
9.2 渐近表示法 …………………………………….. 106
9.3 一些重要的复杂度 ………………………….. 107
9.3.1 常数复杂度 ………………………….. 107
9.3.2 对数复杂度 ………………………….. 108
9.3.3 线性复杂度 ………………………….. 108
9.3.4 对数线性复杂度 …………………… 109
9.3.5 多项式复杂度 ………………………. 109
9.3.6 指数复杂度 ………………………….. 111
9.3.7 复杂度对比 ………………………….. 112
第10 章 一些简单算法和数据结构 ………. 114
10.1 搜索算法 ………………………………………. 115
10.1.1 线性搜索与间接引用元素 ….. 115
10.1.2 二分查找和利用假设 …………. 116
10.2 排序算法 ………………………………………. 119
10.2.1 归并排序 ………………………….. 120
10.2.2 将函数用作参数 ………………… 122
10.2.3 Python 中的排序 ……………….. 123
10.3 散列表 …………………………………………. 124
第11 章 绘图以及类的进一步扩展 ………. 128
11.1 使用PyLab 绘图 ……………………………. 128
11.2 进阶示例：绘制抵押贷款 ………………. 133
第12 章 背包与图的最优化问题 ………….. 139
12.1 背包问题 ………………………………………. 139
12.1.1 贪婪算法 ………………………….. 140
12.1.2 0/1 背包问题的最优解 ……….. 143
12.2 图的最优化问题 ……………………………. 145
12.2.1 一些典型的图论问题 …………… 149
12.2.2 最短路径：深度优先搜索和
广度优先搜索 ………………………. 149
第13 章 动态规划 ………………………………… 155
13.1 又见斐波那契数列 ………………………… 155
13.2 动态规划与0/1 背包问题……………….. 157
13.3 动态规划与分治算法 …………………….. 162
第14 章 随机游走与数据可视化 ………….. 163
14.1 随机游走 ……………………………………… 163
14.2 醉汉游走 ……………………………………… 164
14.3 有偏随机游走 ……………………………….. 170
14.4 变幻莫测的田地 ……………………………. 175
第15 章 随机程序、概率与分布 ………….. 178
15.1 随机程序 ……………………………………… 178
15.2 计算简单概率 ……………………………….. 180
15.3 统计推断 ……………………………………… 180
15.4 分布 …………………………………………….. 192
15.4.1 概率分布 ………………………….. 194
15.4.2 正态分布 ………………………….. 195
15.4.3 连续型和离散型均匀分布 ….. 199
15.4.4 二项式分布与多项式分布 ….. 200
15.4.5 指数分布和几何分布 …………. 201
15.4.6 本福德分布 ………………………. 203
15.5 散列与碰撞…………………………………… 204
15.6 强队的获胜概率 ……………………………. 206
第16 章 蒙特卡罗模拟 …………………………. 208
16.1 帕斯卡的问题 ……………………………….. 209
16.2 过线还是不过线 ……………………………. 210
16.3 使用查表法提高性能 …………………….. 213
16.4 求π 的值 ……………………………………… 214
16.5 模拟模型结束语 ……………………………. 218
第17 章 抽样与置信区间 …………………….. 220
17.1 对波士顿马拉松比赛进行抽样 ……….. 220
17.2 中心极限定理 ……………………………….. 225
17.3 均值的标准误差 ……………………………. 228
第18 章 理解实验数据 …………………………. 231
18.1 弹簧的行为…………………………………… 231
18.2 弹丸的行为…………………………………… 238
18.2.1 可决系数 ………………………….. 240
18.2.2 使用计算模型 ……………………. 241
18.3 拟合指数分布数据 …………………………. 242
18.4 当理论缺失时 ……………………………….. 245
第19 章 随机试验与假设检验 ……………… 247
19.1 检验显著性 …………………………………… 248
19.2 当心P-值 ……………………………………… 252
19.3 单尾单样本检验 ……………………………. 254
19.4 是否显著 ………………………………………. 255
19.5 哪个N ………………………………………….. 257
19.6 多重假设 ………………………………………. 258
第20 章 条件概率与贝叶斯统计 ………….. 261
20.1 条件概率 ………………………………………. 262
20.2 贝叶斯定理 …………………………………… 263
20.3 贝叶斯更新 …………………………………… 264
第21 章 谎言、该死的谎言与统计学 …… 267
21.1 垃圾输入，垃圾输出 ……………………… 267
21.2 检验是有缺陷的 ……………………………. 268
21.3 图形会骗人 …………………………………… 268
21.4 Cum Hoc Ergo Propter Hoc ……………… 270
21.5 统计测量不能说明所有问题 …………… 271
21.6 抽样偏差 ………………………………………. 272
21.7 上下文很重要 ……………………………….. 273
21.8 慎用外推法 …………………………………… 273
21.9 得克萨斯神枪手谬误……………………… 274
21.10 莫名其妙的百分比 ………………………. 276
21.11 不显著的显著统计差别 ………………… 276
21.12 回归假象 …………………………………….. 277
21.13 小心为上 …………………………………….. 278
第22 章 机器学习简介 …………………………. 279
22.1 特征向量 ………………………………………. 281
22.2 距离度量 ………………………………………. 283
第23 章 聚类 ………………………………………… 288
23.1 Cluster 类 ……………………………………. 289
23.2 K 均值聚类 …………………………………… 291
23.3 虚构示例 ………………………………………. 292
23.4 更真实的示例 ……………………………….. 297
第24 章 分类方法 ………………………………… 303
24.1 分类器评价 …………………………………… 303
24.2 预测跑步者的性别 ………………………… 306
24.3 K 最近邻方法 ……………………………….. 308
24.4 基于回归的分类器 ………………………… 312
24.5 从“泰坦尼克”号生还 ………………….. 320
24.6 总结 …………………………………………….. 325
Python 3.5 速查表 ……………………………….. 326

—-

目 錄
第1 章 啟程 …………………………………………….. 1
第2 章 Python 簡介 ………………………………… 6
2.1 Python 基本元素 ………………………………… 7
2.1.1 對象、運算式和數值類型 ………… 8
2.1.2 變數與賦值 …………………………….. 9
2.1.3 Python IDE …………………………….. 11
2.2 程式分支 ………………………………………….. 12
2.3 字串和輸入 …………………………………… 14
2.3.1 輸入 ………………………………………. 15
2.3.2 雜談字元編碼 ………………………… 16
2.4 反覆運算 ………………………………………………… 17
第3 章 一些簡單的數值程式 ………………….. 20
3.1 窮舉法 ……………………………………………… 20
3.2 for 迴圈 …………………………………………… 22
3.3 近似解和二分查找 ……………………………. 24
3.4 關於浮點數 ………………………………………. 27
3.5 牛頓拉弗森法 …………………………………. 29
第4 章 函數、作用域與抽象 ………………….. 31
4.1 函數與作用域 …………………………………… 32
4.1.1 函式定義 ……………………………….. 32
4.1.2 關鍵字參數和預設值 ………………. 33
4.1.3 作用域 …………………………………… 34
4.2 規範 ………………………………………………… 37
4.3 遞迴 ………………………………………………… 39
4.3.1 斐波那契數列 ………………………… 40
4.3.2 回文 ………………………………………. 42
4.4 全域變數 ………………………………………….. 45
4.5 模組 ………………………………………………… 46
4.6 文件 ………………………………………………… 47
第5 章 結構化類型、可變性與
高階函數 …………………………………….. 50
5.1 元組 ………………………………………………… 50
5.2 範圍 ………………………………………………… 52
5.3 列表與可變性 …………………………………… 52
5.3.1 克隆………………………………………. 57
5.3.2 列表推導 ……………………………….. 57
5.4 函數物件 ………………………………………….. 58
5.5 字串、元組、範圍與列表 ………………. 60
5.6 字典 ………………………………………………… 61
第6 章 測試與調試 ………………………………… 65
6.1 測試 ………………………………………………… 65
6.1.1 黑盒測試 ……………………………….. 66
6.1.2 白盒測試 ……………………………….. 68
6.1.3 執行測試 ……………………………….. 69
6.2 調試 ………………………………………………… 70
6.2.1 學習調試 ……………………………….. 72
6.2.2 設計實驗 ……………………………….. 72
6.2.3 遇到麻煩時 ……………………………. 75
6.2.4 找到“目標”錯誤之後 …………… 76
第7 章 異常與斷言 ………………………………… 77
7.1 處理異常 ………………………………………….. 77
7.2 將異常用作控制流 ……………………………. 80
7.3 斷言 ………………………………………………… 82
第8 章 類與物件導向程式設計 ……………………… 83
8.1 抽象資料類型與類 ……………………………. 83
8.1.1 使用抽象資料類型設計程式 ……. 87
8.1.2 使用類記錄學生與教師 …………… 87
2 目 錄
8.2 繼承 ………………………………………………… 90
8.2.1 多重繼承 ……………………………….. 92
8.2.2 替換原則 ……………………………….. 93
8.3 封裝與信息隱藏 ……………………………….. 94
8.4 進階示例：抵押貸款 ………………………… 99
第9 章 演算法複雜度簡介 ……………………….. 103
9.1 思考計算複雜度 ……………………………… 103
9.2 漸近標記法 …………………………………….. 106
9.3 一些重要的複雜度 ………………………….. 107
9.3.1 常數複雜度 ………………………….. 107
9.3.2 對數複雜度 ………………………….. 108
9.3.3 線性複雜度 ………………………….. 108
9.3.4 對數線性複雜度 …………………… 109
9.3.5 多項式複雜度 ………………………. 109
9.3.6 指數複雜度 ………………………….. 111
9.3.7 複雜度對比 ………………………….. 112
第10 章 一些簡單演算法和資料結構 ………. 114
10.1 搜索演算法 ………………………………………. 115
10.1.1 線性搜索與間接引用元素 ….. 115
10.1.2 二分查找和利用假設 …………. 116
10.2 排序演算法 ………………………………………. 119
10.2.1 歸併排序 ………………………….. 120
10.2.2 將函數用作參數 ………………… 122
10.2.3 Python 中的排序 ……………….. 123
10.3 散列表 …………………………………………. 124
第11 章 繪圖以及類的進一步擴展 ………. 128
11.1 使用PyLab 繪圖 ……………………………. 128
11.2 進階示例：繪製抵押貸款 ………………. 133
第12 章 背包與圖的最優化問題 ………….. 139
12.1 背包問題 ………………………………………. 139
12.1.1 貪婪演算法 ………………………….. 140
12.1.2 0/1 背包問題的最優解 ……….. 143
12.2 圖的最優化問題 ……………………………. 145
12.2.1 一些典型的圖論問題 …………… 149
12.2.2 最短路徑：深度優先搜索和
廣度優先搜索 ………………………. 149
第13 章 動態規劃 ………………………………… 155
13.1 又見斐波那契數列 ………………………… 155
13.2 動態規劃與0/1 背包問題……………….. 157
13.3 動態規劃與分治演算法 …………………….. 162
第14 章 隨機遊走與數據視覺化 ………….. 163
14.1 隨機遊走 ……………………………………… 163
14.2 醉漢游走 ……………………………………… 164
14.3 有偏隨機遊走 ……………………………….. 170
14.4 變幻莫測的田地 ……………………………. 175
第15 章 隨機程式、概率與分佈 ………….. 178
15.1 隨機程式 ……………………………………… 178
15.2 計算簡單概率 ……………………………….. 180
15.3 統計推斷 ……………………………………… 180
15.4 分佈 …………………………………………….. 192
15.4.1 概率分佈 ………………………….. 194
15.4.2 正態分佈 ………………………….. 195
15.4.3 連續型和離散型均勻分佈 ….. 199
15.4.4 二項式分佈與多項式分佈 ….. 200
15.4.5 指數分佈和幾何分佈 …………. 201
15.4.6 本福德分佈 ………………………. 203
15.5 散列與碰撞…………………………………… 204
15.6 強隊的獲勝概率 ……………………………. 206
第16 章 蒙特卡羅模擬 …………………………. 208
16.1 帕斯卡的問題 ……………………………….. 209
16.2 過線還是不過線 ……………………………. 210
16.3 使用查表法提高性能 …………………….. 213
16.4 求π 的值 ……………………………………… 214
16.5 類比模型結束語 ……………………………. 218
第17 章 抽樣與置信區間 …………………….. 220
17.1 對波士頓馬拉松比賽進行抽樣 ……….. 220
17.2 中心極限定理 ……………………………….. 225
17.3 均值的標準誤差 ……………………………. 228
第18 章 理解實驗資料 …………………………. 231
18.1 彈簧的行為…………………………………… 231
18.2 彈丸的行為…………………………………… 238
目 錄 3

18.2.1 可決係數 ………………………….. 240
18.2.2 使用計算模型 ……………………. 241
18.3 擬合指數分佈資料 …………………………. 242
18.4 當理論缺失時 ……………………………….. 245
第19 章 隨機試驗與假設檢驗 ……………… 247
19.1 檢驗顯著性 …………………………………… 248
19.2 當心P-值 ……………………………………… 252
19.3 單尾單樣本檢驗 ……………………………. 254
19.4 是否顯著 ………………………………………. 255
19.5 哪個N ………………………………………….. 257
19.6 多重假設 ………………………………………. 258
第20 章 條件概率與貝葉斯統計 ………….. 261
20.1 條件概率 ………………………………………. 262
20.2 貝葉斯定理 …………………………………… 263
20.3 貝葉斯更新 …………………………………… 264
第21 章 謊言、該死的謊言與統計學 …… 267
21.1 垃圾輸入，垃圾輸出 ……………………… 267
21.2 檢驗是有缺陷的 ……………………………. 268
21.3 圖形會騙人 …………………………………… 268
21.4 Cum Hoc Ergo Propter Hoc ……………… 270
21.5 統計測量不能說明所有問題 …………… 271
21.6 抽樣偏差 ………………………………………. 272
21.7 上下文很重要 ……………………………….. 273
21.8 慎用外推法 …………………………………… 273
21.9 德克薩斯神槍手謬誤……………………… 274
21.10 莫名其妙的百分比 ………………………. 276
21.11 不顯著的顯著統計差別 ………………… 276
21.12 回歸假像 …………………………………….. 277
21.13 小心為上 …………………………………….. 278
第22 章 機器學習簡介 …………………………. 279
22.1 特徵向量 ………………………………………. 281
22.2 距離度量 ………………………………………. 283
第23 章 聚類 ………………………………………… 288
23.1 Cluster 類 ……………………………………. 289
23.2 K 均值聚類 …………………………………… 291
23.3 虛構示例 ………………………………………. 292
23.4 更真實的示例 ……………………………….. 297
第24 章 分類方法 ………………………………… 303
24.1 分類器評價 …………………………………… 303
24.2 預測跑步者的性別 ………………………… 306
24.3 K 最近鄰方法 ……………………………….. 308
24.4 基於回歸的分類器 ………………………… 312
24.5 從“泰坦尼克”號生還 ………………….. 320
24.6 總結 …………………………………………….. 325
Python 3.5 速查表 ……………………………….. 326