/** Pro(i)表示不遇到雷的情况下,到达i步的几率,那么 * Pro(n) = Pro(n-1) * p + Pro(n-2) * (1-p) * 首先求递推公式,由特征方程 x^2 - p*x -(1-p) = 0 求得特征根: p-1 和 1 * 所以Pro(n) = C1 + C2*(p-1)^n* 将Pro(1)=1 Pro(2)=p代入,求得待定系数C1 = -1/(p-2), C2 = 1/(p-2)* 故Pro(n) = -1/(p-2) + 1/(p-2)^n** 假设在位置k首次遇到雷,那么到达位置k-1的几率是 Pro(k-1)* 经过雷后存活的几率是 Pro(k-1) * (1-p) * 将这个值即为a * * 假设又经过t步第二次遇到雷,那么到达t-1步的几率是 a*Pro(t-1)* 经过雷后存活的几率是 a * Pro(t-1) * (1-p)** 以此类推 */
posted on 2009-09-12 21:36 jaysoon 阅读(167) 评论(0) 编辑 收藏 引用 所属分类: ACM/ICPC
Powered by: C++博客 Copyright © jaysoon