算法與程序設計

本書遵循“精選案例，面向設計，深入淺出，註重能力培養”的要求，以案例形式實現算法與程序設計教學，精選了窮舉法、遞推法、回溯法、分支限界法、遞歸法、分治法、貪心算法、動態規劃法和隨機算法等常用算法進行講解，並給出了使用各算法求解的典型案例。對於每一個案例的求解，從問題提出到算法設計、從程序實現到算法復雜度分析，環環相扣，融為一體，力求理論與實際相結合、算法與程序相統一，突出算法在解決實際問題中的核心地位與引導作用。本書中的所有案例均給出算法設計要點與完整的C語言或者C++語言程序代碼（均在VC++ 6.0上編譯通過）。為方便教學，每章都附有習題，同時提供教學課件、習題答案、源代碼等配套資源，讀者可登錄華信教育資源網（www.hxedu.com.cn）免費下載使用。本書既可作為高等院校電腦專業相關課程的教材，也可供IT從業人員和電腦編程愛好者參考使用。

第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　結構化程式設計 19 
1.3.3　結構化程式設計實例 20 
習題 21 
第2章　窮舉法 23 
2.1　窮舉法概述 23 
2.1.1　窮舉法的基本思想 23 
2.1.2　窮舉法的實施步驟與演算法描述 23 
2.2　整數搜索 25 
2.2.1　算24點游戲 25 
2.2.2　韓信點兵 27 
2.2.3　素數問題 28 
2.2.4　約瑟夫環問題 29 
2.2.5　火柴棒等式 30 
2.2.6　三色旗問題 31 
2.2.7　勾股數問題 32 
2.2.8　猜價格游戲 33 
2.3　分解與重組 35 
2.3.1　水仙花數 35 
2.3.2　迴文數 35 
2.3.3　完數 36 
2.4　趣味數學 37 
2.4.1　百錢買百雞問題 37 
2.4.2　搬磚問題 38 
2.4.3　雞兔同籠問題 38 
2.4.4　數學燈謎 39 
2.5　解方程與不等式 40 
2.5.1　解二元一次方程 40 
2.5.2　解完美立方式 40 
2.5.3　解一元二次不等式 41 
2.6　數陣與圖形 42 
2.6.1　楊輝三角形 42 
2.6.2　輸出各種圖形 43 
2.7　窮舉設計的優化 45 
習題 47 
第3章　遞推法 48 
3.1　遞推法概述 48 
3.1.1　遞推法的基本思想 48 
3.1.2　遞推法的實施步驟與演算法描述 49 
3.2　遞推數列 51 
3.2.1　斐波那契數列和盧卡斯數列 51 
3.2.2　分數數列 53 
3.2.3　冪序列 53 
3.2.4　雙關系遞推數列 54 
3.2.5　儲油點問題 56 
3.3　遞推數陣 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　整數劃分問題 61 
3.4.4　漢諾塔問題 61 
3.4.5　體重指數BMI 62 
3.4.6　求π的近似值 63 
3.4.7　求一元二次方程的根 63 
3.4.8　求三角形的面積 64 
3.4.9　存錢問題 65 
3.4.10　求最大公約數和最小公倍數 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　批處理作業調度 75 
4.2.5　符號三角形問題 77 
4.2.6　最大團問題 78 
4.2.7　旅行售貨員問題 80 
4.2.8　電路板排列問題 82 
4.2.9　連續郵資問題 84 
4.2.10　圓排列問題 86 
4.2.11　橋本分數式 88 
4.2.12　素數環 89 
4.2.13　神奇古尺 91 
4.3　回溯設計的優化 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　六數位問題 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　整數劃分問題 111 
6.2.2　漢諾塔問題 112 
6.2.3　枚舉排列問題 113 
6.2.4　用遞歸法求斐波那契數列 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　大整數乘法 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　循環賽日程表 137 
7.3　遞歸轉化 139 
7.3.1　一般的遞歸轉非遞歸 139 
7.3.2　分治法中的遞歸轉化 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　區間覆蓋問題 151 
8.5.2　最大不相交覆蓋 151 
8.5.3　點覆蓋 151 
8.6　教室調度問題 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　機器調度問題 175 
8.16　錢幣找零問題 176 
習題 177 
第9章　動態規劃法 178 
9.1　動態規劃法概述 178 
9.1.1　動態規劃法的基本思想 178 
9.1.2　動態規劃法的實施步驟與演算法描述 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　數字三角形最大路徑和 192 
9.6.2　多源最短路徑問題 194 
9.6.3　走方格問題 197 
9.6.4　郵資問題 198 
9.7　動態規劃與其他演算法的比較 199 
習題 200 
第10章　隨機演算法 201 
10.1　隨機演算法概述 201 
10.2　隨機數 201 
10.2.1　隨機生成數組元素 202 
10.2.2　隨機生成數字 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　蒙特卡羅演算法的優缺點及改進措施 213 
10.6　拉斯維加斯演算法 214 
10.7　蒙特卡羅演算法和拉斯維加斯演算法的比較 217 
10.8　隨機演算法的優缺點 217 
習題 217 
附錄A　不同演算法的比較 219 
參考文獻 221