計算思維與算法入門

目錄
前言
第1章 程序設(shè)計與計算思維1
1.1 認(rèn)識計算思維4
1.1.1 分解6
1.1.2 模式識別9
1.1.3 模式概括與抽象11
1.1.4 算法13
1.2 算法的條件15
1.3 課后習(xí)題21
第2章 常用數(shù)據(jù)結(jié)構(gòu)與算法22
2.1 認(rèn)識數(shù)據(jù)結(jié)構(gòu)24
2.2 常見的數(shù)據(jù)結(jié)構(gòu)27
2.3 矩陣與深度學(xué)習(xí)29
2.3.1 稀疏矩陣33
2.3.2 矩陣相加算法34
2.3.3 矩陣相乘算法34
2.3.4 轉(zhuǎn)置矩陣35
2.4 鏈表35
2.4.1 單向鏈表的串接算法37
2.4.2 單向鏈表節(jié)點(diǎn)的刪除算法37
2.4.3 在單向鏈表中添加新節(jié)點(diǎn)38
2.4.4 單向鏈表的反轉(zhuǎn)39
2.5 堆棧40
2.6 隊列42
2.6.1 雙向隊列44
2.6.2 優(yōu)先隊列44
2.7 樹結(jié)構(gòu)45
2.7.1 樹的基本概念46
2.7.2 二叉樹48
2.7.3 樹轉(zhuǎn)化為二叉樹的算法51
2.7.4 二叉樹轉(zhuǎn)化為樹的算法53
2.8 圖簡介54
2.9 哈希表57
2.10 課后習(xí)題59
第3章 分治法60
3.1 分治法簡介61
3.2 遞歸法62
3.3 漢諾塔算法63
3.4 快速排序法68
3.5 合并排序法70
3.6 二分查找法71
3.7 課后習(xí)題72
第4章 貪心法74
4.1 貪心法簡介75
4.2 最小生成樹76
4.2.1 Prim算法77
4.2.2 Kruskal算法79
4.3 圖的最短路徑法81
4.3.1 Dijkstra算法81
4.3.2 A* 算法83
4.3.3 Floyd算法86
4.4 課后習(xí)題88
第5章 動態(tài)規(guī)劃法90
5.1 動態(tài)規(guī)劃法簡介91
5.2 字符串對比功能93
5.3 AOV網(wǎng)絡(luò)與拓?fù)渑判?4
5.4 AOE網(wǎng)絡(luò)97
5.5 青蛙跳臺階算法99
5.6 課后習(xí)題101
第6章 安全性算法102
6.1 數(shù)據(jù)加密104
6.1.1 對稱密鑰加密系統(tǒng)105
6.1.2 非對稱密鑰加密系統(tǒng)與RSA算法106
6.1.3 認(rèn)證107
6.1.4 數(shù)字簽名107
6.2 哈希算法109
6.2.1 除留余數(shù)法109
6.2.2 平方取中法111
6.2.3 折疊法112
6.2.4 數(shù)字分析法113
6.3 碰撞與溢出處理113
6.3.1 線性探測法114
6.3.2 平方探測法114
6.3.3 再哈希法115
6.4 課后習(xí)題116
第7章 樹結(jié)構(gòu)的算法118
7.1 二叉樹的遍歷119
7.2 二叉查找樹122
7.3 優(yōu)化二叉查找樹126
7.3.1 擴(kuò)充二叉樹126
7.3.2 哈夫曼樹128
7.4 平衡樹（AVL樹）129
7.5 博弈樹——八枚金幣問題132
7.6 堆積排序法134
7.7 斐波那契查找法136
7.8 課后習(xí)題139
第8章 改變程序功力的經(jīng)典算法141
8.1 迭代法142
8.1.1 帕斯卡三角算法143
8.1.2 插入排序法145
8.1.3 希爾排序法146
8.1.4 基數(shù)排序法147
8.2 枚舉法148
8.2.1 3個小球放入盒子150
8.2.2 質(zhì)數(shù)求解算法152
8.2.3 順序查找法154
8.2.4 冒泡排序法154
8.2.5 選擇排序法156
8.3 回溯法158
8.3.1 老鼠走迷宮158
8.3.2 八皇后算法160
8.4 課后習(xí)題161
第9章 游戲設(shè)計中的算法163
9.1 游戲中的數(shù)學(xué)與物理算法164
9.1.1 兩點(diǎn)距離的算法164
9.1.2 勻速運(yùn)動166
9.1.3 加速運(yùn)動167
9.2 圖的遍歷算法168
9.2.1 路徑算法168
9.2.2 深度優(yōu)先查找算法170
9.2.3 廣度優(yōu)先查找算法172
9.3 碰撞處理算法173
9.3.1 以行進(jìn)路線來檢測174
9.3.2 范圍檢測176
9.3.3 顏色檢測179
9.4 遺傳算法182
9.5 課后習(xí)題184
附錄 課后習(xí)題與參考答案185