【例4.7】最小n值

GitHub跳转原题关系图返回列表

求调和级数部分和达到给定目标值的最小项数,通过简单循环累加并利用浮点数比较即可解决。

OJ: roj

题目 ID: 5024

难度:入门

标签:模拟循环结构

创建: 2026-10-08 22:29

更新: 2026-10-08 22:29

形式化题目

给定一个正整数 mm,求满足不等式

1+12+13+⋯+1n≥m1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \ge m
的最小正整数 nn 的值。

数据范围: m≤11m \le 11。

正解

思路

本题求的是调和级数部分和(Harmonic number) Hn=∑i=1n1iH_n = \sum_{i=1}^n \frac{1}{i} 达到某个给定整数阈值 mm 的最小项数 nn。 根据调和数近似公式 Hn≈ln⁡n+γH_n \approx \ln n + \gamma,当 Hn=mH_n = m 时,所需的项数 n≈em−γn \approx e^{m - \gamma}。 当 m≤11m \le 11 时,最大值出现在 m=11m=11,对应的真值 n=33617n = 33617。 由于 nn 的规模很小(不超过几万次),我们可以直接用循环从 11 开始累加求 HnH_n,并用双精度浮点数 double 将当前的和与目标整数 mm 进行比较。

具体过程:

  1. 维护一个变量 sum_h 表示当前部分和,初始化为 00;维护一个计数器 n,初始化为 00。
  2. 只要 sum_h < m,就继续循环。
  3. 循环内部将 n 自增 11,并将 1n\frac{1}{n} 累加到 sum_h。
  4. 当 sum_h 累加到 ≥m\ge m 退出循环时,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;
}

复杂度

  • 时间复杂度:迭代 nn 次,其中 n≈em−γn \approx e^{m-\gamma},故循环迭代次数为 O(n)O(n)。对于 m≤11m \le 11,n≤33617n \le 33617,循环执行常数级别次,非常快。
  • 空间复杂度:O(1)O(1),仅需常数个辅助变量。

总结

这是一道经典的循环模拟题,有几个非常值得注意的关键点和易错坑:

  1. 整数除法陷阱:在累加 1n\frac{1}{n} 时,如果误写成 1 / n(即整数除法),则除了 n=1n=1 外,其余结果全被截断为 00。这会导致程序在 m≥2m \ge 2 时永远无法达到条件,陷入死循环。必须写成 1.0 / n 来执行实数除法。
  2. 比较运算符的严谨性:如果将判断条件从 sum_h < m 误写为 sum_h <= m,在 m=1m=1 的边界点时,第一次循环 H1=1≤1H_1=1 \le 1 成立,导致多加一次输出 2(正确答案应为 11)。必须严格按照题意,当部分和未达到 mm 时才继续累加,使用 <。
  3. 边界与数据覆盖:m=1m=1 时,答案为 11。测试点 problem1.in 恰好覆盖了这个边界值;problem10.in 覆盖了最大的 m=11m=11,答案为 3361733617;数据集合中实际包含 {1,2,3,4,5,6,8,9,10,11}\{1,2,3,4,5,6,8,9,10,11\},缺少 m=7m=7(不过这属于出题者的选点自由,非缺陷)。
  4. 浮点精度安全性的【定量】论证(核心关键): 朴素累加使用 double 是否安全,正确的判定逻辑不是比较「误差」与「步长 1n\frac{1}{n}」,因为当 HnH_n 刚好跨过整数 mm 时,决定它有没有被误判的关键是「它距离整数 mm 有多远」,即跨界间隙 min⁡∥Hn−m∥\min \|H_n - m\|。 通过多路严格核对(包括使用精确有理数LCM顺序扫描、二分加上80位Decimal高精度计算等验证手段,对 m=1..11m=1..11 进行全量穷举),我们得到了确切的量化结果:
    • double 在真值 nn 处的最大累积绝对误差约为 2.969e-14(发生在 m=10m=10,n=12367n=12367 处)。
    • 在这11个点中,跨界间隙 min⁡∥Hn−m∥\min \|H_n - m\| 的全局最小值为 1.204e-5(发生在 m=11m=11 时,H33616H_{33616} 从下方逼近11的距离)。
    • 比较发现,安全裕度达到了 1.204×10−52.969×10−14≈4.05×108\frac{1.204 \times 10^{-5}}{2.969 \times 10^{-14}} \approx \mathbf{4.05 \times 10^8}。 累积误差比间隙小了8个数量级。这充分证明了在 m≤11m \le 11 范围内使用 double 是绝对安全可靠的。事实上,间隙裕度大到连使用 float 也能顺利通过。此外,double、long double 与 Kahan 补偿求和这三种实现方式,对 m=1..11m=1..11 算出的结果都完全一致。