GESP編程能力等級認證一本通（C++ 四級）

王桂平，計算機科學與技術專業博士、副教授、碩導。從 2003 年開始從事大學生程

序設計競賽指導工作，帶隊參加過浙江省、重慶市、四川省、廣東省大學生程序設計大賽，以及中國大學生程序設計大賽、國際大學生程序設計大賽、中國高校計算機大賽——團體程序設計天梯賽、藍橋杯大賽等各類程序與算法設計類賽事，指導的學生獲得國家級獎項 100 余項、省級獎項 1000 余項；主持省部級教學研究項目5 項（含重大項目 1 項），主持重慶市一流課程 1 門；以第一作者發表教學研究論文近20 篇；以第一作者發表科學研究論文 30 余篇，其中 SCI 論文 9 篇、EI論文 10 篇，主持省部級科研項目 3 項，主研國家級科研項目 3 項。著有《圖論算法理論、實現及應用》《程序設計方法及算法導引》《C++趣味編程及算法入門》《C++編程與

信息學競賽數學基礎》《信息學競賽教程》等多部圖書；多所中小學兼職信奧教練。

張兵，CCF GESP & PTA 自由度服務中心主任、重慶大學繼續教育學院家校社中心主任、國際人工智能奧林匹克學術活動中國區（NOAI）重慶組委會主任、“傲夢少年”聯盟負責人。在編程教育與信奧教育、青少年人工智能、青少年多元化成長路徑、醫工融合等領域均有深入研究。主導並參與了 1 項重慶市技術創新與應用示範項目、

1 項重慶市科技型企業技術創新與應用發展專項項目。

鄭蘭，重慶市第八中學校信息學競賽主教練，區級學科名師，重慶市中學骨幹教師，重慶市基礎教育教學資源評審專家庫成員，中國計算機學會WCET 委員，全國信息競賽優秀 NOI指導教師。指導學生參加全國青少年信息學奧林匹克競賽（NOI），其中 5 人榮獲金牌，4人進入國家集訓隊；指導學生參加全國青少年信息學奧林匹克聯賽（NOIP），其中 100 多人獲一等獎。

第 1章　二維及多維數組　001

1.1　數組概述　001

1.2　二維數組的定義和引用　002

1.3　案例1：輸出楊輝三角形前n行　005

1.4　一維和二維字符數組　007

1.5　案例2：畫布裁剪（GESP真題）　007

1.6　案例3：黑白方塊（GESP真題）　009

1.7　矩陣中的特殊位置　011

1.8　矩陣的變換—轉置　012

1.9　練習1：矩陣的轉置　012

1.10　練習2：二階矩陣（GESP真題）　013

1.11　拓展：三維及多維數組　015

1.12　基礎知識練習（GESP真題）　016

第 2章　指針變量及應用　020

2.1　指針概述　020

2.2　指針變量的定義與引用　022

2.3　字符型指針變量　025

2.4　指針變量作函數參數　027

2.5　案例1：交換兩個數（函數和指針參數實現）　030

2.6　案例2： Fibonacci數列（函數帶回兩個答案）　033

2.7　案例3：四則運算（函數和指針參數實現）　034

2.8　練習1： 4個數輪換　035

2.9　練習2：平方根、立方根、平方和立方　036

2.10　基礎知識練習（GESP真題）　038

第3章　指針與數組的綜合應用　043

3.1　一維數組與指針變量　043

3.2　用數組名作函數參數　046

3.3　案例1：構造回文　047

3.4　網格狀地圖及相鄰位置的處理　049

3.5　案例2：荒地開墾（GESP真題）　050

3.6　案例3：排兵布陣（GESP真題）　052

3.7　練習1：查找數　055

3.8　前綴和數組　056

3.9　練習2：平衡子矩形（GESP真題）　058

3.10　二維數組與指針變量　060

3.11　指針高級內容　062

3.12　基礎知識練習（GESP真題）　063

第4章　排序基本概念及sort函數的使用　068

4.1　排序基本概念　068

4.2　排序函數sort的使用　068

4.3　字典序　070

4.4　案例1：整數排序（中間大兩頭小）　070

4.5　案例2：重排數字使整數最大　071

4.6　案例3：做題（GESP真題）　072

4.7　練習1：寶箱（GESP真題）　073

4.8　練習2：字符排序（GESP真題）　075

4.9　基礎知識練習（GESP真題）　076

第5章　結構體　078

5.1　結構體概述　078

5.2　結構體類型的聲明　079

5.3　結構體變量、指針、數組的定義　079

5.4　結構體變量、數組的初始化　081

5.5　結構體變量及成員的引用　081

5.6　用typedef聲明一種新類型名　082

5.7　案例1：按身高排序　083

5.8　案例2：數位排序　084

5.9　案例3：字符串排序（按得分高低排序）　086

5.10　練習1：按姓名排序　088

5.11　練習2：病人排隊　089

5.12　結構體其他知識　091

5.13　基礎知識練習（GESP真題）　093

第6章　函數進階　097

6.1　引用及引用類型參數　097

6.2　值的傳遞和地址傳遞　099

6.3　函數的嵌套調用　099

6.4　函數重載及有默認值的參數　100

6.5　全局作用域和局部作用域　101

6.6　案例1：絕對素數（GESP真題）　102

6.7　案例2：圖像壓縮（GESP真題）　103

6.8　案例3：進制轉換（GESP真題）　106

6.9　練習1：變長編碼（GESP真題）　108

6.10　練習2：相似字符串（GESP真題）　110

6.11　函數的設計總結　112

6.12　基礎知識練習（GESP真題）　112

第7章　遞歸函數　122

7.1　遞歸及遞歸函數　122

7.2　案例1：求階乘（遞歸函數）　123

7.3　案例2：遞歸求Fibonacci數列第n項　125

7.4　將較大規模的問題降為較小規模的問題　126

7.5　案例3：三角形的個數（1）　126

7.6　練習1：三角形的個數（2）　128

7.7　練習2：幸運數（GESP真題）　130

7.8　遞歸函數設計總結　132

7.9　基礎知識練習（GESP真題）　133

第8章　遞推算法基礎　134

8.1　遞推概述　134

8.2　遞推的四大要素　134

8.3　案例1：拼積木問題　135

8.4　案例2：放圓珠問題　136

8.5　二維遞推　137

8.6　案例3：網格路徑　138

8.7　練習1：新的兔子數列　140

8.8　練習2：過山車數　141

8.9　基礎知識練習（GESP真題）　143

第9章　遞推算法進階　148

9.1　部分位置受限的遞推問題　148

9.2　案例1：走臺階問題（部分臺階是壞的）　148

9.3　案例2：馬攔過河卒　150

9.4　遞推和其他算法的結合　152

9.5　案例3：猴子分桃子　153

9.6　練習1：Recamán（GESP真題）　155

9.7　練習2：踩方格　157

9.8　基礎知識練習（GESP真題）　159

第 10章　遞推與遞歸的綜合應用　160

10.1　遞推和遞歸總結　160

10.2　案例1：f(n)=Σf( j ), j為n的因數且j

10.3　案例2：矩陣變幻　162

10.4　遞歸存在的問題及解決方法　165

10.5　案例3：數的計算　167

10.6　練習1：漢諾塔遊戲　168

10.7　練習2：填幻方（GESP真題）　171

10.8　基礎知識練習（GESP真題）　172

第 11章　簡單的排序算法　173

11.1　來自生活中的算法思想　173

11.2　排序算法性能及評價　174

11.3　案例1：插入法排序　175

11.4　案例2：冒泡法排序　176

11.5　案例3：簡單選擇法排序　178

11.6　練習1：區間排序（GESP真題）　180

11.7　練習2：最少交換次數（GESP真題）　182

11.8　基礎知識練習（GESP真題）　184

第 12章　排序綜合應用　192

12.1　排序的應用　192

12.2　案例1：田忌賽馬（GESP真題）　192

12.3　案例2：最長連續段（GESP真題）　194

12.4　案例3：修建新的庫房　196

12.5　練習1：人以群分　198

12.6　練習2：排隊取水　199

12.7　基礎知識練習（GESP真題）　201

第 13章　算法及算法復雜度　204

13.1　算法的基本概念　204

13.2　評價算法優劣的標準　204

13.3　案例1：勾股數組合(a, b, b+1)　205

13.4　案例2：買地攻略　208

13.5　案例3：還剩多少人　211

13.6　算法效率的度量　212

13.7　算法時間復雜度的漸進分析和表示　213

13.8　最好、最壞和平均情況　214

13.9　基本的算法復雜度模型　215

13.10　基礎知識練習（GESP真題）　217

第 14章　文件輸入/輸出　219

14.1　文件輸入/輸出概述　219

14.2　ASCII文件和二進制文件　220

14.3　文件名和文件路徑　221

14.4　C語言中的文件輸入/輸出　222

14.5　C++語言中的文件輸入/輸出　226

14.6　基礎知識練習（GESP真題）　231

第 15章　異常處理機制　234

15.1　異常處理引入　234

15.2　C++語言中的異常處理機制　235

15.3　基礎知識練習（GESP真題）　238

附錄A　本書配套資源使用指南　242

附錄B　基礎知識練習答案　243

參考文獻　248