第14章递推与递归 递推是计算机数值计算中的重要算法，递推的思路是通过数学推导，将复杂的运算化 解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。 递归算法在可计算性理论中占有重要地位，也是算法设计中的比较巧妙的方法，它写 出的程序较简短，可以使某些看起来不易解决的问题变得容易解决，在程序设计中常常有 着独特的作用。 14.1递推 14.1.1递推思想 以我们已经比较熟悉的Fibonacei数列问题为例，在该问题的条件中，最前面两项是已 知的，即FT1=0,F21。第二项之后的每一项都是前面相邻两项的和，即：>2时有F[nF F[-1+F-2引。在这样的条件下，我们可以根据所给定的初始值以及相邻项之间的关系， 依次求得F3队、F[4、F.后面每一项的值。 在这类问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有 一定的关联关系，这种关联关系一般是通过一个特定的关系式来表示。求解这类问题时我 们就从初始的一个或若干数据项（比如这里的F0,F2)出发，通过类似于FF F-1+F[n-2]这样特定的关系式逐步推进，从而得到最终结果。这种求解问题的方法叫“递 推法”。 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用 于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知 条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之 间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决 递推法有两种形式，其中已知初始值，通过递推关系式求出最终结果的递推方式称为 顺推法：己知最终结果，通过递推关系式求出初始值的递推方式称为倒推法。无论顺推还 是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简 单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了 通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。 一般说来 可以将递推算法看成是一种特殊的迭代算法。（在解题时往往还把递推问题表现为迭代形 式，用循环处理。所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值， 每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方 法称为迭代。)
第 14 章 递推与递归 递推是计算机数值计算中的重要算法，递推的思路是通过数学推导，将复杂的运算化 解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。 递归算法在可计算性理论中占有重要地位，也是算法设计中的比较巧妙的方法，它写 出的程序较简短，可以使某些看起来不易解决的问题变得容易解决，在程序设计中常常有 着独特的作用。 14.1 递推 14.1.1 递推思想 以我们已经比较熟悉的 Fibonacci 数列问题为例，在该问题的条件中，最前面两项是已 知的，即 F[1]=0，F[2]=1。第二项之后的每一项都是前面相邻两项的和，即：n>2 时有 F[n]= F[n–1]+F[n–2]。在这样的条件下，我们可以根据所给定的初始值以及相邻项之间的关系， 依次求得 F[3]、F[4]、F[5].后面每一项的值。 在这类问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有 一定的关联关系，这种关联关系一般是通过一个特定的关系式来表示。求解这类问题时我 们就从初始的一个或若干数据项（比如这里的 F[1]=0，F[2]=1）出发，通过类似于 F[n]= F[n–1]+F[n–2]这样特定的关系式逐步推进，从而得到最终结果。这种求解问题的方法叫“递 推法”。 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用 于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知 条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之 间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决。 递推法有两种形式，其中已知初始值，通过递推关系式求出最终结果的递推方式称为 顺推法；已知最终结果，通过递推关系式求出初始值的递推方式称为倒推法。无论顺推还 是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简 单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了 通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来 可以将递推算法看成是一种特殊的迭代算法。（在解题时往往还把递推问题表现为迭代形 式，用循环处理。所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值， 每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方 法称为迭代。）
14.1.2求解递推关系的方法 有一类问题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如 下简捷的递推关系式： f=g(fn1)或者fn1=g(fn) 这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或最终结果） 入手，一步步地按递推关系式递推，直至求出最终结果（或初始值）。很多程序就是按这样 的方法逐步求解的。如果对一个问题，我们要是能找到后一项数与前一项数的关系并清楚 其起始条件（或最终结果），相对就比较容易解决，让计算机一步步计算就是了。让高速的 计算机从事这种重复运算，可真正起到“物尽其用”的效果。 递推分倒推法和顺推法两种形式，两者的分析思路如图14.1所示： 由题意（或递推关系）确定初始值： 由题意（或递推关系）确定最终结果[： 求出顺推关系式g(f小： 求出倒推关系式f=g(): 输出顺推结果： 输出倒推结果： a顺推 b逆推 图14.1顺推与逆推 由此可见，递推算法的时间复杂度一般为O(),不管是顺推还是逆推的问题，除了 小部分问题的初始条件（或最终结果）在问题描述中明确给定外，其余大多数问题都需要我 们通过对问题的分析与化简而确定，其递推式更需要对实际问题的仔细梳理与归纳分析而 得到，因此解决递推问题的基础是问题分析与归纳。 14.13递推关系的建立 解决递推类型问题有三个重点：一是如何建立正确的递推关系式，二是递推关系有何 性质，三是递推关系式如何求解。 其中核心问题是如何建立递推关系。建立递推关系的关键在于寻找第项与前面（或后 面)几项的关系式，以及初始项的值（或最终结果值）。它不是一种抽象的概念，而是针对某 一具体题目或一类题目而言的。 下面我们通过一些比较经典的递推问题实例，来进一步展示问题中递推关系的建立、 边界条件的获取以及在此基础上递推求解过程的实现。 2
2 14.1.2 求解递推关系的方法 有一类问题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如 下简捷的递推关系式： fn = g ( fn-1 ) 或者 fn-1 = g '( fn ) 这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件(或最终结果) 入手，一步步地按递推关系式递推，直至求出最终结果(或初始值)。很多程序就是按这样 的方法逐步求解的。如果对一个问题，我们要是能找到后一项数与前一项数的关系并清楚 其起始条件(或最终结果)，相对就比较容易解决，让计算机一步步计算就是了。让高速的 计算机从事这种重复运算，可真正起到“物尽其用”的效果。 递推分倒推法和顺推法两种形式，两者的分析思路如图 14.1 所示： 由此可见，递推算法的时间复杂度一般为 O(n)，不管是顺推还是逆推的问题，除了一 小部分问题的初始条件(或最终结果)在问题描述中明确给定外，其余大多数问题都需要我 们通过对问题的分析与化简而确定，其递推式更需要对实际问题的仔细梳理与归纳分析而 得到，因此解决递推问题的基础是问题分析与归纳。 14.1.3 递推关系的建立 解决递推类型问题有三个重点：一是如何建立正确的递推关系式，二是递推关系有何 性质，三是递推关系式如何求解。 其中核心问题是如何建立递推关系。建立递推关系的关键在于寻找第 n 项与前面(或后 面)几项的关系式，以及初始项的值(或最终结果值)。它不是一种抽象的概念，而是针对某 一具体题目或一类题目而言的。 下面我们通过一些比较经典的递推问题实例，来进一步展示问题中递推关系的建立、 边界条件的获取以及在此基础上递推求解过程的实现。 由题意(或递推关系)确定最终结果 fn； 求出倒推关系式 fi-1=g' (fi)； 从最终结果 fn出发进行倒推: for(i=n;,i>1;i-) fi-1←g' (fi)； 输出倒推结果 fl； 求出顺推关系式 fi=g(fi-1)； 从边界条件 f1 出发进行顺推: for(i=2;,i<=n;i++) fi←g(fi-1)； 输出顺推结果 fn； a. 顺推 b. 逆推 图 14.1 顺推与逆推 由题意(或递推关系)确定初始值 f1；
14.2递推设计实例 14.2.1简单Hanoi塔问题 【例14.1】Hanoi塔移动次数问题 Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大 图142 Hanoi塔移动次数 到小依次套在a柱上，如图14.2所示 要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘： (2)圆盘只能在三个柱上存放： (3)在移动时程中，不允许大盘压小盘 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？ 分析： 设hm为n个盘子从a柱移到c柱所需移动的盘次。下面从最简单情况开始讨论： (1)当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h=1。 (2)当n=2时，分为以下三个过程 首先，将a柱上面的小盘子移动到b柱上去： 然后，将大盘子从a柱移到c柱： 最后，将b柱上的小盘子移到c柱上。 共记3个盘次，故h2=3。 (3)依次类推，当a柱上有nn>2)个盘子时，也分为以下三个过程： 首先，借助c柱把上面的n-1个盘子移动到b柱上，需要移动h个盘次： 然后，把a柱最下面的盘子移动到c柱上，需要移动1个盘次： 最后，借助a柱把b柱上的n-1个盘子移动到c柱上，需要移动hm1个盘次： 总共移动h1+1+ha1个盘次。 归纳： 由以上分析可得到 ∫递推关系式： hm-2hm-1+1(>-2) 递推边界条件：h=1 3
3 14.2 递推设计实例 14.2.1 简单 Hanoi 塔问题 【例 14.1】Hanoi 塔移动次数问题 Hanoi 塔由 n 个大小不同的圆盘和三根木柱 a，b，c 组成。开始时，这 n 个圆盘由大 到小依次套在 a 柱上，如图 14.2 所示。 要求把 a 柱上 n 个圆盘按下述规则移到 c 柱上： （1）一次只能移一个圆盘； （2）圆盘只能在三个柱上存放； （3）在移动过程中，不允许大盘压小盘。 问将这 n 个盘子从 a 柱移动到 c 柱上，总计需要移动多少个盘次？ 分析： 设 hn为 n 个盘子从 a 柱移到 c 柱所需移动的盘次。下面从最简单情况开始讨论： （1） 当 n=1 时，只需把 a 柱上的盘子直接移动到 c 柱就可以了，故 h1=1。 （2） 当 n=2 时，分为以下三个过程： 首先，将 a 柱上面的小盘子移动到 b 柱上去； 然后，将大盘子从 a 柱移到 c 柱； 最后，将 b 柱上的小盘子移到 c 柱上。 共记 3 个盘次，故 h2=3。 （3） 依次类推，当 a 柱上有 n(n>2)个盘子时，也分为以下三个过程： 首先，借助 c 柱把上面的 n-1 个盘子移动到 b 柱上，需要移动 hn-1 个盘次； 然后，把 a 柱最下面的盘子移动到 c 柱上，需要移动 1 个盘次； 最后，借助 a 柱把 b 柱上的 n-1 个盘子移动到 c 柱上，需要移动 hn-1 个盘次； 总共移动 hn-1+1+hn-1 个盘次。 归纳： 由以上分析可得到： 递推关系式： hn=2hn-1+1 (n>=2) 递推边界条件： h1=1 a b c 图 14.2 Hanoi 塔移动次数
程序如下： #include #include #define N 64 int main() int i.n long lo ng h[N+1]; an(d) h11=1 for(i=2;i<=n;i++) h[i]=2*h[i-1]+1: for(i=l:i<=n:itt) printf ("311d\n",h[i]) return 0; 14.2.2捕鱼问题 【例14.2】捕鱼问题 A、B、C、D、E五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地 方睡着了。A第一个醒来，它将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回 家去了。B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E依次醒来，也都按同样的办法分鱼。问：五人至少合伙捕到多少条鱼？每个人醒 来后看到的鱼数是多少条： 分析： (1)数据表示： A、B、C、D、E五人的编号分别为1、2、3、4、5。定义整型数组fish,其中数组 元素fish[k]表示第k个人所看到的鱼数，即：fsh[山表示A看到的鱼数，fish[2]表示B所 看到的鱼数，依此类推。 (2)顺推关系及其局限： 如果试图用顺推的方式来求解的话，由题意可得到fish1]、fish[2]、fsh3引、fish4、 fish5]之间的如下关系： Eish[1]:A所看到的鱼数也是合伙捕到鱼的总数 fish[2]=(fish【1]-1)*4/5:B所看到的鱼 fish[3]=(fish[2]-1)*4/5:C所看到的鱼数 4
4 程序如下： #include #include #define N 64 int main() { int i,n; long long h[N+1]; scanf("%d",&n); h[1]=1; for(i=2;i<=n;i++) { h[i]=2*h[i-1]+1; } for(i=1;i<=n;i++) { printf("%lld\n",h[i]); } return 0; } 14.2.2 捕鱼问题 【例 14.2】捕鱼问题 A、B、C、D、E 五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地 方睡着了。A 第一个醒来，它将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回 家去了。B 第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E 依次醒来，也都按同样的办法分鱼。问：五人至少合伙捕到多少条鱼？每个人醒 来后看到的鱼数是多少条？ 分析： （1）数据表示： A、B、C、D、E 五人的编号分别为 1、2、3、4、5。定义整型数组 fish，其中数组 元素 fish[k]表示第 k 个人所看到的鱼数，即：fish[1]表示 A 看到的鱼数，fish[2]表示 B 所 看到的鱼数，依此类推。 （2）顺推关系及其局限： 如果试图用顺推的方式来求解的话，由题意可得到 fish[1]、fish[2]、fish[3]、fish[4]、 fish[5]之间的如下关系： fish[1]：A 所看到的鱼数也是合伙捕到鱼的总数。 fish[2]=(fish[1]–1)*4/5：B 所看到的鱼数 fish[3]=(fish[2]–1)*4/5：C 所看到的鱼数
fish[4]=(fish[3]-1)*4/5:D所看到的鱼数 fish[5]=(Eish【4]-1)*4/5:E所看到的鱼数 归纳成一般递推关系式即： fish[i]=(fish[i-1]-1)*4/5 1=2,3,5 这个公式适用于已知A看到的鱼数去推算B看到的鱼数，再推算C看到的鱼数，. 先枚举fsh)的值，如果fsh的值可以按照上面的顺推关系推出符合要求的fsh2]、 fish3引、fsh[4]、fish5],则此时的fish1]即为要求的最少鱼数。否则，如果给定的fish[1] 不能保证后续值能够完全推导出来，说明该值不符合要求，让fs[1]加1后再重新进行试 探，直到找到后续值能够完全推导出来的sh[)为止。 由于初始A看到的鱼数fsh[1]没有简洁的条件进行判断，只能从最小的正整数1开始 进行枚举，枚举的效率很低，因此用顺推的办法求解并不方便。 (3)逆推关系及求解时程 相对顺推米说，逆推求解可能更加简单方便。因为E醒来时所看到的鱼数最少，且有 较为简单的条件可以描述，所以可以试着从E看到的鱼数往前逆推，即先由E逆推D看到 的，再由D逆推C看到的， .,最后推出A所看到的。 此时sS)仍然表示E所看到的鱼数，根据题意该数应该满足被5整除后余1，即： fish[5j85=】 ish4]表示D所看到的鱼数，这个数既要满足： fish[4]-fish[5]*5/4+1 又要满足： f1sh[4185==1 按照同样的规律往回推导，与fish4一样，fish3)、fish2、fish1]也要满足如下的条 件，即： fish[i-1]=fish[i]*5/4+1(i=5,4,2) fish【i】&5==1 (i=5,4,.,1) 题目要求的fsh[1),可以根据上面的关系从fsh5)开始往前逆推。由于所求为最少的 鱼数，可以从满足条件的最小s5]值开始进行枚举，由题意可知E所看到的鱼数最少 为6条，即ish[5)的最小值为6，下面将ish[5)取值为6开始进行试探。如果当前fish) 的值可以依次求得的ish4、fish3小、fish[2小、sh,且所求均满足上述条件，则找到了 最少的鱼数。如果求得的某一个fsh们不满足条件，说明fsh5]的初值不合适，让fsh[5 增加5再试，直至可以递推到所有fsh[是整数且除以5之后的余数是1为止。 程序如下： #include int main() 5
5 fish[4]=(fish[3]–1)*4/5：D 所看到的鱼数 fish[5]=(fish[4]–1)*4/5：E 所看到的鱼数 归纳成一般递推关系式即： fish[i]=(fish[i–1]–1)*4/5 i=2，3，.，5 这个公式适用于已知 A 看到的鱼数去推算 B 看到的鱼数，再推算 C 看到的鱼数，. 先枚举 fish[1]的值，如果 fish[1]的值可以按照上面的顺推关系推出符合要求的 fish[2] 、 fish[3]、fish[4]、fish[5]，则此时的 fish[1]即为要求的最少鱼数。否则，如果给定的 fish[1] 不能保证后续值能够完全推导出来，说明该值不符合要求，让 fish[1]加 1 后再重新进行试 探，直到找到后续值能够完全推导出来的 fish[1]为止。 由于初始 A 看到的鱼数 fish[1]没有简洁的条件进行判断，只能从最小的正整数 1 开始 进行枚举，枚举的效率很低，因此用顺推的办法求解并不方便。 （3）逆推关系及求解过程 相对顺推来说，逆推求解可能更加简单方便。因为 E 醒来时所看到的鱼数最少，且有 较为简单的条件可以描述，所以可以试着从 E 看到的鱼数往前逆推，即先由 E 逆推 D 看到 的，再由 D 逆推 C 看到的，.，最后推出 A 所看到的。 此时 fish[5]仍然表示 E 所看到的鱼数，根据题意该数应该满足被 5 整除后余 1，即： fish[5]%5==1 fish[4]表示 D 所看到的鱼数，这个数既要满足： fish[4]=fish[5]*5/4+1 又要满足： fish[4]%5==1 按照同样的规律往回推导，与 fish[4]一样，fish[3]、fish[2]、fish[1]也要满足如下的条 件，即： fish[i–1]=fish[i]*5/4+1 （i=5，4，.，2） fish[i]%5==1 （i=5，4，.，1） 题目要求的 fish[1]，可以根据上面的关系从 fish[5]开始往前逆推。由于所求为最少的 鱼数，可以从满足条件的最小 fish[5]值开始进行枚举，由题意可知 E 所看到的鱼数最少 为 6 条，即 fish[5]的最小值为 6，下面将 fish[5]取值为 6 开始进行试探。如果当前 fish[5] 的值可以依次求得的 fish[4]、fish[3]、fish[2]、fish[1]，且所求均满足上述条件，则找到了 最少的鱼数。如果求得的某一个 fish[i]不满足条件，说明 fish[5]的初值不合适，让 fish[5] 增加 5 再试，直至可以递推到所有 fish[i]是整数且除以 5 之后的余数是 1 为止。 程序如下： #include int main()
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 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 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 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 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 个信封