|
|
|
本書與《程式基本演算法教程》(周元哲、劉偉、鄧萬宇編著)相配套,分為兩部分。第1部分為主教材各章重點和課後習題答案,主要針對主教材各章(程式與演算法、程式設計語言、資料結構、查找與排序、窮舉法、遞迴法、分治法、動態規劃法、貪心法、回溯法)的內容,介紹每章要求和知識重點,給出課後習題答案。第2部分為各類演算法的習題解析,內容包括查找、窮舉法、分治、動態規劃、貪心法、回溯法和深度優先與廣度優先,題目來自ACM ICPC。附錄給出ACM演算法競賽簡介、相關技術簡介和3個軟體演算法競賽簡介。
本書適合作為高等院校電腦軟體及相關專業的教材或教學參考書,也可以供從事電腦應用開發的各類技術人員應用參考,或作為全國電腦等級考試、軟體技術資格與水準考試和各類軟體演算法競賽的培訓資料。
第1部分 各章重點和課後習題答案
第1章程式與演算法/3
1.1本章要求/3
1.2本章知識重點/3
1.2.1程式/3
1.2.2演算法/3
1.2.3演算法的“2、3、5”/4
1.2.4演算法複雜度/5
1.2.5演算法學習步驟/6
1.3課後習題答案/6
第2章程式設計語言/12
2.1本章要求/12
2.2本章知識重點/12
2.2.1結構化程式設計/12
2.2.2程式執行流程/12
2.2.33種基本結構/12
2.2.43種調試工具/15
2.3課後習題答案/15
第3章 資料結構/17
3.1本章要求/17
3.2本章知識重點/17
3.2.1概述/17
3.2.2資料結構研究物件/17
3.2.3線性表/18
3.2.4棧和佇列/18
3.2.5二叉樹/19
3.2.6圖的遍歷/21
3.2.7最短路徑/23
3.3課後習題答案/26
第4章 查找與排序/30
4.1本章要求/30
4.2本章知識重點/30
4.2.1查找/30
4.2.2排序/32
4.2.3排序法總結/33
4.3課後習題答案/34
第5章 窮舉法/40
5.1本章要求/40
5.2本章知識重點/40
5.2.1概述/40
5.2.2窮舉法分類/40
5.3課後習題答案/40
第6章遞迴法/46
6.1本章要求/46
6.2本章知識重點/46
6.2.1遞迴概念/46
6.2.2棧和堆/46
6.2.3基本遞迴/47
6.2.4尾遞迴/47
6.2.5相似術語解析/48
6.3課後習題答案/48
第7章分治法/52
7.1本章要求/52
7.2本章知識重點/52
7.2.1分治法概念/52
7.2.2分治法適用的情況/52
7.2.3分治法的基本步驟/53
7.3課後習題答案/53
第8章動態規劃法/62
8.1本章要求/62
8.2本章知識重點/62
8.2.1動態規劃特性/62
8.2.2動態規劃分類/62
8.2.3動態規劃求解步驟/63
8.3課後習題答案/64
第9章貪心法/70
9.1本章要求/70
9.2本章知識重點/70
9.2.1貪心演算法概念/70
9.2.2貪心演算法的兩個性質/70
9.2.3貪心演算法解題步驟/71
9.2.4貪心演算法和動態規劃的關係/71
9.3課後習題答案/72
第10章回溯法/79
10.1本章要求/79
10.2本章知識重點/79
10.2.1回溯概念/79
10.2.2回溯求解步驟/79
10.3課後習題答案/85
第2部分各類演算法習題解析
第11章查找/95
11.1尋找字串/95
11.2□小的因數對差/96
11.3能否獲勝/97
11.4能解決多少任務/99
11.5最高等級/100
11.6執行任務/102
11.7變化字串的數目/104
11.8兩個人的比賽/106
11.9選擇購物券/109
11.10分蛋糕/111
11.11求先序排列/113
11.12字串匹配/114
第12章窮舉/116
12.1證明錯誤假設/116
12.2平行四邊形第4個頂點/117
12.3能否組成n/118
12.4更改時間/119
12.5捉住小偷/122
12.6Jam的計數法/124
12.7線段/126
12.8求合數和/127
12.9數字挑戰/128
12.10子字串/130
第13章分治/133
13.1排列/133
13.2組合/135
13.3線性時間選擇/137
13.4一維最接近點對問題/140
13.5循環賽日程表/145
第14章動態規劃/148
14.1線段覆蓋/148
14.2過河卒/149
14.3裝箱問題/151
14.4乘積最大/153
14.5數的劃分/154
14.6統計單詞個數/156
14.7給樹上色/159
14.8寫作業/161
14.9炸彈/164
14.10攔截導彈/166
14.11入學考試/168
第15章貪心法/170
15.1均分紙牌/170
15.2胸有成竹/171
15.3今年暑假不AC/173
15.4手機控/175
15.5握手/176
15.6萬聖節/178
15.7逆序對數/179
15.8操作字串/181
15.9吃貨/183
15.10二進位/184
15.11奶牛飛車/185
15.12多處最優服務/187
15.13刪除問題/189
15.14小船過河問題/190
第16章回溯法/193
16.1八數碼/193
16.2素數環/194
16.3素數環的排列/196
16.4符號三角形問題/198
16.5迷宮問題/200
第17章深度優先與廣度優先/204
17.1油田計數/204
17.2偽二進位/206
17.3越過山丘/207
17.4翻轉道路/210
17.5單詞接龍/212
17.6最少步數/214
17.7相鄰數之和為素數/216
附錄AACM演算法競賽簡介/221
A.1線上判題系統/221
A.1.1OJ介紹/221
A.1.2VJ介紹/221
A.2ACM訓練環境/221
A.2.1註冊身份/221
A.2.2訓練過程/222
A.2.3評測狀態詳解/224
A.3ACM的演算法知識點/225
A.3.1初級/225
A.3.2中級/227
A.3.3高級/228附錄B相關技術簡介/231
B.1STL/231
B.1.1簡介/231
B.1.2容器/231
B.1.3演算法/232
B.2標頭檔/232附錄C3個軟體演算法競賽簡介/233
C.1競考網/233
C.2團體程式設計天梯賽/234
C.2.1歷史背景/234
C.2.2參賽隊組成/234
C.2.3競賽規則/235
C.2.4命題與競賽評分/235
C.2.5競賽環境和競賽語言/237
C.2.6獲獎比例/237
C.2.7報名方法/238
C.3中國軟體杯/239參考文獻/240
