P1035.级数求和

题目描述

已知： $S_n= 1+1/2+1/3+…+1/nSn=1+1/2+1/3+…+1/n。显然对于任意一个整数KK，当nn足够大的时候，S_nSn大于KK。$

现给出一个整数 $151≤k≤15），要求计算出一个最小的nn；使得S_n>KSn>K。$

输入格式

一个正整数

输出格式

一个正整数

输入输出样例

输入

输出
2

我的代码:

#include<iostream>

using namespace std;

int main(){
    int a;
    scanf("%d",&a);
    double sum = 0.0000;//代码终极bug
    int n = 0;

    while(sum <= a){
        sum += 1.0/++n;
        // printf("%d
",sum);
    }

    printf("%d",n);
    return 0;
}

大佬的:

 1 在算模拟做法（做法1）的时间复杂度时，我想到了一种新的数论做法（做法2），检查了一遍题解发现没有这种做法，于是我写了这篇题解。
 2 
 3 1.模拟
 4 
 5 这种做法的思路是枚举nn从1开始，直到Sn>kSn>k结束，只需要一个循环即可实现。
 6 
 7 代码：
 8 
 9 #include<cstdio>
10 int main() {
11     int k,n=0;
12     scanf("%d",&k);
13     for(double Sn=0;Sn<=k;++n,Sn+=1.0/n);
14     printf("%d",n);
15     return 0;
16 }
17 空间复杂度O(1)O(1)
18 时间复杂度O(e^{k-gamma})O(e 
19 k−γ
20  )（求法见做法2）
21 
22 （如果那个gammaγ可以约去的话，应该是O(e^k)O(e 
23 k
24  )，但并不知道可不可以约去）
25 
26 2.数论（调和级数）
27 
28 关于调和级数的姿势，点这里。
29 
30 已知Sn=1+1/2+1/3+...+1/n=sum_{k=1}^{n}frac{1}{k}Sn=1+1/2+1/3+...+1/n=∑ 
31 k=1
32 n
33       
34 k
35 1
36      。
37 
38 明显地，SnSn为第nn个调和数。
39 
40 欧拉推导过求调和级数有限多项和的表达式为sum_{k=1}^{n}frac{1}{k}=ln(n+1)+gamma∑ 
41 k=1
42 n
43       
44 k
45 1
46      =ln(n+1)+γ，我们拿过来用即可。（gammaγ约等于0.5772156649）
47 
48 我们需要满足Sn>kSn>k，即满足ln(n+1)+gamma>kln(n+1)+γ>k，化简得n>e^{k-gamma}-1n>e 
49 k−γ
50  −1。
51 
52 我们只需求满足上式的最小的nn，所以n=e^{k-gamma}+0.5n=e 
53 k−γ
54  +0.5（四舍五入），即模拟做法的时间复杂度为O(e^{k-gamma})O(e 
55 k−γ
56  )。
57 
58 关于gammaγ（欧拉-马歇罗尼常数）的姿势，点这里。
59 
60 代码：
61 
62 #include<cstdio>
63 #include<cmath>
64 const double gamma=0.5772156649;
65 int main() {
66     int k,n;
67     scanf("%d",&k);
68     n=exp(k-gamma)+0.5;
69     printf("%d",n);
70     return 0;
71 }
72 空间复杂度O(1)O(1)
73 时间复杂度O(???)O(???)
74 （因为不知道math.h头文件中的exp函数的时间复杂度，所以不知道时间复杂度）
75 
76 未解决的问题
77 
78 1.时间复杂度O(e^{k-gamma})O(e 
79 k−γ
80  )中的gammaγ可不可以约去？
81 
82 2.math.h头文件中的exp函数的时间复杂度为多少？
83 
84 3.有dalao说gammaγ是极限意义下的，不能直接k-gammak−γ是什么意思？