程序设计与算法(二)算法基础
分享
课程详情
课程评价
spContent=本门课程要求学习者已经掌握C语言,以及基本的程序设计思想。本课程将讲述枚举、递归、分治、动态规划、搜索这几种算法。一部分内容,难度与中学信息学奥赛NOIP提高组的较难题,ACM国际大学生程序设计竞赛中的中等题相当。学好本课程,算法及实现能力将超过国内大部分高校计算机专业本科毕业生。
—— 课程团队
课程概述

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

 

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

 

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

 

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

 




具体的课程安排如下:

1)1周: 枚举

2)1周: 二分算法

3) 2周:递归

4) 1周:分治算法

5) 2周:动态规划 

6) 2周:深度优先搜索

7) 1周:广度优先搜索

8) 1周:贪心算法

9) 1周:期末考试




授课目标

1. 通过本课程学习,有能力解决中学生信息学奥赛NOIP提高组的较难题,或ACM国际大学生程序设计竞赛中的中等题。

课程大纲

第一周 枚举

Openjudge在线做题必读

1. 例题:完美立方

2. 例题:生理周期

3. 例题:称硬币

4. 例题:熄灯问题(1)

5. 例题:熄灯问题(2)

第二周 递归(一)

1. 例题1:求阶乘

2. 例题2:汉诺塔

3. 例题3: N皇后

4. 例题4:逆波兰表达式求值

第三周 递归(二)

例题1: 表达式求值

例题2: 上台阶

例题3: 放苹果

例题4: 算24

第四周 二分算法

1. 程序或算法的时间复杂度

2. 二分查找的原理和实现

4. 例题1 找 一对数

5. 例题2 农夫和奶牛

3. 二分法求方程的根

第五周 分治

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. 掌握基本的程序设计思想,如简单排序、简单的递归。



证书要求

完成作业和考试,达到要求后,可以获得课程主讲教师签名颁发的合格证书或优秀证书。总成绩算法如下:

考核

成绩

每周测验(即作业)

70/100

期末考试

30/100




60-84分:合格证书
85-100分:优秀证书


参考资料

高等教育出版社《算法基础与在线实践》,刘家瑛,郭炜,李文新 编著

此书和课程内容配套,课程中大部分例题在书中均有详解。

常见问题

1.本课程的作业和考试形式是怎样的?

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



北京大学
授课老师
郭炜

郭炜

讲师