3.3 递推算法思想

递推算法是很常用的算法思想,在数学计算等方面有着广泛的应用。递推算法适合有着明显公式规律的场合。

3.3.1 递推算法基本思想

递推算法是一种理性思维模式的代表,其根据已有的数据和关系,逐步推导而得到结果。递推算法的执行过程如下:

(1)根据已知结果和关系,求解中间结果。

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

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

3.3.2 递推算法实例

递推算法是基本的算法思想,常用于数学相关的场合。下面通过一个简单的数学例子来分析递推算法的应用。

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

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

1.递推算法

先来分析一下兔子产仔问题。逐月分析每月的兔子对数。

第1个月:1对兔子;

第2个月:1对兔子;

第3个月:2对兔子;

第4个月:3对兔子;

第5个月:5对兔子;

……

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

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

这里,初始第1个月的兔子数为F1=1,第2个月的兔子数为F2=1。

可以通过递归公式来求解。为了通用性的方便,可以编写一个算法,用于计算斐波那契数列问题。并按照这个思路来编写相应的兔子产仔问题的求解算法,代码示例如下:

在上述代码中,输入参数为经历的时间,即月数。程序中通过递归调用来实现斐波那契数列的计算。

2.地推算法求解兔子产仔问题

根据上述通用的兔子产仔问题算法,可以求解任意该类问题。下面给出完整的兔子产仔问题求解程序代码:

【程序3-2】

在该程序中,首先由用户输入时间,即月数。然后调用fibonacci方法求解计算兔子产仔问题。最后输出结果。执行该程序,用户输入12,执行结果如图3-2所示。可见,经过12个月的时间,共有144对兔子。

图3-2 执行结果