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