內容簡介
算法是程序設計的靈魂,代錶著用係統的方法描述解決問題的策略與機製。《算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材》將介紹簡單模擬、枚舉、遞歸、二分、貪心、動態規劃和搜索等經典算法,帶領讀者體會它們巧妙的構思,感受利用它們解決問題的獨特魅力。《算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材》不僅講解這些算法的基本原理思想,還通過具體例題對這些算法進行靈活、有效的展開和準確實現。《算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材》中涉及的編程任務將充分訓練讀者的思維能力和動手能力,促成全麵、縝密思考問題的習慣。
《算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材》可作為高等學校計算機等相關專業算法設計類課程的教材,也可供對算法設計、程序設計競賽感興趣的讀者自學使用。
作者簡介
劉傢瑛,博士,北京大學計算機科學技術研究所副教授。2010年6月畢業於北京大學計算機應用技術專業,獲理學博士學位。2007-2008年。赴美國南加州大學多媒體通信實驗室任訪問學者。2015年.受鑄星計劃支持於微軟亞洲研究院擔任訪問研究員。研究領域包括圖像,視頻錶示、壓縮與增強重建、計算機視覺與理解等。在國際重要期刊和會議上發錶學術論文近80篇,申請國傢發明專利40多項。其中13項已獲得授權。曾獲得“北京大學青年教師教學基本功比賽”一等奬、教學信息化先進個人、北京大學教學優秀奬。
郭煒,本科畢業於中國科學技術大學計算機係,碩士畢業於北京大學計算機科學技術係.現為北京大學信息科學技術學院教師。擔任北京大學ACM國際大學生程序設計競賽隊教練12年.從2008年至今,為ACM國際大學生程序設計競賽亞洲區賽站命題十餘場。北京角鬥士軟件技術有限公司創始人,開發《我愛背單詞》等多款成功的商業軟件。兼具豐富的教學經驗和軟件開發實踐經驗。
李文新,北京大學博士,香港理工大學博士.現任北京大學信息科學技術學院教授、副院長,北京大學計算機實驗教學中心主任。中國計算機學會人工智能與模式識彆專委會委員。主要研究領域為人工智能、生物特徵識彆技術,是國際上*早從事自動化掌紋識彆的研究者之一。曾擔任信息學奧賽科學委員會副主席。北京市科協青少年科技教育協會副理事長、ACM/ICPC國際大學生程序設計競賽亞洲區教練及競賽指導委員會委員、北京大學ACM競賽代錶隊領隊。為推動ACM競賽在北京大學、中國乃至亞洲的普及做瞭大量工作。2006年、2010年獲ACM/ICPC組織頒發的“區域發展傑齣貢獻奬”。2016年獲ACM/ICPC組織頒發的“亞洲領導力”奬。由她組織為訓練ACM隊員而開發的北京大學在綫程序評測係統(http://openjudge.cn)目前已成為國際*有影響力的同類網站之一。
內頁插圖
目錄
第1章 緒論
1.1 什麼是算法
1.2 算法的時間復雜度
1.3 算法時間復雜度分析示例
1.4 PKU 0penJudge在綫評測係統
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無關的數(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:數字三元組(POJ 4146)
習題3-2:質數的和與積(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:斐波那契數列(POJ 2753)
習題4-2:求最大公約數問題(POJ 3248)
習題4-3:分解因數(POJ 2749)
習題4-4:逆波蘭錶達式(POJ 2694)
習題4-5:括號匹配問題(POJ 3704)
第5章 二分查找
5.1 基本思想
5.2 例題:方程求解(POJ 4140)
5.3 例題:在綫翻譯(POJ 2503)
5.4 例題:快速找到和為零的四個數(POJ 3441)
5.5 例題:瘋牛(POJ 2456)
5.6 例題:彎麯的木杆(POJ 1905)
5.7 例題:放棄考試(POJ 4145)
5.8 本章小結
5.9 練習題
習題5-1:查找最接近的元素(PoJ 4134)
習題5-2:二分法求函數的零點(POJ 4142)
習題5-3:和為給定數(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:最小新整數(POJ 4137)
習題6-5:拼點遊戲(POJ 4005)
第7章 動態規劃
7.1 基本思想
7.2 動態規劃解題的一般思路
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:簡單的整數劃分問題(POJ 4117)
習題7-2:開餐館(POJ 4118)
習題7-3:復雜的整數劃分問題(PoJ 4119)
習題7-4:硬幣(POJ 4120)
習題7-5:寵物小精靈之收服(POJ 4102)
習題7-6:股票買賣(POJ 4121)
習題7-7:切割迴文(POJ 4122)
第8章 深度優先搜索
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章 廣度優先搜索
9.1 基本思想
9.2 例題:Catch That cow(POJ 4001)
9.3 例題:拯救行動(POJ 4116)
9.4 例題:鳴人和佐助(POJ 4115)
9.5 例題:八數碼(POJ 1077)
9.6 雙嚮廣度優先搜索
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)
前言/序言
計算機學科是實踐性學科,通過編程解決實際工作生活中的問題是該學科的基礎,也是訓練計算機相關專業學生的基本技能。編寫優雅的程序不僅是指熟練運用程序設計語言,更是利用設計精巧的算法高效地解決實際問題。
使用計算機程序解決實際問題,首先要能夠將一個具體問題抽象成一個可計算的問題或模型,並設計齣一套可行的計算過程。這個構建計算的過程,其實對應的就是算法設計。簡捷、高效的算法是計算機科學的核心和精髓。使用算法進行問題求解的例子存在於生活中的方方麵麵,既可以簡單有效,例如最常見的學生成績信息管理係統、數字排序算法等;也可以非常復雜,例如Google公司旗下的DeepMind公司為AlaphG0程序研發的基於深度學習的人工智能算法等。
算法的本質是取一組值作為輸入,經過一係列計算步驟,産生符閤要求的輸齣結果。對於排序算法,輸入就是待排序的若乾個數,輸齣就是排好序的數列。對於指紋比對算法,輸入就是兩個指紋的圖像數據,輸齣就是一個錶示相似程度的數值。對於AlaphGo的算法,輸入就是一個棋局的描述(棋盤上所有棋子的位置),輸齣就是一個坐標,即落子位置。實際上,算法所研究的不僅是如何得到正確的結果,更重要的是如何盡可能快速地得到正確的結果。試想如果AlaphGo下一步棋要計算一天,那李世石還會願意與它比賽嗎?
算法設計又體現齣一種計算思維的思想。編寫程序的目的是為瞭將算法思想變為計算機能夠執行的指令序列。算法運用不好的程序員,很難說是一個好程序員。作為計算機專業人纔,理應具有一定的算法功底,並且應該具備將算法準確實現為程序的能力。因此本書特彆強調編程實踐,通過具體的例題、樣例程序來講解算法設計的思路和具體實現,並配有大量的課後習題以供練習。本書的作者均在北京大學信息科學技術學院多年講授計算機專業主乾課程“程序設計實習”(通常為本科生第二學期必修課程),課程中長期積纍、精挑細選的例題和習題構成瞭本書的主要內容。
本書從最簡單的算法入手,依次講述瞭模擬、枚舉、遞歸、二分查找、貪心算法、動態規劃和搜索的基本思想,步步深入,係統地對基礎算法進行全麵的講述,並在各章節輔以大量例題對相關算法內容進行有效的補充和深入。通過全麵的設計思路分析與詳細的程序設計描述展示,有效地促進學生全麵、細緻地思考問題,提高編程的準確性,增強程序查錯、調試的能力。通過訓練,學生能夠打下較為堅實的程序設計基礎,為進一步學習其他計算機專業課程,或在其他專業領域運用計算機編程解決問題創造良好的條件。
算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材 [Fundamentals of Programming and Algorithms] epub pdf mobi txt 電子書 下載 2024
算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材 [Fundamentals of Programming and Algorithms] 下載 epub mobi pdf txt 電子書
算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材 [Fundamentals of Programming and Algorithms] mobi pdf epub txt 電子書 下載 2024
算法基礎與在綫實踐/北京大學“程序設計與算法”專項課程係列教材 [Fundamentals of Programming and Algorithms] epub pdf mobi txt 電子書 下載 2024