前言
近些年來，隨著人工智能、大數(shù)據(jù)等技術(shù)的迅猛發(fā)展，計(jì)算機(jī)編程開始逐漸進(jìn)入大眾的視野，特別是教育行業(yè)，各種少兒編程班如雨后春筍般層出不窮。人們開始漸漸意識(shí)到，培養(yǎng)孩子的邏輯和計(jì)算思維能力，已經(jīng)成為一項(xiàng)必不可少的教育方式。而這些在我的童年時(shí)期，是一項(xiàng)遙不可及的事物，甚至在我小學(xué)和初中期間，計(jì)算機(jī)還仍未被普及。那時(shí)候人們對(duì)計(jì)算機(jī)的認(rèn)識(shí)，還只限于QQ和各種網(wǎng)頁小游戲。計(jì)算機(jī)科學(xué)發(fā)展到現(xiàn)在，我們?cè)诟袊@科技發(fā)展迅速的同時(shí)，也必須感謝這個(gè)美好的時(shí)代。
我第一次接觸計(jì)算機(jī)編程是在初三保送高中階段，其他同學(xué)還在埋頭準(zhǔn)備中考時(shí)，我有幸遇到了我的恩師——NOI金牌教練董永建。恰逢董老師在保送生中選拔信息學(xué)奧賽學(xué)生，中考期間和整個(gè)暑假，我們42名保送生提前開始了高中生活，跟隨董老師從零開始接觸計(jì)算機(jī)、學(xué)習(xí)算法，直到暑假結(jié)束僅剩4名同學(xué)堅(jiān)持了下來。后來，我們4個(gè)人從機(jī)房搬進(jìn)了
“小黑屋”，認(rèn)識(shí)了各位師兄，開始了真正的“封閉式訓(xùn)練”。高中三年我們沒有周末、沒有節(jié)假日、沒有寒暑假，把所有的課余時(shí)間全貢獻(xiàn)給“小黑屋”，董老師帶著我們參加各種培訓(xùn)、參加高校ACM比賽，為了鍛煉體能，帶著我們爬山，偷玩游戲被發(fā)現(xiàn)了，罰我們操場(chǎng)跑圈……和師兄、師弟、師妹們?cè)凇靶『谖荨崩锏娜�年時(shí)光，是我至今回想都覺得快樂的時(shí)光，也是影響我一生的時(shí)光。在接觸編程后半年，我第一次參加了NOIP（National Olympiad in Informatics in Provinces，信息學(xué)奧林匹克聯(lián)賽），第一年初出茅廬，只是讓我們見識(shí)了世面，師兄們才是當(dāng)年的主力。我們充當(dāng)了一年陪考，直到第二年，經(jīng)過一年多的積累，我們成了主力，在2017年NOIP競(jìng)賽，我獲得了省一等獎(jiǎng)。所有光鮮的背后，都隱藏著熬過無數(shù)個(gè)不為人知的黑夜。
非常感謝董永建老師的悉心教導(dǎo)，讓我在初中時(shí)期開始，對(duì)計(jì)算機(jī)編程和算法有了初步的認(rèn)識(shí)。也緣于NOIP競(jìng)賽，讓我取得了保送武漢大學(xué)的資格，并因此決定了我畢業(yè)以后的工作和生活。人生選擇一條路，一直走到盡頭，不退讓，不更改，是件幸事。
NOIP競(jìng)賽對(duì)于很多孩子和家長來說，還是一個(gè)比較陌生的事物。它由中國計(jì)算機(jī)學(xué)會(huì)（CCF）統(tǒng)一組織，每年在同一時(shí)間、不同地點(diǎn)以各省市為單位由特派員組織。這個(gè)競(jìng)賽最初設(shè)立的目的是向中學(xué)階段的青少年普及計(jì)算機(jī)科學(xué)知識(shí)，帶來新的學(xué)習(xí)思路，并借此選拔人才。得益于近年來計(jì)算機(jī)知識(shí)的普及，許多對(duì)算法思想感興趣的學(xué)生和家長已經(jīng)開始把NOIP當(dāng)成一種新的學(xué)習(xí)思路和方法。本書所講的算法便是基于NOIP競(jìng)賽內(nèi)容進(jìn)行闡述的，從基礎(chǔ)的排序算法到圖論算法，逐步深入了解算法思路。
為了便于各位讀者對(duì)枯燥算法內(nèi)容的理解，本書融入了游戲設(shè)計(jì)思想，通過游戲攻關(guān)的方式，介紹各種算法的原理和應(yīng)用。當(dāng)你通讀完本書后，會(huì)發(fā)現(xiàn)原來我們平常玩的各種手游，比如“吃雞”“王者”，它們的設(shè)計(jì)思路就是采用了各種算法，這時(shí)候你就已經(jīng)開始領(lǐng)略到算法的奧妙，并開始進(jìn)入算法的魔法大門了。
為什么寫這本書?
寫這本書的原因，是來自朋友和妻子的啟發(fā)。得益于NOIP競(jìng)賽，我大學(xué)的專業(yè)學(xué)的是軟件工程，畢業(yè)后從事的也是軟件開發(fā)工作。在快要邁入而立之年的某一天，我的妻子問了我一個(gè)問題：“你做了這么多年軟件開發(fā)，早年也參加過NOIP，是不是現(xiàn)在得有所沉淀了？”這時(shí)候我們的女兒剛出生6個(gè)月，我因此開始思考教育的問題。這時(shí)候我的一個(gè)朋友告訴
我：“你可以嘗試寫一本書，將你在NOIP競(jìng)賽所學(xué)及多年工作積累記錄下來，說不定以后還能用來給你女兒當(dāng)教材�！庇谑�，便有了這本《哇，編程！——跟小明一起學(xué)算法》。
■ 本書導(dǎo)讀
全書共分8章：
第1章主要介紹排序算法，介紹了經(jīng)典的三種排序方法，同時(shí)介紹了時(shí)間復(fù)雜度、空間復(fù)雜度。
第2章主要介紹了五種基礎(chǔ)的算法，是信息學(xué)奧賽中常見的五種算法，一道算法題往往會(huì)包含多種基礎(chǔ)算法，本章也為后續(xù)篇章的算法奠定基礎(chǔ)。
第3、4章主要介紹了三種數(shù)據(jù)結(jié)構(gòu)——棧、隊(duì)列、樹，數(shù)據(jù)結(jié)構(gòu)是一門語言的基礎(chǔ)，本章在介紹算法的同時(shí)也強(qiáng)化了C++語言，補(bǔ)充了一些C++基礎(chǔ)學(xué)習(xí)中未涉及的內(nèi)容。
第5章主要介紹了動(dòng)態(tài)規(guī)劃算法，動(dòng)態(tài)規(guī)劃算法往往是NOIP（普及組、提高組）的壓軸題，也是能區(qū)分競(jìng)賽選手差距的題目，本章由最經(jīng)典的背包問題開始講解動(dòng)態(tài)規(guī)劃算法，理解本章才算是開始理解“算法的精髓”。
第6、7、8章主要介紹圖論相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、圖的遍歷、最小生成樹、并查集、最短路徑等。這三章所講的算法屬于進(jìn)階算法，圖論相關(guān)算法其本質(zhì)依然是前面章節(jié)所講的基礎(chǔ)算法，在介紹圖論算法時(shí)，也繼續(xù)幫助讀者鞏固前面部分的基礎(chǔ)算法。
閱讀本書的讀者，需要具備基本的C++語言基礎(chǔ)，本書算法盡量采用通俗易懂的例子給讀者講解。學(xué)習(xí)算法并不是一件難事，算法本身也并不高深，難在理解算法后怎么再用通俗的話語講解出來。本書所涉及的算法，也是我從初中就開始接觸并學(xué)習(xí)的，我相信初中程度的讀者也能夠理解并使用本書所寫的算法。
■ 致謝
在開始寫這本書之前，我一直猶豫要不要寫，因?yàn)閯偝錾�的女兒幾乎占用了我所有周末和空閑時(shí)間，是妻子的鼓勵(lì)，讓我下定決心要寫完這本書，作為送給女兒的禮物。在我寫書的這半年里，所有的節(jié)假日我都躲在圖書館度過，感謝我的妻子這半年里辛勞的付出，感謝她在背后的支持。
感謝我的大學(xué)室友——JazyWoo同學(xué)提供了給我寫書的機(jī)會(huì)，幫我聯(lián)絡(luò)各方資源，也感謝他在寫書期間，與我共同探討，共同完成此書。
還要再一次感謝董永建老師，是他的諄諄教導(dǎo)才能讓我有幸寫了這本算法書。

游明偉
2019年4月前言
近些年來，隨著人工智能、大數(shù)據(jù)等技術(shù)的迅猛發(fā)展，計(jì)算機(jī)編程開始逐漸進(jìn)入大眾的視野，特別是教育行業(yè)，各種少兒編程班如雨后春筍般層出不窮。人們開始漸漸意識(shí)到，培養(yǎng)孩子的邏輯和計(jì)算思維能力，已經(jīng)成為一項(xiàng)必不可少的教育方式。而這些在我的童年時(shí)期，是一項(xiàng)遙不可及的事物，甚至在我小學(xué)和初中期間，計(jì)算機(jī)還仍未被普及。那時(shí)候人們對(duì)計(jì)算機(jī)的認(rèn)識(shí)，還只限于QQ和各種網(wǎng)頁小游戲。計(jì)算機(jī)科學(xué)發(fā)展到現(xiàn)在，我們?cè)诟袊@科技發(fā)展迅速的同時(shí)，也必須感謝這個(gè)美好的時(shí)代。
我第一次接觸計(jì)算機(jī)編程是在初三保送高中階段，其他同學(xué)還在埋頭準(zhǔn)備中考時(shí)，我有幸遇到了我的恩師——NOI金牌教練董永建。恰逢董老師在保送生中選拔信息學(xué)奧賽學(xué)生，中考期間和整個(gè)暑假，我們42名保送生提前開始了高中生活，跟隨董老師從零開始接觸計(jì)算機(jī)、學(xué)習(xí)算法，直到暑假結(jié)束僅剩4名同學(xué)堅(jiān)持了下來。后來，我們4個(gè)人從機(jī)房搬進(jìn)了
“小黑屋”，認(rèn)識(shí)了各位師兄，開始了真正的“封閉式訓(xùn)練”。高中三年我們沒有周末、沒有節(jié)假日、沒有寒暑假，把所有的課余時(shí)間全貢獻(xiàn)給“小黑屋”，董老師帶著我們參加各種培訓(xùn)、參加高校ACM比賽，為了鍛煉體能，帶著我們爬山，偷玩游戲被發(fā)現(xiàn)了，罰我們操場(chǎng)跑圈……和師兄、師弟、師妹們?cè)凇靶『谖荨崩锏娜�年時(shí)光，是我至今回想都覺得快樂的時(shí)光，也是影響我一生的時(shí)光。在接觸編程后半年，我第一次參加了NOIP（National Olympiad in Informatics in Provinces，信息學(xué)奧林匹克聯(lián)賽），第一年初出茅廬，只是讓我們見識(shí)了世面，師兄們才是當(dāng)年的主力。我們充當(dāng)了一年陪考，直到第二年，經(jīng)過一年多的積累，我們成了主力，在2017年NOIP競(jìng)賽，我獲得了省一等獎(jiǎng)。所有光鮮的背后，都隱藏著熬過無數(shù)個(gè)不為人知的黑夜。
非常感謝董永建老師的悉心教導(dǎo)，讓我在初中時(shí)期開始，對(duì)計(jì)算機(jī)編程和算法有了初步的認(rèn)識(shí)。也緣于NOIP競(jìng)賽，讓我取得了保送武漢大學(xué)的資格，并因此決定了我畢業(yè)以后的工作和生活。人生選擇一條路，一直走到盡頭，不退讓，不更改，是件幸事。
NOIP競(jìng)賽對(duì)于很多孩子和家長來說，還是一個(gè)比較陌生的事物。它由中國計(jì)算機(jī)學(xué)會(huì)（CCF）統(tǒng)一組織，每年在同一時(shí)間、不同地點(diǎn)以各省市為單位由特派員組織。這個(gè)競(jìng)賽最初設(shè)立的目的是向中學(xué)階段的青少年普及計(jì)算機(jī)科學(xué)知識(shí)，帶來新的學(xué)習(xí)思路，并借此選拔人才。得益于近年來計(jì)算機(jī)知識(shí)的普及，許多對(duì)算法思想感興趣的學(xué)生和家長已經(jīng)開始把NOIP當(dāng)成一種新的學(xué)習(xí)思路和方法。本書所講的算法便是基于NOIP競(jìng)賽內(nèi)容進(jìn)行闡述的，從基礎(chǔ)的排序算法到圖論算法，逐步深入了解算法思路。
為了便于各位讀者對(duì)枯燥算法內(nèi)容的理解，本書融入了游戲設(shè)計(jì)思想，通過游戲攻關(guān)的方式，介紹各種算法的原理和應(yīng)用。當(dāng)你通讀完本書后，會(huì)發(fā)現(xiàn)原來我們平常玩的各種手游，比如“吃雞”“王者”，它們的設(shè)計(jì)思路就是采用了各種算法，這時(shí)候你就已經(jīng)開始領(lǐng)略到算法的奧妙，并開始進(jìn)入算法的魔法大門了。
為什么寫這本書?
寫這本書的原因，是來自朋友和妻子的啟發(fā)。得益于NOIP競(jìng)賽，我大學(xué)的專業(yè)學(xué)的是軟件工程，畢業(yè)后從事的也是軟件開發(fā)工作。在快要邁入而立之年的某一天，我的妻子問了我一個(gè)問題：“你做了這么多年軟件開發(fā)，早年也參加過NOIP，是不是現(xiàn)在得有所沉淀了？”這時(shí)候我們的女兒剛出生6個(gè)月，我因此開始思考教育的問題。這時(shí)候我的一個(gè)朋友告訴
我：“你可以嘗試寫一本書，將你在NOIP競(jìng)賽所學(xué)及多年工作積累記錄下來，說不定以后還能用來給你女兒當(dāng)教材�！庇谑�，便有了這本《哇，編程！——跟小明一起學(xué)算法》。
■ 本書導(dǎo)讀
全書共分8章：
第1章主要介紹排序算法，介紹了經(jīng)典的三種排序方法，同時(shí)介紹了時(shí)間復(fù)雜度、空間復(fù)雜度。
第2章主要介紹了五種基礎(chǔ)的算法，是信息學(xué)奧賽中常見的五種算法，一道算法題往往會(huì)包含多種基礎(chǔ)算法，本章也為后續(xù)篇章的算法奠定基礎(chǔ)。
第3、4章主要介紹了三種數(shù)據(jù)結(jié)構(gòu)——棧、隊(duì)列、樹，數(shù)據(jù)結(jié)構(gòu)是一門語言的基礎(chǔ)，本章在介紹算法的同時(shí)也強(qiáng)化了C++語言，補(bǔ)充了一些C++基礎(chǔ)學(xué)習(xí)中未涉及的內(nèi)容。
第5章主要介紹了動(dòng)態(tài)規(guī)劃算法，動(dòng)態(tài)規(guī)劃算法往往是NOIP（普及組、提高組）的壓軸題，也是能區(qū)分競(jìng)賽選手差距的題目，本章由最經(jīng)典的背包問題開始講解動(dòng)態(tài)規(guī)劃算法，理解本章才算是開始理解“算法的精髓”。
第6、7、8章主要介紹圖論相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、圖的遍歷、最小生成樹、并查集、最短路徑等。這三章所講的算法屬于進(jìn)階算法，圖論相關(guān)算法其本質(zhì)依然是前面章節(jié)所講的基礎(chǔ)算法，在介紹圖論算法時(shí)，也繼續(xù)幫助讀者鞏固前面部分的基礎(chǔ)算法。
閱讀本書的讀者，需要具備基本的C++語言基礎(chǔ)，本書算法盡量采用通俗易懂的例子給讀者講解。學(xué)習(xí)算法并不是一件難事，算法本身也并不高深，難在理解算法后怎么再用通俗的話語講解出來。本書所涉及的算法，也是我從初中就開始接觸并學(xué)習(xí)的，我相信初中程度的讀者也能夠理解并使用本書所寫的算法。
■ 致謝
在開始寫這本書之前，我一直猶豫要不要寫，因?yàn)閯偝錾�的女兒幾乎占用了我所有周末和空閑時(shí)間，是妻子的鼓勵(lì)，讓我下定決心要寫完這本書，作為送給女兒的禮物。在我寫書的這半年里，所有的節(jié)假日我都躲在圖書館度過，感謝我的妻子這半年里辛勞的付出，感謝她在背后的支持。
感謝我的大學(xué)室友——JazyWoo同學(xué)提供了給我寫書的機(jī)會(huì)，幫我聯(lián)絡(luò)各方資源，也感謝他在寫書期間，與我共同探討，共同完成此書。
還要再一次感謝董永建老師，是他的諄諄教導(dǎo)才能讓我有幸寫了這本算法書。

游明偉
2019年4月