《ACM递推求解》PPT课件.ppt

ACM程序设计 why 2020 3 26 2 今天 你了吗 AC 2020 3 26 3 第三讲 递推求解 2020 3 26 4 先来看一个超级简单的例题 有5人坐在一起 当问第5个人多少岁 他说比第4个人大2岁 问第4个人多少岁 他说比第3个人大2岁 依此下去 问第一个人多少岁 他说他10岁 最后求第5个人多少岁 如果所坐的不是5人而是n人 写出第n个人的年龄表达式 2020 3 26 5 显然可以得到如下公式 化简后的公式 F n 10 n 1 2 2020 3 26 6 再来一个简单题 2020 3 26 7 递推公式 F n F n 1 1 2 2020 3 26 8 Fibnacci数列 即 1 2 3 5 8 13 21 34 2020 3 26 9 思考 递推公式的伟大意义 有了公式 人工计算的方法 常见的编程实现方法 优缺点 2020 3 26 10 简单思考题 在一个平面上有一个圆和n条直线 这些直线中每一条在圆内同其他直线相交 假设没有3条直线相交于一点 试问这些直线将圆分成多少区域 2020 3 26 11 是不是这个 F 1 2 F n F n 1 n 化简后 F n n n 1 2 1 2020 3 26 12 太简单了 来个稍微麻烦一些的 2020 3 26 13 例 2050 折线分割平面 问题描述 平面上有n条折线 问这些折线最多能将平面分割成多少块 样例输入12样例输出27 2020 3 26 14 思考2分钟 如何解决 2020 3 26 15 结论 Zn 2n 2n 1 2 1 2n 2n 2 n 1 减去延长线交的区域2n 为什么 2020 3 26 16 总结 递推求解的基本方法 首先 确认 能否容易的得到简单情况的解 然后 假设 规模为N 1的情况已经得到解决 最后 重点分析 当规模扩大到N时 如何枚举出所有的情况 并且要确保对于每一种子情况都能用已经得到的数据解决 强调 1 编程中的空间换时间的思想2 并不一定只是从N 1到N的分析 2020 3 26 17 某人写了n封信和n个信封 如果所有的信都装错了信封 求所有的信都装错信封 共有多少种不同情况 1465不容易系列之一 2020 3 26 18 分析思路 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 3 26 19 得到如下递推公式 基本形式 d 1 0 d 2 1递归式 d n n 1 d n 1 d n 2 这就是著名的错排公式 google上可以搜 2020 3 26 20 在2 n的长方形方格中 用n个1 2的骨牌铺满方格 例如n 3时 为2 3方格 骨牌的铺放方案有三种 如图 输入n 输出铺放方案的总数f n f n 1 f n 2 思考题 2046 2020 3 26 21 最后一个思考题 有点难度 有n个人站成一列 但是含单个女的队列是不合法的 总共有多少种合法的队列 F表示男的 M表示女的 2020 3 26 22 分析过程 1 设 F n 表示n个人的合法队列 则 按照最后一个人的性别分析 他要么是男 要么是女 所以可以分两大类讨论 1 如果n个人的合法队列的最后一个人是男 则对前面n 1个人的队列没有任何限制 他只要站在最后即可 所以 这种情况一共有F n 1 2020 3 26 23 分析过程 2 2 如果n个人的合法队列的最后一个人是女 则要求队列的第n 1个人务必也是女生 这就是说 限定了最后两个人必须都是女生 这又可以分两种情况 2020 3 26 24 分析过程 3 2 1 如果队列的前n 2个人是合法的队列 则显然后面再加两个女生 也一定是合法的 这种情况有F n 2 2020 3 26 25 分析过程 4 2 2 但是 难点在于 即使前面n 2个人不是合法的队列 加上两个女生也有可能是合法的 当然 这种长度为n 2的不合法队列 不合法的地方必须是尾巴 就是说 这里说的长度是n 2的不合法串的形式必须是 F n 4 男 女 这种情况一共有F n 4 2020 3 26 26 结论 所以 通过以上的分析 可以得到递推的通项公式 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 3 26 27 不容易系列之 3 LELE的RPG难题有排成一行的 个方格 用红 Red 粉 Pink 绿 Green 三色涂每个格子 每格涂一色 要求任何相邻的方格不能同色 且首尾两格也不同色 求全部的满足要求的涂法 f 1 3 f 2 6 f 3 6 f n f n 1 2f n 2 前面n 1个合法的 或n 2合法 附加思考题 1 2020 3 26 28 1480 钥匙计数之二一把钥匙有N个槽 2 N 26槽深为1 2 3 4 5 6 每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5 求这样的钥匙的总数 本题无输入对2 N 26 输出满足要求的钥匙的总数 附加思考题 2 2020 3 26 29 详见解题报告 Anyquestion 2020 3 26 31 课后任务 一 DIY在线作业 3 2008 ACMProgramming Exercise 3 递推求解二 常规练习 包含以上作业 1290献给杭电五十周年校庆的礼物1297Children sQueue1438钥匙计数之一1