ACM 程序设计计算机学院 刘春英*1今天，你 了吗？ACDate2每周一星（2）：水域浪子 Date3第三讲 递 推 求 解Date4先来看一个超级简单的例题:l有5人坐在一起，当问第5个人多少岁, 他说比第4个人大2岁，问第4个人多少 岁,他说比第3个人大2岁，依此下去， 问第一个人多少岁，他说他10岁，最后 求第5个人多少岁？ 如果所坐的不是5人而是n人，写出第n 个人的年龄表达式。 Date5显然可以得到如下公式:化简后的公式:F(n)=10+(n-1)*2Date6再来一个简单题:Date7再来一个简单题:蟠桃记Date8递推公式?lF(n)=(F(n-1)+1)*2Date9Fibnacci 数列：即：1、2、3、5、8、13、21、34Date10思考:l递推公式的伟大意义？l有了公式，人工计算的方法？l常见的编程实现方法？（优缺点？）Date11简单思考题:l在一个平面上有一个圆和n条直 线，这些直线中每一条在圆内 同其他直线相交，假设没有3条 直线相交于一点，试问这些直 线将圆分成多少区域。Date12是不是这个F(1)=2; F(n) = F(n-1)+n;化简后： F(n) = n(n+1)/2 +1;Date13太简单了?来个稍微麻烦一些的Date14例: （2050）折线分割平面问题描述：平面上有n条折线，问这些折线最多能将平面分 割成多少块? 样例输入 1 2 样例输出 2 7Date15思考2分钟:如何解决?Date16结论:lZn = 2n ( 2n + 1 ) / 2 + 1 - 2n = 2 n2 n + 1为什么?Date17趁热打铁，来个差不多的Date18说起佐罗，大家首先想到的除了他脸上的面具， 恐怕还有他每次刻下的“Z”字。我们知道，一 个“Z”可以把平面分为2部分，两个“Z”可以 把平面分为12部分，那么，现在的问题是：如果 平面上有n个“Z”,平面最多可以分割为几部分 呢？说明1：“Z”的两端应看成射线 说明2：“Z”的两条射线规定为平行的附加思考题（还没加到OJ）： “佐罗”的烦恼 Date19总结：递推求解的基本方法：l首先确认，是否能很容易的得到简单情 况的解l假设规模为N-1的情况已经得到解决l重点分析：当规模扩大到N时，如何枚举出所 有的情况，并且要确保对于每一种子情况都 能用已经得到的数据解决。l强调： 1、编程中的空间换时间的思想 2、并不一定是从N-1到N的分析Date20问题的提出：设有n条封闭曲线画在平面上，而任 何两条封闭曲线恰好相交于两点，且任何 三条封闭曲线不相交于同一点，问这些封 闭曲线把平面分割成的区域个数。思考题：平面分割方法Date2111324123 465781234567108911121314n=1n=2n=3n=4F(1)=2 F(n)=F(n-1)+2(n-1)Date22某人写了n封信和n个信封，如果 所有的信都装错了信封。求所有 的信都装错信封,共有多少种不同 情况。 1465 不容易系列之一Date23分析思路：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)Date24得到如下递推公式：基本形式：d1=0; d2=1 递归式：dn= (n-1)*( dn-1 + dn- 2)这就是著名的错排公式Date25在2n的一个长方形方格中,用一个1 2的骨牌铺满方格, 例如n=3时,为2 3方格，骨牌的铺放方案有三种(如图), 输入n ,输出铺放方案的总数思考题（2046）：Date26有1n的一个长方形，用11、12、13的骨牌铺满方 格。例如当n=3时为13的方格，此时用11，12， 13的骨牌铺满方格，共有四种铺法。如图输入n（03)然后就是对n=3 的一些特殊情况的处理了， 显然：F(0)=1 (没有人也是合法的，这个可以特殊 处理，就像0的阶乘定义为1一样) F(1)=1 F(2)=2 F(3)=4Date32有排成一行的个方格，用红(Red)、粉 (Pink)、绿(Green)三色涂每个格子，每 格涂一色，要求任何相邻的方格不能同色 ，且首尾两格也不同色求全部的满足要 求的涂法.附加思考题： 不容易系列之(3) LELE的RPG难题 Date33一把钥匙有N个槽，2N26槽深为1，2，3， 4,5,6。每钥匙至少有3个不同的深度且相连的槽 其深度之差不得为5。求这样的钥匙的总数。 本题无输入对2N26，输出满足要求的钥匙的总数。 附加思考题： 1480_钥匙计数之二 Date34详见解题报告：lhttp:/acm.hdu.edu.cn/forum/read.php?tid= 2294&page=1&toread=1l仔细阅读，耐心品味，关键掌握从n-1到 n的推导过程。Date35Any question?Date36HDOJ作业：1290 献给杭电五十周年校庆的礼物 1297 Childrens Queue 1438 钥匙计数之一 1465 不容易系列之一 1466 计算直线的交点数 1480 钥匙计数之二 2013 蟠桃记 2018 母牛的故事 2041 超级楼梯 2042 不容易系列之二 20442050 (10/5专题练习)Date37课后一定 要练习！Date38See you next week.Thank you! Date39