第二章 递推算法

递推法的特点

一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

例题（递推）：

数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
   1、 一步可沿左斜线向下或右斜线向下走；
   2、 三角形行数小于等于100；
   3、 三角形中的数字为0，1，…，99；
   测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

思路：

从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设a[i][j]存放从i,j 出发到达n层的最大值，则a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1] 即为所求的数字总和的最大值。

代码：

#include<iostream>
using namespace std;
int main()
{
  int n,i,j,a[101][101];
  cin>>n;
  for(i=1;i<=n;i++)
   for(j=1;j<=i;j++)
     cin>>a[i][j];                             
  for(i=n-1;i>=1;i--)
   for(j=1;j<=i;j++)
   {
       if(a[i+1][j]>=a[i+1][j+1])  
           a[i][j]+=a[i+1][j];    
       else a[i][j]+=a[i+1][j+1];
   } 
　 cout<<a[1][1]<<endl; 
}

例题（斐波那契数列）

满足F1=F2=1，Fn=Fn-1+Fn-2的数列称为斐波那契数列（Fibonacci），

它的前若干项是1，1，2，3，5，8，13，21，34……求此数 列第n项（n>=3）。

即：f1=1（n=1）        f2=1（n=2）        fn=fn-1 + fn-2（n>=3）

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int f0=1,f1=1,f2;
    int n;
    cin>>n;
    for(int i=3;i<=n ++i)
    {
         f2=f0+f1;
         f0=f1;
         f1=f2;
    }
    printf("%d\n",f2);
    return 0;
}