UVa 557 (概率 递推) Burger

题意：

有两种汉堡给2n个孩子吃，每个孩子在吃之前要抛硬币决定吃哪一种汉堡。如果只剩一种汉堡，就不用抛硬币了。

求最后两个孩子吃到同一种汉堡的概率。

分析：

可以从反面思考，求最后两个孩子吃到不同汉堡的概率。

因为最后两个汉堡是不同的，所以前面的2n-2个孩子吃汉堡之前一定都是要抛硬币的。

所以，吃两种汉堡的孩子人数相等，都是n-1个。

令，对于2n个孩子吃汉堡，所求概率为1 - f(n-1)

 我们还可以递推f，

#include <iostream>
#include <cstdio>
using namespace std;

double a[50000 + 10];

int main()
{
    a[0] = 1; a[1] = 0.5;
    for(int i = 1; i <= 50000; ++i) a[i+1] = (double)(2*i+1)/(2*i+2)*a[i];

    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        n >>= 1; n--;
        printf("%.4f
", 1.0 - a[n]);
    }

    return 0;
}