LightOJ1234Harmonic Number调和级数+欧拉常数 / 直接打表

In mathematics, the n^th harmonic number is the sum of the reciprocals of the first n natural numbers:

In this problem, you are given n, you have to find H_n.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10⁸).

Output

For each case, print the case number and the n^th harmonic number. Errors less than 10^-8 will be ignored.

Sample Input

90000000

99999999

100000000

Sample Output

Case 1: 1

Case 2: 1.5

Case 3: 1.8333333333

Case 4: 2.0833333333

Case 5: 2.2833333333

Case 6: 2.450

Case 7: 2.5928571429

Case 8: 2.7178571429

Case 9: 2.8289682540

Case 10: 18.8925358988

Case 11: 18.9978964039

Case 12: 18.9978964139

解法一：

^{调和级数(即f(n))至今没有一个完全正确的公式，但欧拉给出过一个近似公式}^：

^当^{n很大时：}

f(n)≈ln(n)+C+1(2*n)

^{欧拉常数值：C≈}^{0.57721566490153286060651209}

^{c++ math库中，log即为ln。}

^{当n很小时：}

^{直接求，此时公式不是很准。}

 1 #include<stdio.h>
 2 #include<cmath>
 3 #include<string.h>
 4 typedef long long ll;
 5 using namespace std;
 6 
 7 const double c=0.57721566490153286060651209;
 8 //f(n)≈ln(n)+C+1/(2*n)
 9 
10 double sum[1000200];
11 
12 void fn()
13 {
14     sum[1]=1.0;
15     for(int i=2; i<=100200; i++)
16     {
17         sum[i]=sum[i-1]+1.0/(i*1.0);
18     }
19 }
20 int main()
21 {
22     fn();
23     int t;
24     scanf("%d",&t);
25     int n,tt=1;
26     while(t--)
27     {
28         scanf("%d",&n);
29         if(n<=100200)
30             printf("Case %d: %.10lf\n",tt++,sum[n]);
31         else
32         {
33             double x=log(n)+c+1.0/(2.0*n);
34             printf("Case %d: %.10f\n",tt++,x);
35         }
36     }
37     return 0;
38 }

View Code

解法二：

如果公式记不住可以选择打表，10e8全打表必定MLE，而每40个数记录一个结果，即分别记录1/40,1/80,1/120,...,1/10e8，这样对于输入的每个n，最多只需执行39次运算，大大节省了时间，空间上也够了。（可以学习一下这种每40个数记录一个结果的思想，免去了执行很大运算量的操作。）

 1 #include<stdio.h>
 2 #include<cmath>
 3 #include<string.h>
 4 typedef long long ll;
 5 using namespace std;
 6 
 7 double a[2800010];
 8 
 9 void fn()
10 {
11     double sum=0.0;
12     for(int i=1; i<100000001; i++)
13     {
14         sum+=1.0/i;
15         if(i%40==0)
16         {
17             a[i/40]=sum;
18         }
19     }
20 }
21 int main()
22 {
23     fn();
24     int t;
25     scanf("%d",&t);
26     int n,tt=1;
27     while(t--)
28     {
29         scanf("%d",&n);
30         double ans=a[n/40];
31         for(int i=40*(n/40)+1; i<=n; i++)
32         {
33             ans+=1.0/i;
34         }
35         printf("Case %d: %.10f\n",tt++,ans);
36     }
37     return 0;
38 }

View Code

参考博客：https://www.cnblogs.com/shentr/p/5296462.html