算法之禪:遞推與遞歸

-
【作 者】劉鐵猛 著
【I S B N 】978-7-5170-8934-6
【責(zé)任編輯】陳潔
【適用讀者群】科技
【出版時(shí)間】2020-10-30
【開(kāi) 本】16開(kāi)
【裝幀信息】平裝(光膜)
【版 次】第1版第1次印刷
【頁(yè) 數(shù)】164
【千字?jǐn)?shù)】208
【印 張】10.25
【定 價(jià)】¥68
【叢 書(shū)】暫無(wú)分類(lèi)
【備注信息】
簡(jiǎn)介
本書(shū)特色
前言
章節(jié)列表
精彩閱讀
下載資源
相關(guān)圖書(shū)
算法是個(gè)有趣的東西—針對(duì)某個(gè)問(wèn)題設(shè)計(jì)算法的時(shí)候,不會(huì)的人感覺(jué)像“大海撈針”,而會(huì)的人則感覺(jué)像“一葦渡江”。高手的頭腦里都有一張“算法地圖”,算法之間不是孤立的,而是彼此連通的。算法之間的內(nèi)在聯(lián)系有很多,但挖掘到根源上,就是遞推與遞歸兩種思想。本書(shū)從深度解析遞推和遞歸這兩個(gè)基本算法思想開(kāi)始,用它們貫穿起了《算法導(dǎo)論》中的幾十個(gè)經(jīng)典算法,包括排序、查找、回溯、貪心、分治、動(dòng)態(tài)規(guī)劃、圖算法等。
本書(shū)成稿自作者的教案,秉承了作者一貫的風(fēng)趣幽默又不失嚴(yán)謹(jǐn)?shù)膶?xiě)作風(fēng)格,同時(shí)融入了學(xué)習(xí)心理學(xué)和認(rèn)知科學(xué)的實(shí)踐原理。作者的諸多學(xué)生在參加完以本書(shū)內(nèi)容為藍(lán)本的集訓(xùn)后進(jìn)入了微軟、臉書(shū)、亞馬遜、領(lǐng)英、甲骨文等公司,所以本書(shū)是經(jīng)過(guò)千錘百煉的一線(xiàn)教學(xué)成果。
本書(shū)適合于所有想通過(guò)學(xué)習(xí)算法來(lái)精進(jìn)自己編程能力的讀者。為了傾聽(tīng)讀者們的心聲、不斷完善這本書(shū),作者熱切地期待大家與他在領(lǐng)英上建立聯(lián)系。在那里,作者還將源源不斷地與讀者們分享種類(lèi)教學(xué)資源和工作機(jī)會(huì)。作者的領(lǐng)英首頁(yè)是https://www.linkedin.com/ in/hexagons/。
聚二十年功力,呈禪意才思、匠心代碼
探因由,究所以
遞推遞歸雙重實(shí)現(xiàn),打通算法任督二脈
文品其思,碼鑒其才
親愛(ài)的讀者,當(dāng)你讀到這篇致謝的時(shí)候,你應(yīng)該還沒(méi)有開(kāi)始正文的閱讀,因?yàn)榇蠖鄶?shù)時(shí)候“致謝”都緊跟在一本書(shū)的序言之后。而對(duì)于我們作者來(lái)說(shuō),“致謝”則常常是需要為一本書(shū)撰寫(xiě)的最后部分,因?yàn)檫@時(shí)候整本書(shū)的編輯、勘校、排版等工作已經(jīng)收尾,馬上就要印刷發(fā)行了。對(duì)于我而言,“致謝”也是最激動(dòng)人心的部分,因?yàn)樵谶@里出現(xiàn)的都是與本書(shū)出版相關(guān)的、最重要的人們—它就像一個(gè)時(shí)空隧道,幾十年后打開(kāi)它,依然會(huì)讓我想起這些朋友、讓一件件往事歷歷在目。
本書(shū)的順利出版,首先要感謝中國(guó)水利水電出版社的周春元先生。若不是周先生慷慨接納我的文字并組織最優(yōu)秀的團(tuán)隊(duì)將之編輯成冊(cè),恐怕這些有趣的內(nèi)容會(huì)永遠(yuǎn)躺在互聯(lián)網(wǎng)的某個(gè)角落里、無(wú)緣與大家相見(jiàn)。次者,我要將我最誠(chéng)摯的謝意獻(xiàn)給本書(shū)的責(zé)任編輯陳潔女士,是她親自用一雙慧眼和化腐朽為神奇的能力將我那堆粗鄙不堪的文字編輯成一本讓人賞心悅目、愛(ài)不釋手的書(shū)籍。你可能會(huì)想:“不就是作者對(duì)出版社的日常吹捧嘛,有什么!”還真不是這樣。試想,如果你看到一個(gè)講算法的作者把Java虛擬機(jī)的縮寫(xiě)寫(xiě)成JMV(正確的應(yīng)該是JVM),你會(huì)怎么想?你一定會(huì)想:“你到底會(huì)不會(huì)編程啊?還講算法!”是的,就像你所感受到的,內(nèi)容當(dāng)中的“低級(jí)錯(cuò)誤”傷害的已經(jīng)不僅僅是閱讀體驗(yàn),傷害更多的恐怕是讀者對(duì)內(nèi)容和對(duì)我的信任。而前面這個(gè)錯(cuò)誤,正是我親手寫(xiě)下的、幾十上百個(gè)錯(cuò)誤中的一個(gè)(而且不是最“丟人”的一個(gè))。對(duì)于程序員而言,“筆誤”這個(gè)東西是不存在的,因?yàn)闊o(wú)論是腦子抽筋還是筆誤,所產(chǎn)生的錯(cuò)誤代碼都會(huì)讓程序崩潰。整個(gè)編輯和勘校過(guò)程,自始至終,陳編輯都與我保持著十分密切的聯(lián)系。每次她發(fā)來(lái)的編輯建議中,都會(huì)有那么幾個(gè)讓我汗顏?zhàn)载?zé)的錯(cuò)誤,甚至懷疑自己培養(yǎng)了十多年的職業(yè)素養(yǎng)是不是都拿來(lái)喂鄰居家的哈士奇了。萬(wàn)幸有陳編輯鼎力相助,才讓這本書(shū)在這么快的時(shí)間順利出版。陳編輯不但治學(xué)嚴(yán)謹(jǐn),而且十分耐心—編輯過(guò)程中,經(jīng)常是她剛剛編輯好一章,我就對(duì)原稿內(nèi)容做了補(bǔ)充或者修改,而陳編輯從來(lái)沒(méi)有怨言、馬上就做出相應(yīng)的調(diào)整,讓我十分感動(dòng)。讓我們一起為她點(diǎn)贊!另外,盡管本書(shū)中的代碼在我本機(jī)上都能順利運(yùn)行,但這并不意味著其中就100%沒(méi)有bug,而且,代碼中的bug也完全超出了編輯團(tuán)隊(duì)的知識(shí)范圍。所以,如果大家發(fā)現(xiàn)錯(cuò)誤—算我的,請(qǐng)不要責(zé)怪編輯團(tuán)隊(duì)。我一定會(huì)以最快的速度改正錯(cuò)誤。
我小的時(shí)候,家里經(jīng)濟(jì)條件不好,按理說(shuō)是沒(méi)有機(jī)會(huì)接觸到計(jì)算機(jī)并最終以計(jì)算機(jī)科學(xué)作為自己職業(yè)生涯的。所以,我一生都要感謝我的計(jì)算機(jī)啟蒙老師—?jiǎng)粤窒壬U撬米约业?86將我?guī)狭擞?jì)算機(jī)科學(xué)的道路,讓我認(rèn)識(shí)到了什么是DOS,什么是Windows,什么是編程。一轉(zhuǎn)眼我已經(jīng)成長(zhǎng)到了當(dāng)年劉叔叔教我計(jì)算機(jī)的年齡—我也將肩負(fù)起一個(gè)先行者的責(zé)任,將計(jì)算機(jī)科學(xué)技術(shù)普及給更多的新人,讓更多的新生代年輕人接觸到這個(gè)行業(yè)。
跟師父進(jìn)門(mén)后,我之所以能夠繼續(xù)在計(jì)算機(jī)科學(xué)領(lǐng)域扎根、發(fā)展,全靠志同道合的伙伴們引領(lǐng)和鼓勵(lì)。在這些伙伴中,對(duì)我影響比較深遠(yuǎn)的有這么幾位:劉揚(yáng)(初中摯友,劉叔叔的兒子)、張博(高中摯友,現(xiàn)在在上海從事法律與計(jì)算機(jī)科學(xué)結(jié)合的創(chuàng)新、創(chuàng)業(yè))、謝志威(大學(xué)摯友,現(xiàn)在是小學(xué)校長(zhǎng))、余峰(旅美后的職業(yè)發(fā)展榜樣,現(xiàn)就職于Google)。感謝生命中有你們的出現(xiàn)。
計(jì)算機(jī)科學(xué)行業(yè)是豐富多彩的。進(jìn)入行業(yè)后,我遇到了形形色色的人們,也有了些許起起伏伏的經(jīng)歷。感謝每一位曾經(jīng)與我有過(guò)交集的朋友,感謝每一分信任、每一次鼓勵(lì)、每一個(gè)挑戰(zhàn)……在你們身上,我發(fā)現(xiàn)了無(wú)窮無(wú)盡的優(yōu)點(diǎn),也從你們那里學(xué)到了很多之前不曾具備的能力。是你們,讓我從一個(gè)魯莽無(wú)知的少年,成為了一個(gè)穩(wěn)健前行的中年人。是你們,讓我認(rèn)識(shí)到“尊重真理,尊重人性”是一種多么珍貴的品質(zhì)。
一夜春風(fēng),萬(wàn)樹(shù)梨花
第00章 開(kāi)篇緒言
緣起 1
預(yù)備知識(shí) 3
第01章 思想與實(shí)現(xiàn)
思想 6
實(shí)現(xiàn) 8
準(zhǔn)備一棵樹(shù) 9
用遞推代碼實(shí)現(xiàn)遞推思想 11
用遞歸代碼實(shí)現(xiàn)遞推思想 13
用遞歸代碼實(shí)現(xiàn)遞歸思想 15
“好”的遞歸與“壞”的遞歸 16
用遞推代碼實(shí)現(xiàn)遞歸思想 20
思考題 23
第02章 回溯:上古神話(huà)中的算法
回溯式遞歸的基本原理 24
示例1 25
示例2 26
神話(huà)故事中的算法 27
迷宮設(shè)計(jì)入門(mén) 28
探尋迷宮中的路徑 29
用遞推(循環(huán))代碼實(shí)現(xiàn)回溯 32
思考題 33
第03章 動(dòng)態(tài)規(guī)劃:動(dòng)機(jī)決定性質(zhì)
什么是動(dòng)態(tài)規(guī)劃 35
透徹理解動(dòng)態(tài)規(guī)劃 36
遞推版動(dòng)態(tài)規(guī)劃 37
遞歸版動(dòng)態(tài)規(guī)劃 39
陷阱:這不是動(dòng)態(tài)規(guī)劃! 42
貪心也要?jiǎng)幽X子 43
更上層樓:讓規(guī)劃“動(dòng)態(tài)”起來(lái) 46
切年糕 46
接訂單 48
聽(tīng)講座 56
思考題 60
動(dòng)態(tài)規(guī)劃哲思 60
第04章 排序:算法皇冠上的明珠
游樂(lè)園:O(n^2)的簡(jiǎn)單排序們 63
選擇排序 63
冒泡排序 64
插入排序 66
以空間換時(shí)間:歸并排序 66
看運(yùn)氣的快速排序 68
兩全其美:堆排序 71
什么是“堆” 71
構(gòu)建大/小根堆 72
利用“大根堆”進(jìn)行原地排序 75
利用“小根堆”生成升序數(shù)組 75
思考題 76
第05章 查找:來(lái)而不往非禮也
二分查找 78
在已排序的數(shù)組上 79
在平衡二叉搜索樹(shù)上 80
線(xiàn)段樹(shù):化繁為簡(jiǎn) 81
構(gòu)建線(xiàn)段樹(shù) 82
查詢(xún)子段和 84
字典樹(shù):字母大接龍 86
遞推版實(shí)現(xiàn) 87
遞歸版實(shí)現(xiàn) 89
并查集:朋友的朋友是朋友 90
第06章 圖:包羅萬(wàn)象
圖的表達(dá) 94
鄰接列表 95
鄰接矩陣 97
應(yīng)對(duì)向、權(quán)、環(huán)的變化 98
思考題 100
圖的遍歷 100
廣度優(yōu)先遍歷 101
深度優(yōu)先遍歷 103
遞推版深度優(yōu)先遍歷 105
向、權(quán)、環(huán)對(duì)遍歷的影響 106
頂點(diǎn)的連通性 107
有無(wú)權(quán)重對(duì)連通性的影響 109
有無(wú)向?qū)B通性的影響 110
環(huán)對(duì)連通性的影響 113
強(qiáng)連通性組件 113
Kosaraju-Sharir算法 114
圖上的路徑 116
BFS式路徑搜尋 118
DFS式路徑搜尋 119
自底向上式路徑搜尋 119
回溯式路徑搜尋 121
獲取環(huán)路 122
思考題 123
最短路徑 124
Dijkstra最短路徑算法 125
Bellman-Ford最短路徑算法 129
Floyd-Warshall最短路徑算法 131
最小生成樹(shù) 133
構(gòu)建有權(quán)無(wú)向圖 134
Prim算法 136
Kruskal算法 137
最大流:超時(shí)空移花接木 138
余量邊,反向邊,余量網(wǎng)絡(luò),增益路徑 139
容量返還 140
Ford-Fulkerson算法實(shí)現(xiàn) 143
最小割:流量的瓶頸 145
拓?fù)渑判?147
生成入度圖與出度圖 148
理解頂點(diǎn)的入度 149
遞推實(shí)現(xiàn) 150
遞歸實(shí)現(xiàn) 151
思考題 152
后記

- 教材類(lèi)more>>
- 教輔培訓(xùn)more>>
- 生活經(jīng)管more>>
- 計(jì)算機(jī)基礎(chǔ)實(shí)訓(xùn)指導(dǎo)
- 用英語(yǔ)介紹中國(guó)經(jīng)典小故事
- 新概念英語(yǔ)單詞循環(huán)速記1:14天刻意練
- 新能源場(chǎng)站繼電保護(hù)傳動(dòng)作業(yè)指導(dǎo)書(shū)
- 高職院校“德技并修·三育協(xié)同”的育人
- 網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)師真題及模考卷精析(適用
- 涼山脫貧地區(qū)鄉(xiāng)村治理研究
- 中國(guó)—東盟競(jìng)技體育文化共同體研究
- 數(shù)值分析
- 用英語(yǔ)介紹中國(guó)(四六級(jí)版)
- 用英語(yǔ)介紹中國(guó)(第二版)
- 基于AI的Java技術(shù)項(xiàng)目實(shí)戰(zhàn)
- 信息處理技術(shù)員真題及模考卷精析(適用
- 系統(tǒng)集成項(xiàng)目管理工程師案例分析一本通
- 信息安全工程師考前沖刺100題(第二版
- 信息系統(tǒng)項(xiàng)目管理師考前沖刺100題(配