本文共 661 字，大约阅读时间需要 2 分钟。

本题需要用到欧拉常数和递推。

题意：有n个箱子，n把钥匙随机的放在里面，问打开所有箱子的期望。

解析：每种情况都相当于一个循环的置换个数。

循环置换个数求解：那么考虑f[i]为i个箱子的情况，f[i + 1]要么就是放在最后多一个循环，要么就是插入中间循环个数不变，对应的转移为f[i + 1] = (f[i] + 1) / i + f[i] * (i - 1) / i 化简得到f[i] = f[i - 1] + 1 / i 。即f[n] = 1 + 1/2 + ...+ 1/ n，是个调和级数。

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

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

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

#include 
   
    #include 
    
     #define N 1000005#define C 0.577215664901double a[N];int main(){	int n;	a[1] = 1;	for(int i = 2; i < N; i++)		a[i] = a[i-1] + 1.0 / i;	while(~scanf("%d", &n)){		double ans;		if(n < N)			ans = a[n];		else			ans = log(n) + C + 1/(2*n);		printf("%.4lf\n", ans);	}	return 0;}
    
   

转载地址：https://blog.csdn.net/zhj_fly/article/details/74486941 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！