信息学奥赛基本算法.ppt

第0讲 算法设计概论 时间复杂度空间复杂度调试方法与技巧 时间复杂度 O 1 常数阶O logN 对数阶O N 线性阶O N 2 平方阶O N 3 立方阶 空间复杂度 O 1 常数阶O logN 对数阶O N 线性阶O N 2 平方阶O N 3 立方阶 调试方法与技巧 BreakPointWatchTableDataCheckCode 问题分析 分析题目的模型考虑要用的算法分析算法的时空复杂度如果符合要求即可Coding 第一讲 递归 什么是递归 递归就是指一个函数直接或者间接地调用自身 问题的求解过程 划分成相同性质的子问题的求解 而小问题的求解过程可以很容易的求出 这些子问题的解就构成里原问题的解 总体思想 待求解问题的解 输入变量x的函数f x 通过寻找函数g 使得f x g f x 1 且已知f 0 的值 就可以通过f 0 和g 求出f x 值 推广 扩展到多个输入变量x y z等 x 1也可以推广到x x1 只要递归朝着 出口 的方向即可 递归的三个要点 递归式 如何划分子问题递归边界 递归的终止条件 也就是最小的子问题界函数 问题规模变化的函数 保证递归向边界靠拢 求n includeintF intn if n 0 return1 elsereturnn F n 1 栈 递归的实现是需要栈的 这里所使用的栈是系统自带的栈栈是一种数据结构 它符合先入后出的原则 解决递归问题的关键 找出递推公式 即如何将问题划分为小规模的问题找到边界条件NOTICE 由于函数中的局部变量是存在系统的栈上的 如果你的局部变量过大 如较大的数组 将有可能栈溢出 这个时候要考虑全局变量和人工栈的使用 汉诺塔问题 现在有三根相邻的柱子 标号为A B C A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘 现在把所有盘子一个一个移动到柱子B上 并且每次移动同一根柱子上都不能出现大盘子在小盘子上方 请问至少需要多少次移动 并输出步骤 汉诺塔问题 voidhanoi intn charA charB charC if n 1 printf Movedisk dfrom cto c n n A C else hanoi n 1 A C B printf Movedisk dfrom cto c n n A C hanoi n 1 B A C 前序中序求后序 树中已知先序和中序求后序 如先序为 abdc 中序为 bdac 则程序可以求出后序为 dbca 前序中序求后序 算法思想 先序遍历树的规则为中左右 则说明第一个元素必为树的根节点 比如上例中的a就为根节点 由于中序遍历为 左中右 再根据根节点a 我们就可以知道 左子树包含元素为 db 右子树包含元素 c 再把后序进行分解为db和c 根被消去了 然后递归的进行左子树的求解 左子树的中序为 db 后序为 db 递归的进行右子树的求解 即右子树的中序为 c 后序为 c 如此递归到没有左右子树为止 前序中序求后序 voidpronum charpre intpre s intpre e charin intin s intin e charc intk if in s in e return 非法子树 完成 if in s in e printf c in in s 子树子仅为一个节点时直接输出并完成 return c pre pre s c储存根节点 k find c in in s in e 在中序中找出根节点的位置 pronum pre pre s 1 pre s k in s in in s k 1 递归求解分割的左子树 pronum pre pre s k in s 1 pre e in k 1 in e 递归求解分割的右子树 printf c c 根节点输出 FBI树 我们可以把由 0 和 1 组成的字符串分为三类 全 0 串称为B串 全 1 串称为I串 既含 0 又含 1 的串则称为F串 FBI树是一种二叉树 它的结点类型也包括F结点 B结点和I结点三种 由一个长度为2N的 01 串S可以构造出一棵FBI树T 递归的构造方法如下 1 T的根结点为R 其类型与串S的类型相同 2 若串S的长度大于1 将串S从中间分开 分为等长的左右子串S1和S2 由左子串S1构造R的左子树T1 由右子串S2构造R的右子树T2 现在给定一个长度为2N的 01 串 请用上述构造方法构造出一棵FBI树 并输出它的后序遍历序列 FBI树 算法思想 本题为后序 类似于前一题 我们有相似的解法 FBI树 intfbi inti intj if i0 第二讲 回溯 回溯 回溯是一种实现枚举的算法其本质就是应用了递归这一工具所进行的枚举其优点在于可以加上一些剪枝 使得枚举的效率更加的高我们也可以将其称之为深度优先搜索DFS 回溯框架 inttry if 达到目标 记录结果 elsefor each if 满足条件 改变状态 try 回复状态 8皇后 在8X8格的国际象棋上摆放八个皇后 使其不能互相攻击 即任意两个皇后都不能处于同一行 同一列或同一斜线上 问有多少种摆法 分析 显然 八皇后问题每行必须有一个皇后 所以 对棋盘深搜时 第一个皇后的位置不妨设为第一行 这样只对第一行进行搜索 同理 第二个皇后不妨设为第二行 以此类推 代码 voidtry intk if k 9 if ok ans return0 for inti 1 i 8 i a k i 1 try k 1 a k i 0 优化 用一个use 来记录是否本列被占用用一个Xright Xleft 分别记录每条对角线是否被占用 Fibonacci F n F n 1 F n 2 F 0 F 1 1如何解决这个问题 解法1 递归解法intf intn if n 1 n 0 return1 returnf n 1 f n 2 解法2 递归 记忆化intf intn if n 1 n 0 return1 calc n 1 if calc n returnf n f n f n 1 f n 2 returnf n 解法3 递推f 0 1 f 1 1 for inti 2 i n i f n f n 1 f n 2 解法4 数学方法数学上可以简单推理 存在A B使得 F n A x1 n B x2 n代入F 0 0 F 1 1 解得A 1 sqrt 5 0 B 1 sqrt 5 0 即F n x1 n x2 n sqrt 5 0 时间复杂度为O 1 但不能保证精度 解法5 注意到Fibonacci数列是二阶递推数列 所以存在一个2 2的矩阵A 使得 F n F n 1 F n 1 F n 2 A 求解得到A 1 1 1 0 然后通过递推式 FnFn 1 Fn 1Fn 2 A Fn 2Fn 3 A2 F1F0 An 1 然后只要计算An 1 再与矩阵 F1F0 相乘 就可以的得到Fn的值快速指数相乘法求An 1 n ak 2 k ak 1 2 k 1 a1 2 a0 其中ai 0或1 i 0 1 2 k 所以我们只需要进行logn次的运算 第三讲 分治 分治概念 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题 这些子问题相互独立且与原问题性质相同 求出子问题的解 就可得到原问题的解 分治步骤 分解 将要解决的问题划分成若干规模较小的同类问题 求解 当子问题划分得足够小时 用较简单的方法解决 合并 按原问题的要求 将子问题的解逐层合并构成原问题的解 分治 分治也是运用递归方法进行的算法将大问题化为若干小问题再解决小问题最后由小问题得出大问题的解 分治例子 例1 找出伪币 给你一个装有16个硬币的袋子 16个硬币中有一个是伪造的 并且那个伪造的硬币比真的硬币要轻一些 你的任务是找出这个伪造的硬币 为了帮助你完成这一任务 将提供一台可用来比较两组硬币重量的仪器 利用这台仪器 可以知道两组硬币的重量是否相同 解法1 比较硬币1与硬币2的重量 假如硬币1比硬币2轻 则硬币1是伪造的 假如硬币2比硬币1轻 则硬币2是伪造的 这样就完成了任务 假如两硬币重量相等 则比较硬币3和硬币4 同样 假如有一个硬币轻一些 则寻找伪币的任务完成 假如两硬币重量相等 则继续比较硬币5和硬币6 按照这种方式 可以最多通过8次比较来判断伪币的存在并找出这一伪币 解法2 另外一种方法就是利用分而治之方法 假如把16硬币的例子看成一个大的问题 第一步 把这一问题分成两个小问题 随机选择8个硬币作为第一组称为A组 剩下的8个硬币作为第二组称为B组 这样 就把16个硬币的问题分成两个8硬币的问题来解决 第二步 判断A和B组中是否有伪币 可以利用仪器来比较A组硬币和B组硬币的重量 假如两组硬币重量相等 则可以判断伪币不存在 假如两组硬币重量不相等 则存在伪币 并且可以判断它位于较轻的那一组硬币中 最后 在第三步中 用第二步的结果得出原先16个硬币问题的答案 若仅仅判断硬币是否存在 则第三步非常简单 无论A组还是B组中有伪币 都可以推断这16个硬币中存在伪币 因此 仅仅通过一次重量的比较 就可以判断伪币是否存在 分治应用 归并排序 排序的方法 冒泡排序选择排序快速排序桶排序基数排序归并排序 归并排序 归并 Merge 排序法是将两个 或两个以上 有序表合并成一个新的有序表 即把待排序序列分为若干个子序列 每个子序列是有序的 然后再把有序子序列合并为整体有序序列 归并排序 我们可以在O n 的时间内将两个有序的序列合并每次我们将一个序列平均分成两半 分别进行排序 之后再将其合并 复杂度分析 时间复杂度为O nlogn 这是该算法中最好 最坏和平均的时间性能 空间复杂度为O n 比较操作的次数介于 nlogn 2和nlogn n 1 赋值操作的次数是 2nlogn 归并算法的空间复杂度为 0 n 归并排序比较占用内存 但却效率高且稳定的算法 优点 归并排序是稳定的排序 即相等的元素的顺序不会改变 如输入记录1 1 3 2 2 3 2 4 5 5 括号中是记录的关键字 时输出的1 1 2 3 2 4 3 2 5 5 中的2和2是按输入的顺序 这对要排序数据包含多个信息而要按其中的某一个信息排序 要求其它信息尽量按输入的顺序排列时很重要 这也是它比快速排序优势的地方 例子 如设有数列 6 202 100 301 38 8 1 初始状态 6 202 100 301 38 8 1 比较次数i 1 6202 100301 838 1 3i 2 6100202301 1838 4i 3 16838100202301 4总计 11次 代码 voidMergeSort intarray intfirst intlast intmid 0 if first last mid first last 2 MergeSort array first mid MergeSort array mid 1 last Merge array first mid last code voidmerge ints intt intmid s t 2 inti s i是左边子序列的指针 intj mid 1 j是右边子序列的指针 intk s k是临时队列的指针 while kt a i a j 左边子序列不空 右边子序列已空或左边的元素小于右边的元素 now k a i i else now k a j j k for inti s i t i a i now i 在合并的过程中 我们分别拿出两个有序子序列的一个值进行比较 选择一个较小 或较大 的值 也就是这两个有序子序列中较小 或较大 的值 加入一个临时的队列之中 当其中的有一个子序列空了的时候 另一个子序列中剩下的元素就可以直接加入临时队列中 瑞士轮 2 N名编号为1 2N的选手共进行R轮比赛 每轮比赛开始前 以及所有比赛结束后 都会按照总分从高到低对选手进行一次排名 选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和 总分相同的 约定编号较小的选手排名靠前 瑞士轮 每轮比赛的对阵安排与该轮比赛开始前的排名有关 第1名和第2名 第3名和第4名 第2K 1名和第2K名 第2N 1名和第2N名 各进行一场比赛 每场比赛胜者得1分 负者得0分 也就是说除了首轮以外 其它轮比赛的安排均不能事先确定 而是要取决于选手在之前比赛中的表现 现给定每个选手的初始分数及其实力值 试计算在R轮比赛过后 排名第Q的选手编号是多少 我们假设选手的实力值两两不同 且每场比赛中实力值较高的总能获胜 N 100000R 50 瑞士轮 直接每次都进行快速排序必然超时需要找到每次排序O n 的方法归并排序 瑞士轮 每次将胜利者和失败者分成两个有序序列胜利者每人加一场胜场 所以依然是有序的将两个序列合并 可以做到O n 逆序对 所谓的逆序对是对于一个包含N个非负整数的数组A 1 n 如果有iA j 则称 A i A j 为数组A中的一个逆序对 例如 数组 3 1 4 5 2 的逆序对有 3 1 3 2 4 2 5 2 共4个 求逆序对个数 利用归并排序求逆序对的过程主要是根据 归并排序中元素的位置是稳定的 并且每两个子序列中也是有序的 当左边的子序列中的元素大于右边的子序列的元素时 那么左边子序列中该元素后面的所有元素都要大于右边的那个元素 也就是有这么多的逆序对 因此我们在归并排序的加一句话就可以完成 now k a i i else now k a j j if i mid ans mid i 1 表达式的计算 输入一个由0 9 运算符及括号组成的表达式 比如 17 18 12 3 6 9 表达式中的数字及计算结果都不超过长整型数 请编一个程序计算表达式的值 输入样例 6 8 3输出样例1 8 表达式计算 本题的解法有很多我们采用分治的思想来解决 表达式计算 首先我们计算出每个运算符的优先级 即哪一个运算符需要先计算 17 18 12 3 6 9 我们令加减号优先级为1乘除为2每加一层括号优先级加2则优先级为32354符合我们对表达式计算的顺序 分治 接下来我们按照优先级顺序从低到高进行分治 17 18 12 3 6 9 17 18 12 3 6 9 17 18 12 3 6 9 17 18 12 3 6 9 分治 17 18 12 3 6 9 17 18 12 9 9 17 18 12 81 35 69 2415 在一个2 k 2 k个方格组成的棋盘中 若有一个方格与其他方格不同 则称该方格为一特殊方格 且称该棋盘为一个特殊棋盘 显然特殊方格在棋盘上出现的位置有4 k种情形 因而对任何k 0 有4 k种不同的特殊棋盘 下图中的特殊棋盘是当k 2时16个特殊棋盘中的一个 棋盘覆盖 棋盘覆盖 特殊方格必位于4个较小子棋盘之一中 其余3个子棋盘中无特殊方格 为了将这3个无特殊方格的子棋盘转化为特殊棋盘 可以用一个L型骨牌覆盖这3个较小棋盘的会合处 如下图所示 这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格 从而原问题转化为4个较小规模的棋盘覆盖问题 递归地使用这种分割 直至棋盘简化为1 1棋盘 棋盘覆盖 普通递归 回溯 分治区别 一般的递归是建立在递推函数与边界条件上的 它是将一个子问题化成另一个子问题 或若干 的方法回溯则是利用递归的枚举法分治是将问题按一定的方式划分成若干小问题的方法 一般大于一个 第四讲 贪心 贪心 仅仅由当前的状态导出当前所需决策的算法 我们称之为贪心算法能够应用贪心算法解决的问题 每次必然都是选择最优的策略如果我们可以证明这样做是全局最优的话 那么贪心算法是一种十分高效的算法 贪心 正如人的思考一般 贪心就是针对局部最优情况的决策 无需考虑之后的决策会受到怎样的影响简单的例子 现有10元 7元 2元 1元四种纸币 使用的张数不限 需要用这四种纸币凑成x元钱 怎样用最少的张数达到此要求 贪心思路 每次取最大的纸币当x 14贪心算法14 10 2 2最优 14 7 7但是当纸币种类为10元 5元 1元时贪心明显是正确的这就促使我们思考如何证明贪心算法的正确性 三值排序问题 有一个由N个数值均为1 2或3的数构成的序列 N 1000 其值无序 现要求你用最少的交换次数将序列按升序顺序排列 贪心算法 排序后的序列分为三个部分 排序后应存储1的部分 排序后应存储2的部分和排序后应存储3的部分 贪心排序法应交换尽量多的交换后位置正确的 2 1 3 1 和 3 2 数对 当这些数对交换完毕后 再交换进行两次交换后位置正确的 1 2 3 三个数 贪心 分析 很明显 每一次交换都可以改变两个数的位置 若经过一次交换以后 两个数的位置都由错误变为了正确 那么它必定最优 同时我们还可发现 经过两次交换后 我们可以随意改变3个数的位置 那么如果存在三个数恰好为1 2和3 且位置都是错误的 那么进行两次交换使它们位置正确也必定最优 有由于该题具有最优子结构性质 我们的贪心算法成立 拼点游戏 C和S两位同学一起玩拼点游戏 有一堆白色卡牌和一堆蓝色卡牌 每张卡牌上写了一个整数点数 C随机抽取n张白色卡牌 S随机抽取n张蓝色卡牌 他们进行n回合拼点 每次两人各出一张卡牌 点数大者获得三颗巧克力 小者获得一颗巧克力 如果点数相同 每人各得二颗巧克力 使用过的卡牌不得重复使用 已知C和S取到的卡牌点数 请编程计算S最多和最少能得到多少颗巧克力 田忌赛马 其实本题就是田忌赛马的翻版如果3匹马变成1000匹 齐王仍然让他的马按从优到劣的顺序出赛 田忌可以按任意顺序选择他的赛马出赛 赢一局 田忌可以得到200两银子 输一局 田忌就要输掉200两银子 平局的话不输不赢 请问田忌最多能赢多少银子 解题思路 本题可以用DP来解可以连边进行匹配算法但是最简单的是贪心算法 贪心 当田忌最慢的马比齐王最慢的马快 赢一场先当田忌最慢的马比齐王最慢的马慢 和齐王最快的马比 输一场当田忌最快的马比齐王最快的马快时 赢一场先 当田忌最快的马比齐王最快的马慢时 拿最慢的马和齐王最快的马比 输一场 当田忌最快的马和齐王最快的马相等时 拿最慢的马来和齐王最快的马比 证明 当田忌最慢的马比齐王最慢的马快 赢一场先 因为始终要赢齐王最慢的马 不如用最没用的马来赢它 当田忌最慢的马比齐王最慢的马慢 和齐王最快的马比 输一场 因为田忌最慢的马始终要输的 不如用它来消耗齐王最有用的马 当田忌最慢的和齐王最慢的马慢相等时 分4和5讨论 当田忌最快的马比齐王最快的马快时 赢一场先 因为最快的马的用途就是来赢别人快的马 别人慢的马什么马都能赢 当田忌最快的马比齐王最快的马慢时 拿最慢的马和齐王最快的马比 输一场 因为反正要输一场 不如拿最没用的马输 当田忌最快的马和齐王最快的马相等时 这就要展开讨论了 贪心方法是 拿最慢的马来和齐王最快的马比 电池的寿命 小S新买了一个掌上游戏机 这个游戏机由两节5号电池供电 为了保证能够长时间玩游戏 他买了很多5号电池 这些电池的生产商不同 质量也有差异 因而使用寿命也有所不同 有的能使用5个小时 有的可能就只能使用3个小时 显然如果他只有两个电池一个能用5小时一个能用3小时 那么他只能玩3个小时的游戏 有一个电池剩下的电量无法使用 但是如果他有更多的电池 就可以更加充分地利用它们 比如他有三个电池分别能用3 3 5小时 他可以先使用两节能用3个小时的电池 使用半个小时后再把其中一个换成能使用5个小时的电池 两个半小时后再把剩下的一节电池换成刚才换下的电池 那个电池还能用2 5个小时 这样总共就可以使用5 5个小时 没有一点浪费 现在已知电池的数量和电池能够使用的时间 请你找一种方案使得使用时间尽可能的长 思路 设最大的电池电量为x其余的电量和为S如果x S ans 2 S这个好理解否则ans x S 思路 当x S时我们取最大的两个电池进行消耗消耗到他们不是最大的为止此时x S重复进行前两步则S必然趋于0故x趋于0所以可以全部消耗 活动安排问题 设有n个活动的集合e 1 2 n 其中每个活动都要求使用同一资源 如演讲会场等 而在同一时间内只有一个活动能使用这一资源 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi 且si fi 如果选择了活动i 则它在半开时间区间 si fi 内占用资源 若区间 si fi 与区间 sj fj 不相交 则称活动i与活动j是相容的 也就是说 当si fi或sj fj时 活动i与活动j相容 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合 设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下 算法的计算过程如下图所示 图中每行相应于算法的一次迭代 阴影长条表示的活动是已选入集合的活动 而空白长条表示的活动是当前正在检查相容性的活动 贪心 我们先证明排序后的第一个活动一定在解集中假设我们有一个最有解A他不包含活动1那么我们必然可以将A中end时间最早的替换成活动1得证以此类推 可以证明贪心算法的最优性 旅行家的预算 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 假设出发时油箱是空的 给定两个城市之间的距离D1 汽车邮箱的容量C 以升为单位 每升汽油能行使距离D2 出发点的每升汽油价格P和沿途油站数 N可以是0 油站I离出发点的距离Di 油站I每升汽油价格Pi I 1 2 3 N 编程找出一种加油方案 使费用最少 输出这个最少的费用值 计算结果四舍五入至小数点后两位 如果无法到达目的地 则输出 NoSolution 旅行家的预算 我们可以假设每次都装满油箱 只有当要用油时才对其付款 可以很明确的看到 但我们发现油箱里的油比当前可以买的油贵时 就用便宜的油来替代 这样一定最优 贪心算法的基本要