首页 > 试题广场 >

集齐所有瓶盖所买汽水瓶数的期望，与以下哪个结果最为接近？

[单选题]
某次买可乐集瓶盖活动中有5种不同的瓶盖以等概率出现，每买一瓶汽水可得到一个瓶盖，集齐所有瓶盖所买汽水瓶数的期望，与以下哪个结果最为接近？ 
  • 9
  • 11
  • 13
  • 15
查看正确选项
添加回答
小杨vita头像 小杨vita
算法导论有解答，奖券收集问题 Coupon Collector's Problem

我们现在来算一下这个问题的期望值：

设 T 为获取所有 N 种奖券所用的总次数的随机函数，ti 为获取第 i 张奖券用的次数的随机函数。获取一张新奖券的概率为 pi=(n-(i-1))/n，由于这事件服从几何分布，所以其期望值 E(ti)=1/pi

获取第一张奖券的概率为 p1=100%（因为此时你还没有任何奖券，任意一张对于你来说都是有用的）。 E(t1)=1

获取第二张奖券的概率为 p2=(n-1)/n （此时的概率不再是百分之百了，因为你已经有了第一张，所以概率分子相应地减一）。 E(t2)=n/n-1

最后可以算出：

好了，我就不解释这公式什么意思，直接上图：

编辑于 2017-08-24 15:09:39 回复(3)
知否头像 知否
选11。 取到一种不同瓶盖的期望次数为1； 在已经取到一种瓶盖的情况下，再取到一种不同的瓶盖的期望次数是1/（4/5）=5/4； 在已经取到两种瓶盖的情况下，再取到一种不同的瓶盖的期望次数是1/（3/5）=5/3； 。。。 因此，取到五种瓶盖的期望次数为1+5/4+5/3+5/2+5/1=11+5/12。
发表于 2015-09-16 12:13:54 回复(10)
vvickey111头像 vvickey111
几何分布，在第k次成功的期望是1/p，p为第k次成功的概率。所以第一次五次取到瓶盖都不一样就说明了对每一次都是一次实验k次的实验，也就每次成功的概率倒数的相加，第一次是概率为1因为一定不一和前面的一样，第二次就是1/（4/5），第三次就是1/（3/5），第四次就是1/（2/5），第五次就是1/（1/5）。所以它们的和就是1+5/4+5/3+5/2+5/1。
发表于 2017-06-17 15:53:13 回复(0)
lowbee头像 lowbee
答案是11+5/12.  设 E(i) 表示 目前已有i个不同瓶盖集齐五个不同瓶盖所需的瓶子个数期望。
  • E(0) = E(1)+1  ,  需要一个瓶盖跳到E(1)
  • E(1) = (E(2)+1)*4/5+(E(1)+1)*1/5
  • E(2) = (E(3)+1)*3/5+(E(2)+1)*2/5
  • E(3) = (E(4)+1)*2/5+(E(3)+1)*3/5
  • E(4) = (E(5)+1)*1/5+(E(4)+1)*4/5
  • E(5) = 0
解得E(4) = 5, E(3)=15/2, E(2)=55/6, E(1)= 125/12, E(0) = 11+5/12
E(0)是我们的所求。
编辑于 2016-09-02 18:53:19 回复(0)
呆笑笑头像 呆笑笑
没有那么复杂，把5个瓶盖分别看取多少次
显然 第一个 1次，第二个取到的概率是4/5 为一次 ，第三个取到的概率为3/5 为2次，第四个取到的概率为2/5 也为2次，第五个为1/5就为5次了，所以就是1+1+2+2+5=11 
其实从第二个开始相加（4/5+3/5+2/5+1/5=2）概率之和为2  ，不就是10吗？
    
编辑于 2016-02-03 14:56:36 回复(8)
offer满盆头像 offer满盆
本题目是考察几何分布。
第一次，肯定会有一个瓶盖出现，得到一个瓶盖的概率为1，因而期望是1.
第二次，不同瓶盖出现的概率是4/5，服从 ge(4/5)，期望是1/ p,从而是5/4.
下面同理。
由于随机变量和的期望等于期望的和，因而可以将这些相加起来。
发表于 2019-03-08 10:35:08 回复(0)
Levi_yxc头像 Levi_yxc

其实就是个概率 dp 问题（ap 狂喜）。

设 表示已有 个不同盖子，要达到 个的期望。

那么就有

第一部分表示有 的概率选到新盖子，所以会由 转移过来；第二部分就是选到了原先就有的 个盖子中的一个，所以由自己转移过来。

化简得：

边界条件：。

解得 。

编辑于 2024-03-13 15:30:12 回复(0)
wings_zhang头像 wings_zhang
取到第二个瓶子的概率为4/5，但是为什么是1/p，就不是1*p呢？
发表于 2020-04-28 11:23:19 回复(0)
葱烧小黄鱼头像 葱烧小黄鱼
我认为11+5/12应该向上取整，所以是12，但没有这个答案
发表于 2020-04-26 01:45:02 回复(0)
xlshaoscu头像 xlshaoscu
取到第二个瓶盖的概率为4/5，那么对应的期望为1/（4/5）
发表于 2015-09-23 16:06:22 回复(0)
提交观点

问题信息

C++工程师 运维工程师 美团 算法工程师 概率统计 2016 Java工程师
来自：美团2016研发工程师...
难度：
10条回答 20364浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号