[xsy2962]作业

题意：$f_0=1-\dfrac1e,f_n=1-nf_{n-1}$，求$f_n(n\leq10000)$，保留四位小数

这题代码只有⑨行但是题解很神...

因为递推式中有乘法，所以直接按题目来推肯定会爆精度

我们先把数字存为$a+\dfrac be$的形式然后打个表，发现$f_n$会越来越小且趋于$0$，所以直接从一个相当大的$n$开始倒推（此时可以认为$f_n=0$），$f_{n-1}=\dfrac{1-f_n}n$，因为只有除法和减法所以不会爆精度

对$f_n$的估计，题解给出了一个神仙构造...

对$x^ne^x$分部积分，得到$\int x^ne^x\mathrm dx=x^ne^x-n\int x^{n-1}e^x\mathrm dx$，这和$f_n$的递推式极其相似

因为式中有变量$x$，所以我们要确定积分上下界以削除$x$，我们也想把积分号外的项削到与$n$无关，不妨取$x\in[0,1]$并得到$\int_0^1x^ne^x\mathrm dx=e-n\int_0^1x^{n-1}e^x\mathrm dx$，即$\dfrac1e\int_0^1x^ne^x\mathrm dx=1-n\dfrac1e\int_0^1x^{n-1}e^x\mathrm dx$，比较递推式，立得$f_n=\dfrac1e\int_0^1x^ne^x\mathrm dx$，$f_0=1-\dfrac1e$满足此式

知道这个式子后什么都简单了==很明显它是单调递减而且趋于$0$的...所以以上的做法没有问题

#include<stdio.h>
int main(){
	int n,i;
	double s;
	s=0;
	scanf("%d",&n);
	for(i=7000000;i>n;i--)s=(1-s)/i;
	printf("%.4lf",s);
}

巴特西

[xsy2962]作业

最新文章

热门文章