2.2 递推算法思想

知识点讲解：光盘：视频讲解\第2章\递推算法思想.avi

与枚举算法思想相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案。

2.2.1 递推算法基础

递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推算法。

① 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。

② 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

2.2.2 实践演练——解决“斐波那契数列”问题

为了说明递推算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递推算法思想在编程过程中的基本应用。

实例2-3 使用顺推法解决“斐波那契数列”问题

源码路径 光盘\daima\2\shuntui.c

问题描述：斐波那契数列因数学家列昂纳多•斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

算法分析：以新出生的一对小兔子进行如下分析。

① 第一个月小兔子没有繁殖能力，所以还是一对。

② 2个月后，一对小兔子生下了一对新的小兔子，所以共有两对兔子。

③ 3个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是3对。

……

依次类推可以列出关系表，如表2-1所示。

表2-1 月数与兔子对数关系表

表中数字1,1,2,3,5,8……构成了一个数列，这个数列有个十分明显的特点：前面相邻两项之和，构成了后一项。这个特点的证明：每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，某月兔子的对数等于其前面紧邻两个月的和。

由此可以得出具体算法如下所示：

设臵初始值为F0=1，第1个月兔子的总数是F1=1。

第2个月的兔子总数是F2= F0+F1。

第2个月的兔子总数是F3= F1+F2。

第3个月的兔子总数是F4= F2+F3。

………

第n个月的兔子总数是Fn= Fn-2+Fn-1。

具体实现：根据上述问题描述，根据“斐波那契数列”的顺推算法分析，编写实现文件shuntui.c，具体实现代码如下所示。

          #include <stdio.h>
          #define NUM 13
          int main()
          {
          int i;
              long fib[NUM] = {1,1}; //定义一个拥有13个元素的数组，用于保存兔子的初始数据和每月的总数
          //顺推每个月的总数
          for(i=2; i<NUM; i++)
              {
          fib[i] = fib[i-1]+fib[i-2];
              }
          //循环输出每个月的总数
          for(i=0; i<NUM; i++)
              {
                printf("第%d月兔子总数：%d\n", i, fib[i]);
              }
          getch();
          return 0;
          }

执行后的效果如图2-4所示。

图2-4 “斐波那契数列”问题执行效果

2.2.3 实践演练——解决“银行存款”问题

一个实例不能说明递推算法思想的基本用法，接下来开始使用逆推算法解决“银行存款”问题。

实例2-4 使用逆推法解决“银行存款”问题

源码路径 光盘\daima\2\nitui.c

问题描述：母亲为儿子小Sun 4年的大学生活准备了一笔存款，方式是整存零取，规定小Sun每月月底取下一个月的生活费。现在假设银行的年利息为1.71%，请编写程序，计算母亲最少需要存入多钱？

算法分析：可以采用逆推法分析存钱和取钱的过程，因为按照月为周期取钱，所以需要将4年分为48个月，并分别对每个月进行计算。

如果在第48月后Sun大学毕业时连本带息要取1000元，则要先求出第47个月时银行存款的钱数：

第47月月末存款=1000/(1+0.0171/12)；

第46月月末存款=(第47月月末存款+1000)/(1+0.0171/12)；

第45月月末存款=(第46月月末存款+1000)/(1+0.0171/12)；

第44月月末存款=(第45月月末存款+1000)/(1+0.0171/12);

……

第2月月末存款=(第3月月末存款+1000)/(1+0.0171/12)；

第1月月末存款=(第2月月末存款+1000)/(1+0.0171/12)。

具体实现：编写实现文件nitui.c，具体实现代码如下所示。

        #include <stdio.h>
        #define FETCH 1000
        #define RATE 0.0171
        int main()
        {
            double corpus[49];
            int i;
            corpus[48]=(double)FETCH;
            for(i=47; i>0; i--)
            {
            corpus[i]=(corpus[i+1]+FETCH)/(1+RATE/12);
            }
            for(i=48; i>0; i--)
            {
              printf("%d月月末本利共计：%.2f\n", i, corpus[i]);
            }
            getch();
            return 0;
        }

执行后的效果如图2-5所示。

图2-5 “银行存款”问题执行效果