算法是程序設(shè)計(jì)的靈魂,代表著用系統(tǒng)的方法描述解決問題的策略與機(jī)制。本書將介紹簡單模擬、枚舉、遞歸、二分、貪心、動(dòng)態(tài)規(guī)劃、深度優(yōu)先搜索和廣度優(yōu)先搜索等經(jīng)典算法,帶領(lǐng)讀者體會(huì)它們巧妙的構(gòu)思,感受利用它們解決問題的獨(dú)特魅力。本書不僅講解這些算法的基本原理思想,還通過具體例題對(duì)這些算法進(jìn)行靈活、有效的展開和準(zhǔn)確實(shí)現(xiàn)。本書中涉及的編程任務(wù)將充分訓(xùn)練讀者的思維能力和動(dòng)手能力,促成全面、縝密思考問題的習(xí)慣。
計(jì)算機(jī)學(xué)科是實(shí)踐性學(xué)科,通過編程解決實(shí)際工作生活中的問題是該學(xué)科的基礎(chǔ),也是訓(xùn)練計(jì)算機(jī)相關(guān)專業(yè)學(xué)生的基本技能。編寫優(yōu)雅的程序不僅是指熟練運(yùn)用程序設(shè)計(jì)語言,更是利用設(shè)計(jì)精巧的算法高效地解決實(shí)際問題。
使用計(jì)算機(jī)程序解決實(shí)際問題,首先要能夠?qū)⒁粋(gè)具體問題抽象成一個(gè)可計(jì)算的問題或模型,并設(shè)計(jì)出一套可行的計(jì)算過程。這個(gè)構(gòu)建計(jì)算的過程,其實(shí)對(duì)應(yīng)的就是算法設(shè)計(jì)。簡捷、高效的算法是計(jì)算機(jī)科學(xué)的核心和精髓。使用算法進(jìn)行問題求解的例子存在于生活中的方方面面,既可以簡單有效,例如最常見的學(xué)生成績信息管理系統(tǒng)、數(shù)字排序算法等;也可以非常復(fù)雜,例如Google公司旗下的DeepMind公司為AlaphG0程序研發(fā)的基于深度學(xué)習(xí)的人工智能算法等。
算法的本質(zhì)是取一組值作為輸入,經(jīng)過一系列計(jì)算步驟,產(chǎn)生符合要求的輸出結(jié)果。對(duì)于排序算法,輸入就是待排序的若干個(gè)數(shù),輸出就是排好序的數(shù)列。對(duì)于指紋比對(duì)算法,輸入就是兩個(gè)指紋的圖像數(shù)據(jù),輸出就是一個(gè)表示相似程度的數(shù)值。對(duì)于AlaphGo的算法,輸入就是一個(gè)棋局的描述(棋盤上所有棋子的位置),輸出就是一個(gè)坐標(biāo),即落子位置。實(shí)際上,算法所研究的不僅是如何得到正確的結(jié)果,更重要的是如何盡可能快速地得到正確的結(jié)果。試想如果AlaphGo下一步棋要計(jì)算一天,那李世石還會(huì)愿意與它比賽嗎?
算法設(shè)計(jì)又體現(xiàn)出一種計(jì)算思維的思想。編寫程序的目的是為了將算法思想變?yōu)橛?jì)算機(jī)能夠執(zhí)行的指令序列。算法運(yùn)用不好的程序員,很難說是一個(gè)好程序員。作為計(jì)算機(jī)專業(yè)人才,理應(yīng)具有一定的算法功底,并且應(yīng)該具備將算法準(zhǔn)確實(shí)現(xiàn)為程序的能力。因此本書特別強(qiáng)調(diào)編程實(shí)踐,通過具體的例題、樣例程序來講解算法設(shè)計(jì)的思路和具體實(shí)現(xiàn),并配有大量的課后習(xí)題以供練習(xí)。本書的作者均在北京大學(xué)信息科學(xué)技術(shù)學(xué)院多年講授計(jì)算機(jī)專業(yè)主干課程“程序設(shè)計(jì)實(shí)習(xí)”(通常為本科生第二學(xué)期必修課程),課程中長期積累、精挑細(xì)選的例題和習(xí)題構(gòu)成了本書的主要內(nèi)容。
本書從最簡單的算法入手,依次講述了模擬、枚舉、遞歸、二分查找、貪心算法、動(dòng)態(tài)規(guī)劃和搜索的基本思想,步步深入,系統(tǒng)地對(duì)基礎(chǔ)算法進(jìn)行全面的講述,并在各章節(jié)輔以大量例題對(duì)相關(guān)算法內(nèi)容進(jìn)行有效的補(bǔ)充和深入。通過全面的設(shè)計(jì)思路分析與詳細(xì)的程序設(shè)計(jì)描述展示,有效地促進(jìn)學(xué)生全面、細(xì)致地思考問題,提高編程的準(zhǔn)確性,增強(qiáng)程序查錯(cuò)、調(diào)試的能力。通過訓(xùn)練,學(xué)生能夠打下較為堅(jiān)實(shí)的程序設(shè)計(jì)基礎(chǔ),為進(jìn)一步學(xué)習(xí)其他計(jì)算機(jī)專業(yè)課程,或在其他專業(yè)領(lǐng)域運(yùn)用計(jì)算機(jī)編程解決問題創(chuàng)造良好的條件。
劉家瑛,博士,北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)研究所副教授。2010年6月畢業(yè)于北京大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè),獲理學(xué)博士學(xué)位。2007-2008年。赴美國南加州大學(xué)多媒體通信實(shí)驗(yàn)室任訪問學(xué)者。2015年.受鑄星計(jì)劃支持于微軟亞洲研究院擔(dān)任訪問研究員。研究領(lǐng)域包括圖像,視頻表示、壓縮與增強(qiáng)重建、計(jì)算機(jī)視覺與理解等。在國際重要期刊和會(huì)議上發(fā)表學(xué)術(shù)論文近80篇,申請(qǐng)國家發(fā)明專利40多項(xiàng)。其中13項(xiàng)已獲得授權(quán)。曾獲得“北京大學(xué)青年教師教學(xué)基本功比賽”一等獎(jiǎng)、教學(xué)信息化先進(jìn)個(gè)人、北京大學(xué)教學(xué)優(yōu)秀獎(jiǎng)。
郭煒,本科畢業(yè)于中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系,碩士畢業(yè)于北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系.現(xiàn)為北京大學(xué)信息科學(xué)技術(shù)學(xué)院教師。擔(dān)任北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽隊(duì)教練12年.從2008年至今,為ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲區(qū)賽站命題十余場(chǎng)。北京角斗士軟件技術(shù)有限公司創(chuàng)始人,開發(fā)《我愛背單詞》等多款成功的商業(yè)軟件。兼具豐富的教學(xué)經(jīng)驗(yàn)和軟件開發(fā)實(shí)踐經(jīng)驗(yàn)。
李文新,北京大學(xué)博士,香港理工大學(xué)博士.現(xiàn)任北京大學(xué)信息科學(xué)技術(shù)學(xué)院教授、副院長,北京大學(xué)計(jì)算機(jī)實(shí)驗(yàn)教學(xué)中心主任。中國計(jì)算機(jī)學(xué)會(huì)人工智能與模式識(shí)別專委會(huì)委員。主要研究領(lǐng)域?yàn)槿斯ぶ悄、生物特征識(shí)別技術(shù),是國際上*早從事自動(dòng)化掌紋識(shí)別的研究者之一。曾擔(dān)任信息學(xué)奧賽科學(xué)委員會(huì)副主席。北京市科協(xié)青少年科技教育協(xié)會(huì)副理事長、ACM/ICPC國際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲區(qū)教練及競(jìng)賽指導(dǎo)委員會(huì)委員、北京大學(xué)ACM競(jìng)賽代表隊(duì)領(lǐng)隊(duì)。為推動(dòng)ACM競(jìng)賽在北京大學(xué)、中國乃至亞洲的普及做了大量工作。2006年、2010年獲ACM/ICPC組織頒發(fā)的“區(qū)域發(fā)展杰出貢獻(xiàn)獎(jiǎng)”。2016年獲ACM/ICPC組織頒發(fā)的“亞洲領(lǐng)導(dǎo)力”獎(jiǎng)。由她組織為訓(xùn)練ACM隊(duì)員而開發(fā)的北京大學(xué)在線程序評(píng)測(cè)系統(tǒng)(http://openjudge.cn)目前已成為國際*有影響力的同類網(wǎng)站之一。
第1章 緒論
1.1 什么是算法
1.2 算法的時(shí)間復(fù)雜度
1.3 算法時(shí)間復(fù)雜度分析示例
1.4 PKU 0penJudge在線評(píng)測(cè)系統(tǒng)
1.5 本章小結(jié)
第2章 簡單計(jì)算與模擬
2.1 基本思想
2.2 例題:雞兔同籠(POJ 3237)
2.3 例題:校門外的樹(POJ 2808)
2.4 例題:裝箱問題(POJ 1017)
2.5 例題:約瑟夫問題(POJ 2746)
2.6 例題:顯示器(POJ 2745)
2.7 例題:排列(POJ 1833)
2.8 本章小結(jié)
2.9 練習(xí)題
習(xí)題2-1:與7無關(guān)的數(shù)(POJ 2701)
習(xí)題2-2:細(xì)菌繁殖(POJ 2712)
習(xí)題2-3:判斷閏年(POJ 2733)
習(xí)題2-4:求一兀二次方程的根(PoJ 2707)
習(xí)題2-5:合唱隊(duì)形(POJ 2711)
第3章 枚舉
3.1 基本思想
3.2 例題:假幣問題(POJ 2692)
3.3 例題:生理周期(POJ 4148)
3.4 例題:完美立方(POJ 2810)
3.5 例題:熄燈問題(POJ 2811)
3.6 例題:討厭的青蛙(POJ 2812)
3.7 本章小結(jié)
3.8 練習(xí)題
習(xí)題3-1:數(shù)字三元組(POJ 4146)
習(xí)題3-2:質(zhì)數(shù)的和與積(POJ 4138)
習(xí)題3-3:不定方程求解(POJ 4139)
習(xí)題3-4:砝碼稱重(POJ 4141)
習(xí)題3-5:垃圾炸彈(POJ 4133)
第4章 遞歸
4.1 基本思想
4.2 例題:漢諾塔問題
4.3 例題:小游戲(POJ 2802)
4.4 例題:棋盤分割(POJ 1191)
4.5 例題:八皇后問題(POJ 2754)
4.6 例題:文件結(jié)構(gòu)“圖”(POJ 2775)
4.7 例題:算24(POJ 2787)
4.8 例題:漢諾塔問題利用棧替代遞歸的解法
4.9 本章小結(jié)
4.10 練習(xí)題
習(xí)題4-1:斐波那契數(shù)列(POJ 2753)
習(xí)題4-2:求最大公約數(shù)問題(POJ 3248)
習(xí)題4-3:分解因數(shù)(POJ 2749)
習(xí)題4-4:逆波蘭表達(dá)式(POJ 2694)
習(xí)題4-5:括號(hào)匹配問題(POJ 3704)
第5章 二分查找
5.1 基本思想
5.2 例題:方程求解(POJ 4140)
5.3 例題:在線翻譯(POJ 2503)
5.4 例題:快速找到和為零的四個(gè)數(shù)(POJ 3441)
5.5 例題:瘋牛(POJ 2456)
5.6 例題:彎曲的木桿(POJ 1905)
5.7 例題:放棄考試(POJ 4145)
5.8 本章小結(jié)
5.9 練習(xí)題
習(xí)題5-1:查找最接近的元素(PoJ 4134)
習(xí)題5-2:二分法求函數(shù)的零點(diǎn)(POJ 4142)
習(xí)題5-3:和為給定數(shù)(POJ 4143)
習(xí)題5-4:月度開銷(POJ 4135)
習(xí)題5-5:矩形分割(PoJ 4136)
第6章 貪心算法
6.1 基本思想
6.2 例題:圣誕老人的禮物(POJ 4110)
6.3 例題:電池的壽命(POJ 3468)
6.4 例題:建立雷達(dá)(POJ 1328)
6.5 例題:田忌賽馬(POJ 2287)
6.6 例題:釣魚(POJ 1042)
6.7 例題:畜欄保留問題(POJ 4144)
6.8 本章小結(jié)
6.9 練習(xí)題
習(xí)題6-1:金銀島(POJ 2795)
習(xí)題6-2:最短前綴(POJ 2797)
習(xí)題6-3:書架(POJ 3406)
習(xí)題6-4:最小新整數(shù)(POJ 4137)
習(xí)題6-5:拼點(diǎn)游戲(POJ 4005)
第7章 動(dòng)態(tài)規(guī)劃
7.1 基本思想
7.2 動(dòng)態(tài)規(guī)劃解題的一般思路
7.3 例題:最長上升子序列(POJ 2533)
7.4 例題:最長公共子序列(POJ 1458)
7.5 例題:CIlarm Bracelet(POJ 4131)
7.6 例題:滑雪(POJ 1088)
7.7 例題:灌溉草場(chǎng)(POJ 2373)
7.8 例題:方盒游戲(POJ 1390)
7.9 例題:美妙柵欄(POJ 1037)
7.10 本章小結(jié)
7.11 練習(xí)題
習(xí)題7-1:簡單的整數(shù)劃分問題(POJ 4117)
習(xí)題7-2:開餐館(POJ 4118)
習(xí)題7-3:復(fù)雜的整數(shù)劃分問題(PoJ 4119)
習(xí)題7-4:硬幣(POJ 4120)
習(xí)題7-5:寵物小精靈之收服(POJ 4102)
習(xí)題7-6:股票買賣(POJ 4121)
習(xí)題7-7:切割回文(POJ 4122)
第8章 深度優(yōu)先搜索
8.1 基本思想
8.2 例題:城堡問題(POJ 2815)
8.3 例題:ROADS(POJ 1724)
8.4 例題:生日蛋糕(POJ 1190)
8.5 例題:sticks(POJ 1011)
8.6 本章小結(jié)
8.7 練習(xí)題
習(xí)題8-1:踩方格(POJ 4103)
習(xí)題8-2:棋盤問題(POJl321)
習(xí)題8-3:馬走日(POJ 4123)
習(xí)題8-4:海賊王之偉大航路(PoJ 4124)
習(xí)題8-5:DNA(POJ 4126)
第9章 廣度優(yōu)先搜索
9.1 基本思想
9.2 例題:Catch That cow(POJ 4001)
9.3 例題:拯救行動(dòng)(POJ 4116)
9.4 例題:鳴人和佐助(POJ 4115)
9.5 例題:八數(shù)碼(POJ 1077)
9.6 雙向廣度優(yōu)先搜索
9.7 本章小結(jié)
9.8 練習(xí)題
習(xí)題9-1:迷宮問題(POJ 4127)
習(xí)題9-2:單詞序列(POJ 4128)
習(xí)題9-3:變換的迷宮(POJ 4129)
習(xí)題9-4:Flip Game(POJ 1753)
習(xí)題9-5:SavingTang Monk(POJ 4130)
習(xí)題9-6:Jack and Jill(POJ 1729)