UVa 10056 題解 — C++

記得考慮 p = 0 的情況，因為浮點數不一定準，所以我設為 p < 1e-9 就輸出 0.0000。 這題也同時要注意，不一定第一輪就會結束，因此要考慮無窮次數的情況。 第 i 人獲勝的機率就是： 前 i 個人輸、第 i 個人贏的機率 * 前面幾輪全輸的機率。
$P_i = ((1-p)^{i-1} \times p) \times \sum_{k = 0}^{\infty}((1-p)^n)^k - (1)$
利用等比級數公式：
$S_k = \frac{a_1(1-r^k)}{1-r}$
代入 $(1)$ 後得：
$P_i = ((1-p)^{i-1} \times p) \times \frac{1 \times (1-((1-p)^n)^\infty)}{1-(1-p)^n}$
因為 $1 - p < 1$，所以 $((1-p)^n)^\infty \approx 0$
$P_i \approx ((1-p)^{i-1} \times p) \times \frac{1}{1-(1-p)^n} \approx \frac{(1-p)^{i-1} \times p}{1-(1-p)^n}$
答案就是此公式的結果。
<另解> 這邊用條件機率的方式也算一下 $E$：第 i 個人獲勝的事件 $A$：第一輪第 i 個人獲勝的事件 $B$：第一輪其他人獲勝的事件 $F$：第一輪沒人獲勝的事件
$P(E)=P(E|A)P(A)+P(E|B)P(B)+P(E|F)P(F)$ 當 $P(A)$ 發生就代表第 $i$ 個人已經獲勝，那 $A$ 發生後 $E$ 發生的機率 $P(E|A)$ 一定是 1。 反之當 $P(B)$ 發生就代表其他人已經獲勝，那 $B$ 發生後 $E$ 發生的機率 $P(E|B)$ 一定是 0。 而當 $P(F)$ 發生後，就代表第一輪無人獲勝，那 $F$ 發生後 $E$ 發生的機率 $P(E|F)$ 其實也是 $P(E)$，因為他不影響第 $i$ 個人獲勝的機率。 由此可知： $P(E)=1 \times P(A)+0 \times P(B)+P(E)P(F)$ $\Rightarrow P(E)=(1-p)^{i-1} \times p+(1-p)^nP(E)$ $\Rightarrow (1-(1-p)^n)P(E)=(1-p)^{i-1} \times p$ $\Rightarrow P(E)=\frac{(1-p)^{i-1} \times p}{1-(1-p)^n}$ 答案是一樣的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int j, k;
	int s, n, i;
	double p, ans;
	
	cin >> s;
	
	for (j=0;j<s;j++) {
		cin >> n >> p >> i;
		
		if (p < 1e-9) {  // 浮點數不一定準 
			cout << 0.0000 << endl;
			continue;
		}
		
		ans = (p * pow((1-p), i-1)) / (1 - pow((1-p), n));
		
		cout << fixed << setprecision(4) << ans << endl; 
	}

	return 0;
}