递推算法所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
从问题出发逐步推到已知条件，此种方法叫逆推。
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

例一满足F₁=F₂=1, F_n=F_n-1+F_n-2的数列称为斐波那契数列(Fibonacci)，它的前若干项是1，1，2，3，5，8，13，21，34…..求此数列第n项(n>=3)。
即： f₁=1 (n=1)
f₂=1 (n=2)
f_n=f_n-1+f_n-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;
}

例二、数塔问题，如图1所示为一个数字三角形。请编一个程序计算从顶到底的路径中，使该路径所经过的数字总和最大，只要求输出总和。
测试数据通过键盘逐行输入，如上例数据应以如图2所示格式输入。

#include <iostream>
using namespace std;

int main(){
    int n,i,j,a[100][100];
    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];
    return 0;
    
}

洛谷：P1216

P1216

Previous Topic

Back to Lesson

Next Topic