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