《HDUACM版03递推求解》由会员分享，可在线阅读，更多相关《HDUACM版03递推求解（32页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计程序设计8/28/20241今天，今天，你你 了吗？了吗？AC8/28/20242每周一星（每周一星（2）：）：HoxilyHoxily8/28/20243第三讲第三讲递推求解递推求解8/28/20244先来看一个先来看一个超级超级简单的简单的例题例题:n有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？n如果所坐的不是5人而是n人，写出第n个人的年龄表达式。 8/28/20245显然可以得到如下公式显然可以得到如下公式: :化简后的公式:F(n)=10+(n-1)*2
2、8/28/20246Fibnacci Fibnacci 数列：数列：即：1、2、3、5、8、13、21、348/28/20247思考思考: :n递推公式的意义？n有了公式，人工计算的方法？n常见的编程实现方法？（优缺点？）8/28/20248简单思考题简单思考题: :n在一个平面上有一个圆和在一个平面上有一个圆和n n条直线，条直线，这些直线中每一条在圆内同其他直这些直线中每一条在圆内同其他直线相交，假设没有线相交，假设没有3 3条直线相交于一条直线相交于一点，试问这些直线将圆分成多少区点，试问这些直线将圆分成多少区域。域。8/28/20249是不是这个是不是这个F(1)=2; F(n) =
3、F(n-1)+n;化简后：F(n) = n(n+1)/2 +1;8/28/202410太简单了太简单了? ?来个稍微麻烦一些的来个稍微麻烦一些的8/28/202411例例: :（20502050）折线分割平面）折线分割平面问题描述问题描述： 平面上有平面上有n n条折线，问这些折线最多能将平面分割条折线，问这些折线最多能将平面分割成多少块成多少块? ?样例输入样例输入1 12 2样例输出样例输出2 27 78/28/202412思考思考: :如何用递推解决如何用递推解决? ?结论结论F(n)=F(n-1)+4(n-1)+1F(n)=F(n-1)+4(n-1)+18/28/202413另外一种结
4、论另外一种结论: :nZn = 2n ( 2n + 1 ) / 2 + 1 - 2nZn = 2n ( 2n + 1 ) / 2 + 1 - 2n= 2 n2 n + 1= 2 n2 n + 1为什么为什么? ?8/28/202414总结：递推求解的基本方法：总结：递推求解的基本方法：n首先，确认：能否容易的得到简单情况的解？首先，确认：能否容易的得到简单情况的解？n然后，假设：规模为然后，假设：规模为N-1N-1的情况已经得到解决。的情况已经得到解决。n最后，重点分析：当规模扩大到最后，重点分析：当规模扩大到N N时，如何枚时，如何枚举出所有的情况，并且要确保对于每一种子举出所有的情况，并且
5、要确保对于每一种子情况都能用已经得到的数据解决。情况都能用已经得到的数据解决。n强调：强调：1 1、编程中的空间换时间的思想、编程中的空间换时间的思想2 2、并不一定只是从、并不一定只是从N-1N-1到到N N的分析的分析8/28/202415问题的提出：问题的提出： 设有设有n n条封闭曲线画在平面上，而任条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。闭曲线把平面分割成的区域个数。思考题：平面分割方法思考题：平面分割方法8/28/20241
6、6F(1)=2F(1)=2F(n)=F(n-1)+2(n-1)F(n)=F(n-1)+2(n-1)简单分析简单分析11324123465781234567108911121314n=1n=1n=2n=2n=3n=3n=4n=428/28/202417在在2n2n的长方形方格中的长方形方格中, ,用用n n个个1212的骨牌铺满方格的骨牌铺满方格, ,例如例如n=3n=3时时, ,为为2323方格，骨牌的铺放方案有三种方格，骨牌的铺放方案有三种( (如如图图), ), 输入输入n ,n ,输出铺放方案的总数输出铺放方案的总数思考题（思考题（20462046）：）：8/28/202418有有1n1
7、n的一个长方形，用的一个长方形，用1111、1212、1313的骨牌铺的骨牌铺满方格。例如当满方格。例如当n=3n=3时为时为1313的方格（如图），此时用的方格（如图），此时用1111，1212，1313的骨牌铺满方格，共有四种铺法。的骨牌铺满方格，共有四种铺法。 输入：输入： n n（0=n=300=n3)F(n)=F(n-1)+F(n-2)+F(n-4) (n3)然后就是对然后就是对n=3 n=3 的一些特殊情况的处理了，的一些特殊情况的处理了，显然：显然：F(0)=1F(0)=1 ( (没有人也是合法的，这个可以特没有人也是合法的，这个可以特殊处理，就像殊处理，就像0 0的阶乘定义为的
8、阶乘定义为1 1一样一样) ) F(1)=1F(1)=1 F(2)=2 F(3)=4F(2)=2 F(3)=48/28/202426不容易系列之不容易系列之(3)(3) LELE LELE的的RPGRPG难题难题有排成一行的个方格，用红有排成一行的个方格，用红(Red)(Red)、粉、粉(Pink)(Pink)、绿、绿(Green)(Green)三色涂每个格子，每格涂三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要求的涂法尾两格也不同色求全部的满足要求的涂法. .附加题（看看效果）：附加题（看看效果）：8/28/20
9、2427某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。 附加题：附加题：14651465不容易系列之一不容易系列之一8/28/202428分析思路：分析思路：1 1、当、当N=1N=1和和2 2时，易得解，假设时，易得解，假设F(N-1)F(N-1)和和F(N-2)F(N-2)已经得到，重点分析下面的情况：已经得到，重点分析下面的情况：4 4、后者简单，只能是没装错的那封和第、后者简单，只能是没装错的那封和第N N封封交换信封，没装错的那封可以是前面交换信封，没装错的那封可以是前面N-1N-1封封中的任意一个，故中的任意一个，故= F(N-2)
10、* (N-1)= F(N-2) * (N-1)3 3、前者，对于每种错装，可从、前者，对于每种错装，可从N-1N-1封信中任封信中任意取一封和第意取一封和第N N封错装，故封错装，故=F(N-1)*(N-1)=F(N-1)*(N-1)2 2、当有、当有N N封信的时候，前面封信的时候，前面N-1N-1封信可以有封信可以有N-1N-1或者或者 N-2 N-2封错装封错装8/28/202429得到如下递推公式：得到如下递推公式：基本形式：d1=0; d2=1递归式：dn= (n-1)*( dn-1 + dn-2)这就是著名的错排公式这就是著名的错排公式8/28/202430课后任务：课后任务：DIYDIY在线作业在线作业: : 201003ACM程序设计在线作业程序设计在线作业（3）递推求解递推求解 8/28/202431Welcome to HDOJWelcome to HDOJThank Thank You You 8/28/202432
