UVa 557

题意

2n个孩子分汉堡，n个鸡肉堡, n个牛肉堡
抛硬币决定, 正面朝上吃牛肉, 反面朝上吃鸡
如果没的可选了就不抛硬币了
求最后两个孩子吃到汉堡相同的概率

思路

就是简单的数学概率问题
直接求题目要求的概率不好求
考虑先求P(最后两个孩子吃到不同的汉堡), 然后用1-P即为答案

P[i] = 1/2^(2i-2) * C(i-1, 2i-2)
得到递推公式 P[i+1] = (2n-1) / 2n * P[i]

AC代码

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 50000+10;
double p[maxn];

void find_P()
{
    p[1] = 1;
    for (int i = 1; i <= 50000; i++){
        p[i+1] = p[i] * (2 * i - 1) / (2 * i);
        //printf("%.4f
",p[i]);
    }
}
int main()
{
    int T, n;
    find_P();
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%.4lf
",1-p[n/2]);
    }
    return 0;
}