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。

示例代码

#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下载