- Java常用算法手册(第3版)
- 宋娟
- 925字
- 2021-03-29 11:50:35
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 执行结果