ACM算法 递推求解

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