找出某個人贏的機率。
假設贏的機率是 p，輸的機率是 q = (1 - p)。
在第一回合中，第一個人贏的機率是 p。
在第一回合中，第二個人贏的機率是 q * p。
在第一回合中，第三個人贏的機率是 q^2 * p。
在第一回合中，第 k個人贏的機率是 q^(k - 1) * p。
再假設有 n個人：
在第二回合中，第一個人贏的機率是 q^n * p。 (第一回合中每個人都失敗)
在第二回合中，第二個人贏的機率是 q^n * q * p。
在第二回合中，第三個人贏的機率是 q^n * q^2 * p。
在第二回合中，第 k個人贏的機率是 q^n * q^(k - 1) * p。
再假設這是第R回合：
在第 R回合中，第 k個人贏的機率是 q^( (R - 1) * n) * q^(k - 1) * p。
這是通式。
題目要求第 k個人贏的總機率，這個機率相等於：
Σ(R from 1 to infinity) q^( (R - 1) * n) * q^(k - 1) * p
這樣就可以求出答案了，R的數字愈大，則答案愈精確。
但是這樣程式執行效率太差了，所以必須想出更好的數學方法來解這個題目：
在第一回合中，第 k個人贏的機率是 q^(k - 1) * p。
在第二回合中，第 k個人贏的機率是 q^n * q^(k - 1) * p。
在第三回合中，第 k個人贏的機率是 q^2n * q^(k - 1) * p。
可以看出是等比數列，而我們要求等比級數和。等比級數
等比級數和 = (首項 * (1 - 公比^n) ) / (1 - 公比)
公比(common ratio) = 第n項 / 第n-1項 = (q^2n * q^(k - 1) * p) / (q^n * q^(k - 1) * p) = q^n。
首項 = q^(k - 1) * p。
帶入即可得出答案
--------------------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>
#define ACCURACY 100 /* Definable */
int main()
{
int _case, num_of_people, the_people;
double answer, p, q, common_ratio, first_term; /* p == winning probability in single round. */
scanf("%d", &_case);
while(_case--)
{
scanf("%d%lf%d", &num_of_people, &p, &the_people);
q = 1 - p;
first_term = pow(q, the_people - 1) * p;
common_ratio = pow(q, num_of_people);
if(1 == common_ratio)
{
printf("0.0000\n");
continue;
}
answer = first_term*(1 - pow(common_ratio, ACCURACY) ) / (1 - common_ratio);
printf("%.4lf\n", answer);
}
return 0;
}
丟在coding frezy上的code，要丟到UVA要自行修改(去掉public class main的 public 並將 main 改成 Main
----2017-06-24----------------------------------------------------------
import java.util.*;
public class main{
public static void main(String[] args) {
try {
Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();
double precision = 100000; // N stands for precision
while (cases-- > 0) {
int players, serialNumber;
double p, result, q; // p stands for the win probability and q stands for lose probability.
players = sc.nextInt();
p = sc.nextDouble();
serialNumber = sc.nextInt();
if (0.0 == p) {
System.out.println("0.0000");
continue;
}
q = 1 - p;
// Sn = a1(1-r^n) / (1-r)
// Sn = (q^(R-1) * p * (1 - (q^N)^n) ) / (1 - q^N)
result = Math.pow(q, serialNumber - 1) * p * (1 - Math.pow(Math.pow(q, players), precision)) / (1 - Math.pow(q, players));
System.out.printf("%.4f", result); // 這兩行一直導致我在Uva上 get a presentation error，因為我原本的換行是\r\n而非System.out.println();，為什麼改了之後就可以呢? 因為不同的OS，換行字元會不一樣，詳請可以查se 8 的 System.out.println() 的description
System.out.println();
}
} catch (Exception e) {
System.out.println("Input error");
}
}
};
留言列表
