目錄
第1章 環境搭建1
1 1Microsoft Visual C++2010學習版的使用1
1 1 1Visual C++ 2010學習版的安裝2
1 1 2創建、編輯、編譯和運行項目4
1 1 3為什麼缺少很多選項8
1 1 4為什麼一閃而過9
1 1 5其他配置選項11
1 2Code∷Blocks的使用14
1 2 1安裝Code∷Blocks14
1 2 2創建項目和編輯源代碼16
1 2 3調試20
第2章 排序算法23
2 1冒泡排序23
2 1 1冒泡排序的基本思想23
2 1 2冒泡排序過程分析24
2 1 3冒泡排序代碼分析26
2 2選擇排序28
2 2 1選擇排序的基本思想28
2 2 2選擇排序過程分析29
2 2 3選擇排序代碼分析30
2 3插入排序31
2 3 1插入排序的基本思想31
2 3 2插入排序過程分析32
2 3 3插入排序代碼分析33
2 4計數排序35
2 4 1計數排序的基本思想35
2 4 2計數排序過程分析36
2 4 3計數排序代碼分析38
2 4 4統計句子中字母出現的次數40
算法設計練習42第3章 遞歸算法43
3 1漢諾塔問題43
3 1 1漢諾塔問題解題思路分析43
3 1 2漢諾塔問題代碼分析45
3 2全排列問題46
3 2 1無重複元素的全排列47
3 2 2有重複元素的全排列49
3 3因數分解問題52
3 3 1因子遞增方式遞歸求解53
3 3 2子問題分解方式遞歸求解54
3 3 3因數分解問題代碼分析54
3 4分形圖形56
3 4 1盒分形思路分析56
3 4 2盒分形代碼分析57
算法設計練習59
第4章 數論基礎60
4 1餘數和最大公約數60
4 1 1餘數60
4 1 2最大公約數63
4 1 3歐幾裡得算法63
4 2素數問題65
4 2 1素數的概念65
4 2 2素數相關的定理65
4 2 3篩選法求素數66
4 3同餘問題74
4 3 1同餘及其性質74
4 3 2線性同餘75
算法設計練習92
第5章 組合數學基礎94
5 1排列生成算法94
5 1 1序數生成法95
5 1 2字典序生成法99
5 1 3”火星人”問題100
5 2組合生成算法102
5 2 1基於字典序的組合生成算法103
5 2 2基於格雷碼的組合生成算法107
算法設計練習116
第6章 貪心算法117
6 1結構體117
6 2貪心算法概述119
6 3活動時間安排120
6 3 1活動安排過程分析121
6 3 2活動安排代碼分析123
6 4最優裝載問題125
6 4 1最優裝載問題過程分析125
6 4 2最優裝載問題代碼分析126
6 5可切割背包問題128
6 5 1可切割背包問題分析128
6 5 2可切割背包代碼分析130
6 6刪數問題132
6 7操作系統內存分配134
6 7 1First Fit內存分配136
6 7 2Best Fit內存分配137
6 7 3Worst Fit內存分配139
算法設計練習141
第7章 分治算法142
7 1快速排序143
7 1 1快速排序過程分析143
7 1 2快速排序代碼分析144
7 2歸併排序146
7 2 1歸併排序過程分析146
7 2 2歸併排序代碼分析147
7 3二分查找149
7 3 1二分查找過程分析149
7 3 2二分查找代碼分析150
7 4循環賽152
7 4 12k循環賽日程表152
7 4 2奇偶循環賽日程表155
7 5大整數乘法160
7 5 1大整數乘法過程分析160
7 5 2大整數乘法代碼分析161
算法設計練習165第8章 動態規劃算法166
8 1數字三角形166
8 1 1使用樸素遞歸求解數字三角形問題167
8 1 2使用動態規劃算法求解數字三角形問題168
8 2最長公共子序列175
8 2 1最長公共子序列問題過程分析175
8 2 2最長公共子序列問題代碼分析176
8 3編輯距離180
8 3 1編輯距離的正向生成180
8 3 2操作序列的逆向回溯182
8 401背包問題(一)186
8 4 101背包問題過程分析186
8 4 201背包問題代碼分析187
8 5石子合併191
8 5 1石子合併問題過程分析192
8 5 2石子合併問題代碼分析193
算法設計練習201
第9章 回溯算法202
9 1八皇后問題202
9 1 1八皇后問題過程分析202
9 1 2八皇后問題代碼分析204
9 2子集和問題207
9 2 1子集和問題過程分析208
9 2 2子集和問題代碼分析209
9 301背包問題(二)211
9 3 101背包問題過程分析211
9 3 201背包問題代碼分析213
9 4裝載問題216
9 4 1裝載問題過程分析216
9 4 2裝載問題代碼分析216
9 5任務分配問題 219
9 5 1任務分配問題過程分析219
9 5 2任務分配問題代碼分析219
算法設計練習222
參考文獻224
前言/序言
“算法分析與設計”的課程目標是培養運用數學思維和計算思維分析問題與應用所學專業知識解決問題的能力。通過對基礎理論和典型案例的學習,讀者能夠掌握算法設計的方法和技巧,為後續數據結構等相關課程的學習及參加各類學科競賽奠定基礎。
在學習本書內容之前,讀者應具備一定的編程基礎,能夠熟練運用C、C++、Java、Python等至少一門編程語言,無須具備數據結構基礎知識。本書是程序設計基礎和算法分析與設計之間的過渡,為剛剛學習過程序設計基礎的算法入門者量身定制。
本書的主要特點是算法知識”基礎化”和分析過程”圖表化”,只要求讀者具備程序設計基礎知識,重在興趣與入門,不涉及艱深晦澀的內容。以圖表方式給出算法的動態分析過程,使讀者能夠真正理解和掌握算法的本質,能夠根據實際工作設計和優化算法。
全書由9章 構成,各章 具體內容如下。
第1章 : 環境搭建。主要介紹Windows操作系統下學習環境的搭建及注意事項。
第2章 : 排序算法。介紹冒泡排序、選擇排序、插入排序和計數排序等常見排序算法。
第3章 : 遞歸算法。分析遞歸算法的本質特徵,並通過遞歸算法求解漢諾塔、全排列、因數分解和分形圖形問題。
第4章 : 數論基礎。介紹數論的基本概念及性質,分析素數和同餘兩類典型的數論基礎問題。
第5章 : 組合數學基礎。介紹組合數學的基本概念和性質,分析排列和組合生成的典型算法。
第6章 : 貪心算法。介紹結構體類型,分析活動時間安排、最優裝載、可切割背包、刪數問題及操作系統內存分配等典型貪心算法案例。
第7章 : 分治算法。介紹分治算法的基本思想,應用分治思想求解快速排序、歸併排序、二分查找、循環賽及大整數乘法問題。
第8章 : 動態規劃算法。介紹動態規劃算法的特點和解題過程,利用動態規劃算法求解數字三角形、最長公共子序列、編輯距離、01背包問題及石子合併問題。
第9章 : 回溯算法。介紹回溯算法的解題思路,通過圖表詳細分析八皇后問題、子集和問題、01背包問題、裝載問題及任務分配問題的探索和回溯過程。
算法分析與設計的核心是體會和實踐,講授是基礎,實踐是關鍵。本書提供各典型案例相關的全部源代碼(C和C++版本,在Visual C++2010、Visual C++2019及Code∷Blocks中調試通過)。
本書由吉林師範大學教材出版基金資助,是授課教師多年教學經驗的總結,但由於編者水平所限,書中難免存在遺漏和不足之處,敬請讀者批評指正,在此表示誠摯謝意。
編者2025年1月
詳細資料或其他書籍請至台灣高等教育出版社查詢,查後請於客服中心或Line或本社留言板留言,我們即儘速上架。