题意

分数序列首项为 $2/1$。若当前项为 $q_i/p_i$，则下一项满足 $q_{i+1}=q_i+p_i$、$p_{i+1}=q_i$。求前 $n$ 项之和。

思路

只需维护当前分子 numerator 和分母 denominator。先把当前分数加入 total，再用并行赋值更新为下一项：numerator, denominator = numerator + denominator, numerator。

并行赋值的右侧会先按旧值计算，所以不会在更新分子后误用新分子作为分母。

代码

Python代码

1
2
3
4
5
6
7
8
9term_count = int(input())
numerator, denominator = 2, 1
total = 0.0

for _ in range(term_count):
    total += numerator / denominator
    numerator, denominator = numerator + denominator, numerator

print(f"{total:.4f}")

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include <cstdio>


int main(){
    int n;
    scanf("%d",&n);
    double p = 1,q = 2;
    double sum = 0;
    int i;
    for (i=1;i<=n;i++){
        sum += q/p;
        double tq = q;
        q = q+p;
        p = tq;
    }
    printf("%0.4lf\n",sum);
    return 0;
}

复杂度

循环 $n$ 次，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

总结

递推题常常不必保存整个序列，保留生成下一项所需的少量状态即可。