随机数生成器

· · 题解

直接设 work 函数返回的期望值构成数列 a

1$. $a_1=0 2$. $a_n=\sum\limits_{i=1}^n \frac{1}{n} (a_i+1)

式 2 中等号两边都存在 a_n 项，不妨把右边的那一项拆出来放到左边，就会变成这个样子：

\frac{n-1}{n} a_n=\frac{1}{n}\sum\limits_{i=1}^{n-1} a_i+1

继续化简

a_n=\frac{1}{n-1}\sum\limits_{i=1}^{n-1}a_i+\frac{n-1+1}{n-1}=\sum\limits_{i=1}^{n-1}a_i+1+\frac{1}{n-1}=a_{n-1}+\frac{1}{n-1}

结合 1 式，很容易得到数列 a 的通项公式：

a_n=\sum\limits_{i=2}^{n}\frac{1}{i-1}=\sum\limits_{i=1}^{n-1}\frac{1}{i}

这就是 O(n) 的递推式，但貌似仍然不足以通过此题。

于是涉及到另一个知识点，调和级数求和

由麦克劳林展开式可知：

\ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}.....

于是：

\ln(1+\frac{1}{x})=\ln(\frac{x+1}{x})=\frac{1}{x}-\frac{1}{2x^2}+\frac{1}{3x^3}-\frac{1}{4x^4}......

两边同时从 1 到 n 求和：

\ln(n+1)=\sum\limits_{i=1}^{n}\frac{1}{i}-\frac{1}{2}\sum\limits_{i=1}^{n}\frac{1}{i^2}+\frac{1}{3}\sum\limits_{i=1}^{n}\frac{1}{i^3}...... \sum\limits_{i=1}^{n}\frac{1}{i}=\ln(n+1)+\frac{1}{2}\sum\limits_{i=1}^{n}\frac{1}{i^2}-\frac{1}{3}\sum\limits_{i=1}^{n}\frac{1}{i^3}......

感兴趣的可以尝试证明下，后面那一坨是收敛的。提示：

\lim\limits_{n\to+\infty} \sum\limits_{i=1}^{n}{\frac{1}{i^2}}=\frac{\pi^2}{6}

很容易验证后面一坨的单调性，结合上式进行放缩，就可以通过单调有界法则来证明极限存在。不妨设极限为 C，于是调和级数求和就出来了：

\sum\limits_{i=1}^{n}\frac{1}{i}=\ln(n+1)+C

我们可以先用前一百万个数据算出 C，然后就能直接加自然对数了。。

实在不行上网搜搜复制下来就行

附代码：

#include <bits/stdc++.h>
using namespace std;
double C,sum;
int n;
int main(void)
{
    scanf("%d",&n);
    --n;
    if(n<=1e6)  {
        if(n==0) {
            printf("%.5lf\n",0);
            return 0;
        }
        for(int i=1;i<=n;i++)
            sum+=1.0/i;
        printf("%.5lf\n",sum+1);
        return 0;
    }
    for(int i=1;i<=1e6;i++)
        sum+=1.0/i;
    C=sum-log(1e6);
    printf("%.5lf",log(n)+C+1);
    return 0;
}