求调和级数部分和达到给定目标值的最小项数,通过简单循环累加并利用浮点数比较即可解决。
OJ: roj
题目 ID: 5024
难度:入门
标签:模拟循环结构
创建: 2026-10-08 22:29
更新: 2026-10-08 22:29
形式化题目
给定一个正整数
数据范围:
正解
思路
本题求的是调和级数部分和(Harmonic number) double 将当前的和与目标整数
具体过程:
- 维护一个变量
sum_h表示当前部分和,初始化为;维护一个计数器 n,初始化为。 - 只要
sum_h < m,就继续循环。 - 循环内部将
n自增,并将 累加到 sum_h。 - 当
sum_h累加到退出循环时, n即为所求的最小值。
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:23
# update_at: 2026-10-08 22:23
import sys
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
m = next(data) # 目标值:求最小的 n 使 1 + 1/2 + ... + 1/n >= m
# 与 C++ 解同阶:逐项累加直到部分和 >= m,按分母顺序加是数值上最稳的次序。
# 必须写 1.0 / n,1 / n 会得到 0。
sum_h = 0.0
n = 0
while sum_h < m:
n += 1
sum_h += 1.0 / n
print(n)
if __name__ == "__main__":
solve()cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 22:23
* update_at: 2026-10-08 22:23
*/
#include <iostream>
using namespace std;
typedef long long ll;
ll m; // 目标值:求最小的 n 使 1 + 1/2 + ... + 1/n >= m
double sum_h; // 当前调和级数部分和 H_n
ll n; // 当前已经累加到的项数(也是分母)
void solve() {
// 逐项累加,直到部分和达到 m;退出时 n 就是最小的合法项数。
// 注意必须做实数除法:写成 1 / n 会按整数截断成 0,循环永不结束。
// m <= 11 时 n 最大 33617,double 的累积误差(~1e-10)远小于
// H_n 跨过整数 m 时的最小间隙(~1e-5),比较不会误判。
while (sum_h < m) {
n++;
sum_h += 1.0 / n;
}
cout << n << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (cin >> m) {
solve();
}
return 0;
}复杂度
- 时间复杂度:迭代
次,其中 ,故循环迭代次数为 。对于 , ,循环执行常数级别次,非常快。 - 空间复杂度:
,仅需常数个辅助变量。
总结
这是一道经典的循环模拟题,有几个非常值得注意的关键点和易错坑:
- 整数除法陷阱:在累加
时,如果误写成 1 / n(即整数除法),则除了外,其余结果全被截断为 。这会导致程序在 时永远无法达到条件,陷入死循环。必须写成 1.0 / n来执行实数除法。 - 比较运算符的严谨性:如果将判断条件从
sum_h < m误写为sum_h <= m,在的边界点时,第一次循环 成立,导致多加一次输出 2(正确答案应为)。必须严格按照题意,当部分和未达到 时才继续累加,使用 <。 - 边界与数据覆盖:
时,答案为 。测试点 problem1.in恰好覆盖了这个边界值;problem10.in覆盖了最大的,答案为 ;数据集合中实际包含 ,缺少 (不过这属于出题者的选点自由,非缺陷)。 - 浮点精度安全性的【定量】论证(核心关键):
朴素累加使用
double是否安全,正确的判定逻辑不是比较「误差」与「步长」,因为当 刚好跨过整数 时,决定它有没有被误判的关键是「它距离整数 有多远」,即跨界间隙 。 通过多路严格核对(包括使用精确有理数LCM顺序扫描、二分加上80位Decimal高精度计算等验证手段,对 进行全量穷举),我们得到了确切的量化结果: double在真值处的最大累积绝对误差约为 2.969e-14(发生在 , 处)。 - 在这11个点中,跨界间隙
的全局最小值为 1.204e-5(发生在 时, 从下方逼近11的距离)。 - 比较发现,安全裕度达到了
。 累积误差比间隙小了8个数量级。这充分证明了在 范围内使用 double是绝对安全可靠的。事实上,间隙裕度大到连使用float也能顺利通过。此外,double、long double与 Kahan 补偿求和这三种实现方式,对算出的结果都完全一致。