(HDUACM2010版_03)递推求解[稻谷文苑]

1、ACM程序设计程序设计 杭州电子科技大学 刘春英 1优质荟萃 今天，今天， 你你 了吗？了吗？ AC 2优质荟萃 每周一星（每周一星（2）：）： HoxilyHoxily 3优质荟萃 第三讲第三讲 递推求解递推求解 4优质荟萃 先来看一个先来看一个超级超级简单的简单的例题例题: n有5人坐在一起，当问第5个人多少岁, 他说比第4个人大2岁，问第4个人多少 岁,他说比第3个人大2岁，依此下去， 问第一个人多少岁，他说他10岁，最 后求第5个人多少岁？ n如果所坐的不是5人而是n人，写出第 n个人的年龄表达式。 5优质荟萃 22)1( 110 )( nnf n nf 显然可以得到如下公式显然可以得

2、到如下公式: : 化简后的公式: F(n)=10+(n-1)*2 6优质荟萃 Fibnacci Fibnacci 数列：数列： 2 12 01 21 nff n n f nn n 即：1、2、3、5、8、13、21、34 7优质荟萃 思考思考: : n递推公式的意义？ n有了公式，人工计算的方法？ n常见的编程实现方法？（优缺点？） 8优质荟萃 简单思考题简单思考题: : n在一个平面上有一个圆和在一个平面上有一个圆和n n条直线，条直线， 这些直线中每一条在圆内同其他直这些直线中每一条在圆内同其他直 线相交，假设没有线相交，假设没有3 3条直线相交于条直线相交于 一点，试问这些直线将圆分成多

3、少一点，试问这些直线将圆分成多少 区域。区域。 9优质荟萃 是不是这个是不是这个 F(1)=2; F(n) = F(n-1)+n; 化简后： F(n) = n(n+1)/2 +1; 10优质荟萃 太简单了太简单了? ? 来个稍微麻烦一些的来个稍微麻烦一些的 11优质荟萃 例例: :（20502050）折线分割平面）折线分割平面 问题描述问题描述： 平面上有平面上有n n条折线，问这些折线最多能将平面分割条折线，问这些折线最多能将平面分割 成多少块成多少块? ? 样例输入样例输入 1 1 2 2 样例输出样例输出 2 2 7 7 12优质荟萃 思考思考: :如何用递推解决如何用递推解决? ? 结

4、论结论 F(n)=F(n-1)+4(n-1)+1F(n)=F(n-1)+4(n-1)+1 13优质荟萃 另外一种结论另外一种结论: : nZn = 2n ( 2n + 1 ) / 2 + 1 - 2nZn = 2n ( 2n + 1 ) / 2 + 1 - 2n = 2 n2 = 2 n2 n + 1 n + 1 为什么为什么? ? 14优质荟萃 总结：递推求解的基本方法：总结：递推求解的基本方法： n首先，确认：能否容易的得到简单情况的解？首先，确认：能否容易的得到简单情况的解？ n然后，假设：规模为然后，假设：规模为N-1N-1的情况已经得到解决。的情况已经得到解决。 n最后，重点分析：当

5、规模扩大到最后，重点分析：当规模扩大到N N时，如何枚时，如何枚 举出所有的情况，并且要确保对于每一种子举出所有的情况，并且要确保对于每一种子 情况都能用已经得到的数据解决。情况都能用已经得到的数据解决。 n强调：强调： 1 1、编程中的空间换时间的思想、编程中的空间换时间的思想 2 2、并不一定只是从、并不一定只是从N-1N-1到到N N的分析的分析 15优质荟萃 问题的提出：问题的提出： 设有设有n n条封闭曲线画在平面上，而任条封闭曲线画在平面上，而任 何两条封闭曲线恰好相交于两点，且任何何两条封闭曲线恰好相交于两点，且任何 三条封闭曲线不相交于同一点，问这些封三条封闭曲线不相交于同一点

6、，问这些封 闭曲线把平面分割成的区域个数。闭曲线把平面分割成的区域个数。 思考题：平面分割方法思考题：平面分割方法 16优质荟萃 F(1)=2F(1)=2 F(n)=F(n-1)+2(n-1)F(n)=F(n-1)+2(n-1) 简单分析简单分析 1 1 32 4 1 2 3 4 6 5 7 8 1 2 3 4 5 6 7 10 8 9 11 12 13 14 n=1n=1n=2n=2n=3n=3 n=4n=4 2 17优质荟萃 在在2 2n n的长方形方格中的长方形方格中, ,用用n n个个1 12 2的骨牌铺满方格的骨牌铺满方格, , 例如例如n=3n=3时时, ,为为2 23 3方格，骨

7、牌的铺放方案有三种方格，骨牌的铺放方案有三种( (如如 图图), ), 输入输入n ,n ,输出铺放方案的总数输出铺放方案的总数 思考题（思考题（20462046）：）： 18优质荟萃 有有1 1n n的一个长方形，用的一个长方形，用1 11 1、1 12 2、1 13 3的骨牌铺的骨牌铺 满方格。例如当满方格。例如当n=3n=3时为时为1 13 3的方格（如图），此时用的方格（如图），此时用 1 11 1，1 12 2，1 13 3的骨牌铺满方格，共有四种铺法。的骨牌铺满方格，共有四种铺法。 输入：输入： n n（0=n=300=n3) (n3) 然后就是对然后就是对n=3 n=3 的一些特

8、殊情况的处理了，的一些特殊情况的处理了， 显然：显然： F(0)=1F(0)=1 ( (没有人也是合法的，这个可以特殊没有人也是合法的，这个可以特殊 处理，就像处理，就像0 0的阶乘定义为的阶乘定义为1 1一样一样) ) F(1)=1F(1)=1 F(2)=2 F(3)=4F(2)=2 F(3)=4 26优质荟萃 不容易系列之不容易系列之(3)(3) LELE LELE的的RPGRPG难题难题 有排成一行的个方格，用红有排成一行的个方格，用红(Red)(Red)、粉、粉 (Pink)(Pink)、绿、绿(Green)(Green)三色涂每个格子，每格涂三色涂每个格子，每格涂 一色，要求任何相邻

9、的方格不能同色，且首一色，要求任何相邻的方格不能同色，且首 尾两格也不同色求全部的满足要求的涂法尾两格也不同色求全部的满足要求的涂法. . 附加题（看看效果）：附加题（看看效果）： 27优质荟萃 某人写了n封信和n个信封，如果 所有的信都装错了信封。求所有 的信都装错信封,共有多少种不 同情况。 附加题：附加题：14651465不容易系列之一不容易系列之一 28优质荟萃 分析思路：分析思路： 1 1、当、当N=1N=1和和2 2时，易得解，假设时，易得解，假设F(N-1)F(N-1)和和 F(N-2)F(N-2)已经得到，重点分析下面的情况：已经得到，重点分析下面的情况： 4 4、后者简单，只

10、能是没装错的那封和第、后者简单，只能是没装错的那封和第N N封封 交换信封，没装错的那封可以是前面交换信封，没装错的那封可以是前面N-1N-1 封中的任意一个，故封中的任意一个，故= F(N-2) = F(N-2) * * (N-1) (N-1) 3 3、前者，对于每种错装，可从、前者，对于每种错装，可从N-1N-1封信中任封信中任 意取一封和第意取一封和第N N封错装，故封错装，故=F(N-1)=F(N-1)* *(N-1)(N-1) 2 2、当有、当有N N封信的时候，前面封信的时候，前面N-1N-1封信可以有封信可以有N-1N-1 或者或者 N-2 N-2封错装封错装 29优质荟萃 得到如下递推公式：得到如下递推公式： 基本形式：d1=0; d2=1 递归式：dn= (n-1)*( dn-1 + dn-2