概率题-约妹子问题

[kumobot]

有 N 个妹子，每次随机约 1 个，求平均多少次才能把每个妹子都约到？

结果请保留 4 位小数。

1. 写出 N∈[1,10]的结果

2. 编程计算 N∈[1, 100000]的结果

[zhidian]

你没机会提交了，嗯……哈哈哈。

[kumobot]

@zhidian 别的论坛上看到的问题，并没有参加这个比赛，等结束以后可以分享一下思路。

[Vinty]

https://zh.wikipedia.org/wiki/%E8%B4%88%E5%88%B8%E6%94%B6%E9%9B%86%E5%95%8F%E9%A1%8C
这个差不多

[xujinkai]

这个有公式的 sigma N/i 好像

[blankme]

我怎么算出来是个发散的级数。。。

[snnn]

这叫奖券搜集问题

[Mistwave]

不能保证所有一定约到 只能保证概率

[starvedcat]

“约到”产生了歧义。。

[doctorlai]

@kumobot 哪个网站上看到的？求原题

[irainsoft]

还是换成抽奖吧，约妹子成功概率再高，现实情况也可能是很残酷的

[Tunar]

前提条件呢

[yalanaika]

约 <> 约到
这又不是小浣熊，每次都能给张卡的。

[cloudzhou]

f(n) = (1+2+3...+n)/(1*2*3*...*n)
迭代实现，1+2+3... 和 1*2*3 不用每次重复计算，可以使用上次计算结果

[Ahri]

Coupon collector's problem

[cloudzhou]

我的答案不对的，还没想好

[Valyrian]

约出第 1 个妹子的所需次数的期望是 1
约出第 2 个（不同）妹子所需次数的期望是 N/N-1，（因为每次概率是 N-1/N，几何分布)
约出第 3 个（不同）妹子所需次数的期望是 N/N-2
...
约出第 N 个（不同）妹子所需次数的期望是 N/1

所有期望相加就是全约出来的期望
N*(调和级数前 N 项的和)

[ebony0319]

@Vinty 总算破解了我小时候的未解之谜，我还以为这是一个未知数，因为好像从没有人收集完过。

[aev2ex]

@yalanaika 小浣熊都不保证每次都给一张卡😂

[inFinityzc]

https://www.zhihu.com/question/38331955/answer/102681833

[ipwx]

递推公式：
E[x(1)] = 1
E[x(k)] = (E[x(k-1)] + 1) * ((N-k+1)/N) + (E[x(k)] + 1) * ((k-1) / N)

整理：
E[x(k)] = E[x(k-1)] + N/(N-k+1)

得到：
E[x(N)] = N * sum(1/(N-k+1), k from 1 to N)

也就是 @Valyrian 的答案。