黄海同学的忧郁

NC21664. 黄海同学的忧郁

描述

黄海同学准备在新生赛后举办一个女装展，他一共准备了n件女装，每i件女装放在第i个柜橱里面。

然而麻烦的是熊孩纸齐齐忍不住把女装全部试了一遍，黄海同学十分生气，要求齐齐把女装放回原位，而熊孩纸齐齐却将第一件女装随便放进一个橱柜就跑路了。黄海同学无奈只得把女装一一归位，而他又懒得去那么多橱柜中把第一件女装找出来，于是他把第2件女装到第n件女装依次放回原来的柜橱，如果当前柜橱已经放了女装，那么黄海同学就会随机把这件女装放进一个柜橱。

最后他想知道，正确归位的女装件数的期望。

输入描述

输入一个正整数n(n<=1000000)，代表女装的数目

输出描述

输出题目所求的期望

设选手输出为a，标准输出为b，若 $\frac{|a-b|}{\max(1,b)}<10^{-6}$ ，则视选手输出正确答案。

示例1

输入:

输出:

1.5000000

说明:

齐齐有1/3的概率将第一件女装放进第1个柜橱，此时黄海同学将第2、3件女装分别放进第2、3个柜橱，归位的女装数为3

齐齐1/3有的概率将第一件女装放进第2个柜橱，此时对第2件女装，黄海同学有1/2的概率将它放进第1个柜橱，而第三件女装则放进第3个柜橱，归位的女装数为1；黄海同学又有1/2的概率将它放进第3个柜橱，将第三件女装放进第1个柜橱，归位的女装数为0

齐齐还有1/3的概率将第一件女装放进第3个柜橱，黄海同学就先将第2件女装放进第2个柜橱，将第三件女装放进第一个柜橱，归位女装数为1

故期望为1/3*3+1/3*1/2*1+1/3*1/2*0+1/3*1=1.5

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 14ms, 内存消耗: 384K, 提交时间: 2018-12-10 16:59:02

double get(int n){
    double sget=0,nget=0;
    int i;
    for(i=1;i<=n;i++){
        nget=sget/i+i/2.0-0.5;
        sget+=nget;
    }
	return 1.0/n+nget;
}
main(){
	int n,i;
	scanf("%d",&n);
    printf("%f",get(n));
}

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 484K, 提交时间: 2018-12-08 19:31:44

#include<cstdio>
double n,i,x;
signed main(){
    scanf("%lf",&n);
    for(i=1;i<n;i++) x+=i/(i+1);
    printf("%.9lf",x+1/n);
}

C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 356K, 提交时间: 2018-12-08 18:04:22

#include<cstdio>
double n,i,x;
signed main(){
	scanf("%lf",&n);
	for(i=1;i<n;i++) x+=i/(i+1);
	printf("%.9lf",x+1/n);
}

上一题

下一题

详情