程式設計與算法（二）算法基礎

程式設計與算法（二）算法基礎課程是北京大學建設的慕課、國家精品線上開放課程。該課程於2017年01月23日首次在中國大學MOOC開課。該課程老師是郭煒。據2021年7月中國大學MOOC官網顯示，該課程已開課12次。

該課程共十一章，包括枚舉算法、遞歸、二分算法、分治算法、動態規劃、深度優先搜尋、廣度優先搜尋、貪心算法的內容。

基本介紹

• 中文名：程式設計與算法（二）算法基礎
• 建設院校：北京大學
• 開課時間：2017年01月23日
• 授課老師：郭煒
• 類別：慕課、國家精品線上開放課程
• 授課平台：中國大學MOOC

課程大綱

第一課時 枚舉算法	6.3 動態規劃解題一般思路
1.1. 枚舉的基本思想	6.4 例題： 最長上升子序列
1.2. 例題：生理周期	6.5 例題：最長公共子序列
1.3. 例題：稱硬幣	6.6 例題：最佳加法表達式
1.4 例題：熄燈問題(1)	第七課時 動態規劃（二）
1.5 例題：熄燈問題(2)	7.1 例題 Help Jimmy
1.6 Openjudge線上做題必讀	7.2 例題 滑雪
第二課時 遞歸（一）	7.3 例題 神奇的口袋
2.1 遞歸的基本思想	7.4 例題 0-1背包問題
2.2 例題：漢諾塔	7.5 例題 分蛋糕
2.3 例題： N皇后	第八課時 深度優先搜尋（一）
2.4 例題：逆波蘭表達式求值	8.1. 在圖上尋找路徑和遍歷（一）
第三課時 遞歸（二）	8.2. 在圖上尋找路徑和遍歷（二）
3.1 例題: 表達式求值	8.3. 圖的表示方法：鄰接矩陣和鄰接表
3.2 例題: 上台階	8.4. 例題1. 城堡問題
3.3 例題: 放蘋果	8.5. 例題2. 踩方格
3.4 例題: 算24	第九課時 深度優先搜尋（二）
第四課時 二分算法	9.1. 剪枝的思想和例題1 尋路問題（一）
4.1 程式或算法的時間複雜度	9.2. 例題1 尋路問題（二）
4.2 二分查找的原理和實現	9.3. 例題2. 生日蛋糕
4.3 二分法求方程的根	第十課時 廣度優先搜尋
4.4 例題1 找 一對數	10.1 廣度優先搜尋的思想
4.5 例題2 農夫和奶牛	10.2 例題 迷宮問題
第五課時 分治算法	10.3 例題 八數碼問題
5.1 分治的基本思想	第十一課時 貪心算法
5.2 快速排序	11.1. 貪心算法的基本思想
5.3 例題：輸出前m大的數	11.2.例題: 電影節
5.4 例題：求排列的逆序數	11.3.例題：分配畜欄
第六課時 動態規劃（一）	11.4.例題：放置雷達
6.1 動態規劃的基本思想	11.5.例題：釣魚
6.2 例題： 數字三角形

（註：課程大綱排版從左到右列）

zhua曲子白渡白顆

開課信息

開課次數	開課時間	學時安排	授課教師	參與人數
第1次開課	2017年01月23日~2017年04月10日	4~5小時每周	郭煒	23911
第2次開課	2017年07月10日~2017年10月12日	3~5小時每周		20831
第3次開課	2017年11月13日~2018年02月12日	4~5小時每周		22182
第4次開課	2018年03月19日~2018年06月17日	3~5小時每周		11893
第5次開課	2018年09月03日~2018年12月03日			19567
第6次開課	2019年02月18日~2019年05月20日			11093
第7次開課	2019年07月08日~2019年10月13日			15553
第8次開課	2019年11月11日~2020年02月03日			19785
第9次開課	2020年02月17日~2020年08月24日			16262
第10次開課	2020年09月21日~2020年12月30日			9142
第11次開課	2021年03月01日~2021年06月14日			9045
第12次開課	2021年07月05日~2021年09月05日			待定
表格內容參考資料

教學目標

通過該課程學習，有能力解決中學生信息學奧賽NOIP提高組的較難題，或ACM國際大學生程式設計競賽中的中等題。

學習預備

• 預備知識

1. 熟練掌握C語言；
2. 掌握基本的程式設計思想，如簡單排序、簡單的遞歸。

• 學習資料

書名	作者	出版時間	ISBN	出版社
《算法基礎與線上實踐》	劉家瑛、郭煒、李文新	2017年-3月-30日	9787040473001	高等教育出版社

考核標準

每周測驗（即作業）占70%；考試占30%；總分60~84為合格，85~100為優秀。

教師簡介

郭煒，男，北京大學信息學院講師。