找滚木

NC220152. 找滚木

描述

NIT正在玩皇室战争,NIT需要一种叫滚木的卡牌。众所周知皇室战争一共有n(n<=100000)种卡牌，NIT每开一个宝箱就能得到一张卡牌（宝箱开到每种卡牌的概率都是一样的）。现在NIT有一个换卡币，当NIT有两张一样（种类相同）的卡牌时，NIT可以用换卡币和这张卡牌换到滚木这张卡牌。NIT很想知道期望开多少个宝箱就可以得到滚木这张卡牌。

输入描述

输入一个正整数n(n<=100000)表示皇室战争有多少张卡牌。

输出描述

输出一个小数，保留两位小数，表示期望开多少个宝箱可以拿到滚木这张卡。

示例1

输入:

输出:

1.50

说明:

有两种可能

1：NIT第一次开宝箱就拿到了滚木这张卡。一共开一个宝箱。

2：NIT第一次开宝箱没有拿到滚木，第二次要么拿到滚木要么拿到第一次拿到的卡牌，换到滚木。一共开两个宝箱。

所以期望(1+2)/2 = 1.5次拿到滚木

示例2

输入:

输出:

1.89

示例3

输入:

输出:

291.78

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

C(clang11) 解法, 执行用时: 6ms, 内存消耗: 1020K, 提交时间: 2021-05-03 15:06:23

#include <stdio.h>
const int Max=1000005;
double ans=0,f[Max];
int n;

int main() {
	scanf("%d",&n);
	f[0]=1;
	ans=1;
	for (int i=1;i<n;i++)
	{
		f[i]=f[i-1]*(double)(n-i)/n;
		ans+=f[i];
	}printf("%.2f",ans);
	return 0;
}

C++(clang++11) 解法, 执行用时: 7ms, 内存消耗: 396K, 提交时间: 2021-05-04 10:02:49

#include<cstdio>
signed main()
{
	int n;
	double ans=1,now=1;
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	now=now*(n-i)/n,ans=ans+now;
	printf("%.2lf",ans);
}

Python3(3.9) 解法, 执行用时: 47ms, 内存消耗: 6860K, 提交时间: 2021-05-03 08:57:56

n=int(input())
a=0
b=1
c=n
for i in range(1,n+1):
    a+=(b/c)*(i*i)
    b*=(n-i)
    c*=n
    if i==1600:
        break
print("%.2lf"%a)