首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

概率题-约妹子问题

  •  
  •   kumobot · 2017-04-26 22:35:46 +08:00 · 3840 次点击
    这是一个创建于 956 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    结果请保留 4 位小数。

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

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

    23 回复  |  直到 2017-04-28 11:55:58 +08:00
        1
    zhidian   2017-04-26 22:51:08 +08:00
    你没机会提交了,嗯……哈哈哈。
        2
    kumobot   2017-04-26 22:54:34 +08:00
    @zhidian 别的论坛上看到的问题,并没有参加这个比赛,等结束以后可以分享一下思路。
        3
    Vinty   2017-04-26 23:17:40 +08:00   ♥ 3
        4
    xujinkai   2017-04-26 23:25:11 +08:00 via Android
    这个有公式的 sigma N/i 好像
        5
    blankme   2017-04-26 23:27:41 +08:00
    我怎么算出来是个发散的级数。。。
        6
    snnn   2017-04-27 00:13:43 +08:00 via Android
    这叫奖券搜集问题
        7
    Mistwave   2017-04-27 00:24:23 +08:00 via iPhone
    不能保证所有一定约到 只能保证概率
        8
    starvedcat   2017-04-27 01:15:55 +08:00
    “约到”产生了歧义。。
        9
    doctorlai   2017-04-27 01:22:03 +08:00
    @kumobot 哪个网站上看到的?求原题
        10
    irainsoft   2017-04-27 03:08:50 +08:00
    还是换成抽奖吧,约妹子成功概率再高,现实情况也可能是很残酷的
        11
    Tunar   2017-04-27 07:25:30 +08:00 via Android
    前提条件呢
        12
    yalanaika   2017-04-27 07:54:53 +08:00   ♥ 2
    约 <> 约到
    这又不是小浣熊,每次都能给张卡的。
        13
    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 不用每次重复计算,可以使用上次计算结果
        14
    Ahri   2017-04-27 08:12:53 +08:00
    Coupon collector's problem
        15
    cloudzhou   2017-04-27 08:13:32 +08:00
    我的答案不对的,还没想好
        16
    Valyrian   2017-04-27 08:19:28 +08:00   ♥ 1
    约出第 1 个妹子的所需次数的期望是 1
    约出第 2 个(不同)妹子所需次数的期望是 N/N-1,(因为每次概率是 N-1/N,几何分布)
    约出第 3 个(不同)妹子所需次数的期望是 N/N-2
    ...
    约出第 N 个(不同)妹子所需次数的期望是 N/1

    所有期望相加就是全约出来的期望
    N*(调和级数前 N 项的和)
        17
    ebony0319   2017-04-27 09:00:33 +08:00
    @Vinty 总算破解了我小时候的未解之谜,我还以为这是一个未知数,因为好像从没有人收集完过。
        18
    aev2ex   2017-04-27 10:17:33 +08:00
    @yalanaika 小浣熊都不保证每次都给一张卡😂
        19
    inFinityzc   2017-04-27 14:08:54 +08:00   ♥ 1
        20
    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 的答案。
        21
    zsdroid   2017-04-27 15:26:37 +08:00
    答案是 0,因为我没有妹子
        22
    xiaoyu233   2017-04-28 10:55:58 +08:00 via iPhone
    答案是 0,因为我没有妹子
        23
    zero1234888   2017-04-28 11:55:58 +08:00
    答案是 0,因为我没有妹子
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4319 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 29ms · UTC 03:17 · PVG 11:17 · LAX 19:17 · JFK 22:17
    ♥ Do have faith in what you're doing.