ACM算法_递推求解

1、2021-12-141ACM ACM 程序设计程序设计计算机学院计算机学院 刘春英刘春英2021-12-142你 了吗？AC2021-12-143水域浪子水域浪子 2021-12-1442021-12-145l有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？l如果所坐的不是5人而是n人，写出第n个人的年龄表达式。 2021-12-146化简后的公式:F(n)=10+(n-1)*222)1(110)(nnfnnf2021-12-1472021-12-148蟠桃记2021-12-149

2、lF(n)=(F(n-1)+1)*22021ffnnfnnn即：1、2、3、5、8、13、21、342021-12-1411l递推公式的伟大意义？l有了公式，人工计算的方法？l常见的编程实现方法？（优缺点？）2021-12-1412l在一个平面上有一个圆和在一个平面上有一个圆和n条直条直线，这些直线中每一条在圆内线，这些直线中每一条在圆内同其他直线相交，假设没有同其他直线相交，假设没有3条条直线相交于一点，试问这些直直线相交于一点，试问这些直线将圆分成多少区域。线将圆分成多少区域。2021-12-1413F(1)=2; F(n) = F(n-1)+n;化简后：F

3、(n) = n(n+1)/2 +1;2021-12-14142021-12-1415例例: : （20502050）折线分割平面）折线分割平面问题描述问题描述： 平面上有平面上有n n条折线，问这些折线最多能将平面分条折线，问这些折线最多能将平面分割成多少块割成多少块? ?样例输入样例输入1 12 2样例输出样例输出2 27 72021-12-14162021-12-1417lZn = 2n ( 2n + 1 ) / 2 + 1 - 2n= 2 n2 n + 1为什么为什么? ?2021-12-14182021-12-1419说起佐罗，大家首先想到的除了他脸上的面具说起佐罗，大家首先想到的除了

4、他脸上的面具，恐怕还有他每次刻下的，恐怕还有他每次刻下的“Z”Z”字。我们知道，字。我们知道，一个一个“Z”Z”可以把平面分为可以把平面分为2 2部分，两个部分，两个“Z”Z”可可以把平面分为以把平面分为1212部分，那么，现在的问题是：部分，那么，现在的问题是：如果平面上有如果平面上有n n个个“Z”,Z”,平面最多可以分割为几平面最多可以分割为几部分呢？部分呢？说明说明1 1：“Z”Z”的两端应看成射线的两端应看成射线说明说明2 2：“Z”Z”的两条射线规定为平行的的两条射线规定为平行的2021-12-1420l首先确认，是否能很容易的得到简单情况的解l假设规模为N-1的情况已经得到解决l

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

6、4F(1)=2F(n)=F(n-1)+2(n-1)2021-12-1423某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。 2021-12-14241、当有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)2021-12-1425基本形式：d1=0; d2=1递归式：dn= (n-1)*( dn-1 + d

7、n-2)2021-12-1426在在2 2n n的一个长方形方格中的一个长方形方格中, ,用一个用一个1 1 2 2的骨牌铺满方格的骨牌铺满方格, ,例如例如n=3n=3时时, ,为为2 2 3 3方格，骨牌的铺放方案有三种方格，骨牌的铺放方案有三种( (如图如图),),输入输入n ,n ,输出铺放方案的总数输出铺放方案的总数2021-12-1427有有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的骨牌铺满方格，

8、共有四种铺法。如图的骨牌铺满方格，共有四种铺法。如图 输入输入 n n（0=n=300=n3)然后就是对n=3 的一些特殊情况的处理了，显然：F(0)=1 (没有人也是合法的，这个可以特殊处理，就像0的阶乘定义为1一样) F(1)=1F(2)=2F(3)=42021-12-1433有排成一行的个方格，用红有排成一行的个方格，用红(Red)(Red)、粉、粉(Pink)(Pink)、绿、绿(Green)(Green)三色涂每个格子，每三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要，且首尾两格也不同色求全部的满足要求的涂

9、法求的涂法. .2021-12-1434一把钥匙有一把钥匙有N N个槽，个槽，2N262N26槽深为槽深为1 1，2 2，3 3，4,5,64,5,6。每钥匙至少有。每钥匙至少有3 3个不同的深度且相连的个不同的深度且相连的槽其深度之差不得为槽其深度之差不得为5 5。求这样的钥匙的总数。求这样的钥匙的总数。 本题无输入本题无输入对对2N262N26，输出满足要求的钥匙的总数。，输出满足要求的钥匙的总数。 2021-12-1435lhttp:/ 献给杭电五十周年校庆的礼物献给杭电五十周年校庆的礼物1297 Childrens Queue 1438 钥匙计数之一钥匙计数之一1465 不容易系列之一不容易系列之一1466 计算直线的交点