斐波那契分数序列求和算法与实现

1. 问题背景与需求分析

这道题目来自《算法笔记》的2.4章节，要求计算一个特殊分数序列的前20项之和。这个序列的特点是：分子为斐波那契数列，分母则是斐波那契数列向后移动一位的结果。具体来说，序列的第n项可以表示为fib(n+2)/fib(n+1)，其中fib(n)表示第n个斐波那契数。

在实际编程中，这类分数序列求和问题常见于算法竞赛和编程练习中，主要考察以下几个核心能力：

• 斐波那契数列的生成与性质理解
• 浮点数精度处理（特别是使用double类型的注意事项）
• 循环结构的正确使用
• 累加操作的实现技巧

提示：虽然题目只要求计算前20项，但理解这个序列的数学性质对后续解决更复杂的问题很有帮助。这个序列实际上会收敛于黄金比例(1+√5)/2 ≈ 1.618033988749895。

2. 斐波那契数列的实现方案

2.1 基本递归方法（不推荐）

最直观的方法是使用递归计算斐波那契数：

c复制long long fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

但这种方法存在严重问题：

• 时间复杂度O(2^n)，计算fib(20)需要约2^20=1,048,576次递归调用
• 重复计算严重，例如fib(5)会重复计算fib(3)多次
• 当n较大时（如n>40），运行时间会变得不可接受

2.2 迭代法（推荐方案）

更高效的方式是使用迭代法，时间复杂度O(n)，空间复杂度O(1)：

c复制long long fib(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

这种方法避免了递归带来的性能问题，是解决此类问题的标准做法。

2.3 动态规划法

也可以使用动态规划，将中间结果存储在数组中：

c复制long long dp[100] = {0};

long long fib(in