C 語言經典面試題：分數數列求和（斐波那契數列變體）

題目描述

求數列前 20 項之和：

2/1, 3/2, 5/3, 8/5, 13/8, 21/13, ...

分子分母皆為斐波那契數列，第 n 項分子 = F(n+2)，分母 = F(n+1)。

C 語言實現

#include <stdio.h>

int main() {
    float numerator = 2.0f;   // 分子
    float denominator = 1.0f; // 分母
    float sum = 0.0f;
    int i = 0;
    float temp;

    while (i < 20) {
        sum += numerator / denominator;
        temp = numerator;
        numerator = numerator + denominator; // 下一項分子 = 當前分子 + 分母
        denominator = temp;                  // 下一項分母 = 當前分子
        i++;
    }
    printf("和: %g\n", sum);
    return 0;
}

運行結果

和: 32.6603

解析

利用兩個變量迭代更新分子分母，避免陣列存儲，空間複雜度 O(1)，時間複雜度 O(n)。