算法設計(C++版)（簡體書）

本書是一本注重理論聯繫實踐，系統介紹算法設計方法、分析技巧和C 編程實戰的著作。本著“易理解，重實用”的指導思想，結合多年的教學經驗，以算法設計策略為主線，沿著“算法思想——算法設計——構造實例——算法描述——算法分析——C 實戰”的思路來組織學習內容，主要包括：算法概述、貪心算法、分治算法、動態規劃、回溯算法及分支限界算法、隨機化算法、網絡流算法和NP完全理論等八章內容。為突出教材的可讀性、可用性及前沿性，每章增設了學習目標、閱讀材料及習題解析。配套資源包括實驗指導書、大綱、PPT課件、經典案例源代碼、微課視頻等內容。適合作為計算機類及相關專業的本科生教材，也可供工程技術人員和自學讀者學習參考，還適合作為程序設計大賽愛好者的參考用書。

王秋芬：一位具有近20年一線教學經驗的教育工作者，主講算法設計與分析、操作系統原理、數據結構、Linux操作系統等課程。致力於算法、操作系統和智能計算等領域的研究，主持或參與了10余項重要課題，並發表了20多篇學術論文，獲國家發明專利4項。此外，還出版了《算法設計與分析》、《算法設計藝術》、《算法設計與分析——Python版》、《算法設計與分析——基於C 編程語言的描述》和《Flash CS5 中文版基礎教程》等5部著作，為國家和社會的發展做出了貢獻。

• 內容全面：系統介紹了經典算法設計策略及分析方法，如貪心算法、分治算法、動態規劃、搜索算法（回溯法和分支限界法）、隨機化算法、網絡流算法等，深入剖析了算法策略在經典案例中的運用，詳細演示了算法運行過程並分析了算法的效率。
• 實用性強：選用經典又流行的C 編程語言，緊扣算法思想，為每一個案例編程展示了理論思想中的描述與具體編碼之間的對應，為讀者從理論到實踐的成長指明了方向。
• 資源豐富：開源了全部課程源代碼，同時提供了配套課件、微課視頻、大綱、實驗指導、測驗題庫、習題解答等資源。

【教學資源】

• 微課視頻
• 程序源碼
• 教學大綱
• 教學課件
• 測驗題庫
• 習題解答

說明：關注“人工智能科學與技術”微信公眾號，在“知識”→“資源下載”→“配書資源”菜單獲取下載鏈接（或到清華大學出版社網站本書頁面獲取下載鏈接）。

關於本書

根據作者多年教學經驗及實踐，充分考慮教學難度和授課學時安排，本書在
《算法設計與分析——基於C 編程語言的描述》
的基礎上，刪減了窮舉搜索、深度優先搜索、寬度優先搜索和線性規劃問題等內容，整合精簡了數論算法和計算幾何算法。本書本著“易理解，重實用”的指導思想，以掌握算法設計與分析的基本概念和方法、拓展學生專業知識結構為宗旨，按照“算法思想—算法設計—構造實例—算法描述—算法分析—C 實戰”的思路組織
內容，詳細講述了多種經典算法設計策略。縱觀全書，這裡並沒有創造出任何新的算法，因為作者僅僅是希望通過對經典算法的講解，把算法設計中基礎且重要的內容用更清晰的思路、更直觀的形式展現給讀者。

本書結構

本書以算法策略為知識單元，共8章內容，其中第1章介紹算法的基礎知識，第2~7章介紹經典的算法設計策略，第8章簡單介紹了NP完全理論。具體結構安排如下：

第1章算法概述，主要介紹了算法的基本概念與描述方式、算法設計的一般過程、算法分析方法及遞歸等。

第2~5章介紹經典的算法設計策略： 貪心算法、分治算法、動態規劃算法、回溯算法及分支限界算法。每種算法設計策略均按照算法思想、算法設計、構造實例、算法描述、算法分析、C 實戰的思路來組織。

第6章隨機化算法，講述了四種類型的隨機化算法，並結合實例講述了每種類型隨機化算法的特點。

第7章網絡流算法，著重講述網絡流的基本概念及理論、求最大網絡流的增廣路算法、求最小費用最大流的消圈算法。

第8章NP完全理論，簡單介紹了NP完全理論和近似算法，以引起讀者進一步學習和研究的興趣。

本書特點

本書側重於算法步驟的設計、實例構造和編程實戰，注重算法與數據結構的結合，以及算法時間效率分析。其特色在於針對
每種算法設計策略，按照算法思想設計了詳細的算法步驟，構造了具體實例展現算法的執行過程，最後給出算法描述和編程實現
的完整源代碼。

本書內容精煉，算法設計步驟清晰，實例構造詳盡，算法描述清楚，源碼完整，閱讀材料豐富，易教、易學，適合高等學校計算機及其相關專業的學生、編程愛好者、各類想從事計算機編程工作的專業或非專業人士閱讀。通過本書，讀者一方面可以學習到基本的算法設計策略和分析方法； 另一方面，還可以對當今流行算法和算法界的大師有所了解。

本書配套資源豐富，包括教學大綱、教學課件、微課視頻、程序代碼、實驗指導、測試題庫等。

授課方法

1. 在線線下混合式教學

利用隨書提供的微課視頻和測試題庫，教師可以布置在線學習任務，檢測在線學習效果。線下課堂基於在線學習的情況，有針對性地答疑解惑，採用參與式學習策略，比如問題驅動、任務驅動等教學方法，教師引導，學生充分思考、討論，尋求問題答案，完成課堂任務。

2. 注重運用前驅課程基本知識、基本原理

“算法”課程與“數學”“程序設計基礎”“數據結構”等前驅課程緊密聯繫。在講授本課程時，針對要解決的問題：
①要求學生審清題意，明確問題給定的已知數據、約束條件和求解目標； ②運用數學知識，引入數學符號表達已知數據、約束條件及求解目標，構建數學模型； ③訓練計算思維，要求學生思考、討論數學模型中的符號如何存儲到計算機中，即採用什麼數據結構存儲數學模型中涉及的各種符號； ④選擇貪心、分治、動態規劃、搜索等一種或多種算法設計策略； ⑤分組任務，要求各小組根據選定的數據結構和算法策略設計求解問題的算法步驟，然後各組分享各自的設計成果，最後教師總結、追問引發更深層的思考； ⑥課下任務，以作業的形式，借助實踐教學平臺（如頭歌）或刷題平臺（如洛谷、力扣），選用各自擅長的程序設計語言，將課堂上設計的算法翻譯成程序，完成實戰訓練。

3. 注重創新意識、創新精神、創新思維的訓練

“算法”課程應注重應用創新和技術創新，在分析問題求解的思想、方法的基礎上，從數據結構、算法設計策略、編程語言、具體操作等方面分析現有方法的優勢與不足，發揮現有方法本身的優勢，舉一反三，創新應用； 針對現有方法自身的不足，開動腦筋，不斷創新、創造，尋求其他更好的求解方法，讓學生認識到人人可以創新，時時可以創新，處處可以創新。

4. 思政育人、價值塑造

“算法”課程中講解的策略、思想、方法是人類智能的結晶，蘊含著豐富的科學思想、技術創新、中華優秀傳統文化。教師傳道授業解惑時，通過算法名師、技術革新、工程倫理、前沿技術等揭示算法本身的思政屬性，把知識傳授、能力培養、價值塑造映射到教學的每個環節，實現“課程承載思政，思政寓於課程”的有機統一。通過潛移默化、循循善誘的方式，在不經意中實現“潤物細無聲”的育人目標。“算法”課程思政育人體系如下，僅供授課教師參考。

另外，要說明一下，書中出現的log均是以2為底的對數。

在此，謹向清華大學出版社負責本書編輯出版工作的全體人員和每位曾經關心和支持本書編寫工作的各方面專家表示衷心的感謝。

由於編者水平有限，書稿雖幾經修改，但仍難免有疏漏或不妥之處，歡迎廣大讀者和專家批評指正。

編者
2023年12月

第1章算法概述

1.1算法的基本概念

1.1.1學習算法的重要性

1.1.2算法的定義及特性

1.1.3算法的描述方式

1.2算法設計的一般過程

1.3算法分析

1.3.1算法分析的概念

1.3.2時間複雜性

1.3.3空間複雜性

1.3.4算法漸進複雜性

1.3.5算法複雜性的權衡考慮

1.4遞歸

1.4.1認知遞歸

1.4.2n的階乘

1.4.3排列問題

1.4.4最大公約數

1.4.5遞歸算法的複雜性分析

拓展知識： 算法界十大名師簡介

本章習題

第2章貪心算法

2.1貪心算法概述

2.1.1貪心算法的基本思想

2.1.2貪心算法的基本要素

2.1.3貪心算法的解題步驟及算法設計模式

2.2會場安排問題

2.3單源最短路徑問題

2.4哈夫曼編碼

2.5最小生成樹

2.5.1Prim算法

2.5.2Kruskal算法

2.5.3兩種算法的比較

拓展知識： 遺傳算法

本章習題

第3章分治算法

3.1分治算法概述

3.1.1分治算法的基本思想

3.1.2分治算法的解題步驟

3.2二分查找

3.3循環賽日程表

3.4合並排序

3.5快速排序

3.6最接近點對問題

拓展知識： 禁忌搜索算法

本章習題

第4章動態規劃算法

4.1動態規劃算法概述

4.1.1動態規劃算法的基本思想

4.1.2動態規劃算法的解題步驟

4.1.3動態規劃算法的基本要素

4.2矩陣連乘問題

4.3凸多邊形最優三角剖分問題

4.4最長公共子序列問題

4.5加工順序問題

4.601背包問題

4.7最優二叉查找樹

拓展知識： 模擬退火算法

本章習題

第5章回溯算法及分支限界算法

5.1回溯算法

5.1.1回溯算法的算法框架及思想

5.1.2子集樹

5.1.3排列樹

5.1.4滿m叉樹

5.2分支限界算法

5.2.1分支限界算法的基本思想

5.2.201背包問題

5.2.3旅行商問題

5.2.4布線問題

5.2.5分支限界算法與回溯算法的比較

拓展知識： 蟻群算法

本章習題

第6章隨機化算法

6.1隨機化算法概述

6.1.1隨機化算法的類型及特點

6.1.2隨機數發生器

6.2數值隨機化算法

6.2.1計算π值的問題及分析

6.2.2計算定積分

6.3蒙特卡洛算法

6.3.1主元素問題

6.3.2素數測試

6.4拉斯維加斯算法

6.4.1整數因子分解問題

6.4.2n皇后問題

6.5舍伍德算法

6.5.1隨機快速排序

6.5.2線性時間選擇問題

拓展知識： 粒子群優化算法

本章習題

第7章網絡流算法

7.1最大網絡流

7.1.1基本概念

7.1.2增廣路算法

7.1.3最大網絡流的變換與應用

7.2最小費用最大流

7.2.1基本概念

7.2.2消圈算法

7.2.3最小費用最大流的變換與應用

拓展知識： 捕食搜索算法

本章習題

第8章NP完全理論

8.1易解問題和難解問題

8.2P類問題和NP類問題

8.2.1P類問題

8.2.2NP類問題

8.2.3P類問題和NP類問題的關係

8.3NP完全問題

8.3.1多項式變換技術

8.3.2典型的NP完全問題

8.4NP完全問題的近似算法

8.4.1頂點覆蓋問題

8.4.2裝箱問題

8.4.3旅行商問題

8.4.4集合覆蓋問題

拓展知識： DNA計算

本章習題