Harmonic Number 调和级数

你的名字 2022-08-21 05:38 162阅读 0赞

今天做了一道关于调和级数的题目，之前接触有关级数的“神马”还是在高数上，当时只是研究了调和级数的发散还是收敛等关系，10^8那么大的数据正常跑肯定会超时不是，一直都不知道对于这个伟大的级数来说，还有一个计算它的公式，浅尝辄止了，不该，不该。。。今天特地去问了度娘，公式是能用，但是对于这个题目的数据来说，还是需要一点小技巧的，具体分析如下：

*Harmonic Number ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329\#problem/D][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_109329_problem_D]*

为了更方便看（还有后来者的搜索，(\*^\_\_^\*) 嘻嘻……），我还是把题面粘上吧！

*Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu  
Submit  
  
Status  
Description  
In mathematics, the nth 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 Hn.  
  
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 ≤ 108).  
  
Output  
For each case, print the case number and the nth harmonic number. Errors less than 10-8 will be ignored.  
  
Sample Input  
12  
1  
2  
3  
4  
5  
6  
7  
8  
9  
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*

题目不难，先看数据，***1.***虽然输出五花八门，但是不用管它，精度能保证在*10 ^-8*就没问题，直接用%.10lf 即可；***2.*** n的范围是*10^8*，肯定不能正常跑，但是我们有公式，不怕，前面10000个可以正常打表，后面的我们就用公式，再说了，这个公式能成立，本来就是在n比较大的时候，公式如下：![Center][] *r*为常数，*r=0.57721566490153286060651209*（r就是欧拉常数）。

特别注意，由于题目要求精度为*10^-8*，常数r也是前人推导出来的，然而也只推导了有限位数，所以正常利用这个公式，并不能达到精度要求，我们只好比较样例和我们自己输出的数据，增添一些可行的项，经尝试，在原公式的基础上，再减去一个***1.0/(2\*n)***恰好可以满足精度，也算是投机取巧了。实现代码如下：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    #define R 0.57721566490153286060651209
    
    double ans[10010];
    int main()
    {
        int t,n,casenum=0;
        double sum;
        ans[1]=1;
        for(int i=2; i<=10000; i++)
        {
            ans[i]=ans[i-1]+1.0/i;
        }
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            if(n<=10000)
            {
                printf("Case %d: ",++casenum);
                printf("%.10lf\n",ans[n]);
            }
            else
            {
                sum=log(n+1)+R-1.0/(2*n);
                printf("Case %d: ",++casenum);
                printf("%.10lf\n",sum);
            }
        }
        return 0;
    }

思维逆转，让我们用另一种思路再去看这个题目。

其实，如果只靠打表，而且是有技术含量的打表，也能很好的解决这个问题，既然*10^8*的表我们打不出来，但是200万的表我们还是能打的，这样一来，我们先平均分而且间隔着，每50个记录一个，先把分布在*10^8*数据中的值放在表里，真正计算时，我们便先找到距离我们的n最近的且小于n的在表中存过数据的一个数，然后再在这个数的基础上递推这往下算，这样一来，便大大降低了时间复杂度，太啰嗦了，还是看代码吧！

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    #define MAX 100000000
    
    double ans[2000100];
    int main()
    {
        int t,n,k;
        int casenum;
        casenum=0;
        double sum=0.0;
        k=0;
        ans[0]=0;
        for(int i=1;i<=MAX;i++)
        {
            sum+=1.0/i;
            if(i%50==0)
            {
                ans[++k]=sum;
            }
        }
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            int yushu=n%50;
            int num=n/50;
            double s;
            s=ans[num];
            for(int i=50*num+1;i<=n;i++)
            {
                s+=1.0/i;
            }
            printf("Case %d: %.10lf\n",++casenum,s);
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_109329_problem_D]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329#problem/D
[Center]: /images/20220731/dc1cee6ba4214c908791a89afeea6839.png