本書遵循“精選案例，面向設計，深入淺出，注重能力培養”的要求，以案例形式實現算法與程序設計教學。本書精選了枚舉、遞推、遞歸、回溯、動態規劃、貪心算法與模擬等常用算法，精選各算法求解的典型案例。每一個案例求解，從案例提出到算法設計，從程序實現到算法復雜度分析，環環相扣，融為一體，力求算法理論與實際應用相結合，算法與程序相統一，突出算法在解決實際問題中的核心地位與引導作用。書中所有案例求解給出詳細的算法描述與完整的C程序，程序均在Visual C++ 6.0下編譯通過，所有源代碼均可從清華大學出版社網站下載。 本書可作為高等院校計算機及相關專業“算法設計與分析”、“程序設計基礎與應用”等課程的教材，也可供軟件設計人員與計算機愛好者學習參考。
計算機算法與程序設計是計算機科學與技術的核心，是大學計算機相關專業的一門重要專業基礎課。通過我們對現有計算機本科專業“算法設計與分析”課程教學的調研分析，發現很多同學對學過的算法思路不明了，描述不清楚，設計不到位，無法應用算法設計程序解決一些常見的實際問題。缺少適合計算機本科層次的“算法與程序設計”教材是造成這一局面的重要原因之一。
一般現有“算法設計與分析”教材在算法選取上貪多求全、貪廣求深，混雜一些難度大、理論深、應用少的帶有學術研究性質、適宜研究生階段的算法內容。同時這些教材普遍存在以下問題： 算法與數據結構結合多，而與程序設計結合少；羅列算法多，應用算法設計解決實際問題少；算法與程序設計脫節，算法理論與實際應用脫節，不利于算法設計的應用推廣，也不利于學生應用算法與程序設計解決實際問題能力的提高。
為此，筆者在編著《計算機程序設計經典題解》（清華大學出版社,2007）與《計算機常用算法與程序設計教程》（“十一五”國家級規劃教材,人民郵電出版社,2008）的基礎上進行優化整合，推出適合本科“算法與程序設計”教學實際的案例教程。
本教程遵循“精選案例，面向設計，深入淺出，注重能力培養”的宗旨編寫，在常用算法應用案例的選取與深度的把握上，在算法理論與案例求解的結合上進行精心設計，力圖滿足高校計算機本科教學目標與知識結構的要求。本書體現出以下五個特色。
（1） 以案例形式實現算法與程序設計教學。
學習算法與程序設計是為了培養提高學生應用算法與程序設計解決實際問題的能力，算法與程序設計課程教學無疑是最適宜以案例形式來實現的。通過典型案例來引導算法設計的逐步深入，實現以典型案例支撐算法，以算法設計指導案例求解的良性循環。
采用案例形式實現算法與程序設計教學在全國是首創，從案例提出到算法設計與程序實現，從案例結果討論到算法改進與復雜度分析，環環相扣，融為一體，使學生看得見，摸得著，學得會，用得上，容易收到立竿見影、舉一反三的效果。
（2） 注重常用算法的選取與組織。
在常用算法的選取上避免貪多求全、貪廣求深，去除一些難度大、理論深、應用少的帶有學術研究性質的算法內容，結合本科教學實際與應用需求，選取枚舉、遞推、遞歸、回溯、動態規劃、貪心算法與模擬等常用算法。其中模擬算法中的“豎式運算模擬”是我們總結推廣用于數論高精計算的創新成果。
對精選的各種常用算法，在介紹算法的基本理論與設計思路后，從實際案例的解決入手，講述算法中要求本科學生掌握的基本思路、設計內容與實施步驟，避免出現本科階段與研究生階段的教學內容混雜不清，避免出現蜻蜓點水、面面俱到、空洞不實的局面。
（3） 注重典型案例的精選與提煉。
針對選取的每一種常用算法，精選典型的實際案例，包括典型的數值求解、常見的數據處理、有趣的智力測試以及巧妙的模擬探索，既有引導入門的基礎案例，也有難度較大的綜合案例，既有構思巧妙的新創趣題，也有歷史悠久的經典名題，難度適宜，深入淺出。
培養學生的學習興趣，激發學生的學習熱情，提高學生的設計技能，不是一兩句空洞說教所能奏效的，必須通過一系列有趣的實際案例來引導。本教程針對所精選的常用算法，設計了初等難度基礎型、中等難度應用型、較高難度綜合型三種梯度的案例。這些案例的精選與提煉，有利于提高學生學習算法與程序設計的興趣，有利于學生在計算機實際應用上開闊視野，使之在算法思路的開拓與設計技能的運用上有一個深層次的鍛煉與提高。其中難度較大的綜合案例可作為相應課程的課程設計選用。
（4） 注重算法設計與程序實現的緊密結合。
算法與程序實際上是一個統一體，不應該也不可能將它們對立與分割。本教程在材料的組織上克服了羅列算法多，應用算法設計解決實際問題少，算法與程序設計脫節，算法理論與實際應用脫節的問題。在講述每一種常用算法的基本思路與設計步驟的基礎上，落實到每一個案例求解，從案例提出到算法設計、從程序實現到算法復雜度分析，環環相扣，融為一體，力求算法理論與實際應用相結合，算法與程序相統一，突出算法在解決實際問題中的核心地位與引導作用，切實提高學生對所學算法的理解和掌握。
本教程采用功能豐富、應用面廣、高校學生使用率最高的 C語言來描述算法、編寫程序。為使讀者使用方便，程序均在Visual C++ 6.0下編譯通過。
（5） 注重算法改進與程序優化。
本教程對一些典型案例應用多種不同的算法設計，編寫不同表現形式與不同設計風格的程序，體現了算法與程序設計的靈活性和多樣性。
算法與程序設計都不是一成不變的，可以實施多方位多層次的變通，變通出成果，變通長能力。算法改進與程序優化的過程，既是提高案例求解效率的過程，也是算法設計能力培養與提高的過程，更是優化意識與創新能力增強的過程。
為方便讀者學習，附錄中提供了部分習題求解提示，簡介在Visual C++ 6.0環境下運行C程序的方法，并列出C語言常用函數。同時，本教程中的所有源程序與各章習題的完整代碼均可在清華大學出版社網站（http://www.tup.com.cn）下載。
本教程適合各高校計算機相關本科專業“算法設計與分析”、“程序設計基礎與應用”課程教學，并可供各級程序設計競賽與ACM復習參考，也可供IOI、NOI培訓選用。
在本書的編著修訂過程中，湖南理工學院王岳斌教授、周持中教授、嚴權鋒副教授與譚用秋博士等給予作者多方面的支持與幫助，劉志輝碩士閱讀了全部書稿并運行了所有程序，作者在此一并深表感謝。
盡管每一案例求解都經反復核實檢查，每一求解程序都經多次運行調試，但因涉及內容較廣，書中難免存在差錯，懇請讀者批評指正。
楊克昌2014年6月于岳陽南湖
第1章算法與程序設計概述1
1.1算法及其描述1
1.1.1算法定義1
1.1.2算法描述3
1.2算法的復雜性分析7
1.2.1時間復雜度7
1.2.2空間復雜度12
1.3算法設計與分析示例13
1.3.1求解最大公約數13
1.3.2拆分為連續正整數之和15
1.3.3統計n!尾部零17
1.4算法與程序設計19
1.4.1算法與程序19
1.4.2結構化程序設計23
習題126第2章枚舉28
2.1枚舉概述28
2.2統計與求和29
2.2.1全素組30
2.2.2最簡真分數32
2.3解方程33
2.3.1佩爾方程33
2.3.2超越方程35
2.4解不等式37
2.4.1分數不等式37
2.4.2代數和不等式38
2.5求最值41
2.5.1基于素數的代數和41
2.5.2整數的因數比43
2.6數組與序列44
2.6.1雙和二組44
2.6.2和積三組46
2.6.3雙碼二部數序列47
2.7數式探求50
2.7.1逆序乘積式50
2.7.2完美綜合式51
2.8趣味數陣55
2.8.1素數幻方55
2.8.2和積三角形58
2.9枚舉應用小結60
習題265第3章遞推66
3.1遞推概述66
3.1.1遞推算法66
3.1.2遞推實施步驟與描述67
3.2超級素數搜索69
3.3遞推數列72
3.3.1擺動數列72
3.3.2分數數列73
3.4冪序列75
3.4.1雙冪序列75
3.4.2冪積序列76
3.5數陣與網格82
3.5.1楊輝三角82
3.5.2交通方格網84
3.6整數劃分問題86
3.6.1整數劃分遞推設計86
3.6.2整數劃分遞推優化88
3.7水手分椰子問題90
3.7.15個水手分椰子90
3.7.2n個水手分椰子93
3.8猴子爬山94
3.8.1簡單案例的具體遞推95
3.8.2一般情形的分級遞推95
3.9遞推應用小結97
習題399第4章遞歸101
4.1遞歸概述101
4.2排隊購票104
4.3漢諾塔問題106
4.3.1求移動次數106
4.3.2展示移動過程107
4.4旋轉數陣109
4.4.1雙轉向旋轉方陣109
4.4.2m行n列順轉矩陣111
4.5快速排序與選擇114
4.5.1快速排序114
4.5.2分區交換選擇117
4.6排列組合的實現119
4.6.1實現排列A(n,m)119
4.6.2實現組合C(n,m)121
4.6.3復雜排列123
4.7整數的拆分125
4.7.1拆分零數取自連續區間126
4.7.2拆分零數取自指定整數127
4.8遞歸應用小結129
習題4132第5章回溯法133
5.1回溯法概述133
5.1.1回溯的概念133
5.1.2回溯描述133
5.2橋本分數式137
5.2.1橋本分數式138
5.2.210數字分數式140
5.3直尺與串珠141
5.3.1古尺神奇141
5.3.2數碼串珠144
5.4逐位整除數146
5.5環序列149
5.5.1素數和環150
5.5.2德布魯金環151
5.6伯努利裝錯信封問題154
5.6.1裝錯信封問題154
5.6.2特殊錯位探索157
5.7別出心裁的情侶拍照問題159
5.7.1逐位安排與回溯159
5.7.2成對安排與回溯161
5.8回溯應用小結163
習題5166第6章動態規劃167
6.1動態規劃概述167
6.1.1動態規劃的概念167
6.1.2動態規劃實施步驟168
6.2最長子序列探索169
6.2.1最長非降子序列169
6.2.2最長公共子序列172
6.3最優路徑搜索175
6.3.1點數值三角形的最優路徑175
6.3.2邊數值矩形的最優路徑177
6.4裝載問題180
6.501背包問題183
6.5.1一般01背包問題184
6.5.2二維約束01背包問題188
6.6凸n邊形的三角形劃分190
6.7插入乘號問題193
6.8動態規劃應用小結195
習題6198第7章貪心算法200
7.1貪心算法概述200
7.2刪數字問題202
7.3埃及分數式205
7.3.1選擇最小分母構建205
7.3.2貪心選擇范圍的擴展207
7.4可拆背包問題208
7.5數列操作與極差209
7.5.1數列操作210
7.5.2數列操作優化211
7.5.3數列極差212
7.6哈夫曼樹及其應用215
7.6.1哈夫曼樹215
7.6.2哈夫曼編碼217
7.7貪心算法應用小結221
習題7222第8章模擬224
8.1模擬概述224
8.1.1模擬分類224
8.1.2豎式運算模擬227
8.2乘數探求229
8.2.1積為若干個1構成229
8.2.2積為若干個2015構成230
8.2.3積的任意指定構成231
8.3尾數前移問題233
8.3.1限1位尾數前移233
8.3.2多位尾數前移235
8.4階乘冪與排列組合數的計算236
8.5圓周率計算238
8.5.1蒙特卡羅模擬計算238
8.5.2指定高精度計算239
8.6漫步坐標系241
8.7模擬發橋牌244
8.8泊松分酒問題247
8.9模擬應用小結250
習題8251第9章算法的綜合應用253
9.1高斯皇后問題253
9.1.1高斯八皇后問題253
9.1.2n皇后問題255
9.1.3皇后全控棋盤問題259
9.2翻轉硬幣游戲263
9.2.1翻轉m×9矩陣263
9.2.2翻轉m×n矩陣266
9.2.3大規模矩陣求解270
9.3最優復雜路徑探索273
9.3.1矩陣迷宮中的最短通道273
9.3.2三角數陣中的最小路徑277
9.4馬步遍歷與哈密頓圈280
9.4.1馬步遍歷280
9.4.2馬步型哈密頓圈287
9.4.3組合型哈密頓圈292
9.5綜合應用小結299
習題9300附錄A部分習題求解要點301附錄B在Visual C++ 6.0環境下運行C程序方法簡介315附錄CC語言常用庫函數320參考文獻324
新書資訊