UVa 557 汉堡

https://vjudge.net/problem/UVA-557

题意：

有n个牛肉堡和n个鸡肉堡给2n个孩子吃。每个孩子在吃之前都要抛硬币，正面吃牛肉堡，反面吃鸡肉堡。如果剩下的所有汉堡都一样，则不用抛硬币。求最后两个孩子迟到相同汉堡的概率。

思路：

我们可以先计算出最后两个孩子迟到不一样的汉堡的概率，这样之前的2n-2个孩子都需要抛硬币。

易得此时的概率为

因为有n-1个孩子吃同一种汉堡，所有一共有C（n-1,2n-2）种不同的选择方法，每种方法的概率都是（1/2）^（2n-2）。这也就是一个全概率公式。

最后得出一个递推公式，

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 50000+5;

double p[maxn];

void init()
{
    p[1]=1;
    for(int i=1;i<=maxn;i++)
    {
        p[i+1]=(1-1./(2*i))*p[i];
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    int t;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d",&n);
        printf("%.4f
",1-p[n/2]);
    }
    return 0;
}