ACM 程序设计（一） 主讲：朱佳 博士 华南师范大学计算机学院.

Presentation on theme: "ACM 程序设计（一） 主讲：朱佳 博士 华南师范大学计算机学院."— Presentation transcript:

1 ACM 程序设计（一） 主讲：朱佳 博士 华南师范大学计算机学院

2 课程概要(Course Outline) 讲师介绍 (About Me) 课程目的 (Course Purpose)
课程要求 (Course Requirement) 时间安排 (Schedule) 华南师范大学计算机学院 朱佳博士 9/04/2019

3 讲师介绍(About Me) Name: 朱佳 Education: University of Queensland
Research: DM/ML/AI, SCI/EI: 100+ Contact: Subject:ACM程序设计一:学号:名字 10+ industry work experience，  画图， 和决策有关系的都叫AI， ML 是数据分析技术 华南师范大学计算机学院 朱佳博士 9/04/2019

4 University of Queensland
10+ industry work experience， 图 华南师范大学计算机学院 朱佳博士 9/04/2019

5 University of Queensland
Jacarandas 蓝花 华南师范大学计算机学院 朱佳博士 9/04/2019

6 课程概要(Course Outline) 讲师介绍 (About Me) 课程目的 (Course Purpose)
课程要求 (Course Requirement) 时间安排 (Schedule) 华南师范大学计算机学院 朱佳博士 9/04/2019

7 课程目的(Course Purpose) 本课程是讲解的内容是 ACM 竞赛的基本知识，主 要包括基本数据结构、图论算法、搜索算法、动态 规划算法、排序算法、贪心算法等知识的应用，并 能利用程序设计语言进行 ACM 竞赛题目的设计与 编写。 华南师范大学计算机学院 朱佳博士 9/04/2019

8 课程概要(Course Outline) 讲师介绍 (About Me) 课程目的 (Course Purpose)
课程要求 (Course Requirement) 时间安排 (Schedule) 华南师范大学计算机学院 朱佳博士 9/04/2019

9 课程要求(Course Requirement)
平时/实验-- 30% Final Exam(期末考试，闭卷) -- 70% Pass Line Overall >= 60% and Final Exam >= 60% Course Homepage(课程主页): 展示主页 华南师范大学计算机学院 朱佳博士 9/04/2019

10 课程概要(Course Outline) 讲师介绍 (About Me) 课程目的 (Course Purpose)
课程要求 (Course Requirement) 时间安排 (Schedule) 华南师范大学计算机学院 朱佳博士 9/04/2019

11 时间安排(Schedule) 每双周周二上午三四节实验课，地点学院530 第16周总结 华南师范大学计算机学院 朱佳博士 9/04/2019
1-18 weeks 华南师范大学计算机学院 朱佳博士 9/04/2019

12 ACM/ICPC介绍 全称

13 ACM-ICPC是什么? ACM/ICPC（国际大学生程序设计竞赛)是由国际计算 机界历史悠久、颇具权威性的组织ACM主办的，世界上公 认的规模最大、水平最高的国际大学生程序设计竞赛。 其宗旨是提供一个让大学生向IT界展示自己分析问 题和解决问题的能力的绝好机会，让下一代IT天才可以 接触到其今后工作中将要用到的各种软件。 ACM国际大学生程序设计竞赛（英文全称：ACM International Collegiate Programming Contest)

14 ACM的历史及其影响 ACM/ICPC从1970年开始举办，其目的旨在使大学生运 用计算机来充分展示自己分析问题和解决问题的能力。该 竞赛一直受到国际各知名大学的重视，并受到全世界各著 名计算机公司的高度关注。可以说，ACM国际大学生程序设 计竞赛已成为世界各国大学生最具影响力的国际级计算机 类的赛事。

15 ACM在中国 中国大陆高校从1996年开始参加ACM国际大学生 程序设计竞赛亚洲预赛。 前六届中国赛区设在上海，由上海大学承办；
2002年由清华大学和西安交通大学承办； 2003年由清华大学和中山大学承办。 2004年由北京大学和上海交通大学承办。 2005年由四川大学、北大和浙大承办。 2006年由上海大学、清华和西电承办。 2007年由北航、南航、吉大、西华

16 比赛 比赛形式 试题 时间：持续5个小时 三人一组 1支队伍1台机器（提供打印服务） 上机编程解决问题（可带纸质资料） 实时测试，动态排名
10题左右 全英文（可以带字典） 时间：持续5个小时

17 如何比赛 可以携带诸如书、手册、 程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具；
可能收到的反馈信息包括： Compile Error -- 程序不能通过编译。 Run Time Error -- 程序运行过程中出现非正常中断。 Time Limit Exceeded -- 运行超过时限还没有得到输出结果。 Wrong Answer -- 答案错误。 Presentation Error-- 输出格式不对，可检查空格、回车等等细节。 Accepted -- 恭喜恭喜！

18 如何排名？ 首先根据解题数目进行排名。 如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。
总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。 每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。

19

20 ACM-ICPC能给你带来什么 去外地参赛、甚至出境去新加坡、韩国、日本参赛的机 会
获奖，更够为你带来非常多的荣誉（奖励学分、奖学 金），简历上增添光彩的一笔，更接近国外名校。 但参加这个竞赛，不是为了去外地比赛玩的，也不是单 单为了拿个奖

21 参加ACM-ICPC的意义 ACM-ICPC的竞赛题目，很少有固定的模式、公式套用， 需要有极好洞察力，综合运用所学知识解决。
能够极好的培养我们的学习、实践、思维能力，这是 顶尖技术人才区别与一般程序员的地方。

22 参加ACM-ICPC的意义 ACM-ICPC竞赛是组队参赛的模式，要求队员之间有很 好的配合、协作才能取得好的成绩。我们的培训，也会给 同学们创造良好的交流环境，这样才能取长补短，共同提 高互相促进。 通过竞赛，你也能结识到全国顶尖的计算机高手。

23 参加ACM-ICPC的意义 在ACM-ICPC竞赛中取得较好成绩的队伍人员，一直是各 大软件公司如Microsoft、Google、SUN、IBM公司竞相 聘请的对象。 关于ACM-ICPC的培训给同学们带来的能力、素质上的提 升，也将成为同学们今后踏入IT行业最有力的竞争优势。

24 参加ACM-ICPC的意义 吉林省一等奖，免挂本学期三门课；吉林省二等奖，免挂本学期两门课；吉林省三等奖，免挂本学期一门课
国家奖学金参评加分 德育分加分 课外活动分加分 优先考虑入党

25 ACM队队员的基本原则 数学 基本要求 能力要求 愿意花时间在这项赛事上 有团队合作精神 练习、练习、再练习 程序设计语言 英语科技文献阅读
数据结构与算法 数学

26 数据结构与算法 数据结构 掌握队列、堆栈、树、图的基本表达与操作 （保证时间复杂度低，可以以空间换时间”的 原则策略） 算法：
算法中最基本和常用的是搜索，主要是回溯和 分支限界法的使用。 常用算法中的另一类是以“相似或相同子问题” 为核心的，包括递推、递归、贪心法和动态规 划。 算法分析

27 题型划分

28 分治 欢迎辞

29 算法总体思想 T(n) n = T(n/m) T(n/m) T(n/m) T(n/m)
对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 将要求解的较大规模的问题分割成k个更小规模的子问 题。 T(n) = n T(n/m) T(n/m) T(n/m) T(n/m)  

30 算法总体思想 T(n) n = n/m n/m n/m n/m
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 T(n) = n n/m T(n/m2) n/m T(n/m2) n/m T(n/m2)   n/m T(n/m2)

31 算法总体思想 T(n) n = n/m n/m n/m n/m
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 T(n) = n n/m T(n/m2) n/m T(n/m2) n/m T(n/m2)   n/m T(n/m2)

32 算法总体思想 T(n) n = 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。

33 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具 有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间 不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。 能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。 这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用

34 分治法的基本步骤 divide-and-conquer(P) {
if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 } 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

35 二分搜索技术 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。 分析：
该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。 分析：比较x和a的中间元素a[mid]，若x=a[mid]，则x在L中的位置就是mid；如果x<a[mid]，由于a是递增排序的，因此假如x在a中的话，x必然排在a[mid]的前面，所以我们只要在a[mid]的前面查找x即可；如果x>a[i]，同理我们只要在a[mid]的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件 分析：很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。

36 二分搜索技术 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。 据此容易设计出二分搜索算法：
template<class Type> int BinarySearch(Type a[], const Type& x, int l, int r) { while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; 算法复杂度分析： 每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。 interview

37 分治法求数组最大值 给定n个元素a[0:n-1]，现要在这n个元素中找出最大值x。 思路： 将数组一分为二
求前半部分的最大值位置，求后半部分最大值位置（分的过程） 求前后两部分最大值位置。（合的过程）

38 T(n)=O(nlogn) 渐进意义下的最优算法
合并排序 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 复杂度分析 T(n)=O(nlogn) 渐进意义下的最优算法 void MergeSort(Type a[], int left, int right) { if (left<right) {//至少有2个元素 int i=(left+right)/2; //取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a }

39 合并排序 算法mergeSort的递归过程可以消去。 [49] [38] [65] [97] [76] [13] [27]
初始序列 [49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] 第一步 第二步 [ ] [ ] 第三步 [ ]

40 合并排序 最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n)

41 棋盘覆盖 在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 题目分析，比如4*4，tips：从小样例分析，如上面这个阳历其实补充5个L型就可以满足 分治+递归

42 棋盘覆盖 当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

43 棋盘的识别 首先，子棋盘的规模是一个必要的信息，有了 这个信息，只要知道左上角的方格在原棋盘中的 行、列号就可以标识这个子棋盘了；其次子棋盘 中残缺方格或“伪”残缺方格直接用它们在原棋 盘中的行、列号标识。 ①tr表示棋盘左上角方格的行号； ②tc表示棋盘 左上角方格的列号 ③dr表示特殊方格所在的行号 ④dc表示特殊方格所在的列号， ⑤size表示方形 棋盘行数或列数。 1），2），3），4）符号说明

44 棋盘数据结构 用二维数组Board[][]来模拟棋盘，Board[1][1]是棋盘的左上角方格。title 表示L 型骨牌的编号，其初始值为0。覆盖残缺棋盘所需要的三格板数 目为：(size*size -1)/3。将这些 三格板编号为1到(size*size-1)/3，则将覆 盖残缺棋盘的三格板编号存储在数组Board的对应位置，这样输出数组 内容就是问题的解。如果是一个4 ×4的棋盘，特殊方格为(2,1)，那么 程序的输出为对于如图左所示的棋盘，其结果为图右所示的棋盘。其 中特殊方格为0，相同数字的为同一骨牌。

45 棋盘覆盖 复杂度分析 T(n)=O(4k) 渐进意义下的最优算法
void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) chessBoard(tr, tc+s, dr, dc, s); // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) chessBoard(tr+s, tc+s, dr, dc, s); else {// 用 t 号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; chessBoard(tr+s, tc+s, tr+s, tc+s, s);} } 复杂度分析 T(n)=O(4k) 渐进意义下的最优算法

46 循环赛日程表 设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次；
按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。 1 2 3 4 5 6 7 8 约束条件(1)(2)(3)

47 本题方法有很多，递归是其中一种比较容易理解的方法。 下图所示是k=8时的一个可行解，它是4块拼起来的。左 上角是k=4时的一组解，左下角是左上角每个数加4得到， 而右上角、右下角分别由左下角、左上角复制得到的。 1 2 3 4 5 6 7 8 K递归次数

48 #include <iostream>
using namespace std; int table[100][100]; void Creattable(int r1,int c1,int r2,int c2,int size){ int i,j; int halfsize=size/2; if(size>1) //递归创建左上角的赛程表 Creattable(0,0,halfsize,halfsize,halfsize); else table[0][0]=1;

49 for(i=0;i<size;i++)
for(j=0;j<size;j++) { //右上角的赛程是左上角的赛程加上halfsize if(i<halfsize && (j>=halfsize && j<size)) //左下角的赛程和右上角的赛程相同 table[i][j]=table[i][j-halfsize]+halfsize; if((i>=halfsize && i<size) && j<halfsize) //右下角的赛程和左上角的赛程相同 table[i][j]=table[i-halfsize][j+halfsize]; if((i>=halfsize && i<size) && (j>=halfsize && j<size)) table[i][j]=table[i-halfsize][j-halfsize]; }