本書是“CCF全國青少年信息學奧林匹克競賽教程”叢書的第二冊，旨在普及計算機科學與程序設計知識。書中遵循由淺入深、邏輯嚴密的編寫思路，輔以豐富的實例解析，引領讀者逐步提升計算思維能力。全書共四章，涉及C++程序設計進階、數(shù)據(jù)結構及其應用、算法設計、數(shù)學運用等內容，全面覆蓋NOI競賽大綱所要求的基礎知識。根據(jù)競賽的特點，書中還對一些常見的難點和易錯點進行了深入的解析。 本書可作為信息學奧林匹克競賽的教學用書，也可作為青少年學習計算機科學知識、了解信息學奧賽的參考資料。
本書由中國計算機學會組編，適合NOI參賽師生/信息學愛好者/程序設計競賽愛好者。 本書特色： 關注學習過程，強調反思意識解決， 引導主動探究，建構知識體系。
在信息學的廣闊天地中，編程不僅是一種技術，更是一門藝術。自1984年中國計算機學會舉辦青少年信息學奧林匹克競賽以來，編程逐漸成為青少年科技教育的重要組成部分。這種教育不僅培養(yǎng)了無數(shù)青少年的編程能力，也激發(fā)了他們對計算機科學的熱情和探索欲望。近年來，CCF組織編撰了《全國青少年信息學奧林匹克系列競賽大綱》（以下簡稱“NOI競賽大綱”）、《信息學奧林匹克辭典》，本書正是在此基礎之上編寫而成的，旨在為廣大青少年提供一本深入淺出、實用高效的編程教材。我們發(fā)現(xiàn)，盡管已經(jīng)出版了不少相關書籍，但真正能夠契合青少年學習特點、兼顧理論深度與實踐應用、精準覆蓋NOI競賽大綱的教材仍然稀缺。因此，我們希望通過這本“不一樣”的書，為讀者搭建一座從概念理解到實際運用的橋梁，讓中小學編程愛好者能夠迅速成長。本書具有以下幾個突出特點：1循序漸進，深入淺出我們精心設計了一條由淺入深的學習路徑。通過“情境導航”環(huán)節(jié)，從生活常識出發(fā)，引入問題。通過豐富的圖示和通俗易懂的語言講解核心概念，再逐步過渡到更復雜的算法實現(xiàn)。這種漸進式的學習方法旨在激發(fā)讀者的學習興趣，建立直觀的算法和數(shù)據(jù)結構認識，并避免因概念陡增引起的畏難情緒。2問題導向，實踐驅動通過“問題抽象”環(huán)節(jié)，從分析問題入手，抽象出知識或概念。每節(jié)都從一個實際問題（有些是經(jīng)典競賽題）出發(fā)，引導讀者分析問題、思考解決方案，然后學習相關算法原理，找出解決問題的基本方法，最后通過程序代碼來鞏固所學知識。這種問題導向的方法不僅能激發(fā)讀者的學習興趣，更能培養(yǎng)他們解決實際問題的能力。3強調思維訓練除了傳授具體的算法知識之外，我們十分注重培養(yǎng)讀者的算法思維。每節(jié)都設有“知識探究”“實踐應用”“總結提升”等環(huán)節(jié)，引導并鼓勵讀者獨立思考、大膽假設、認真求證。通過這種方式，我們希望讀者不僅學會“是什么”，更能理解“為什么”。通過給出注意事項和拓展方向，引導讀者進一步鉆研，最終達到舉一反三、觸類旁通的目的。4緊扣競賽實戰(zhàn)作為一本面向信息學競賽的教材，我們特別關注了競賽中的重點和難點。本書圍繞著信息學競賽的核心需求編寫，精選了很多經(jīng)典的競賽題目，通過詳盡的解析和豐富的實例，向讀者展示從問題分析到解決方案的全過程。此外，根據(jù)競賽的特點，對一些常見的競賽難點和易錯點進行了深入的剖析和講解。我們希望這些內容能夠幫助讀者更快地適應競賽節(jié)奏，提高解題速度和準確率。5注重知識體系構建在信息學領域，編程和算法是兩項不可或缺的核心技能。本書作為系列教材的基礎篇，涵蓋了NOI競賽大綱中入門級的算法與數(shù)據(jù)結構知識，這些知識是構建信息學競賽完整知識體系的重要環(huán)節(jié)。本書適合參加信息學奧林匹克競賽的學生使用，同時也適合對信息學算法感興趣的讀者閱讀。我們希望本書能夠幫助讀者在競賽中取得更好的成績，同時也為他們未來的學習和發(fā)展打下堅實的基礎。本書是一把開啟智慧之門的鑰匙，是一本培養(yǎng)學習方法和思維習慣的教科書。我們希望每一位讀者在學習本書的過程中，不僅能學會編程，更能學會如何思考和探索。作為編者，我們深知編寫一本好的教材何等艱難。盡管我們傾注了大量心血，仍難免存在疏漏和不足。我們真誠地希望能得到廣大讀者、教育工作者和業(yè)內專家的批評指正，以便在后續(xù)版本中不斷完善。最后，感謝所有為本書付出努力的人。感謝朱全民、宋新波等專家的指導和幫助，感謝所有讀者對本書的關注和支持。希望本書能夠成為你備戰(zhàn)信息學奧林匹克競賽的良師益友，陪伴你一起迎接挑戰(zhàn)，創(chuàng)造輝煌。讓我們共同在信息學的世界中探索未知，享受解決問題的樂趣，不斷前行！江 濤2024年7月
江濤，1965年出生，1986年畢業(yè)于安徽師范大學數(shù)學專業(yè)。廣東省佛山市南海區(qū)石門中學特級教師、信息學國際金牌教練。培養(yǎng)出7位IOI選手、30多位國家集訓隊隊員，專注信息學培訓方法研究，編寫了4本相關的著作和教材，完成2個省級課題。曾獲全國先進工作者、全國五一勞動獎章、國務院政府津貼、全國信息學十杰指導教師等榮譽
叢書序前言第一章 C++程序設計進階第一節(jié) 二維數(shù)組3一、情境導航3二、問題抽象3三、知識探究4（一） 二維數(shù)組的定義4（二） 二維數(shù)組的輸入、輸出4（三） 貪吃蛇問題5四、實踐應用6五、總結提升9第二節(jié) 多維數(shù)組11一、情境導航11二、問題抽象12三、知識探究12（一） 三維數(shù)組的定義12（二） 三維數(shù)組的輸入、輸出13（三） 統(tǒng)計石頭問題13四、實踐應用15五、總結提升19第三節(jié) 常用數(shù)學函數(shù)23一、情境導航23二、問題抽象23三、知識探究24（一） 絕對值函數(shù)24（二） 四舍五入函數(shù)24（三） 取下整函數(shù)（地板函數(shù)）25（四） 取上整函數(shù)（天花板函數(shù)）26（五） 平方根函數(shù)26（六） 常用三角函數(shù)27（七） 對數(shù)函數(shù)27（八） 冪函數(shù)28四、實踐應用29五、總結提升31第四節(jié) 自定義函數(shù)的參數(shù)33一、情境導航33二、問題抽象33三、知識探究34（一） 形參和實參34（二） 參數(shù)的傳遞方式34四、實踐應用36五、總結提升38第五節(jié) 結構體與聯(lián)合體42一、情境導航42二、問題抽象43三、知識探究44（一） 結構體的引入44（二） 結構體的定義44（三） 創(chuàng)建結構體變量45（四） 訪問結構體變量的成員45（五） 初始化結構體變量的成員45（六） 結構體數(shù)組46（七） 結構體作為函數(shù)參數(shù)46（八） 圖書館里的尋書游戲46四、實踐應用48五、總結提升51第六節(jié) 指針類型60一、情境導航60二、問題抽象60三、知識探究61（一） 什么是指針61（二） 如何聲明指針61（三） 指針的初始化62（四） 使用指針62（五） 指針和函數(shù)63（六） 指針的算術運算63（七） 指針與數(shù)組63（八） 動態(tài)分配內存64四、實踐應用66五、總結提升68第七節(jié) STL（標準模板庫）——算法函數(shù)72一、情境導航72二、問題抽象72三、知識探究73（一） 什么是STL73（二） 算法函數(shù)max、min、swap73（三） 算法函數(shù)sort75四、實踐應用77五、總結提升80第八節(jié) STL（標準模板庫）——線性容器85一、情境導航85二、問題抽象86三、知識探究87（一） STL的線性容器87（二） STL的向量(vector)87（三） 向量的成員函數(shù)89（四） STL的鏈表（list）90（五） STL的隊列（queue）92（六） STL的棧（stack）93（七） 線性容器相關函數(shù)總結95四、實踐應用96五、總結提升98第二章 數(shù)據(jù)結構及其運用第一節(jié) 線性結構——鏈表103一、情境導航103二、問題抽象103三、知識探究104（一） 鏈表的基本概念104（二） 鏈表的分類104（三） 鏈表的操作105（四） 鏈表操作的STL list實現(xiàn)105（五） 鏈表操作的數(shù)組模擬實現(xiàn)106（六） 雙向鏈表操作的數(shù)組模擬實現(xiàn)109（七） 循環(huán)鏈表操作的數(shù)組模擬實現(xiàn)111（八） 為什么學習鏈表操作的數(shù)組模擬實現(xiàn)112四、實踐應用112五、總結提升116第二節(jié) 線性結構——隊列和棧116一、情境導航116二、問題抽象117三、知識探究117（一） 什么是隊列117（二） 隊列的基本操作117（三） 隊列操作的STL queue實現(xiàn)118（四） 隊列操作的數(shù)組實現(xiàn)119（五） 與隊列類似的棧121（六） 棧的基本操作121（七） 棧操作的STL stack實現(xiàn)121（八） 棧操作的數(shù)組實現(xiàn)122四、實踐應用124五、總結提升130第三節(jié) 樹的引入133一、情境導航133二、問題抽象134三、知識探究134（一） 什么是樹134（二） 樹的表示與存儲135（三） 樹的基本操作136四、實踐應用137五、總結提升139第四節(jié) 二叉樹141一、情境導航141二、問題抽象142三、知識探究142（一） 什么是二叉樹142（二） 二叉樹的性質143（三） 二叉樹的表示與存儲143（四） 二叉樹的基本操作144四、實踐應用144五、總結提升146第五節(jié) 二叉搜索樹150一、情境導航150二、問題抽象151三、知識探究151（一） 什么是二叉搜索樹151（二） 二叉搜索樹的插入操作152（三） 二叉搜索樹的查找操作153（四） 二叉搜索樹的遍歷操作154四、實踐應用155五、總結提升157第六節(jié) 哈夫曼樹160一、情境導航160二、問題抽象160三、知識探究161（一） 什么是哈夫曼樹161（二） 構建哈夫曼樹161（三） 哈夫曼樹的性質162（四） 哈夫曼編碼162（五） 哈夫曼編碼的實現(xiàn)163四、實踐應用166五、總結提升169第七節(jié) 完全二叉樹170一、情境導航170二、問題抽象170三、知識探究171（一） 什么是完全二叉樹171（二） 完全二叉樹的平衡性質171（三） 完全二叉樹的數(shù)組實現(xiàn)171（四） 什么是堆173（五） 堆的操作173四、實踐應用175五、總結提升177第八節(jié) 圖的定義和存儲181一、情境導航181二、問題抽象182三、知識探究183（一） 什么是圖183（二） 圖的性質183（三） 什么是圖的鄰接矩陣184（四） 圖的鄰接矩陣的實現(xiàn)185（五） 圖的鄰接矩陣的優(yōu)缺點186（六） 圖的鄰接鏈表186（七） 圖的鄰接鏈表的實現(xiàn)187（八） 圖的鄰接鏈表的優(yōu)缺點188四、實踐應用188五、總結提升190第三章 算法設計第一節(jié) 算法基礎195一、算法概述195（一） 算法的定義195（二） 算法的特性195二、算法的描述195（一） 自然語言描述195（二） 流程圖描述196（三） 偽代碼描述197（四） 三種描述方式的比較197第二節(jié) 基礎算法1——貪心法198一、情境導航198二、問題抽象198三、知識探究199（一） 貪心法的定義與原理199（二） 貪心法的適用場景199（三） 分發(fā)餅干問題199四、實踐應用201五、總結提升206第三節(jié) 基礎算法2——遞推法208一、情境導航208二、問題抽象209三、知識探究209（一） 遞推法的基本步驟209（二） 遞推法的適用場景210四、實踐應用210五、總結提升213第四節(jié) 基礎算法3——遞歸法214一、情境導航214二、問題抽象215三、知識探究216（一） 什么是遞歸法216（二） 斐波那契數(shù)列的遞歸法描述216（三） 遞歸法的優(yōu)點216四、實踐應用217五、總結提升221第五節(jié) 基礎算法4——二分法222一、情境導航222二、問題抽象223三、知識探究223（一） 二分法原理223（二） 二分法的基本步驟223四、實踐應用225五、總結提升229第六節(jié) 基礎算法5——倍增法233一、情境導航233二、問題抽象233三、知識探究234四、實踐應用236五、總結提升238第七節(jié) 基礎算法6——前綴和245一、情境導航245二、問題抽象245三、知識探究245（一） 前綴和的定義與優(yōu)勢245（二） 前綴和的適用場景246（三） 用前綴和解決倉庫統(tǒng)計問題246四、實踐應用248五、總結提升250（一） 注意事項250（二） 算法復雜度250（三） 前綴和的優(yōu)缺點250第八節(jié) 數(shù)值處理算法256一、情境導航256二、問題抽象257三、知識探究257（一） 高精度加法257（二） 高精度減法259（三） 高精度乘法262四、實踐應用264五、總結提升265第九節(jié) 排序算法269一、情境導航269二、問題抽象270三、知識探究271（一） 冒泡排序271（二） 選擇排序273（三） 插入排序275四、實踐應用276五、總結提升278第十節(jié) 搜索算法281一、情境導航281二、問題抽象282三、知識探究282（一） 深度優(yōu)先搜索282（二） 廣度優(yōu)先搜索287四、實踐應用290五、總結提升292第十一節(jié) 圖論算法298一、情境導航298二、問題抽象299三、知識探究299（一） 圖的深度優(yōu)先搜索299（二） 圖的廣度優(yōu)先搜索303四、實踐應用305五、總結提升308第十二節(jié) 動態(tài)規(guī)劃1——簡單一維動態(tài)規(guī)劃312一、情境導航312二、問題抽象312三、知識探究313（一） 動態(tài)規(guī)劃概述315（二） 動態(tài)規(guī)劃的原理315四、實踐應用317五、總結提升320第十三節(jié) 動態(tài)規(guī)劃2——簡單背包類型動態(tài)規(guī)劃321一、情境導航321二、問題抽象322三、知識探究329四、實踐應用331五、總結提升334ⅩⅦⅩⅧ第十四節(jié) 動態(tài)規(guī)劃3——簡單區(qū)間類型動態(tài)規(guī)劃335一、情境導航335二、問題抽象336三、知識探究337四、實踐應用340五、總結提升344第四章 數(shù)學運用第一節(jié) 初等數(shù)論351一、情境導航351二、問題抽象351三、知識探究352（一） 整除352（二） 因數(shù)（因子）352（三） 倍數(shù)352（四） 指數(shù)352（五） 質數(shù)與合數(shù)352（六） 整數(shù)唯一分解定理352四、實踐應用357五、總結提升363第二節(jié) 組合數(shù)學368一、情境導航368二、問題抽象369三、知識探究369（一） 加法原理與乘法原理369（二） 排列與組合370四、實踐應用371五、總結提升374附錄 本書內容與NOI競賽大綱的對應關系379
書單推薦
