题目来源
NOIP2002普及组 第一题
难度
题目
描述
已知:Sn=1+21+31+…+n1 。显然对于任意一个整数 k,当 n 足够大的时候,Sn>k。
现给出一个整数 kk,要求计算出一个最小的 nn,使得 Sn>k。
输入格式
一个正整数 k。
输出格式
一个正整数n。
输入输出样例
输入
1
输出
2
数据范围
对于 100% 的数据,1≤k≤15。
参考题解
前导知识
- for结构
算法分析
- 模拟
n从1开始枚举,直到Sn>k结束,只需要一个循环即可实现。
- 利用调和级数求和公式
Sn=1+1/2+1/3+…+1/n=∑k=1nk1=ln(n+1)+γ
γ叫作欧拉常数又称欧拉-马斯克若尼常数γ≈0.577215664901532860606512090082402431042159335。
我们需要满足Sn>k,即满足ln(n+1)+γ>k,化简得n>ek−γ−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;
}
|