ACM课件(lecture_03)递推.ppt

1、ACM程序设计,第三讲 递归求解,2020/9/28,2,先来看一个超级简单的例题:,有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？,如果所坐的不是5人而是n人，写出第n个人的年龄表达式。,2020/9/28,3,显然可以得到如下公式:,化简后的公式: F(n)=10+(n-1)*2,2020/9/28,4,再来一个简单题:2013,2020/9/28,5,2013 蟠桃记,第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，

2、到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？,分析,2020/9/28,6,第1天,第2天,第n天 剩余1个,？,倒数第1天,倒数第n-1天,倒数第n天,2020/9/28,7,递推公式?,F(n)=(F(n-1)+1)*2,斐波那契数列,1.问题描述： 斐波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数a，要求斐波那契数列中第a个数是多少。,2020/9/28,8,2020/9/28,9,Fibnacci 数列：,2. 输入数据 第一行是测试数据的组数n，后面跟着n行输入。每组测

3、试数据占1行，包括一个正整数a（1=a=20）。 3.输出要求 输出有n行，每行输出对应一个输入。输出应是一个正整数，为斐波那契数列中第a个数的大小。,4. 输入样例 4 5 2 19 1,2020/9/28,10,5. 输出样例 5 1 4181 1,解题思路,这个题目要求很明确，因为a的规模很小，所以递归调用不会产生栈溢出的问题。设第n项值为f(n)，则f(n)=f(n-1)+f(n-2)。已知f(1)=1，f(2)=1，则从第3项开始，可以用公式求。,2020/9/28,11,即：1、1、2、3、5、8、13、21、34,参考程序,2020/9/28,12,兔子繁殖问题（Fibnacci

4、）,问题描述： 有雌雄兔子一对，假定过两个月便可繁殖雌雄各一的一对小兔子。问过来n个月后共有多少对兔子。 （轻院ACM，Problem ID1055）,2020/9/28,13,2020/9/28,14,思考:,递推公式的伟大意义？,有了公式，人工计算的方法？,常见的编程实现方法？（优缺点？）,注意：如果你不能直接求出解析式，可 用迭代，但不要用递归,2020/9/28,15,用如下程序测试一下递归的次数(1113),#include int t=0; long f(int n) t+; if(n3)return 1; else return f(n-1)+f(n-2); int main()

5、 printf(%ldn,f(15); printf(函数调用次数：%dn,t); ,2020/9/28,16,简单思考题:,在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。,2020/9/28,17,是不是这个,F(1)=2; F(n) = F(n-1)+n;,化简后： F(n) = n(n+1)/2 +1;,第n条直线与前n-1条直线有n-1个交点，第n条直线被分成n条线段，每条线段将一个区域一分为二,2020/9/28,18,太简单了?,来个稍微麻烦一些的,2020/9/28,19,例:（2050）折线分割平

6、面,问题描述： 平面上有n条折线，问这些折线最多能将平面分割成多少块?,2020/9/28,20,输入输出样例,样例输入 1 2 样例输出 2 7,2020/9/28,21,思考2分钟:如何解决?,2020/9/28,22,分析,当第n个折线加入时，已有f(n-1)个平面，有2(n-1)条折线， 第n条折线将与这2(n-1)条折线构成4(n-1)个交点，将使平面多4(n-1)个区域，而第n条折线的顶点将使平面多一个区域 故： f(n)=f(n-1)+4(n-1)+1,2020/9/28,23,结论:,Fn = 2n ( 2n + 1 ) / 2 + 1 - 2n = 2 n2 n + 1,为什

7、么?,2020/9/28,24,总结：递推求解的基本方法：,首先，确认：能否容易的得到简单情况的解？,然后，假设：规模为N-1的情况已经得到解决。,最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。,强调： 1、编程中的空间换时间的思想 2、并不一定只是从N-1到N的分析,2020/9/28,25,编程中的空间换时间的思想,2013蟠桃记程序一 #include int main() int n,i,s; while(scanf(%d, ,2020/9/28,26,编程中的空间换时间的思想,2013蟠桃记程序二 #include int

8、 main() int n,i; int a31; a1=1; for(i=2;i30;i+) ai=(ai-1+1)*2; while(scanf(%d, ,2020/9/28,27,64位整数的使用,_int64 a60; printf(%I64dn,an),2020/9/28,28,问题的提出： 设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。,思考题：平面分割方法,2020/9/28,29,F(1)=2 F(n)=F(n-1)+2(n-1),简单分析,2020/9/28,30,某人写了n封信和n个信封

9、，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。,1465 不容易系列之一,2020/9/28,31,分析思路：,1、当N=1和2时，易得解，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：,4、后者简单，只能是没装错的那封和第N封交换信封，没装错的那封可以是前面N-1封中的任意一个，故有 F(N-2) * (N-1)种 两种情况相加F(N)= (N-1)(F(N-1)+F(N-2),3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故有F(N-1)*(N-1)种,2、当有N封信的时候，前面N-1封信可以有N-1或者 N-2封错装,2020/9/

10、28,32,得到如下递推公式：,基本形式：d1=0; d2=1递归式：dn= (n-1)*( dn-1 + dn-2),这就是著名的错排公式,2020/9/28,33,在2n的长方形方格中,用n个12的骨牌铺满方格, 例如n=3时,为23方格，骨牌的铺放方案有三种(如图), 输入n ,输出铺放方案的总数,思考题-骨牌铺方格（2046）,推理：,假设用arri表示2*i的方格一共有组成的方法数，我们知道arr1=1;arr2=2;arr3=3 假设已经知道了arri-1和arri-2,求arri,所谓arri,不过是在2*（i-1）的格子后边加上一格2*1的方格罢了，骨牌在这一格上横着放，竖着放

11、，如果前面i-1块已经铺好，则第i块只有一种铺法，就是竖着放，如果要横着放，也只有一种铺法，不过要求前面i-2块已经铺好！ 因此arri=arri-1+arri-2;,2020/9/28,34,2020/9/28,35,归纳分析,F(n-2),F(n-1),F(n)=f(n-1)+f(n-2),递推公式,f(1)=1, f(2)=2 f(n)=f(n-1)+f(n-2), 当n=3时,2020/9/28,36,2020/9/28,37,有1n的一个长方形，用11、12、13的骨牌铺满方格。例如当n=3时为13的方格（如图），此时用11，12，13的骨牌铺满方格，共有四种铺法。,输入： n（0=

12、n=30）; 输出： 铺法总数,再思考题：,2020/9/28,38,仔细分析最后一个格的铺法,发 现无非是用11,12,13三种铺法,很容易就可以得出： f(n)=f(n-1)+f(n-2)+f(n-3); 其中f(1)=1,f(2)=2,f(3)=4,典型例题,分析过程：,2020/9/28,39,最后一个思考题（有点难度）,1297 Childrens Queue,有n个人组成的队列，不能有单个女生排在队列中，要么没有女生，要么至少两个女生相邻。,N=4的情况： FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM,2020/9/28,40,分析过程（1）,设

13、：F(n)表示n个人的合法队列，则： 按照最后一个人的性别分析，他要么是男，要么是女，所以可以分两大类讨论： 1、如果n个人的合法队列的最后一个人是男，则对前面n-1个人的队列没有任何限制，他只要站在最后即可，所以，这种情况一共有F(n-1);,2020/9/28,41,2、如果n个人的合法队列的最后一个人是女，则要求队列的第n-1个人务必也是女生，这就是说，限定了最后两个人必须都是女生，这又可以分两种情况：,分析过程（2）,2020/9/28,42,2.1、如果队列的前n-2个人是合法的队列，则显然后面再加两个女生，也一定是合法的，这种情况有F(n-2);,分析过程（3）,2020/9/28

14、,43,2.2、但是，难点在于，即使前面n-2个人不是合法的队列（队尾是女生，她前面是男生），加上两个女生也有可能是合法的，当然，这种长度为n-2的不合法队列，不合法的地方必须是尾巴，就是说，这里说的长度是n-2的不合法串的形式必须是“F(n-4)+男+女”，这种情况一共有F(n-4).,分析过程（4）,2020/9/28,44,结论：,所以，通过以上的分析，可以得到递推的通项公式：F(n)=F(n-1)+F(n-2)+F(n-4) (n3)然后就是对n=3 的一些特殊情况的处理了，显然：F(0)=1 (没有人也是合法的，这个可以特殊处理，就像0的阶乘定义为1一样) F(1)=1 F(2)=2

15、 F(3)=4,2020/9/28,45,提示：,1297 用64位整数无法实现，要用数组模拟大整数才能实现,2020/9/28,46,2045 不容易系列之(3) LELE的RPG难题 有排成一行的个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要求的涂法.,附加思考题（1）：,2020/9/28,47,分析,此题公式为f(n)=f(n-1)+f(n-2)*2 (n=4)1.若前n-1合法，则首尾不同，再添1个时，只有1种方法；2.若前n-1不合法，而添1个时合法，即只是因为首尾相同引起的不合法，这样前n-2必定合法。此时第n个的添 加有2种方法。3.f(1)=3;f(2)=6;f(3)=6.至此，可得。,2020/9/28,48,1480_钥匙计数之二 一把钥匙有N个槽，2N26槽深为1，2，3，4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。 本题无输入 对2N26，输出满足要求的钥匙的总数。,附加思考题（2）：,2020/9/28,49,详见解题报告：, 仔细阅读，耐心