《ACM基础算法入门教程课件》由会员分享,可在线阅读,更多相关《ACM基础算法入门教程课件(32页珍藏版)》请在金锄头文库上搜索。
1、ACM基础算法入门.基础动态规划.基础的“穷竭搜索”.贪心的三种区间问题.数论那些事.二分的另类法 引言n算法简单但思想及其重要n介绍的算法都堪称为经典中的经典基础动态规划n多阶段决策过程最优化的数学方法三要素:-阶段-决策-状态动态规划的适用范围n最优子结构(最优化原理)当前状态依赖于前面的状态得到,是前面状态的完美总结n无后效性(不成环)经典模型n数塔模型n背包问题n区间最大和模型n最长非降子序列模型n最长公共子序列n数字归并(区间dp)n旅行商问题(状态压缩)n求解从顶到下经过节点的最大值是多少解题思路n列状态 v I j 表示走到第i层的第j个节点的最大值n分阶段 每一个层就是一个阶段
2、n状态转移方程(决策)V i-1 j += V I j v I j + 1 ? V I j : v I j + 1 ;单调递增非降子序列n给定一整型数列a1,a2.,an(0n=100000),找出单调递增最长子序列,并求出其长度。n如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。解题思路n定义状态dp【i】以i为结束节点最长单调子序列长度n阶段每一个点选择过程即阶段转移方程:Dp【i】= max(dp【1(i-1)】) + 1想想有没有更好的方法?dp总结n模型匹配法n三要素法 先确定阶段(数塔问题)先确定状态(一般题目都是)先确定决策(背包问题
3、)贪心的三种区间问题n选择不相交区间n区间选点n区间覆盖选择不相交区间n 数轴上有数轴上有n个开区间(个开区间(ai,bi),选择尽量多个区间,),选择尽量多个区间,n使得这些区间两两没有公共点。使得这些区间两两没有公共点。【分析】 首先明确一个问题:假设有两个区间x,y,区间x完全包含y。那么,选x是不划算的,因为x和y最多只能选一个,选x不如选y,这样不仅区间数目不会减少,而且给其他区间留出了更多的位置。接下来,按照bi从小到大的顺序对所有区间排序。会场安排问题n 先对n个区间按照bi从小到大的顺序排序,如果nbi相同,则ai按照从大到小的顺序排序。然后从前往后n扫描每个区间,找出所有的符
4、合条件的区间。n 注意:排序后第一个区间一定会选,因为它的注意:排序后第一个区间一定会选,因为它的bi最小,最小,n它不影响后面区间的选取,而且如果不选此区间,最它不影响后面区间的选取,而且如果不选此区间,最终终n求出的区间数目会变少。求出的区间数目会变少。区间选点问题n 数轴上有数轴上有n个闭区间个闭区间ai, bi。取尽量少的点,使得每个。取尽量少的点,使得每个n区间内都至少有一个点(不同区间内含的点可以是同一个)。区间内都至少有一个点(不同区间内含的点可以是同一个)。【分析】 如果区间i内已经有一个点被取到,我们称此区间已经被满足。受上一题的启发,我们先讨论区间包含的情况。由于小区间被满
5、足时大区间一定也被满足。所以在区间包含的情况下,大区间不需要考虑。 因此,我们把所有区间按b从小到大排序(b相同时a从大到小排序),则如果出现区间包含的情况,小区间一定排在前面。第一个区间应该选取哪一个点呢?正确的贪心策略是:取最后一个点。如下图。解题思路n根据刚才的讨论,所有需要考虑的区间的a也是递增的,n我们把它画成上图的形式。如果第一个区间不选最后一个点,n而是去中间的,如灰色点,那么把它移动到最后一个点后,n被满足的区间增加了,而且原先被满足的区间现在一定被满n足。这样才能保证选取的点最少。区间覆盖问题n 数轴上有数轴上有n个闭区间个闭区间ai, bi,选择尽量少的区间覆盖,选择尽量少
6、的区间覆盖n一条指定线段一条指定线段s, t。【分析】 本题的突破口仍然是区间包含和排序扫描,不过要先进行一次预处理。每个区间在s,t外的部分都应该预先被切掉,因为它们的存在是毫无意义的。例如要覆盖线段3,5,闭区间0,1的存在无意义。在预处理后,在相互包含的情况下,小区间显然不应该被考虑。解题思路n 把各区间按照a从小到大顺序。如果区间1的起点不是s,n则无解,即s,t无法被完全覆盖(因为其他区间的起点更大,n不可能覆盖到s点),否则选择起点在s的最长区间。选择此n区间ai,bi后,新的起点应该被设置为bi,并且忽略所有区间在nbi之前的部分,就像预处理一样。虽然贪心策略比上面的题n复杂,但
7、是仍然只需要一次扫描。如下图5所示。s为当前有n效起点(此前部分已被覆盖),则应该选择区间2。s穷竭搜索是指将所有的可能性罗列出来,在其中寻找答案的方法。概念:这里,我们主要介绍:深度优先搜索宽度优先搜索基础的“穷竭搜索”深度优先搜索n深度优先搜索(DFS,Depth-First Search)是搜索的手段之一。n它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步的状态,继续转移到其他状态,如此不断重复,直至找到最终的解。n根据深度优先搜索的特点,采用递归函数实现比较简单。 例题n给定整数 a1,a2,a3,.,an, 判断是否可以从中选出若干个数,使他们的和恰好为k。n限制条件:
8、n1=n20n-108=ai=108n-108=k只需1次转移就可到达的所有状态-只需2次转移就可到达的状态-.,这样的顺序进行搜索。对于同一状态,宽度优先搜索只经过一次,因此复杂度为O(状态数*转移的方式)。n根据宽度优先搜索的特点,采用队列进行实现。例题:n水池数目n南阳理工学院校园里有一些小河和一些湖泊,现在,我们把它们通一看成水池,假设有一张我们学校的某处的地图,这个地图上仅标识了此处是否是水池,现在,你的任务来了,请用计算机算出该地图中共有几个水池。n输入m行每行输入n个数,表示此处有水还是没水n(1表示此处是水池,0表示此处是地面) n0m100n0n100n输入:n3 4n1 0
9、 0 0 n0 0 1 1n1 1 1 0n输出:n2输入:5 51 1 1 1 00 0 1 0 10 0 0 0 01 1 1 0 00 0 1 1 1输出:3解题过程n本题是简单的搜索问题,采用深度优先遍历可以解决,根据题目要求,假设从任意一点值为1的出发,将这点的坐标上下左右全部用0替换,1次DFS后与初始动这个1连接的1全部被替换成0,因此,直到图中不再存在1为至,总共进行的DFS的次数就是最后的结果咯!那么,根据题目要求,有4个方向,时间复杂度为O(4*n*m)。数论那些事n数学,特别是数论与计算机科学有着密切的联系,所以也常被选作题材。虽然数学问题大多需要使用特定方法求解,但其中
10、有几个基础算法扮演着重要的角色。数论基础n辗转相除法n有关素数的基础算法n快速幂1、求最大公约数2、扩展欧几里得3、ax+by=gcd(a,b)1、埃氏筛法2、区间筛法辗转相除法n扩展欧几里得n 双六n一个双六上面有向前向后无限延续的格子,每个格子都写有整数。其中0号格子是起点,1号格子是终点。而骰子上只有 a , b , -a , -b 四个整数,所以根据 a 和 b 的值的不同,有可能无法到达终点。n格子如下:n -4 -3 -2 -1 0 1 2 3 4 n掷出四个整数各多少次可以到达终点?输出任意一组解。n1= a , b b。n1,显然当 b=0,gcd(a,b)=a。此时 x=1,
11、y=0;n2,ab!=0 时n设 ax1+by1=gcd(a,b);nbx2+(a mod b)y2=gcd(b,a mod b);n根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);n则:ax1+by1=bx2+(a mod b)y2;n即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;n根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;n这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.n上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。埃氏筛
12、法n给定整数n,请问n以内多少个素数nn=106n输入n25n输出n9解题思路n要枚举n以内素数,可以用埃氏筛法n列出2以后的所有序列:n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25n标出序列中的第一个素数,也就是2,序列变成:n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 252n将剩下序列中,划摽2的倍数,序列变成:n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2
13、4 25n 4 6 8 10 12 14 16 18 20 22 24 (划出的数)n如果现在这个序列中最大数小于最后一个标出的素数的平方,那么剩下的序列中所有的数都是素数,否则回到第二步。n本例中,因为25大于2的平方,我们返回第二步:n剩下的序列中第一个素数是3,将主序列中3的倍数划出,主序列变成:n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25n 4 6 8 9 10 12 14 15 16 18 20 21 22 24 (划出的数)n我们得到的素数有:2,3n25仍然大于3的平方,所以我们还要返回第二步:n
14、现在序列中第一个素数是5,同样将序列中5的倍数划出,主序列成了:n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25n 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 (划出的数)n我们得到的素数有:2 3 5 。n因为25等于5的平方,跳出循环.n结论:去掉数字,2到25之间的素数是:2 3 5 7 11 13 17 19 23。总结n算法竞赛是展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的竞赛。n在此送上楼教主一句名言:n虽然我不会这道题,但是AC还是没有问题的!n谢谢