递推算法

概念与定义

递推算法是一种理性思维模式的代表，其根据已有的数据和关系，逐步推导而得到结果，即从下到上，从已知到未知解决问题。

（1）算法特点：

一个问题的求解需一系列的计算

在已知条件和所求问题之间总存在着某种相互联系的关系

找到前后过程之间的数量关系（即递推式），分为顺推和逆推。

无论顺推还是逆推，其关键是要找到递推式

（2）关键：

用递推算法解决问题时，关键是找到递推式以及边界条件（临界条件）

顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

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

递推算法的执行过程如下∶

1、根据已知结果和关系，求解中间结果。

2、判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确的答案。

递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有明确的计算公式可以遵循，因此常常采用递推算法实现。

案例分析

数学里面的斐波那契数列便是一个使用递推算法的经典例子。13世纪意大利数学家斐波那契的《算盘书》中记载了典型的兔子产仔问题，其大意如下：

如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1月份出生，3月份才可产仔。那么假定一年内没有产生兔子死亡事件，那么 1年后共有多少对兔子呢?

我们先来分析一下兔子产仔问题。我们来逐月看一次每月的兔子对数：

♦第一个月：1对兔子;

♦第二个月：1对兔子;

♦第三个月：2对兔子;

♦第四个月：3对兔子;

♦第五个月：5对兔子;

从上面可以看出，从第个3月开始，每个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式如下：

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

这里，初始第一个月的兔子数为F1=1，第二个月的兔子数为F2=1。

代码实现：

#include <iostream>

using namespace std;

int a[10005];

int main()

{

int n;

cin >> n;

a[1] = 1; //初始化第一个月数量为 1，已知条件

a[2] = 1; //初始化第二个月数量为 1，已知条件

for (int i=3; i<= n;i++)

{

a[i]=a[i-1]+a[i-2]; // 当前月等于前两个月之和

}

cout<<a[n];

return 0;

}