C_C++常用数据结构和算法(八)递推算法思想

递推算法思想

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

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

示例

菲波那切数列(“兔子产仔”问题)

13世纪意大利数学家斐波那契的《算盘书》中记载了兔子产仔问题,其大意文如下:

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

解析

  • 第 1 个月:1 对兔子;
  • 第 2 个月:1 对兔子;
  • 第 3 个月:2 对兔子;
  • 第 4 个月:3 对兔子;
  • 第 5 个月:5 对兔子;
  • 。。。

由此可以看出,从第 3 个月开始,每个月的兔子总数等于前两个月兔子数的总和:

  • F(1) = 1
  • F(2) = 1
  • F(n) = F(n-2) + F(n -1), n >= 3

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#pragma mark -- 斐波那契数列求和
unsigned int Fibonacci(unsigned int count)
{
if (0 == count)
{
return 0;
}
if (1 == count || 2 == count)
{
return 1;
}
unsigned int one, two;
one = Fibonacci(count - 1);
two = Fibonacci(count - 2);
return one + two;
}

Demo下载

------ 本文结束 ------
欣赏此文?求鼓励,求支持!