LightOJ 1234 Harmonic Number 调和级数部分和

2023-01-05 09:44:01

题目链接：http://lightoj.com/volume_showproblem.php?problem=1234

Sample Input

Sample Output

Case :

Case : 1.5

Case : 1.8333333333

Case : 2.0833333333

Case : 2.2833333333

Case : 2.450

Case : 2.5928571429

Case : 2.7178571429

Case : 2.8289682540

Case : 18.8925358988

Case : 18.9978964039

Case : 18.9978964139

分析：这个是高数的东西发散 n足够大时它无穷大直接公式解。

1.虽然输出五花八门，但是不用管它，精度能保证在10 ^-8就没问题，直接用%.10lf 即可；

2. n的范围是10^8，肯定不能正常跑，但是我们有公式，不怕，前面10000个可以正常打表，后面的我们就用公式，再说了，这个公式能成立，本来就是在n比较大的时候，公式如下： r为常数，r=0.57721566490153286060651209（r就是欧拉常数）。

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

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long LL;

 #define INF 0x3f3f3f3f

 #define N 12000

 #define mod 1000000007

 #define R 0.57721566490153286060651209///R就是欧拉常数

 double a[N];

 int main()

 {

     int T,k,i,x;

     double sum=0.0;

     a[]=;

     for(i=;i<=;i++)

         a[i]=a[i-]+1.0/i;

     scanf("%d", &T);

     k=;

     while(T--)

     {

         printf("Case %d: ", k++);

         scanf("%d", &x);

         if(x<=)

             printf("%.10f\n", a[x]);

         else

         {

             sum=log(x+)+R-1.0/(*x);

             printf("%.10f\n", sum);

         }

     }

     return ;

 }

 /*sum=log(n+1)+R-1.0/(2*n);*/

有大神说:可以思维逆转，让我们用另一种思路再去看这个题目。

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

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long LL;

 #define INF 0x3f3f3f3f

 #define N 2100000

 #define MAXN 100000000

 #define mod 1000000007

 #define R 0.57721566490153286060651209///R就是欧拉常数

 double a[N];

 int main()

 {

     int T,k,i,x,c;

     double sum=0.0;

     a[]=;

     c=;

     for(i=;i<=MAXN;i++)

     {

          sum+=1.0/i;

          if(i%==)

             a[c++]=sum;

     }

     scanf("%d", &T);

     k=;

     while(T--)

     {

         scanf("%d", &x);

         int num=x/;

         double s;

         s=a[num];

         for(i=*num+;i<=x;i++)

         s+=1.0/i;

        printf("Case %d: %.10f\n", k++, s);

     }

     return ;

 }

 /*sum=log(n+1)+R-1.0/(2*n);*/

码农公寓

相关文章