•注重常用算法的選取與組織。結(jié)合本科教學(xué)實(shí)際，精心選取了幾個(gè)常用算法。

•注重典型案例的精選與提煉。對(duì)選取的每一種算法，設(shè)計(jì)了基礎(chǔ)型、應(yīng)用型與綜合型三種難度梯度的典型案例。

•注重算法設(shè)計(jì)與實(shí)現(xiàn)的緊密結(jié)合。采用功能豐富、應(yīng)用面廣、高校學(xué)生使用率最高的C語(yǔ)言描述算法，并直接在VC++環(huán)境下測(cè)試通過(guò)，大大縮減了算法設(shè)計(jì)與程序?qū)崿F(xiàn)的距離。

•注重算法設(shè)計(jì)的改進(jìn)與優(yōu)化。對(duì)某些典型案例提供了多種算法設(shè)計(jì)，編寫(xiě)出不同表現(xiàn)形式和設(shè)計(jì)風(fēng)格的算法，體現(xiàn)了算法設(shè)計(jì)的靈活性和多樣性。

進(jìn)入21世紀(jì)，隨著計(jì)算機(jī)的廣泛普及與信息技術(shù)的深入發(fā)展，培養(yǎng)應(yīng)用型軟件開(kāi)發(fā)人才成為提高國(guó)家科技水平的重要方面。國(guó)家“973”信息技術(shù)與高性能軟件基礎(chǔ)規(guī)劃項(xiàng)目首席科學(xué)家顧鈞教授與中國(guó)工程院院士李國(guó)杰教授指出：“我國(guó)的軟件開(kāi)發(fā)要算法先行，這樣才能推動(dòng)軟件技術(shù)的研究與開(kāi)發(fā)，提高我國(guó)企業(yè)軟件產(chǎn)品的技術(shù)競(jìng)爭(zhēng)力和市場(chǎng)競(jìng)爭(zhēng)力。”

“算法設(shè)計(jì)與分析”是計(jì)算機(jī)科學(xué)技術(shù)學(xué)科體系的一個(gè)核心問(wèn)題，是大學(xué)計(jì)算機(jī)專(zhuān)業(yè)一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課。計(jì)算機(jī)算法設(shè)計(jì)是應(yīng)用計(jì)算機(jī)解決實(shí)際問(wèn)題的核心環(huán)節(jié)，是一種創(chuàng)造性思維活動(dòng)，其教育必須面向應(yīng)用。針對(duì)目前相關(guān)教材中，算法內(nèi)容貪多求全、貪廣求深，算法理論與實(shí)際應(yīng)用脫節(jié)的現(xiàn)狀，探索與改革適合計(jì)算機(jī)本科層次教學(xué)的“算法設(shè)計(jì)與分析”教材，直接關(guān)系到學(xué)生應(yīng)用算法設(shè)計(jì)解決實(shí)際問(wèn)題能力的培養(yǎng)與提高，是實(shí)現(xiàn)算法課程教學(xué)目標(biāo)的當(dāng)務(wù)之急。

為此，我們?cè)凇队?jì)算機(jī)常用算法與程序設(shè)計(jì)教程》（“十一五”國(guó)家級(jí)規(guī)劃教材，人民郵電出版社，2008.11）與《計(jì)算機(jī)常用算法與程序設(shè)計(jì)案例教程》（清華大學(xué)出版社，2011.7）兩本書(shū)的基礎(chǔ)上進(jìn)行整合優(yōu)化，推出適合計(jì)算機(jī)本科教學(xué)實(shí)際的《算法設(shè)計(jì)與分析實(shí)用教程》，對(duì)算法的組織與案例的選取、算法理論闡述與案例實(shí)際應(yīng)用結(jié)合進(jìn)行精心設(shè)計(jì)，力求適合高校本科教學(xué)目標(biāo)與知識(shí)結(jié)構(gòu)的要求。

本書(shū)遵循“精選算法，面向設(shè)計(jì)，突出案例應(yīng)用，注重能力培養(yǎng)”的編寫(xiě)宗旨，具有以下“四注重”特色。

（1）注重常用算法的選取與組織

本書(shū)在常用算法的選取方面，克服以往貪多求全、貪廣求深的弊端，結(jié)合本科教學(xué)實(shí)際，精心選取了枚舉、遞推、遞歸、動(dòng)態(tài)規(guī)劃、回溯、貪心算法與模擬等常用算法，避免出現(xiàn)本科階段與研究生階段的教學(xué)內(nèi)容混雜不分的局面。其中，模擬算法中的“豎式運(yùn)算模擬”是我們總結(jié)推廣應(yīng)用于數(shù)論高精計(jì)算的創(chuàng)新成果。

對(duì)選取的常用算法，在介紹算法的基本理論與設(shè)計(jì)規(guī)范的基礎(chǔ)上，推介該算法設(shè)計(jì)應(yīng)用的常用模式，聯(lián)系典型案例講述該算法中要求本科生掌握的基本內(nèi)容與應(yīng)用設(shè)計(jì)，刪除一些難度大、理論深、應(yīng)用少的帶研究性質(zhì)的算法內(nèi)容。

（2）注重典型案例的精選與提煉

算法是程序設(shè)計(jì)的核心，算法需要典型案例的展示與支撐。培養(yǎng)學(xué)生學(xué)習(xí)算法設(shè)計(jì)的興趣，激發(fā)學(xué)生應(yīng)用算法設(shè)計(jì)解決實(shí)際問(wèn)題的學(xué)習(xí)熱情，不是一兩句空洞說(shuō)教所能奏效的，必須通過(guò)一些有趣的、有啟發(fā)性的典型案例來(lái)引導(dǎo)。教程在算法材料的組織上，克服以往羅列算法多、應(yīng)用算法設(shè)計(jì)解決實(shí)際問(wèn)題少、算法理論與實(shí)際應(yīng)用脫節(jié)的弊端，對(duì)選取的每一種算法，設(shè)計(jì)了基礎(chǔ)型、應(yīng)用型與綜合型三種難度梯度的典型案例，包括基礎(chǔ)的數(shù)值求解、常見(jiàn)的數(shù)據(jù)處理、有趣的智力測(cè)試、巧妙的模擬探索，既有啟發(fā)引導(dǎo)的基礎(chǔ)案例，也有難度較大的綜合案例，既有構(gòu)思巧妙的新創(chuàng)趣題，也有歷史悠久的經(jīng)典名題，難度適宜，深入淺出。

這些典型案例的精選與提煉有利于提高學(xué)生學(xué)習(xí)算法設(shè)計(jì)的興趣，有利于學(xué)生在計(jì)算機(jī)實(shí)際案例求解上開(kāi)闊視野，使之在算法思路的開(kāi)拓與設(shè)計(jì)技巧的應(yīng)用上有一個(gè)深層次的鍛煉與提高。通過(guò)典型案例來(lái)展開(kāi)算法設(shè)計(jì)與分析，突出算法設(shè)計(jì)在解決實(shí)際案例中的核心地位與指導(dǎo)作用。其中一些難度較大的綜合型案例可作為課后的專(zhuān)題研究與課程設(shè)計(jì)選用。

（3）注重算法設(shè)計(jì)與實(shí)現(xiàn)的緊密結(jié)合

算法是程序設(shè)計(jì)的核心與靈魂，程序是算法的一種描述與實(shí)現(xiàn)手段。算法與程序?qū)嶋H上是一個(gè)統(tǒng)一體，不應(yīng)該也不能將它們對(duì)立或分割。教程采用功能豐富、應(yīng)用面廣、高校學(xué)生使用率最高的C語(yǔ)言描述算法，并直接在VC++環(huán)境下測(cè)試通過(guò)，大大縮減了算法設(shè)計(jì)與程序?qū)崿F(xiàn)的距離。對(duì)每一個(gè)實(shí)際案例，從案例提出、算法設(shè)計(jì)與描述，到算法測(cè)試與分析、算法改進(jìn)與優(yōu)化，環(huán)環(huán)相扣，融為一體。學(xué)生看得懂、學(xué)得會(huì)、用得上，可以收到立竿見(jiàn)影、舉一反三的效果，力求理論與實(shí)際相結(jié)合、算法設(shè)計(jì)與應(yīng)用實(shí)際相統(tǒng)一，突出算法在解決實(shí)際案例中的核心地位與引導(dǎo)作用，切實(shí)提高學(xué)生對(duì)算法思想的理解和算法設(shè)計(jì)的把握，有效提高學(xué)生應(yīng)用算法設(shè)計(jì)解決實(shí)際問(wèn)題的水平和能力。

（4）注重算法設(shè)計(jì)的改進(jìn)與優(yōu)化

算法設(shè)計(jì)不可能是一成不變的，教材對(duì)某些典型案例提供了多種算法設(shè)計(jì)，編寫(xiě)出不同表現(xiàn)形式與不同設(shè)計(jì)風(fēng)格的算法，并對(duì)一些常規(guī)設(shè)計(jì)實(shí)施多層次多方位的變通、改進(jìn)與優(yōu)化，集中體現(xiàn)了算法設(shè)計(jì)的靈活性和多樣性。對(duì)不同算法的復(fù)雜性分析，確立不同算法的特點(diǎn)與適應(yīng)環(huán)境，比較出不同算法的優(yōu)劣。

變通出成果，變通長(zhǎng)能力。算法改進(jìn)與優(yōu)化的過(guò)程既是提高案例求解效率的過(guò)程，也是對(duì)學(xué)生算法設(shè)計(jì)能力培養(yǎng)與提高的過(guò)程，更是優(yōu)化意識(shí)與創(chuàng)新能力增強(qiáng)的過(guò)程。

為方便師生教學(xué)，本書(shū)配套的教學(xué)課件、源代碼與習(xí)題的參考解答均可從指定網(wǎng)站下載。

本書(shū)可作為各高等院校計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)“算法設(shè)計(jì)與分析”、“計(jì)算機(jī)程序設(shè)計(jì)應(yīng)用基礎(chǔ)”等課程教材，供各級(jí)程序設(shè)計(jì)選拔賽與ACM復(fù)習(xí)參考；也可供IOI、NOI及各省程序設(shè)計(jì)競(jìng)賽培訓(xùn)選用；還可作為廣大程序設(shè)計(jì)愛(ài)好者與軟件開(kāi)發(fā)人員的參考書(shū)。

本書(shū)由楊克昌、嚴(yán)權(quán)峰進(jìn)行策劃、編著與統(tǒng)稿。在本書(shū)的編寫(xiě)過(guò)程中，湖南理工學(xué)院的王岳斌教授、周持中教授以及甘靖、方世林等老師給予了多方面的指導(dǎo)與幫助，唐雁、陳凱、姜鎮(zhèn)林等同學(xué)閱讀了書(shū)稿并測(cè)試了相關(guān)算法，在此深表感謝。

盡管每一算法設(shè)計(jì)都經(jīng)反復(fù)核實(shí)檢查與檢測(cè)調(diào)試，但因涉及內(nèi)容較廣，難免存在差錯(cuò)，懇請(qǐng)專(zhuān)家與讀者批評(píng)指正。

編著者

2013年6月

前言

第1章 算法及其復(fù)雜性分析 1
1.1 算法及其描述 1
1.1.1 算法定義與特性 1
1.1.2 算法描述 3
1.2 算法復(fù)雜性分析 7
1.2.1 算法的時(shí)間復(fù)雜度 7
1.2.2 算法的空間復(fù)雜度 12
1.2.3 NP完全問(wèn)題 12
1.3 算法設(shè)計(jì)與分析實(shí)例 13
1.3.1 求解最大公約數(shù) 13
1.3.2 計(jì)算n! 14
1.3.3 全碼倍數(shù)搜索 16
1.4 算法與程序設(shè)計(jì) 17
1.4.1 算法與程序 17
1.4.2 結(jié)構(gòu)化程序設(shè)計(jì) 21
習(xí)題1 23
第2章 枚舉 26
2.1 枚舉概要 26
2.2 統(tǒng)計(jì)求和 27
2.2.1 同碼小數(shù) 27
2.2.2 三角網(wǎng)格 30
2.3 整數(shù)搜索 32
2.3.1 整數(shù)對(duì) 32
2.3.2 基于s的雙和數(shù)組 33
2.3.3 最小連續(xù)m個(gè)合數(shù) 34
2.4 解方程與不等式 37
2.4.1 佩爾方程 37
2.4.2 分?jǐn)?shù)不等式 38
2.5 數(shù)式與運(yùn)算 40
2.5.1 奇數(shù)序列運(yùn)算式 40
2.5.2 完美綜合運(yùn)算式 41
2.6 數(shù)列與數(shù)陣 44
2.6.1 H形數(shù)序列 44
2.6.2 三階素?cái)?shù)幻方 46
2.7 表格與圖形 48
2.7.1 p進(jìn)制乘法表 48
2.7.2 基于s的和積三角形 49
2.8 枚舉設(shè)計(jì)的改進(jìn)與優(yōu)化 52
2.8.1 選擇枚舉路線(xiàn) 52
2.8.2 精簡(jiǎn)枚舉結(jié)構(gòu) 54
2.8.3 優(yōu)化枚舉參數(shù) 55
習(xí)題2 56
第3章 遞推 59
3.1 遞推概述 59
3.1.1 遞推的概念 59
3.1.2 遞推常用模式 60
3.2 遞推數(shù)列 61
3.2.1 雙關(guān)系遞推數(shù)列 62
3.2.2 振動(dòng)數(shù)列 63
3.2.3 分?jǐn)?shù)數(shù)列 65
3.3 超級(jí)素?cái)?shù)搜索 66
3.4 數(shù)陣與網(wǎng)格 69
3.4.1 楊輝三角 69
3.4.2 方格網(wǎng)交通線(xiàn)路 71
3.5 六六順數(shù)組 73
3.6 猴子爬山 76
3.6.1 簡(jiǎn)單遞推設(shè)計(jì) 76
3.6.2 分級(jí)遞推設(shè)計(jì) 77
3.7 整數(shù)劃分 79
3.7.1 整數(shù)劃分式的個(gè)數(shù) 79
3.7.2 整數(shù)劃分式的實(shí)現(xiàn) 80
3.7.3 實(shí)現(xiàn)整數(shù)劃分式的優(yōu)化 82
3.8 遞推與迭代 84
習(xí)題3 86
第4章 遞歸 88
4.1 分治策略與遞歸 88
4.2 漢諾塔游戲 92
4.2.1 移動(dòng)次數(shù)求解 93
4.2.2 移動(dòng)過(guò)程實(shí)現(xiàn) 94
4.3 排隊(duì)購(gòu)票問(wèn)題 96
4.3.1 常規(guī)排隊(duì) 96
4.3.2 帶條件限制的排隊(duì) 98
4.4 多轉(zhuǎn)向旋轉(zhuǎn)方陣 100
4.5 快速排序與選擇 102
4.5.1 分區(qū)交換排序 103
4.5.2 分區(qū)交換選擇 105
4.6 實(shí)現(xiàn)排列組合 107
4.6.1 基本排列實(shí)現(xiàn) 107
4.6.2 復(fù)雜排列實(shí)現(xiàn) 109
4.6.3 組合實(shí)現(xiàn) 111
4.7 整數(shù)的拆分式 113
4.8 遞歸與遞推 115
習(xí)題4 117
第5章 回溯法 119
5.1 回溯法概述 119
5.1.1 回溯的概念 119
5.1.2 回溯的數(shù)學(xué)概括與效益分析 120
5.1.3 回溯法的分類(lèi) 121
5.2 橋本分?jǐn)?shù)式 124
5.3 直尺與串珠 127
5.3.1 古尺神奇 127
5.3.2 數(shù)碼串珠 129
5.4 逐位整除數(shù) 132
5.4.1 回溯探索 132
5.4.2 遞推求解 133
5.5 二組均分 135
5.6 伯努利裝錯(cuò)信封問(wèn)題 136
5.6.1 回溯設(shè)計(jì) 137
5.6.2 遞歸探索 138
5.7 情侶拍照 140
5.7.1 逐位安排回溯設(shè)計(jì) 140
5.7.2 成對(duì)安排回溯設(shè)計(jì) 142
5.8 回溯應(yīng)用小結(jié) 144
習(xí)題5 145
第6章 動(dòng)態(tài)規(guī)劃 147
6.1 動(dòng)態(tài)規(guī)劃概述 147
6.1.1 動(dòng)態(tài)規(guī)劃的概念 147
6.1.2 動(dòng)態(tài)規(guī)劃實(shí)施步驟 149
6.2 0-1背包問(wèn)題 150
6.2.1 一般0-1背包問(wèn)題 150
6.2.2 二維約束0-1背包問(wèn)題 153
6.3 西瓜分堆 156
6.4 凸n邊形的三角形劃分 158
6.5 最長(zhǎng)子序列 160
6.5.1 最長(zhǎng)非降子序列 160
6.5.2 最長(zhǎng)公共子序列 163
6.6 插入乘號(hào)問(wèn)題 165
6.7 數(shù)陣中的最優(yōu)路徑 167
6.7.1 三角數(shù)陣中的最大路徑 167
6.7.2 矩陣中的最大路徑 169
6.8 動(dòng)態(tài)規(guī)劃設(shè)計(jì)小結(jié) 172
習(xí)題6 172
第7章 貪心算法 174
7.1 貪心算法概述 174
7.1.1 貪心算法的概念 174
7.1.2 貪心算法的理論基礎(chǔ) 175
7.2 背包問(wèn)題 176
7.2.1 可拆背包問(wèn)題 176
7.2.2 0-1背包問(wèn)題 178
7.3 刪數(shù)字問(wèn)題 179
7.4 埃及分?jǐn)?shù)式 182
7.4.1 選擇最小分母構(gòu)建 182
7.4.2 貪心選擇范圍的擴(kuò)展 184
7.5 數(shù)列操作與極差 185
7.5.1 數(shù)列操作 185
7.5.2 數(shù)列操作優(yōu)化 187
7.5.3 數(shù)列極差 188
7.6 哈夫曼樹(shù)及其應(yīng)用 190
7.6.1 哈夫曼樹(shù) 190
7.6.2 哈夫曼編碼 193
7.7 貪心算法應(yīng)用小結(jié) 196
習(xí)題7 197
第8章 模擬 199
8.1 模擬概述 199
8.1.1 模擬分類(lèi) 199
8.1.2 豎式運(yùn)算模擬 202
8.2 乘數(shù)探求 203
8.2.1 積為若干個(gè)1構(gòu)成 203
8.2.2 積為若干個(gè)2014構(gòu)成 204
8.2.3 積為任意指定構(gòu)成 205
8.3 特殊數(shù)積 206
8.3.1 01串積 206
8.3.2 二部數(shù)積 209
8.4 尾數(shù)前移問(wèn)題 213
8.4.1 限1位尾數(shù)前移 213
8.4.2 多位尾數(shù)前移 215
8.5 圓周率計(jì)算 218
8.5.1 蒙特卡羅模擬計(jì)算 218
8.5.2 指定高精度計(jì)算 219
8.6 模擬發(fā)橋牌 221
8.7 泊松分酒 223
8.8 模擬應(yīng)用小結(jié) 226
習(xí)題8 227
第9章 算法的綜合應(yīng)用與優(yōu)化案例 228
9.1 冪積序列 228
9.1.1 雙冪積枚舉設(shè)計(jì) 228
9.1.2 雙冪積遞推設(shè)計(jì) 230
9.1.3 多冪積拓廣 233
9.2 高斯皇后問(wèn)題 234
9.2.1 高斯八皇后問(wèn)題 235
9.2.2 n皇后問(wèn)題 236
9.2.3 皇后全控棋盤(pán) 238
9.3 翻轉(zhuǎn)硬幣 241
9.3.1 m×9矩陣枚舉設(shè)計(jì) 241
9.3.2 m×n矩陣回溯設(shè)計(jì) 247
9.3.3 大規(guī)模矩陣貪心設(shè)計(jì) 251
9.4 最優(yōu)復(fù)雜路徑 257
9.4.1 三角數(shù)陣中的最小路徑 257
9.4.2 矩陣迷宮中的最小通道 260
9.5 馬步遍歷與哈密頓圈 263
9.5.1 馬步遍歷 263
9.5.2 馬步型哈密頓圈 268
9.5.3 組合型哈密頓圈 272
9.6 算法綜合應(yīng)用小結(jié) 277
習(xí)題9 278
附錄A 在VC++ 6.0環(huán)境下運(yùn)行C程序
方法簡(jiǎn)介 280
附錄B C常用庫(kù)函數(shù) 284
參考文獻(xiàn) 288

1. 算法設(shè)計(jì)與分析 [趙晶]
2. 信息技術(shù)基礎(chǔ) [主編 唐倩 邵銳]
3. 大學(xué)計(jì)算機(jī)基礎(chǔ)實(shí)驗(yàn)（WPS版） [主編　謝江宜　蔡勇]
4. 信息技術(shù)（微課版） [王云　徐江鴻　李清霞　羅學(xué)鋒　]
5. 計(jì)算思維與大學(xué)計(jì)算機(jī)基礎(chǔ) [主編　趙旭劍]
6. 大學(xué)信息技術(shù)實(shí)訓(xùn)教程 [主編 任云暉 丁紅 趙琳琳]
7. 大學(xué)信息技術(shù)教程 [主編 任云暉 馮政軍 魏斌]
8. 信息技術(shù)基礎(chǔ)立體化教程 [鄒承俊 周洪林 劉和文 葉煜 ]
9. 大學(xué)計(jì)算機(jī)基礎(chǔ)與計(jì)算思維 [主編 閔笛 汪瑩]
10. 信息技術(shù)基礎(chǔ)項(xiàng)目化教程 [主編 王宏斌 王萬(wàn)麗 王芳]
11. 大學(xué)計(jì)算機(jī)信息素養(yǎng)（第二版） [主編 盧山]
12. 全國(guó)計(jì)算機(jī)等級(jí)考試一級(jí)（MS Office）指導(dǎo)手冊(cè) [主編 王宏斌 孫元 禹晨]
13. 大學(xué)計(jì)算機(jī)基礎(chǔ)實(shí)驗(yàn)指導(dǎo)及習(xí)題解析 [主編 閔笛 李明]
14. 大學(xué)計(jì)算機(jī)信息素養(yǎng)實(shí)驗(yàn)指導(dǎo)（第二版） [主編 盧山]
15. 信息技術(shù)基礎(chǔ)（微課版） [主編　趙艷莉　喻林]
16. 大學(xué)信息技術(shù)基礎(chǔ) [主編 黎夏克 張倩文 王靜]
17. 計(jì)算機(jī)信息素養(yǎng)基礎(chǔ)實(shí)踐教程 [王錦 姚曉杰 王立武 等 編著]
18. 計(jì)算機(jī)基礎(chǔ)與應(yīng)用實(shí)踐教程 [楊毅 劉立君 張春芳 梁寧玉 ]
19. 計(jì)算機(jī)信息素養(yǎng)基礎(chǔ) [主編 陳艷 秦凱 黃海玉]
20. 計(jì)算機(jī)基礎(chǔ)與應(yīng)用 [主編 秦凱 梁寧玉 王毅]
21. 大學(xué)計(jì)算機(jī)基礎(chǔ)上機(jī)實(shí)踐教程（第六版） [主編 何振林 羅奕]
22. 大學(xué)計(jì)算機(jī)基礎(chǔ)教程實(shí)驗(yàn)指導(dǎo)與測(cè)試題集 [主編 饒拱維 吳華光 巫滿(mǎn)秀]
23. 大學(xué)計(jì)算機(jī)基礎(chǔ)（等級(jí)考試版） [主編 鐘誠(chéng)]
24. 大學(xué)計(jì)算機(jī)基礎(chǔ)教程（第二版） [主編 安志遠(yuǎn) 崔巖]
25. 計(jì)算機(jī)應(yīng)用基礎(chǔ)實(shí)訓(xùn)教程（第三版） [主 編 王向慧 康秀蘭]
26. 計(jì)算機(jī)應(yīng)用基礎(chǔ)（第三版） [主 編 王向慧 康秀蘭]
27. 計(jì)算機(jī)應(yīng)用基礎(chǔ) [主編　趙艷莉]
28. 大學(xué)計(jì)算機(jī)基礎(chǔ)案例教程（第二版） [主 編 葉潮流 金 瑩]
29. 大學(xué)信息技術(shù) [主編　連衛(wèi)民　張志明　陳炎龍]
30. 新編計(jì)算機(jī)應(yīng)用基礎(chǔ)教程 [主編　戴毅　吳瑞芝　賈姍姍]