O(1) 的小乐

Job Hunting

公告

记录我的生活和工作。。。
<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

  • 随笔 - 182
  • 文章 - 1
  • 评论 - 41
  • 引用 - 0

留言簿(10)

随笔分类(70)

随笔档案(182)

文章档案(1)

如影随形

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜

Hat-Check problem 帽子保管问题

这个是算法导论习题5.2-4

  n个顾客在进酒店之前,都会把自己的帽子给前台服务员保管。每个顾客在离开时,前台服务员又会随机地挑选一个帽子给他。问:最终,能拿到自己帽子的顾客们期望数是多少

首先从简单情况入手,对于n=2 n=3 很容易求出 结果res=1;
对于n>=4,我们严格的用概率方法来推导一下!
首先定义P(n)为伯努利放错信的问题的答案。
P_n=n!\sum_{i=2}^{n}\frac{(-1)^i}{i!}

SLE[7}IS3_~VFKO3}MB71JL

然后对于n个人中i个人匹配正确这个事件的数目是C(n,i)P(i)  
总共有n!中事件,2^n种情况,(可以把人看成是10串,拿到自己帽子的为1)
所以 答案就是
(n-i)*C(n,i)P(i) /n!求和
整理一下是 
\sum_{i=2}^{n-1}\frac{n-i}{(n-i)!}\sum_{j=2}^{i}\frac{(-1)^j}{j!}+\frac{1}{(n-1)!}

 

U~HZ[AVXP)X2TC`4}(3J[XV
可以证明这个等式等于1
所以答案是1

posted on 2010-10-17 15:21 Sosi 阅读(1579) 评论(0)  编辑 收藏 引用 所属分类: Courses


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


统计系统