spContent=本门课程要求学习者已经掌握C语言,以及基本的程序设计思想。本课程将讲述枚举、递归、分治、动态规划、搜索这几种算法。一部分内容,难度与中学信息学奥赛NOIP提高组的较难题,ACM国际大学生程序设计竞赛中的中等题相当。学好本课程,算法及实现能力将超过国内大部分高校计算机专业本科毕业生。
本门课程要求学习者已经掌握C语言,以及基本的程序设计思想。本课程将讲述枚举、递归、分治、动态规划、搜索这几种算法。一部分内容,难度与中学信息学奥赛NOIP提高组的较难题,ACM国际大学生程序设计竞赛中的中等题相当。学好本课程,算法及实现能力将超过国内大部分高校计算机专业本科毕业生。
—— 课程团队
课程概述
仅仅熟练掌握程序设计语言并不能成为好的程序员。对于许多问题,如果没有好的算法,计算机只能低效地解决,甚至无法解决。因此,好的程序员,还应该对程序的灵魂 --- 算法有较好理解并能灵活应用。
本课程要讲授的就是枚举、二分、递归、分治、动态规划、搜索、贪心这七种基本的通用算法。各种复杂算法问题的解决,都可能用到这些基本的思想。
本门课程面向需要进一步提高编程和算法水平的学习者。要求学习者已经掌握C语言,以及基本的程序设计思想,如简单排序、简单的递归。
本课程中一部分的例题,难度与中学信息学奥赛NOIP提高组的较难题相当,也和ACM国际大学生程序设计竞赛中的中等题相当。掌握了本课程的内容,学员的算法水平和实现能力将超过国内大部分高校计算机专业本科毕业生。
本课程作业和考试网址:cxsjsxmooc.openjudge.cn
注意,不要写成 https://cxsjsxmooc.openjudge.cn/, 那样会访问不了!
如果访问不了,就注意浏览器地址栏里面是不是写了 https:// 不能有s!
郭炜老师还在中国大学MOOC开设另外三门好评如潮的4.9分高分课程,请不要错过:
1) 程序设计与算法(一)C语言程序设计(国家精品)
https://www.icourse163.org/course/PKU-1001553023
0基础学习者应该先学习这门课程
2) 程序设计与算法(三)C++面向对象程序设计(国家精品)
https://www.icourse163.org/course/PKU-1002029030
算法基础课中用到了一些面向对象的知识,不明白的可以先看看这门课
3) 实用Python程序设计 (强烈推荐,Python的百科书式大全课程,入门、提高均非常适合!)
https://www.icourse163.org/course/PKU-1460924165
授课目标
1. 通过本课程学习,有能力解决中学生信息学奥赛NOIP提高组的较难题,或ACM国际大学生程序设计竞赛中的中等题。
课程大纲
枚举算法
1.1. 枚举的基本思想
1.2. 例题:生理周期
1.3. 例题:称硬币
1.4 例题:熄灯问题(1)
1.5 例题:熄灯问题(2)
1.6 Openjudge在线做题必读
递归(一)
2.1 递归的基本思想
2.2 例题:汉诺塔
2.3 例题: N皇后
2.4 例题:逆波兰表达式求值
递归(二)
3.1 例题: 表达式求值
3.2 例题: 上台阶
3.3 例题: 放苹果
3.4 例题: 算24
二分算法
4.1 程序或算法的时间复杂度
4.2 二分查找的原理和实现
4.3 二分法求方程的根
4.4 例题1 找 一对数
4.5 例题2 农夫和奶牛
分治算法
5.1 分治的基本思想
5.2 快速排序
5.3 例题:输出前m大的数
5.4 例题:求排列的逆序数
动态规划(一)
6.1 动态规划的基本思想
6.2 例题: 数字三角形
6.3 动态规划解题一般思路
6.4 例题: 最长上升子序列
6.5 例题:最长公共子序列
6.6 例题:最佳加法表达式
动态规划(二)
7.1 例题 Help Jimmy
7.2 例题 滑雪
7.3 例题 神奇的口袋
7.4 例题 0-1背包问题
7.5 例题 分蛋糕
深度优先搜索(一)
8.1. 在图上寻找路径和遍历(一)
8.2. 在图上寻找路径和遍历(二)
8.3. 图的表示方法:邻接矩阵和邻接表
8.4. 例题1. 城堡问题
8.5. 例题2. 踩方格
深度优先搜索(二)
9.1. 剪枝的思想和例题1 寻路问题(一)
9.2. 例题1 寻路问题(二)
9.3. 例题2. 生日蛋糕
广度优先搜索
10.1 广度优先搜索的思想
10.2 例题 迷宫问题
10.3 例题 八数码问题
贪心算法
11.1. 贪心算法的基本思想
11.2.例题: 电影节
11.3.例题:分配畜栏
11.4.例题:放置雷达
11.5.例题:钓鱼
展开全部
预备知识
1. 熟练掌握C语言
2. 掌握基本的程序设计思想,如简单排序、简单的递归。
3. 有C++语言类和对象的概念,会用C++的 STL
参考资料
高等教育出版社《算法基础与在线实践》,刘家瑛,郭炜,李文新 编著
此书和课程内容配套,课程中大部分例题在书中均有详解。

常见问题
1.本课程的作业和考试形式是怎样的?
答:本课程的作业,以及最后的期末考试,形式都是在北京大学在线程序评测系统 openjudge.cn上提交程序,由系统自动评判正误。程序不能有丝毫错误。这种形式对于提高编程能力极其有效。