概率题-约妹子问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2775 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

结果请保留 4 位小数。

写出 N∈[1,10]的结果
编程计算 N∈[1, 100000]的结果

妹子

小数

结果

编程

23 条回复 • 2017-04-28 11:55:58 +08:00

zhidian

2017-04-26 22:51:08 +08:00

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

kumobot

2017-04-26 22:54:34 +08:00

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

Vinty

2017-04-26 23:17:40 +08:00

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

xujinkai

2017-04-26 23:25:11 +08:00 via Android

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

blankme

2017-04-26 23:27:41 +08:00

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

snnn

2017-04-27 00:13:43 +08:00 via Android

这叫奖券搜集问题

Mistwave

2017-04-27 00:24:23 +08:00 via iPhone

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

starvedcat

2017-04-27 01:15:55 +08:00

“约到”产生了歧义。。

doctorlai

2017-04-27 01:22:03 +08:00

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

irainsoft

2017-04-27 03:08:50 +08:00

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

Tunar

2017-04-27 07:25:30 +08:00 via Android

前提条件呢

yalanaika

2017-04-27 07:54:53 +08:00

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

cloudzhou

2017-04-27 08:02:09 +08:00

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

Ahri

2017-04-27 08:12:53 +08:00

Coupon collector's problem

cloudzhou

2017-04-27 08:13:32 +08:00

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

Valyrian

2017-04-27 08:19:28 +08:00

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

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

ebony0319

2017-04-27 09:00:33 +08:00

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

aev2ex

2017-04-27 10:17:33 +08:00

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

inFinityzc

2017-04-27 14:08:54 +08:00

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

ipwx

2017-04-27 14:59:40 +08:00

递推公式：
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 的答案。

zsdroid

2017-04-27 15:26:37 +08:00

答案是 0，因为我没有妹子

xiaoyu233

2017-04-28 10:55:58 +08:00 via iPhone

答案是 0，因为我没有妹子

zero1234888

2017-04-28 11:55:58 +08:00

答案是 0，因为我没有妹子