ACM递推求解算法.ppt

ACM程序设计 杭州电子科技大学刘春英acm 2020 1 15 2 今天 你了吗 AC 2020 1 15 3 每周一星 2 07052311周天涯 2020 1 15 4 第三讲 递推求解 2020 1 15 5 先来看一个超级简单的例题 有5人坐在一起 当问第5个人多少岁 他说比第4个人大2岁 问第4个人多少岁 他说比第3个人大2岁 依此下去 问第一个人多少岁 他说他10岁 最后求第5个人多少岁 如果所坐的不是5人而是n人 写出第n个人的年龄表达式 2020 1 15 6 显然可以得到如下公式 化简后的公式 F n 10 n 1 2 2020 1 15 7 再来一个简单题 2020 1 15 8 递推公式 F n F n 1 1 2 2020 1 15 9 Fibnacci数列 即 1 2 3 5 8 13 21 34 2020 1 15 10 思考 递推公式的伟大意义 有了公式 人工计算的方法 常见的编程实现方法 优缺点 2020 1 15 11 简单思考题 在一个平面上有一个圆和n条直线 这些直线中每一条在圆内同其他直线相交 假设没有3条直线相交于一点 试问这些直线将圆分成多少区域 2020 1 15 12 是不是这个 F 1 2 F n F n 1 n 化简后 F n n n 1 2 1 2020 1 15 13 太简单了 来个稍微麻烦一些的 2020 1 15 14 例 2050 折线分割平面 问题描述 平面上有n条折线 问这些折线最多能将平面分割成多少块 样例输入12样例输出27 2020 1 15 15 思考2分钟 如何解决 2020 1 15 16 结论 Zn 2n 2n 1 2 1 2n 2n 2 n 1 为什么 2020 1 15 17 趁热打铁 来个差不多的 2020 1 15 18 佐罗 的烦恼说起佐罗 大家首先想到的除了他脸上的面具 恐怕还有他每次刻下的 Z 字 我们知道 一个 Z 可以把平面分为2部分 两个 Z 可以把平面分为12部分 那么 现在的问题是 如果平面上有n个 Z 平面最多可以分割为几部分呢 说明1 Z 的两端应看成射线说明2 Z 的两条射线规定为平行的 附加思考题 还没加到OJ 2020 1 15 19 总结 递推求解的基本方法 首先 确认 能否容易的得到简单情况的解 然后 假设 规模为N 1的情况已经得到解决 最后 重点分析 当规模扩大到N时 如何枚举出所有的情况 并且要确保对于每一种子情况都能用已经得到的数据解决 强调 1 编程中的空间换时间的思想2 并不一定只是从N 1到N的分析 2020 1 15 20 问题的提出 设有n条封闭曲线画在平面上 而任何两条封闭曲线恰好相交于两点 且任何三条封闭曲线不相交于同一点 问这些封闭曲线把平面分割成的区域个数 思考题 平面分割方法 2020 1 15 21 F 1 2F n F n 1 2 n 1 简单分析 2020 1 15 22 某人写了n封信和n个信封 如果所有的信都装错了信封 求所有的信都装错信封 共有多少种不同情况 1465不容易系列之一 2020 1 15 23 分析思路 1 当N 1和2时 易得解 假设F N 1 和F N 2 已经得到 重点分析下面的情况 4 后者简单 只能是没装错的那封和第N封交换信封 没装错的那封可以是前面N 1封中的任意一个 故 F N 2 N 1 3 前者 对于每种错装 可从N 1封信中任意取一封和第N封错装 故 F N 1 N 1 2 当有N封信的时候 前面N 1封信可以有N 1或者N 2封错装 2020 1 15 24 得到如下递推公式 基本形式 d 1 0 d 2 1递归式 d n n 1 d n 1 d n 2 这就是著名的错排公式 2020 1 15 25 在2 n的长方形方格中 用n个1 2的骨牌铺满方格 例如n 3时 为2 3方格 骨牌的铺放方案有三种 如图 输入n 输出铺放方案的总数 思考题 2046 2020 1 15 26 有1 n的一个长方形 用1 1 1 2 1 3的骨牌铺满方格 例如当n 3时为1 3的方格 如图 此时用1 1 1 2 1 3的骨牌铺满方格 共有四种铺法 输入 n 0 n 30 输出 铺法总数 再思考题 2020 1 15 27 仔细分析最后一个格的铺法 发现无非是用1 1 1 2 1 3三种铺法 很容易就可以得出 f n f n 1 f n 2 f n 3 其中f 1 1 f 2 2 f 3 4 典型例题 分析过程 2020 1 15 28 最后一个思考题 有点难度 2020 1 15 29 分析过程 1 设 F n 表示n个人的合法队列 则 按照最后一个人的性别分析 他要么是男 要么是女 所以可以分两大类讨论 1 如果n个人的合法队列的最后一个人是男 则对前面n 1个人的队列没有任何限制 他只要站在最后即可 所以 这种情况一共有F n 1 2020 1 15 30 2 如果n个人的合法队列的最后一个人是女 则要求队列的第n 1个人务必也是女生 这就是说 限定了最后两个人必须都是女生 这又可以分两种情况 分析过程 2 2020 1 15 31 2 1 如果队列的前n 2个人是合法的队列 则显然后面再加两个女生 也一定是合法的 这种情况有F n 2 分析过程 3 2020 1 15 32 2 2 但是 难点在于 即使前面n 2个人不是合法的队列 加上两个女生也有可能是合法的 当然 这种长度为n 2的不合法队列 不合法的地方必须是尾巴 就是说 这里说的长度是n 2的不合法串的形式必须是 F n 4 男 女 这种情况一共有F n 4 分析过程 4 2020 1 15 33 结论 所以 通过以上的分析 可以得到递推的通项公式 F n F n 1 F n 2 F n 4 n 3 然后就是对n 3的一些特殊情况的处理了 显然 F 0 1 没有人也是合法的 这个可以特殊处理 就像0的阶乘定义为1一样 F 1 1F 2 2F 3 4 2020 1 15 34 不容易系列之 3 LELE的RPG难题有排成一行的 个方格 用红 Red 粉 Pink 绿 Green 三色涂每个格子 每格涂一色 要求任何相邻的方格不能同色 且首尾两格也不同色 求全部的满足要求的涂法 附加思考题 1 2020 1 15 35 1480 钥匙计数之二一把钥匙有N个槽 2 N 26槽深为1 2 3 4 5 6 每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5 求这样的钥匙的总数 本题无输入对2 N 26 输出满足要求的钥匙的总数 附加思考题 2 2020 1 15 36 详见解题报告 Anyquestion 2020 1 15 38 课后任务 一 DIY在线作业 3 2008 ACMProgramming Exercise 3 递推求解二 常规练习 包含以上作业 1290献给杭电五十周年校庆的礼物1297Chi