算法與程序設計

第1章　算法與程序設計簡介 1
1.1　初識算法 1
1.1.1　算法的基本概念 2
1.1.2　算法的描述 4
1.1.3　算法設計的步驟 7
1.1.4　算法的分類 8
1.2　算法復雜度分析 9
1.2.1　時間復雜度 9
1.2.2　空間復雜度 14
1.2.3　算法設計實例 15
1.3　程序設計簡介 17
1.3.1　算法與程序 18
1.3.2　結(jié)構(gòu)化程序設計 19
1.3.3　結(jié)構(gòu)化程序設計實例 20
習題 21
第2章　窮舉法 23
2.1　窮舉法概述 23
2.1.1　窮舉法的基本思想 23
2.1.2　窮舉法的實施步驟與算法描述 23
2.2　整數(shù)搜索 25
2.2.1　算24點游戲 25
2.2.2　韓信點兵 27
2.2.3　素數(shù)問題 28
2.2.4　約瑟夫環(huán)問題 29
2.2.5　火柴棒等式 30
2.2.6　三色旗問題 31
2.2.7　勾股數(shù)問題 32
2.2.8　猜價格游戲 33
2.3　分解與重組 35
2.3.1　水仙花數(shù) 35
2.3.2　回文數(shù) 35
2.3.3　完數(shù) 36
2.4　趣味數(shù)學 37
2.4.1　百錢買百雞問題 37
2.4.2　搬磚問題 38
2.4.3　雞兔同籠問題 38
2.4.4　數(shù)學燈謎 39
2.5　解方程與不等式 40
2.5.1　解二元一次方程 40
2.5.2　解完美立方式 40
2.5.3　解一元二次不等式 41
2.6　數(shù)陣與圖形 42
2.6.1　楊輝三角形 42
2.6.2　輸出各種圖形 43
2.7　窮舉設計的優(yōu)化 45
習題 47
第3章　遞推法 48
3.1　遞推法概述 48
3.1.1　遞推法的基本思想 48
3.1.2　遞推法的實施步驟與算法描述 49
3.2　遞推數(shù)列 51
3.2.1　斐波那契數(shù)列和盧卡斯數(shù)列 51
3.2.2　分數(shù)數(shù)列 53
3.2.3　冪序列 53
3.2.4　雙關(guān)系遞推數(shù)列 54
3.2.5　儲油點問題 56
3.3　遞推數(shù)陣 57
3.3.1　累加和 57
3.3.2　階乘問題 58
3.3.3　九九乘法表 58
3.4　遞推的其他應用 59
3.4.1　猴子爬山問題 59
3.4.2　整幣兌零問題 60
3.4.3　整數(shù)劃分問題 61
3.4.4　漢諾塔問題 61
3.4.5　體重指數(shù)BMI 62
3.4.6　求π的近似值 63
3.4.7　求一元二次方程的根 63
3.4.8　求三角形的面積 64
3.4.9　存錢問題 65
3.4.10　求公約數(shù)和小公倍數(shù) 66
習題 67
第4章　回溯法 68
4.1　回溯法概述 68
4.1.1　回溯法的基本思想 68
4.1.2　回溯法的實施步驟和算法描述 69
4.2　回溯法的應用 70
4.2.1　八皇后問題 70
4.2.2　圖的著色問題 71
4.2.3　裝載問題 73
4.2.4　批處理作業(yè)調(diào)度 75
4.2.5　符號三角形問題 77
4.2.6　團問題 78
4.2.7　旅行售貨員問題 80
4.2.8　電路板排列問題 82
4.2.9　連續(xù)郵資問題 84
4.2.10　圓排列問題 86
4.2.11　橋本分數(shù)式 88
4.2.12　素數(shù)環(huán) 89
4.2.13　神奇古尺 91
4.3　回溯設計的優(yōu)化 92
習題 93
第5章　分支限界法 94
5.1　分支限界法概述 94
5.1.1　分支限界法的基本思想 94
5.1.2　分支限界法的實施步驟和算法描述 94
5.2　分支限界法的應用 95
5.2.1　迷宮問題 95
5.2.2　六數(shù)碼問題 98
5.2.3　旅行商問題 101
5.2.4　背包問題 104
5.3　回溯法與分支限界法的比較 108
習題 109
第6章　遞歸法 110
6.1　遞歸法概述 110
6.1.1　遞歸法的基本思想 110
6.1.2　遞歸法的實施步驟和算法描述 110
6.2　遞歸法的應用 111
6.2.1　整數(shù)劃分問題 111
6.2.2　漢諾塔問題 112
6.2.3　枚舉排列問題 113
6.2.4　用遞歸法求斐波那契數(shù)列 114
6.2.5　排隊買票問題 115
6.2.6　猴子吃桃子問題 116
6.2.7　RPG涂色問題 117
6.2.8　二叉樹的遍歷 118
6.3　回溯法與遞歸法的比較 120
習題 120
第7章　分治法 121
7.1　分治法概述 121
7.1.1　分治法的基本思想 121
7.1.2　分治法的實施步驟和算法描述 122
7.2　分治法的應用 123
7.2.1　二分查找法 123
7.2.2　大整數(shù)乘法 125
7.2.3　斯特拉森矩陣乘法 127
7.2.4　棋盤覆蓋問題 128
7.2.5　合并排序 129
7.2.6　快速排序 132
7.2.7　線性時間選擇 133
7.2.8　近點對問題 136
7.2.9　循環(huán)賽日程表 137
7.3　遞歸轉(zhuǎn)化 139
7.3.1　一般的遞歸轉(zhuǎn)非遞歸 139
7.3.2　分治法中的遞歸轉(zhuǎn)化 141
習題 143
第8章　貪心算法 145
8.1　貪心算法概述 145
8.1.1　貪心算法的基本思想 145
8.1.2　貪心算法的實施步驟與算法描述 145
8.2　活動安排問題 146
8.3　田忌賽馬 148
8.4　背包問題 149
8.5　覆蓋問題 151
8.5.1　區(qū)間覆蓋問題 151
8.5.2　不相交覆蓋 151
8.5.3　點覆蓋 151
8.6　教室調(diào)度問題 153
8.7　小生成樹——Kruskal算法 155
8.8　小生成樹——Prim算法 157
8.9　哈夫曼編碼 160
8.10　教室分配問題 164
8.11　短路徑——弗洛伊德算法 166
8.12　短路徑——迪杰斯德拉算法 169
8.13　均分紙牌 172
8.14　瀏覽路線問題 173
8.15　機器調(diào)度問題 175
8.16　錢幣找零問題 176
習題 177
第9章　動態(tài)規(guī)劃法 178
9.1　動態(tài)規(guī)劃法概述 178
9.1.1　動態(tài)規(guī)劃法的基本思想 178
9.1.2　動態(tài)規(guī)劃法的實施步驟與算法描述 179
9.2　裝載問題 180
9.3　投資分配問題 181
9.4　背包問題 185
9.4.1　0-1背包問題 185
9.4.2　二維0-1背包問題 187
9.5　長子序列探索 188
9.5.1　長非降子序列 188
9.5.2　長公共子序列（Longest Common Subsequence，LCS） 190
9.6　路徑搜索 192
9.6.1　數(shù)字三角形路徑和 192
9.6.2　多源短路徑問題 194
9.6.3　走方格問題 197
9.6.4　郵資問題 198
9.7　動態(tài)規(guī)劃與其他算法的比較 199
習題 200
第10章　隨機算法 201
10.1　隨機算法概述 201
10.2　隨機數(shù) 201
10.2.1　隨機生成數(shù)組元素 202
10.2.2　隨機生成數(shù)字 204
10.2.3　隨機生成計算題 206
10.3　同余算法 208
10.4　舍伍德算法 209
10.5　蒙特卡羅算法 211
10.5.1　用蒙特卡羅算法求π的值 211
10.5.2　用蒙特卡羅算法求特殊圖形的面積 212
10.5.3　蒙特卡羅算法的優(yōu)缺點及改進措施 213
10.6　拉斯維加斯算法 214
10.7　蒙特卡羅算法和拉斯維加斯算法的比較 217
10.8　隨機算法的優(yōu)缺點 217
習題 217
附錄A　不同算法的比較 219
參考文獻 221