程序设计与算法(二)算法基础

本门课程要求学习者已经掌握C语言,以及基本的程序设计思想。本课程将讲述枚举、递归、分治、动态规划、搜索这几种算法。一部分内容,难度与中学信息学奥赛NOIP提高组的较难题,ACM国际大学生程序设计竞赛…

国家精品计算机
1639 次查看
北京大学
中国大学MOOC
  • 完成时间大约为 14
  • 初级
  • 中文
注:因开课平台的各种因素变化,以上开课日期仅供参考

课程概况

仅仅熟练掌握程序设计语言并不能成为好的程序员。对于许多问题,如果没有好的算法,计算机只能低效地解决,甚至无法解决。因此,好的程序员,还应该对程序的灵魂 — 算法有较好理解并能灵活应用。

本课程要讲授的就是枚举、二分、递归、分治、动态规划、搜索、贪心这七种基本的通用算法。各种复杂算法问题的解决,都可能用到这些基本的思想。

本门课程面向需要进一步提高编程和算法水平的学习者。要求学习者已经掌握C语言,以及基本的程序设计思想,如简单排序、简单的递归。

本课程中一部分的例题,难度与中学信息学奥赛NOIP提高组的较难题相当,也和ACM国际大学生程序设计竞赛中的中等题相当。掌握了本课程的内容,学员的算法水平和实现能力将超过国内大部分高校计算机专业本科毕业生。

具体的课程安排如下:

1)1周: 枚举

2)1周: 二分算法

3) 2周:递归

4) 1周:分治算法

5) 2周:动态规划 

6) 2周:深度优先搜索

7) 1周:广度优先搜索

8) 1周:贪心算法

9) 1周:期末考试

课程大纲

第一周 枚举
1. 例题:完美立方
2. 例题:生理周期
3. 例题:称硬币
4. 例题:熄灯问题(1)
5. 例题:熄灯问题(2)

第一周讲义
Openjudge在线做题必读

第一周测验

第二周 递归(一)
1. 例题1:求阶乘
2. 例题2:汉诺塔
3. 例题3: N皇后
4. 例题4:逆波兰表达式求值

第二周讲义

第二周测验

第三周 递归(二)
例题1: 表达式求值
例题2: 上台阶
例题3: 放苹果
例题4: 算24

第三周讲义

第三周测验

第四周 二分算法
1. 程序或算法的时间复杂度
2. 二分查找的原理和实现
3. 二分法求方程的根
4. 例题1 找 一对数
5. 例题2 农夫和奶牛

第四周讲义

第四周测验

第五周 分治
1. 归并排序
2. 快速排序
3. 输出前m大的数
4. 求排列的逆序数

第五周讲义

第五周测验

第六周 动态规划(一)
例题1. 数字三角形(1)
例题1. 数字三角形(2)
动态规划解题一般思路
例题2. 最长上升子序列
例题3. 最长公共子序列
例题4. 最佳加法表达式

第六周讲义

第六周测验

第七周 动态规划(二)
例题1. Help Jimmy
例题2. 滑雪
例题3. 神奇的口袋
例题4. 0-1背包问题
例题5. 分蛋糕

第七周讲义

第七周测验

第八周 深度优先搜索(一)
1. 在图上寻找路径和遍历(一)
2. 在图上寻找路径和遍历(二)
3. 图的表示方法:邻接矩阵和邻接表
4. 例题1. 城堡问题
5. 例题2. 踩方格

第八周讲义

第八周测验

第九周 深度优先搜索(二)
1. 例题1 寻路问题(一)
2. 例题1 寻路问题(二)
3. 例题2. 生日蛋糕

第九周讲义

第九周测验

第十周 广度优先搜索
例题1. 抓住这头牛
例题2. 迷宫问题
例题3. 八数码

第十周讲义

第十周测验

第十一周 贪心算法
1.例题: 圣诞老人的礼物
2.例题: 电影节
3.例题:分配畜栏
4.例题:放置雷达
5.例题:钓鱼

第十一周讲义

第十一周测验

第一周测验答案

第一周测验答案

第二周测验答案

第二周测验答案

第三周测验答案

第三周测验答案

第四周测验答案

第四周测验答案

第五周测验答案

第五周测验答案

第六周测验答案

第六周测验答案

第七周测验答案

第七周测验答案

第八周测验答案

第八周测验答案

第九周测验答案

第九周测验答案

第十周测验答案

第十周测验答案

第十一周测验答案

第十一周测验答案

预备知识

1. 熟练掌握C语言
2. 掌握基本的程序设计思想,如简单排序、简单的递归。

参考资料

高等教育出版社《算法基础与在线实践》,刘家瑛,郭炜,李文新 编著
此书和课程内容配套,课程中大部分例题在书中均有详解。

常见问题

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

千万首歌曲。全无广告干扰。
此外,您还能在所有设备上欣赏您的整个音乐资料库。免费畅听 3 个月,之后每月只需 ¥10.00。
Apple 广告
声明:MOOC中国十分重视知识产权问题,我们发布之课程均源自下列机构,版权均归其所有,本站仅作报道收录并尊重其著作权益。感谢他们对MOOC事业做出的贡献!
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc
  • (部分课程由Coursera、Udemy、Linkshare共同提供)

© 2008-2020 MOOC.CN 慕课改变你,你改变世界