OIer博客

题目大意：当你有i颗星星的时候，参与游戏获得一颗星星的概率是$\frac{x_i}{y_i}$，失去一颗星星的概率是$\frac{y_i-x_i}{y_i}$，一开始没有星星，请问获得n颗星星的期望是多少？

解题思路

一开始，只有0颗星星，不会减少，可以得出$f_1$和$f_0$的关系：

$f_0 = 1 + \frac{x}{y} f_1 + \frac{y-x}{y} f_0$

$f_1 = (\frac{x}{y} f_0 – 1) * \frac{y}{x} = f_0 – \frac{y}{x}$

当至少1颗星星的时候，跟前后都有关系：

$f_i = 1 + \frac{x}{y} f_{i+1} + \frac{y-x}{y} f_{i-1}$

$f_{i+1} = (f_i – \frac{y-x}{y} f_{i-1} – 1) * \frac{y}{x} = \frac{y}{x} f_i – \frac{y-x}{x} f_{i-1} – \frac{y}{x}$

从$f_2$开始，每一项都跟前两项有联系，都可以转换成若干个$f_0$加上一个常数。推到$f_n = 0$时，即可算出$f_0$。

程序实现