哇編程！-跟小明一起學(xué)算法

??

?悢???怺?乚?

???


???



??

文文前.indd前.indd122020/4/14020/4/14115:53:295:53:29

內(nèi)容簡介

本書融入了游戲設(shè)計思想，通過游戲攻關(guān)的方式，介紹各種算法的原理和應(yīng)用。全書共分

8章，具體包括排序算法、窮舉算法、遞歸算法、回溯算法、貪心算法、分治算法，棧、隊列、

樹三種數(shù)據(jù)結(jié)構(gòu)，動態(tài)規(guī)劃算法，圖論相關(guān)算法等內(nèi)容。

本書適合程序員和參加NOIP、NOI、ACM/ICPC競賽的讀者閱讀學(xué)習(xí)，也可作為高等院校

計算機、數(shù)學(xué)及相關(guān)專業(yè)的師生用書和培訓(xùn)學(xué)校的教材。

圖書在版編目（CIP）數(shù)據(jù)

哇，編程！:跟小明一起學(xué)算法/游明偉,吳健之編著.—北京：

中國鐵道出版社有限公司，2020.5

ISBN978-7-113-26736-0

Ⅰ.①哇…Ⅱ.①游…②吳…Ⅲ.①程序設(shè)計－算法－少兒讀物

Ⅳ.①TP311.1-49

中國版本圖書館CIP數(shù)據(jù)核字（2020）第046339號

書名：哇，編程！——跟小明一起學(xué)算法

WA,BIANCHENG!——GENXIAOMINGYIQIXUESUANFA

作者：游明偉吳健之

責(zé)任編輯：于先軍讀者熱線電話：（010）63560056

責(zé)任印制：趙星辰封面設(shè)計：

出版發(fā)行：中國鐵道出版社有限公司（100054，北京市西城區(qū)右安門西街8號）

印刷：三河市航遠(yuǎn)印刷有限公司

版次：2020年5月第1版2020年5月第1次印刷

開本：787mm×1092mm1/16印張：17.25字?jǐn)?shù)：330千

書號：ISBN978-7-113-26736-0

定價：69.80元

版權(quán)所有侵權(quán)必究

凡購買鐵道版圖書，如有印制質(zhì)量問題，請與本社讀者服務(wù)部聯(lián)系調(diào)換。電話：（010）51873174

打擊盜版舉報電話：（010）51873659

文文前.indd前.indd222020/4/14020/4/14115:53:345:53:34

配套資源下載地址：

/2020/0404/14246.shtml

前言

近些年來，隨著人工智能、大數(shù)據(jù)等技術(shù)的迅猛發(fā)展，計算機編程開始逐漸進入大眾的

視野，特別是教育行業(yè)，各種少兒編程班如雨后春筍般層出不窮。人們開始漸漸意識到，培

養(yǎng)孩子的邏輯和計算思維能力，已經(jīng)成為一項必不可少的教育方式。而這些在我的童年時期，

是一項遙不可及的事物，甚至在我小學(xué)和初中期間，計算機還仍未被普及。那時候人們對計

算機的認(rèn)識，還只限于QQ和各種網(wǎng)頁小游戲。計算機科學(xué)發(fā)展到現(xiàn)在，我們在感嘆科技發(fā)

展迅速的同時，也必須感謝這個美好的時代。

我第一次接觸計算機編程是在初三保送高中階段，其他同學(xué)還在埋頭準(zhǔn)備中考時，我有

幸遇到了我的恩師——NOI金牌教練董永建。恰逢董老師在保送生中選拔信息學(xué)奧賽學(xué)生，

中考期間和整個暑假，我們42名保送生提前開始了高中生活，跟隨董老師從零開始接觸計

算機、學(xué)習(xí)算法，直到暑假結(jié)束僅剩4名同學(xué)堅持了下來。后來，我們4個人從機房搬進了

“小黑屋”，認(rèn)識了各位師兄，開始了真正的“封閉式訓(xùn)練”。高中三年我們沒有周末、沒

有節(jié)假日、沒有寒暑假，把所有的課余時間全貢獻(xiàn)給“小黑屋”，董老師帶著我們參加各

種培訓(xùn)、參加高校ACM比賽，為了鍛煉體能，帶著我們爬山，偷玩游戲被發(fā)現(xiàn)了，罰我們

操場跑圈……和師兄、師弟、師妹們在“小黑屋”里的三年時光，是我至今回想都覺得快

樂的時光，也是影響我一生的時光。在接觸編程后半年，我第一次參加了NOIP（National

OlympiadinInformaticsinProvinces，信息學(xué)奧林匹克聯(lián)賽），第一年初出茅廬，只是讓我

們見識了世面，師兄們才是當(dāng)年的主力。我們充當(dāng)了一年陪考，直到第二年，經(jīng)過一年多的

積累，我們成了主力，在2017年NOIP競賽，我獲得了省一等獎。所有光鮮的背后，都隱

藏著熬過無數(shù)個不為人知的黑夜。

非常感謝董永建老師的悉心教導(dǎo)，讓我在初中時期開始，對計算機編程和算法有了初步

的認(rèn)識。也緣于NOIP競賽，讓我取得了保送武漢大學(xué)的資格，并因此決定了我畢業(yè)以后的

工作和生活。人生選擇一條路，一直走到盡頭，不退讓，不更改，是件幸事。

文文前.indd前.indd322020/4/14020/4/14115:53:355:53:35

哇，編程！——跟小明一起學(xué)算法

NOIP競賽對于很多孩子和家長來說，還是一個比較陌生的事物。它由中國計算機學(xué)會

（CCF）統(tǒng)一組織，每年在同一時間、不同地點以各省市為單位由特派員組織。這個競賽最

初設(shè)立的目的是向中學(xué)階段的青少年普及計算機科學(xué)知識，帶來新的學(xué)習(xí)思路，并借此選拔

人才。得益于近年來計算機知識的普及，許多對算法思想感興趣的學(xué)生和家長已經(jīng)開始把

NOIP當(dāng)成一種新的學(xué)習(xí)思路和方法。本書所講的算法便是基于NOIP競賽內(nèi)容進行闡述的，

從基礎(chǔ)的排序算法到圖論算法，逐步深入了解算法思路。

為了便于各位讀者對枯燥算法內(nèi)容的理解，本書融入了游戲設(shè)計思想，通過游戲攻關(guān)的

方式，介紹各種算法的原理和應(yīng)用。當(dāng)你通讀完本書后，會發(fā)現(xiàn)原來我們平常玩的各種手游，

比如“吃雞”“王者”，它們的設(shè)計思路就是采用了各種算法，這時候你就已經(jīng)開始領(lǐng)略到

算法的奧妙，并開始進入算法的魔法大門了。

為什么寫這本書?

寫這本書的原因，是來自朋友和妻子的啟發(fā)。得益于NOIP競賽，我大學(xué)的專業(yè)學(xué)的是

軟件工程，畢業(yè)后從事的也是軟件開發(fā)工作。在快要邁入而立之年的某一天，我的妻子問了

我一個問題：“你做了這么多年軟件開發(fā)，早年也參加過NOIP，是不是現(xiàn)在得有所沉淀了？”

這時候我們的女兒剛出生6個月，我因此開始思考教育的問題。這時候我的一個朋友告訴

我：“你可以嘗試寫一本書，將你在NOIP競賽所學(xué)及多年工作積累記錄下來，說不定以后

還能用來給你女兒當(dāng)教材?！庇谑牵阌辛诉@本《哇，編程！——跟小明一起學(xué)算法》。

■本書導(dǎo)讀

全書共分8章：

第1章主要介紹排序算法，介紹了經(jīng)典的三種排序方法，同時介紹了時間復(fù)雜度、空間

復(fù)雜度。

第2章主要介紹了五種基礎(chǔ)的算法，是信息學(xué)奧賽中常見的五種算法，一道算法題往往

會包含多種基礎(chǔ)算法，本章也為后續(xù)篇章的算法奠定基礎(chǔ)。

第3、4章主要介紹了三種數(shù)據(jù)結(jié)構(gòu)——棧、隊列、樹，數(shù)據(jù)結(jié)構(gòu)是一門語言的基礎(chǔ)，

本章在介紹算法的同時也強化了C++語言，補充了一些C++基礎(chǔ)學(xué)習(xí)中未涉及的內(nèi)容。

第5章主要介紹了動態(tài)規(guī)劃算法，動態(tài)規(guī)劃算法往往是NOIP（普及組、提高組）的

壓軸題，也是能區(qū)分競賽選手差距的題目，本章由最經(jīng)典的背包問題開始講解動態(tài)規(guī)劃算法，

理解本章才算是開始理解“算法的精髓”。

·4·

文文前.indd前.indd422020/4/14020/4/14115:53:355:53:35

第6、7、8章主要介紹圖論相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、圖的遍歷、

最小生成樹、并查集、最短路徑等。這三章所講的算法屬于進階算法，圖論相關(guān)算法其本質(zhì)依

然是前面章節(jié)所講的基礎(chǔ)算法，在介紹圖論算法時，也繼續(xù)幫助讀者鞏固前面部分的基礎(chǔ)算法。

閱讀本書的讀者，需要具備基本的C++語言基礎(chǔ)，本書算法盡量采用通俗易懂的例子

給讀者講解。學(xué)習(xí)算法并不是一件難事，算法本身也并不高深，難在理解算法后怎么再用通

俗的話語講解出來。本書所涉及的算法，也是我從初中就開始接觸并學(xué)習(xí)的，我相信初中程

度的讀者也能夠理解并使用本書所寫的算法。

■致謝

在開始寫這本書之前，我一直猶豫要不要寫，因為剛出生的女兒幾乎占用了我所有周末

和空閑時間，是妻子的鼓勵，讓我下定決心要寫完這本書，作為送給女兒的禮物。在我寫書

的這半年里，所有的節(jié)假日我都躲在圖書館度過，感謝我的妻子這半年里辛勞的付出，感謝

她在背后的支持。

感謝我的大學(xué)室友——JazyWoo同學(xué)提供了給我寫書的機會，幫我聯(lián)絡(luò)各方資源，也

感謝他在寫書期間，與我共同探討，共同完成此書。

還要再一次感謝董永建老師，是他的諄諄教導(dǎo)才能讓我有幸寫了這本算法書。

游明偉

2019年4月

·5·

文文前.indd前.indd522020/4/14020/4/14115:53:355:53:35

目錄

第1章整理下背包.....................................................................................1

1.1桶排序........................................................................................................2

1.2冒泡排序.....................................................................................................8

1.3快速排序....................................................................................................15

1.4時間和空間復(fù)雜度.....................................................................................20

第2章開始闖關(guān)吧...................................................................................22

2.1忘記密碼了——窮舉算法...........................................................................23

2.2漢諾塔——遞歸算法..................................................................................25

2.3八皇后——回溯算法...................................................................................31

2.4分裝備——貪心算法...................................................................................41

2.5二分查找——分治算法..............................................................................45

第3章爆滿的服務(wù)器與背包.....................................................................53

3.1服務(wù)器爆滿——隊列..................................................................................54

3.2合成寶石——優(yōu)先隊列...............................................................................61

3.3背包里的道具——棧..................................................................................65

3.4十進制轉(zhuǎn)任意進制.....................................................................................74

文文前.indd前.indd622020/4/14020/4/14115:53:355:53:35

第4章點亮技能樹...................................................................................77

4.1樹.............................................................................................................78

4.1.1樹的定義...........................................................................................................................79

4.1.2樹的相關(guān)術(shù)語...................................................................................................................80

4.2二叉樹......................................................................................................83

4.2.1二叉樹性質(zhì).......................................................................................................................84

4.2.2特殊的二叉樹...................................................................................................................85

4.2.3二叉樹的遍歷...................................................................................................................87

4.2.4二叉樹的存儲結(jié)構(gòu).........................................................................................................105

4.3堆...........................................................................................................107

4.3.1大根堆與小根堆.............................................................................................................107

4.3.2堆的操作.........................................................................................................................109

4.4堆排序.....................................................................................................132

第5章爆裝備啦，快來撿......................................................................139

5.1撿到完美的海螺——遞推算法....................................................................140

5.201背包——動規(guī)算法................................................................................143

5.3完全背包——動規(guī)算法.............................................................................148

5.4多重背包——動規(guī)算法.............................................................................152

第6章迷宮............................................................................................156

6.1圖的概念..................................................................................................157

6.1.1圖的定義.........................................................................................................................158

6.1.2圖的存儲結(jié)構(gòu).................................................................................................................162

文文前.indd前.indd722020/4/14020/4/14115:53:355:53:35

6.2圖的遍歷.................................................................................................167

6.2.1深度優(yōu)先搜索法.............................................................................................................168

6.2.2廣度優(yōu)先搜索法.............................................................................................................172

6.3并查集.....................................................................................................176

6.3.1分析.................................................................................................................................177

6.3.2并查集的原理.................................................................................................................179

6.3.3并查集的操作.................................................................................................................180

6.4最小生成樹..............................................................................................186

6.4.1Prim算法........................................................................................................................187

6.4.2Kruskal算法...................................................................................................................192

第7章探索地圖每個角落......................................................................197

7.1深度優(yōu)先搜索...........................................................................................198

7.2廣度優(yōu)先搜索...........................................................................................211

第8章快逃命去吧.................................................................................229

8.1拓?fù)渑判?................................................................................................230

8.2最短路徑................................................................................................240

8.2.1Floyd算法.......................................................................................................................240

8.2.2Dijkstra算法...................................................................................................................250

8.2.3Bellman-Ford算法.........................................................................................................255

8.2.4SPFA算法.......................................................................................................................261

文文前.indd前.indd822020/4/14020/4/14115:53:355:53:35

第1章

整理下背包

正正文.indd文.indd122020/4/14020/4/14115:54:325:54:32

哇，編程！——跟小明一起學(xué)算法

1.1桶排序

?Ρ??????????????????????????????????Ρ?

???????????????????úú??ǎ

???к??????????t????????????t??????????

???????????t????????????ζ?????t?????????

??????????????ǎ???к?????Ν????

??????????????????ǒ?????ǔǎ?????????????

?????????????????????????????ΓΡ??????ΓΡ?

????????????????NPC?????????????????????

ǎ???????????????????????ΓΡ?

????????????3??????1??????6?????????????

?ǎ??????3????????10??????7??āā????????????

?????????1?????????Χ????????????????????

?3??????3??????6??????7????????10??āā?????

?????????????????Χ????????

·2·

正正文.indd文.indd222020/4/14020/4/14115:54:345:54:34

第1章整理下背包

?????Ρ????????ǎ??Ρ???????????????р?????

?Ρ???????????????úú???ǎ

??????????????????????????????????????

?????????????????ǎ

??????Ρ????Χ?????ǎ

第1步首先，我們知道裝備價格最大是10，所以我們先準(zhǔn)備10個編號分別為1～10號

的桶，同時將每個桶的計數(shù)器設(shè)置為0，如下圖所示。

第2步我們將斗篷（3金）放入3號桶中，3號桶計數(shù)器+1。

第3步將護腕（1金）放入1號桶中，1號桶計數(shù)器+1。

·3·

正正文.indd文.indd322020/4/14020/4/14115:54:345:54:34

哇，編程！——跟小明一起學(xué)算法

第4步將冰杖（6金）放入6號桶中，6號桶計數(shù)器+1。

第5步將水銀鞋（3金）放入3號桶中，3號桶計數(shù)器+1，此時3號計數(shù)器累加到2，

表示有2個價格為3的裝備。

·4·

正正文.indd文.indd422020/4/14020/4/14115:54:345:54:34

第1章整理下背包

第6步將風(fēng)暴巨劍（10金）放入10號桶中，10號桶計數(shù)器+1。

第7步將圣杯（7金）放入7號桶中，7號桶計數(shù)器+1。

1?????????0?????????????????????????????

ǎ?2?????2??????????????1??

0??????????????Ρ?????1?10??????????????

2????2???āā??1????1??????????????

?1??2?????3???2??4?????5?????6???1??7??1

?1??8?????9?????10???1?ǎ??

????????????

·5·

正正文.indd文.indd522020/4/14020/4/14115:54:355:54:35

哇，編程！——跟小明一起學(xué)算法

?Χ???????????????????????Ρ?Ν??????????

???????Χ????ǎ?

???Ρ????????????Λ????

第1步首先，我們準(zhǔn)備一個數(shù)組bucket[11]來代表桶，bucket單詞就是桶的意思，

bucket[1]就表示編號為1的桶，用來對價格為1的裝備進行計數(shù)；有同學(xué)可能會覺得奇怪

了，明明只要10個桶，bucket[]數(shù)組長度為什么定義成11呢？同學(xué)們回想一下，我們在

C語言基礎(chǔ)里學(xué)過的數(shù)組概念，由于數(shù)組的下標(biāo)是從0開始，bucket[11]表示是從bucket[0]

到bucket[10]的長度為11的數(shù)組；如果我們只定義bucket[10]，那數(shù)組的最后一個元素是

bucket[9]，我們就沒地方放價格為10的道具。

第2步定義好bucket[]后，我們用memset函數(shù)將數(shù)組初始化，表示計數(shù)器初始化設(shè)置

為0。

第3步然后循環(huán)6個裝備的價格，將每個價格對應(yīng)的計數(shù)器+1。

第4步最后，按1～10順序，根據(jù)bucket數(shù)量，打印出數(shù)組下標(biāo)。

ǘΛ???ǚ

#include<iostream>

#include<cstdio>

usingnamespacestd;

intmain()

{

inti,j;

·6·

正正文.indd文.indd622020/4/14020/4/14115:54:355:54:35

第1章整理下背包

intn=6;

inta[6]={3,1,6,3,10,7};

//a[]最大數(shù)為10，需申請空間大小為10的buckets[]

intbuckets[11];

//將buckets中的所有數(shù)據(jù)都初始化為0，表示初始時每個桶的計數(shù)器都是0。

memset(buckets,0,sizeof(buckets));

//將a[]中的數(shù)分別放入對應(yīng)標(biāo)號的buckets中，每放入一個，計數(shù)器+1

for(i=0;i<n;i++){

buckets[a[i]]++;

}

//循環(huán)桶的標(biāo)號，根據(jù)每個桶的計數(shù)器打印出桶的標(biāo)號

for(i=1;i<11;i++)

for(j=0;j<buckets[i];j++)

{

printf("%d",i);

}

return0;

}

????????

???????????N????????????????Ρ?????????

?????????????????????????????????????ǎ

?????????????Ρ????????????????????????

???????????????????????к??Ρ??[2,1,9999999]????

???????Ρ???????bucket[1000000]????????Ρ???bucket[1]?

bucket[2]?bucket[9999999]???Γ??????Ρ???ǎ?Ν?????ζ?????

??????????????????ǎ

?Ρ????????????????????????O?n???????р?

?Ρ??t???????ǎ

??????????????????????????????????????

?????????Ν??????????úú???2.0?????????????

????????ǎ

к??Ρ?bucket[0]???Χ?0?9??????bucket[1]???Χ?10?19?

āā???Ρ????bucket[0]????bucket[2]???Χ?20?29????????

??????????????bucket[1]????????????????bucket[2]?

?????????????āā

·7·

正正文.indd文.indd722020/4/14020/4/14115:54:355:54:35

哇，編程！——跟小明一起學(xué)算法

???Ρ????????????10Ф???bucket[0]???Χ?0?99???

??Ρ????ζ????100Ф?1000Ф?????????Χ?0?999??????

??????????????????????2.5????????Ρ???????

??2.0Λ??ǎ

1.2冒泡排序

???????????????????????????????????Ρ??

??????????????t?????????????????????????

?????ǎ

???????????????????????????????bz?????d??

?????fbjj?????hw?????sb??????syx???Ρ?Ν????????

?р???ǎ

?????????Χ????????6.5??????Χ???????????

????????????????????????????????

?Ρ??t???????????úú????ǎ???????????????

???????????????????Ρ????????????????????

???ζ???????????ǎ???????????????????úú???

·8·

正正文.indd文.indd822020/4/14020/4/14115:54:355:54:35

第1章整理下背包

??????ǎ??

?Ρ?????????????Χ??????????????????

?????10??????7??????3??????1??????6?????

??3??

1．第一趟冒泡排序

第1步進行第一次比較，比對第一位10和第二位7，10>7，交換位置。

第2步進行第二次比較，比對第二位10（因上輪位置交換，此時第二位是10）和第三位3，

10>3，交換位置。

第3步進行第三次比較，比對第三位10和第四位1，10>1，交換位置。

第4步進行第四次比較，比對第四位10和第五位6，10>6，交換位置。

第5步進行第五次比較，比對第五位10和第六位3，10>3，交換位置。

???????????????????????????????10???з?

?10??t????ǎ??????????ǎ????Ρ?Ν?????????з?

????Ρ?????????????????ǎ

2．第二趟冒泡排序

第1步進行第一次比較，比對第一位7和第二位3，7>3，交換位置。

·9·

正正文.indd文.indd922020/4/14020/4/14115:54:365:54:36

哇，編程！——跟小明一起學(xué)算法

第2步進行第二次比較，比對第二位7（因上輪位置交換，此時第二位是7）和第三位1，

7>1，交換位置。

第3步進行第三次比較，比對第三位7和第四位6，7>6，交換位置。

第4步進行第四次比較，比對第四位7和第五位3，7>3，交換位置。

?7????10?????????????????????????????з??

????????????????????????????????????????

?????t?????10???7????????з?????????????з?

??Ρ??????????????7?10??????N-1???????????ǎ?

????Ρ?????????????????ǎ

3．第三趟冒泡排序

第1步進行第一次比較，比對第一位3和第二位1，3>1，交換位置。

第2步進行第二次比較，比對第二位3（因上輪位置交換，此時第二位是3）和第三位6，

3<6，不交換位置。

第3步進行第三次比較，比對第三位6（因上輪位置不交換，此時第三位還是6）和第四位3，

6>3，交換位置。

·10·

正正文.indd文.indd101022020/4/14020/4/14115:54:365:54:36

第1章整理下背包

?6????7?????????????ǎ???????????????з??

?????????????????????????????????3<6???

??δ??????????Ν?????????ǎ?Ρ??????????????

???ζ??t??ǎ????Ρ?????????????????ǎ???????з

???????????????????Ν??????Ρ???????????

??Ρ????????????????????????????????Ρ????

??t?????????1?3?3?Ρ?????Ρ??????????6?7?10?з??

??????t?????Ρ?????????????Ρ?????????????

р?????????Ρt???ǎ

4．第四趟冒泡排序

第1步進行第一次比較，比對第一位1和第二位3，1<3，不交換位置。

第2步進行第二次比較，比對第二位3和第三位3，此時兩個數(shù)值相等，我們可以進行位

置交換，也可以不進行位置交換，對最終排序結(jié)果沒有影響，為了少進行一次交換操作，我

們不交換位置。

·11·

正正文.indd文.indd111122020/4/14020/4/14115:54:365:54:36

哇，編程！——跟小明一起學(xué)算法

?3????6?????????????ǎ???????????????з??

????Ρ????????????????????????Ρ???3???ǎ??

??Ρ?????????????????ǎ

5．第五趟冒泡排序

?????????????1????3?1<3??????ǎ

·12·

正正文.indd文.indd121222020/4/14020/4/14115:54:365:54:36

第1章整理下背包

?3????3?????????????ǎ???????????????з??

????Ρ???????????ǎ??????????????????t1???

???1?????????ǎ?