题目来源

NOIP2002普及组 第一题

难度

题目

描述

已知：$S_n= 1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$ 。显然对于任意一个整数 $k$，当 $n$ 足够大的时候，$S_n>k$。

现给出一个整数 kk，要求计算出一个最小的 nn，使得 $S_n>k$。

输入格式

一个正整数 $k$。

输出格式

一个正整数$n$。

输入输出样例

输入

1

输出

2

数据范围

对于 $100\%$ 的数据，$1\le k \le 15$。

参考题解

前导知识

  1. for结构

算法分析

  1. 模拟

$n$从$1$开始枚举，直到$S_n>k$结束，只需要一个循环即可实现。

  1. 利用调和级数求和公式

$S_n=1+1/2+1/3+…+1/n=\sum_{k=1}^{n}\frac{1}{k}=\ln(n+1)+\gamma$

$\gamma$叫作欧拉常数又称欧拉-马斯克若尼常数$\gamma ≈0.57721 56649 01532 86060 65120 90082 40243 10421 59335$。

我们需要满足$S_n>k$，即满足$\ln(n+1)+\gamma>k$，化简得$n>e^{k-\gamma}-1$。

第二种算法仅作了解。

参考代码

算法1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include<iostream>
using namespace std;
int main(){
	double sum=0.0;
	int n = 1, k;
	cin >>k;
	while(1){
		sum +=	1.0/double(n);
		if(sum > k) break;
		n++;
	}
	cout << n << endl;
	return 0;
}

image