程序設計實踐入門：大學程序設計課程與競賽訓練教材（簡體書）

剖析ACM典型賽題，提升編程求解問題的能力

我們編著“大學程序設計課程與競賽訓練教材”系列圖書的初心是，基於程序設計競賽的試題，以全面、系統地訓練和提高學生編程解決問題的能力為目標，出版既能用於大學程序設計類課程的教學和實驗，又能用於程序設計競賽選手訓練的著作。目前，這一系列在中國大陸出版了簡體中文版，在中國臺灣地區出版了繁體中文版，在美國由CRC Press出版了英文版。而我們不僅對本系列不斷進行改進，也就課程建設、教學和訓練體系的建設開展了一系列的工作。
對於“大學程序設計課程與競賽訓練教材”系列圖書的建設，寧夏理工學院副校長俞經善教授建議，要出版一部專門進行程序設計入門訓練的書籍，它不僅能夠適用於“雙一流”院校的學生，也要能夠適用於應用技術型院校的學生。華東交通大學的周娟老師一直負責學校的程序設計競賽訓練，她有一本使用了若幹年的講義，我們對這本講義進行了改編，形成了本書。
對於本書的編寫，我們的指導思想如下。
1）內容上，基於大學一年級的程序設計語言、高等數學、線性代數課程的教學內容，以及中學期間所學的數學、物理相關知識，讓學生體會和實踐通過編程解決問題。
2）形式上，和系列著作一樣，章節的組織以實驗為核心，以程序設計競賽試題以及詳細的解析、帶注解的程序作為主要內容。
本書的內容如下。
第1章給出簡單輸出，以及練習“輸入-處理-輸出”模式的實驗。第2章給出選擇結構、循環結構、嵌套結構、數組、二維數組、字符和字符串的實驗；第3章給出函數、遞歸函數、結構體、指針的實驗。本書的前三章是基於程序設計語言的教學大綱，循序漸進地展開編程實驗，可以作為程序設計語言課程的實驗教材。
第4章分為五節：幾何初步，歐幾裡得算法和擴展的歐幾裡得算法，概率論初步，微積分初步，矩陣計算。一方面，結合學生在中學期間所學習和掌握的數學知識進行編程解題訓練；另一方面，配合學生大一期間學習的高等數學中的導數、線性代數中的矩陣給出編程實驗。第5章也分為五節：簡單的排序算法（選擇排序、插入排序、冒泡排序），歸並排序，快速排序，利用排序函數進行排序，結構體排序。首先，給出運用運行時間為O(n2)的簡單排序算法進行排序的實驗；然後，給出運用時間復雜度為O(nlog2n)的排序算法進行排序的實驗；最後，給出利用排序函數進行排序以及結構體排序的實驗。第6章分為兩節：STL容器，STL算法。
本書可作為大學程序設計語言入門課程的實驗教材，也可用作程序設計競賽選手的入門訓練參考書籍。
我們對浩如煙海的ACM-ICPC程序設計競賽區域預賽和全球總決賽、大學的程序設計競賽、在線程序設計競賽以及中學生信息學奧林匹克競賽的試題進行了分析和整理，從中精選出84道試題（包括一題多解）作為本書的實驗範例試題，每道試題不僅有詳盡的試題解析，還給出了標有詳細注釋的參考程序。
華章網站提供了本書所有試題的英文原版以及大部分試題的官方測試數據。
這些年來，我們秉承“不忘初心，方得始終”的信念，不斷地完善和改進系列著作。我們非常感謝廣大海內外同人的情義相挺，並特別感謝中國大陸及中國臺灣、中國香港、中國澳門的同人一起創建ACM-ICPC亞洲訓練聯盟，該聯盟不僅為本書也為我們的系列著作及其課程建設提供了一個實踐的平臺。
由於時間和水平所限，書中肯定會夾雜一些錯誤，表述不當和筆誤也在所難免，熱忱歡迎學術界同人和讀者賜正。如果你在閱讀中發現了問題，請通過電子郵件告訴我們，以便我們在課程建設和中英文版再版時加以改進。
周　娟　吳永輝
2021年4月

前　言
第1章　編程起點：輸入和輸出 1
1.1　輸出 1
1.2　輸入與輸出 2
第2章　編程基礎I 4
2.1　選擇結構 4
2.2　循環結構 7
2.3　嵌套結構 14
2.4　數組 21
2.4.1　數組的特點 22
2.4.2　離線計算 26
2.4.3　序列 29
2.5　二維數組 33
2.6　字符和字符串 41
第3章　編程基礎II 49
3.1　函數 49
3.2　遞歸函數 57
3.3　結構體 61
3.4　指針 69
第4章　數學計算 76
4.1　幾何初步 76
4.2　歐幾裡得算法和擴展的歐幾裡得算法 87
4.3　概率論初步 93
4.4　微積分初步 101
4.5　矩陣計算 108
第5章　排序 115
5.1　簡單的排序算法：選擇排序、插入排序、冒泡排序 116
5.2　歸並排序 122
5.3　快速排序 129
5.4　利用排序函數進行排序 132
5.5　結構體排序 138
第6章　C++ STL 144
6.1　STL容器 144
6.1.1　序列式容器 144
6.1.2　關聯式容器 150
6.1.3　迭代器 161
6.2　STL算法 170