1、4.1.1 递推法的设计思想递推法（recurrence method）是一种根据递推关系进行问题求解的方法，也是一种重要的数学方法，常用来进行序列计算。无论正推还是逆推，关键都是要找到递推关系式。递推法通过初始条件，根据递推关系式，按照一定的规律逐项进行计算，直至得到结果。递推法有正推和逆推两种形式（1）正推：从前向后递推，已知小规模问题的解递推到大规模问题的解；（2）逆推：从后向前递推，已知大规模问题的解递推到小规模问题的解。初始条件或是问题本身已经给定，或是通过对问题进行分析得到4.1.2 一个简单的例子猴子吃桃【问题】一只猴子摘了很多桃子，每天吃现有桃子的一半多一个，到第10天时只有一
2、个桃子，问原有桃子多少个？【想法】设 an 表示第 n 天桃子的个数，猴子吃桃问题存在如下递推式：int MonkeyPeach(int n)int i,num=1;for(i=n-1;i=1;i-)num=(num+1)*2;return num;【算法实现】由于每天的桃子个数依赖于前一天的桃子个数，属于逆推法。设函数MonkeyPeach实现猴子吃桃问题，变量num表示桃子的个数，程序如下：时间复杂度？O(n)4.1.2 一个简单的例子猴子吃桃v第 4 章 递推法4-2 数学问题中的递推法4.2.1 Fibonacci数列【想法】令 f(n)表示第 n 个月围栏中兔子的对数，第 1 个月有
3、 1 对，由于每对新兔子在第 2 个月以后才可以生兔子，因此，第 2 个月仍然有 1 对；第 n 个月时，那些在第 n-1 个月就在围栏中的兔子仍然存在，第 n-2 个月就在围栏中的每对兔子都会生出一对新兔子，即 f(n)=f(n-1)+f(n-2)。因此，有如下递推式：【问题】Fibonacci（斐波那契）数列是一个经典问题：把一对兔子（雌雄各 1 只）放到围栏中，从第 2 个月以后，每个月这对兔子都会生出一对新兔子，其中雌雄各 1 只，从第 2 个月以后，每对新兔子每个月都会生出一对新兔子，也是雌雄各 1 只，问一年后围栏中有多少对兔子？int Fibonacci(int n)int f,
4、f1=1,f2=1,i;for(i=3;i=n;i+)f=f1+f2;f2=f1;f1=f;return f;【算法实现】设函数Fibonacci求解第 n 个月兔子的对数，变量 f1 和 f2 分别存储第 n-1 和 n-2 个月兔子的对数，程序如下：时间复杂度？O(n)4.2.1 Fibonacci数列4.2.2 Catalan数列【问题】Catalan数列是欧拉在计算凸多边形的三角形剖分问题时得到的。在一个凸 n（n 3）边形中，通过插入内部不相交对角线将其剖分成一些三角形区域，问有多少种不同的分法？Catalan数列的前 5 项是1,2,5,14,42,。4.2.2 Catalan数列
5、【想法】凸 n 边形的顶点用 A1,A2,An 表示，取边 A1An，再取凸 n 边形的任一个顶点 Ak（2 k n-1），将 Ak 分别与 A1 和 An 连线得到三角形 T，则三角形 T 将凸 n 边形分成 R1、T 和 R2 三个部分，其中 R1 为凸 k 边形，R2 为凸 n-k+1 边形。定义 h(n)为凸 n 边形的三角形剖分方案数，则 R1 有h(k)种剖分方法，R2 有h(n-k+1)种剖分方法。补充定义h(2)=1，得到Catalan数列的递推关系式：int Catalan(int n)int cn+1=0,0,1,1,i,k,temp;for(i=4;i=n;i+)temp
6、=0;for(k=2;k 2 时，设第一封信装在第二个信封中，若第二封信装在第一个信封中，则剩下的即为 n-2 错排问题；若第二封信不装在第一个信封中，则剩下的即为 n-1 错排问题，设第一封信装不在第一个信封中，共有 n-1 种方法，得到如下递推关系式：4.3.1 伯努利错装信封问题int Bernoulli(int n)int i,b,b1=1,b2=0;for(i=3;i=n;i+)b=(i-1)*(b1+b2);b2=b1;b1=b;return b;【算法实现】设函数Bernoulli实现错排问题，变量 b1 和 b2 分别存储 n-1 和 n-2 错排数，程序如下：时间复杂度？O(
7、n)4.3.1 伯努利错装信封问题【问题】万花筒的初始形状如下图所示，其中的圆圈代表万花筒的闪烁点，每旋转一次万花筒形状就演变一次，演变的规则是在末端再生出同样的形状，求第 n 次旋转后有多少个闪烁点？【想法】每次旋转都是在上一次旋转的每个分支端点多了 2 个闪烁点4.3.2 旋转的万花筒【想法】设 Sn 表示第 n 次旋转的闪烁点个数，初始时有 4 个闪烁点，有 3 个分支端点，每次旋转都是在上一次旋转的每个分支端点又多了 2 个闪烁点，得到如下递推关系式：4.3.2 旋转的万花筒int Kale(int n)int i,lamps=4,addLamp=3;for(i=1;i=n;i+)ad
8、dLamp*=2;lamps+=addLamp;return lamps;【算法实现】设函数Kale实现旋转的万花筒，变量 lamps 表示上一次旋转后的闪烁点，变量 addLamp 表示当次旋转闪烁点的增量，程序如下：时间复杂度？O(n)4.3.2 旋转的万花筒v第 4 章 递推法4-4 拓展与演练4.4.1 整数划分【问题】对于一个大于 2 的整数 n，要求仅使用 2 的若干次幂的整数集合进行划分，使得集合中所有整数之和等于 n，问有多少种划分？【想法】列出一些整数的划分，寻找递推关系式：2：1,1,2（2种）3：1,1,1,1,2（2种）4：1,1,1,1,1,1,2,2,2,4（4种）
9、5：1,1,1,1,1,1,1,1,2,1,2,2,1,4（4种）6：1,1,1,1,1,1,1,1,1,1,2,1,1,2,2,1,1,4,2,2,2,2,4（6种）7：1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,1,4,1,2,2,2,1,2,4（6种）令 dn 表示对整数 n 进行 2 的幂次划分的集合个数，有如下递推关系式：int Devide(int n)int i,dn+1=0;d1=1;d2=2;for(i=3;i=n;i+)if(i%2!=0)di=di-1;else di=di-1+di/2;return dn;【算法实现】设函数Devid
10、e实现集合划分，数组 dn+1 表示对整数 n 进行 2 的幂次划分的集合数，程序如下：时间复杂度？O(n)4.4.1 整数划分4.4.2 捕鱼知多少【问题】五个人合伙夜间捕鱼，上岸时都疲惫不堪，各自在湖边的树丛中找地方睡觉了。清晨，第一个人醒来，将鱼分成 5 份，把多余的一条扔回湖中，拿自己的一份回家了；第二个人醒来，也将鱼分成 5 份，扔掉多余的一条鱼，拿自己的一份回家了；接着，其余三个人依次醒来，也都按同样的办法分鱼。问：5 个人至少共捕到多少条鱼？每个人醒来后看到多少条鱼？【想法】设五个人的编号为 0、1、2、3、4，数组 fish5 表示五个人醒来后看到的鱼数，则 fishi（0 i
11、 4）均满足被 5 整除后余 1。显然，5 个人合伙捕到的鱼数即是 A 醒来后看到的鱼数，第 i（1 i 4）个人醒来后看到鱼数 fishi 满足：fishi=(fishi-1 1)/5*4（i=1,2,3,4）4.4.2 捕鱼知多少【算法实现】采用正推法，fish0从 1 开始，每次增 5，依次考查fishn的所有元素是否满足被 5 整除后余 1，函数GetFish返回至少捕到多少条鱼，程序如下：int GetFish(int fish,int n)int i,flag=0;fish0=1;/从鱼数1开始正推 while(flag=0)fish0=fish0+5;for(i=1;i n;i+)/递推其他人看到的鱼数 fishi=(fishi-1-1)/5*4;if(fishi%5!=1)break;if(i=n)flag=1;return fish0;时间复杂度？
