级数求和

题意

求最小的正整数 $n$ ，使得

1 + \frac{1}{2} + \cdots + \frac{1}{n} > K.

思路

从第 $1$ 项开始逐项累加。变量 term 表示当前加入的是第几项，total 表示已经得到的级数和。

循环条件必须写为 total <= threshold：题目要求的是严格大于 $K$ ，当和恰好等于 $K$ 时还必须继续加入下一项。循环结束时的 term 就是最小答案。

代码

Python代码

python

1
2
3
4
5
6
7
8
9threshold = int(input())
total = 0.0
term = 0

while total <= threshold:
    term += 1
    total += 1 / term

print(term)

C++代码

cpp

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

int main(){
    int k;
    scanf("%d",&k);
    double sum = 0,kk = k;
    int i;
    for (i=1;1;i++){
        sum += 1.0/i;
        if( sum > k){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}

复杂度

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

总结

处理“最小位置使条件成立”时，先写清结束条件是否包含等号，能避免典型的边界错误。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结