HDU4986 Little Pony and Alohomora Part I
发布日期:2021-06-29 05:37:38
浏览次数:4
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月24日 15时22分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
webpack打包错误:Invalid configuration object. Webpack has been initialised using a configuration object
2019-04-29
TypeError: this.getOptions is not a function
2019-04-29
el-table 二维数组合并行
2019-04-29
js获取当月的天数
2019-04-29
多个相邻的盒子外边框合并的问题
2019-04-29
js实现复制功能
2019-04-29
UR5e机械臂运行一直阻塞在waitForServer
2019-04-29
ROS把pkg1下的某个头文件和源文件生成动态链接库供pkg2调用
2019-04-29
使用urdf_tutorial快速可视化urdf文件
2019-04-29
SQl 数据完整性(随堂博客)
2019-04-29
左连接、右连接、内连接
2019-04-29
MySQL DQL语句基础(随堂博客)
2019-04-29
MySQL基础练习
2019-04-29
利用MySQL进行数据复杂查询(1)
2019-04-29
利用MySQL进行数据复杂查询(2)
2019-04-29
MySQL 表与表之间的关系
2019-04-29
Python数据处理
2019-04-29
Java练习题(面向对象)
2019-04-29
Python 利用os和shutil复制系统文件
2019-04-29