吸血鬼,挺有意思的,概率数列题。
村子里有 n-1 个人,1 个吸血鬼,每天随机抽取两个家伙进行反应,如果是一个人一个鬼,那么有 p 的概率会把人变成吸血鬼,求全部变成吸血鬼的期望天数。
分析一下,假设 n, p 为常数 E(k) 为有 k 只吸血鬼的期望天数,不难发现,其实从 E(k) 到 E(k+1) 有一个直接的递推关系。
初始值,E(1) = 0,现在要求 E(n)。
然后我们说一下这个递推关系:
- 如果有 k 只鬼,那么每个晚上可以变成 k+1 只鬼的概率是:
q = p*k*(n-k)/c(n,2) = 2*p*k*(n-k)/n/(n+1)
- 然后有:
E(k+1) = E(k) + 1*q + 2*q*(1-q) + 3*q*(1-q)^2 + ...
- 对于上式右侧的数列,高中的时候学过,可以这样解:
设:
s = q * (1 + 2*(1-q) + 3*(1-q)^2 + ...)
则:
(1-q)*s = q * (0 + (1-q) + 2*(1-q)^2 + ...)
两式相减得到:
s * q = q * (1 + (1-q) + (1-q)^2 + (1-q)^3 + ...)
这是一个等比数列的所有项和,因此:
s = 1 / q
多么优美的结果,也就是说:
E(k+1) = E(k) + 1/q
所以,我们将 k 从 1 遍历到 n-1,求出对应的 1/q,累加起来,就得到了结果。
// 3493567 2013-12-21 18:16:02 Accepted 3551 C++ 90 168 呆滞的慢板
#include <cstdio>
int main() {
int t, n, k;
double p, ans;
for(scanf("%d", &t); t--;) {
scanf("%d%lf", &n, &p);
for(ans = 0, k = 1; k < n; ++k)
ans += 1.0/k/(n-k);
printf("%.3lf\n", 0.5*n*(n-1)/p*ans);
}
}
【转载请附】愿以此功德,回向 >>
原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3551.html【zoj 3551 – Bloodsucker】