int fish[6]={1,1,1,1,1,1,i=0: do 1/让起看到的鱼数增5 (1=41>=1；1-) fish[i]-fish(i+1]*5/4+1; /计算第1人看到的鱼数 if (fish(i]851-1)breaki while(i>=1 ) f0r（1=1:1<=5:1++) printf("sd\n",fishlil)a return 0: 1 程序运行结果； 1312】 22496 31996 41596 51276 14.2.3 Fibonacci类问题 在所有的弟推关系中，Fibonacci数列应该是最为大家所熟悉的。Fibonacci数列的 代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”（又称 “Fibonacci问题”)，问题描述如下： 【例14.3】兔子繁殖问题（经典Fibonacci数列） 如果有一对刚出生的小兔，第三个月开始可以每一个月都生下一对小兔，而所生下的 每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，满一年时一 共可以繁殖成多少对兔子 分析： 用列举的方法可以很快找出本题的答案，第一个月，这对小兔还没有成年，只有这 对兔子。 第二个月，这对兔子成年，生了一对小兔，于是这个月共有2对(1+1=2)兔子。 第三个月，第一对兔子又生了一对兔子，其余小兔未成年。因此共有3对(1+2=3) 兔子。 第四个月，第一对免子义生了一对小兔，而在第一个月出生的小免也生下门了一对小兔， 其余小兔未成年。所以，这个月共有5对(2+3=5)兔子。 第五个月，第一对兔子以及第一、二两个月生下的兔子也都各生下了一对小兔。因此， 这个月连原先的5对兔子共有8对(3+5=8)兔子。 6
6 { int fish[6]={1,1,1,1,1,1},i=0; do { fish[5]=fish[5]+5; // 让 E 看到的鱼数增 5 for (i=4; i>=1; i-) { fish[i]=fish[i+1]*5/4+1; // 计算第 i 人看到的鱼数 if (fish[i]%5!=1) break; } } while( i>=1 ); for (i=1; i<=5; i++) printf("%d\n",fish[i]); return 0; } 程序运行结果： 1 3121 2 2496 3 1996 4 1596 5 1276 14.2.3 Fibonacci 类问题 在所有的递推关系中，Fibonacci 数列应该是最为大家所熟悉的。Fibonacci 数列的 代表问题是由意大利著名数学家 Fibonacci 于 1202 年提出的“兔子繁殖问题”(又称 “Fibonacci 问题”)，问题描述如下： 【例 14.3】兔子繁殖问题（经典 Fibonacci 数列） 如果有一对刚出生的小兔，第三个月开始可以每一个月都生下一对小兔，而所生下的 每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，满一年时一 共可以繁殖成多少对兔子？ 分析： 用列举的方法可以很快找出本题的答案，第一个月，这对小兔还没有成年，只有这一 对兔子。 第二个月，这对兔子成年，生了一对小兔，于是这个月共有 2 对（1+1=2）兔子。 第三个月，第一对兔子又生了一对兔子，其余小兔未成年。因此共有 3 对（1+2=3） 兔子。 第四个月，第一对兔子又生了一对小兔，而在第一个月出生的小兔也生下了一对小兔， 其余小兔未成年。所以，这个月共有 5 对（2+3=5）兔子。 第五个月，第一对兔子以及第一、二两个月生下的兔子也都各生下了一对小兔。因此， 这个月连原先的 5 对兔子共有 8 对（3+5=8）兔子
可列表如下： 表14-1兔子繁殖分月统计表 月份 大兔数1个月小兔数2个月小兔数 兔子总数 初始 0 1 0 1 0 0 1 1 0 3 1 1 1 3 2 2 1 5 5 3 3 2 8 6 5 5 3 13 7 8 8 5 21 8 13 13 8 9 21 21 13 55 10 34 34 21 89 11 55 55 34 144 1289 89 55 233 在上表各月具体数据分类的基础上，如何分析归纳得到Fibonacci数列一般项的递推 关系式？这是解决递推问题的核心。 不妨设满x个月共有兔子F,对，其中当月新生的兔子数目为N对。第x-1个月留下 的兔子数目设为0x对。则： Fx=Nd+Ox 而0=F, N,=O1=F2(即第x-2个月的所有兔子到第x个月都有繁殖能力了) 归纳： 由以上分析可得到： 厂递推关系式：FF+fx2(心=2) 递推边界条件：Fo0,F1=I 有了上面的递推关系式与边界条件，就不难写出其程序代码了，之前在介绍循环结构 与一维数组时，我们在这两部分都已经给出了程序代码，本节重点是与读者一起梳理问题 的分析过程与归纳方法，因此在此不再赘述代码。读者可以参考前面两章的代码，也可以 自行完成本问题代码的实现。 斐波那契数具有许多重要的数学知识，用途广泛，它引起了数学界的普遍关注，为了 促进对它的研究，在美国还专门出版了一本杂志叫做《斐波那契季刊》，登载对这个数列的 7
7 . 可列表如下： 表 14-1 兔子繁殖分月统计表 月份 大兔数 1 个月小兔数 2 个月小兔数 兔子总数 初始 0 1 0 1 1 0 0 1 1 2 1 1 0 2 3 1 1 1 3 4 2 2 1 5 5 3 3 2 8 6 5 5 3 13 7 8 8 5 21 8 13 13 8 34 9 21 21 13 55 10 34 34 21 89 11 55 55 34 144 12 89 89 55 233 在上表各月具体数据分类的基础上，如何分析归纳得到 Fibonacci 数列一般项的递推 关系式？这是解决递推问题的核心。 不妨设满 x 个月共有兔子 Fx 对，其中当月新生的兔子数目为 Nx 对。第 x-1 个月留下 的兔子数目设为 Ox 对。则： Fx=Nx+Ox 而 Ox=Fx-1， Nx=Ox-1=Fx-2 (即第 x-2 个月的所有兔子到第 x 个月都有繁殖能力了) 归纳： 由以上分析可得到： 递推关系式： Fx=Fx-1+Fx-2 (x>=2) 递推边界条件： F0=0，F1=1 有了上面的递推关系式与边界条件，就不难写出其程序代码了，之前在介绍循环结构 与一维数组时，我们在这两部分都已经给出了程序代码，本节重点是与读者一起梳理问题 的分析过程与归纳方法，因此在此不再赘述代码。读者可以参考前面两章的代码，也可以 自行完成本问题代码的实现。 斐波那契数具有许多重要的数学知识，用途广泛，它引起了数学界的普遍关注，为了 促进对它的研究，在美国还专门出版了一本杂志叫做《斐波那契季刊》，登载对这个数列的
研究成果和最新发现。与在数学领域一样，在程序设计求解过程中有许多与斐波那契数列 性质相同或相近的问题，可以按照上述的分析归纳方法找到解决问题的策略，下面再来看 几个具体问题，请读者仔细体会它们与经典斐波那契数列问题的异同。 【例14.4】母牛的故事 有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也 生一头小母牛。请编程实现在第年的时候，共有多少头母牛？ 分析： 初看起来问题比较复杂，由于小母牛出生的年份不同，计算下一年要出生的小牛的数 目不容易实现。但是程序设计的目的是要找到解决问题的规律，本问题有什么样的规律呢？ 首先，用数组f来存储第i年的母牛总数，则第n年的母牛总数为]。如果仔细思 考的话，的值只与两个值有关，一个是在本年之前就已经出生的母牛数目，另一个则 是在本年新出生的小母牛数目。 本年之前就已经出生的母牛数日，实际上就是前一年的母牛总数，即为-小。由于 每一头可以生育的母牛每年只生育一头小母牛，所以在本年新出生的小母牛数目，实际上 是到今年可以生育的母牛的数目。又因为每头小母牛从第四个年头才开始生育，所以今年 可以生有的母牛的数实际上就是三年前的母牛总数，即为-3). 归幼， 由以上分析可以得到递推公式： ntn-l+n-3](>=4) 当然，递推要有初始的边界条件，第一、二、三年的母牛总数是直接可以知道的，即： f【11=1: f[2]=2: f[31-3: 这样看起来，问题的解决就是一个与Fibonacci数列问题非常相近的方法了，因此不难 得到实现的程序，代码如下： #include <stdio.h> int main() int i,n; ong long int f[50] 3canf("d /从健盘输入计算母牛的年数 for(i=4;i<=n;i++) f[i]=f[i-3】+f[i-1]: printf("611d\n",f[n]); return 0; 8
8 研究成果和最新发现。与在数学领域一样，在程序设计求解过程中有许多与斐波那契数列 性质相同或相近的问题，可以按照上述的分析归纳方法找到解决问题的策略，下面再来看 几个具体问题，请读者仔细体会它们与经典斐波那契数列问题的异同。 【例 14.4】 母牛的故事 有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也 生一头小母牛。请编程实现在第 n 年的时候，共有多少头母牛？ 分析： 初看起来问题比较复杂，由于小母牛出生的年份不同，计算下一年要出生的小牛的数 目不容易实现。但是程序设计的目的是要找到解决问题的规律，本问题有什么样的规律呢？ 首先，用数组 f[i]来存储第 i 年的母牛总数，则第 n 年的母牛总数为 f[n]。如果仔细思 考的话，f[n]的值只与两个值有关，一个是在本年之前就已经出生的母牛数目，另一个则 是在本年新出生的小母牛数目。 本年之前就已经出生的母牛数目，实际上就是前一年的母牛总数，即为 f[n–1]。由于 每一头可以生育的母牛每年只生育一头小母牛，所以在本年新出生的小母牛数目，实际上 是到今年可以生育的母牛的数目。又因为每头小母牛从第四个年头才开始生育，所以今年 可以生育的母牛的数实际上就是三年前的母牛总数，即为 f[n–3)。 归纳： 由以上分析可以得到递推公式： f[n]=f[n–1]+f[n–3] (n>=4) 当然，递推要有初始的边界条件，第一、二、三年的母牛总数是直接可以知道的，即： f[1]=1； f[2]=2; f[3]=3； 这样看起来，问题的解决就是一个与 Fibonacci 数列问题非常相近的方法了，因此不难 得到实现的程序，代码如下： #include <stdio.h> int main() { int i,n; long long int f[50]; scanf("%d",&n); // 从键盘输入计算母牛的年数 f[1]=1;f[2]=2;f[3]=3; for(i=4; i<=n; i++) { f[i]=f[i-3]+f[i-1]; } printf("%lld\n",f[n]); return 0; }
再来看一个表面上似乎与菲波那切数列无关的问题： 【例14.5】骨牌问题 在2×n的长方形方格中，用n个1×2的骨牌铺满方格，输入n,输出铺放方案的 总数 例如=3时，为2×3方格，骨牌的铺放方案有三种，如图14.3所示。 图14.3n=3时骨牌的铺放方案 分析： 既然是求长度为时的骨牌铺放方案，不妨从比较简单的情况开始来寻找问题解决的 规律，仍然用fn来表示当长度为n时的铺放方案。 当n=1时，只能是一种铺法，即1=1，如图14.4(a)所示。 当n=2时，只能有两种铺法，即2]=2，如图14.4b、图14.4(c)所示。 (3) 图144n1与n-2时骨牌的铺放方案 当=3时，如图14.3所示，可以有三种铺法，即33。这三种铺放方法可以采用如 下的步骤分析得到： =3时，第一块骨牌的铺法只有两种可能，横铺或者竖铺，即： (1)横铺方式：在第一格横放一个骨牌，此时剩余两格，在两格内铺放骨牌有2]种 铺法。 (2)竖铺方式：在第一、二格竖放两个骨牌，此时剩余一格，在一格内铺放骨牌有山 种铺法。 由此可知，=3时的骨牌铺法为首块骨牌横铺方式的铺法与竖铺方式的铺法之和，即： f3=2]+f1=2+1=3. 同理，对于一般的值，其第一块骨牌的铺法也只有两种可能，横铺或者竖铺，即： 9
9 再来看一个表面上似乎与菲波那切数列无关的问题： 【例 14.5】 骨牌问题 在 2×n 的长方形方格中，用 n 个 1×2 的骨牌铺满方格，输入 n，输出铺放方案的 总数。 例如 n=3 时，为 2×3 方格，骨牌的铺放方案有三种，如图 14.3 所示。 图 14.3 n=3 时骨牌的铺放方案 分析： 既然是求长度为 n 时的骨牌铺放方案，不妨从比较简单的情况开始来寻找问题解决的 规律，仍然用 f[n]来表示当长度为 n 时的铺放方案。 当 n=1 时，只能是一种铺法，即 f[1]= 1，如图 14.4(a)所示。 当 n=2 时，只能有两种铺法，即 f[2]= 2，如图 14.4(b)、图 14.4(c)所示。 （a） （b） （c） 图 14.4 n=1 与 n=2 时骨牌的铺放方案 当 n=3 时，如图 14.3 所示，可以有三种铺法，即 f[3]= 3。这三种铺放方法可以采用如 下的步骤分析得到： n=3 时，第一块骨牌的铺法只有两种可能，横铺或者竖铺，即： （1）横铺方式：在第一格横放一个骨牌，此时剩余两格，在两格内铺放骨牌有 f[2]种 铺法。 （2）竖铺方式：在第一、二格竖放两个骨牌，此时剩余一格，在一格内铺放骨牌有 f[1] 种铺法。 由此可知，n=3 时的骨牌铺法为首块骨牌横铺方式的铺法与竖铺方式的铺法之和，即： f[3]=f[2]+f[1]=2+1=3。 同理，对于一般的 n 值，其第一块骨牌的铺法也只有两种可能，横铺或者竖铺，即：
(1)横铺方式：若第一格横放一个骨牌，此时剩余-1格，在-1格放n-1个骨牌有 n-1种铺法。 (2)竖铺方式：若第一、二格竖放两格骨牌，此时剩余n-2格，在-2格放n-2个骨 牌有n-2]种铺法。 归纳： 由以上分析可知，块骨牌的铺法为首块骨牌横铺方式的铺法与竖铺方式的铺法之和， 即： 厂递推关系式 :f[m=f[n-1]+f[m-2】(n>2） 气L递推边界 :f[1]=1,f[2]=2 由此可以很容易得到如下的程序： #include<stdio.h> int main() int i,n; long long int f[50]; f[0]=1: f[1]=-2: scanf ("d",&n); for(i=2;i<n;i++) f[i]=f[i-1]+f[i-2] printf("$11d\n",f[n-1]) 14.2.4错排公式 【例14.6】错排公式 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封， 共有多少种不同情况？ 分析： 这个问题初看起来比较复杂，直接入手不容易找到解决问愿的递推规律。但有了前面 例14.5骨牌问题的问题分析与归纳过程后，可以试着采用类似的方法来推导。 对n封信以及n个信封各自按照从1到n进行编号，当n个编号的信放在n个编号位 置的信封时，信的编号与信封位置编号各不对应的方法数用表示，那么-就表示-】 个编号的信放在-1个编号位置的信封，各不对应的方法数，其他类推。 第一步，把第n封信放在一个信封，比如第k个信封(k≠n),一共有n-1种方法。 第二步，放编号为k的信，这时有两种情况： (1)把它放到第n个信封，那么，对于剩下的-2封信，需要放到剩余的n-2个信封 10
10 （1）横铺方式：若第一格横放一个骨牌，此时剩余 n–1 格，在 n–1 格放 n–1 个骨牌有 f[n–1]种铺法。 （2）竖铺方式：若第一、二格竖放两格骨牌，此时剩余 n–2 格，在 n–2 格放 n–2 个骨 牌有 f[n–2]种铺法。 归纳： 由以上分析可知，n 块骨牌的铺法为首块骨牌横铺方式的铺法与竖铺方式的铺法之和， 即： 递推关系式 ：f[n]=f[n-1]+f[n-2] （n>2） 递推边界 ：f[1]=1,f[2]=2 由此可以很容易得到如下的程序： #include<stdio.h> int main() { int i,n; long long int f[50]; f[0]=1; f[1]=2; scanf("%d",&n); for(i=2;i<n;i++) { f[i]=f[i-1]+f[i-2]; } printf("%lld\n",f[n-1]); } 14.2.4 错排公式 【例 14.6】 错排公式 某人写了 n 封信和 n 个信封，如果所有的信都装错了信封。求所有的信都装错信封， 共有多少种不同情况？ 分析： 这个问题初看起来比较复杂，直接入手不容易找到解决问题的递推规律。但有了前面 例 14.5 骨牌问题的问题分析与归纳过程后，可以试着采用类似的方法来推导。 对 n 封信以及 n 个信封各自按照从 1 到 n 进行编号，当 n 个编号的信放在 n 个编号位 置的信封时，信的编号与信封位置编号各不对应的方法数用 f[n]表示，那么 f[n–1]就表示 n–1 个编号的信放在 n–1 个编号位置的信封，各不对应的方法数，其他类推。 第一步，把第 n 封信放在一个信封，比如第 k 个信封（k≠n），一共有 n–1 种方法。 第二步，放编号为 k 的信，这时有两种情况： （1）把它放到第 n 个信封，那么，对于剩下的 n–2 封信，需要放到剩余的 n–2 个信封