hdu 2048 神、上帝以及老天爷 (错排公式)

hdu2048 题目链接

题意:n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片,取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。

思路:错排。。。

复习了一下错排公式。。。d[n] = (n-1)*(d[n-1]+d[n-2])  (d[1]=0,d[2]=1)

然后求概率的时候。。惊讶得发现概率稳定在了36.79%(1/e)附近。。。

这是因为。。。错排还有一个公式:D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

求概率每次把n!除掉了。。剩下的。。其实就是e的泰勒展开,当x=-1时的值。

因为当n越大时。。这个概率越接近1/e

这道题里。。。在保留百分数的小数点两位的精度的条件下。。当n为7的时候。。答案就已经是36.79保持不变了。。。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz