题目来源

NOIP2002普及组 第一题

难度

题目

描述

已知:Sn=1+12+13++1nS_n= 1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n} 。显然对于任意一个整数 kk,当 nn 足够大的时候,Sn>kS_n>k

现给出一个整数 kk,要求计算出一个最小的 nn,使得 Sn>kS_n>k

输入格式

一个正整数 kk

输出格式

一个正整数nn

输入输出样例

输入

1

输出

2

数据范围

对于 100%100\% 的数据,1k151\le k \le 15

参考题解

前导知识

  1. for结构

算法分析

  1. 模拟

nn11开始枚举,直到Sn>kS_n>k结束,只需要一个循环即可实现。

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

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

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

我们需要满足Sn>kS_n>k,即满足ln(n+1)+γ>k\ln(n+1)+\gamma>k,化简得n>ekγ1n>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