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

题意：

n个人，n/2个牛肉煲，n/2个鸡肉堡

每次抛硬币，根据正反决定每个人吃什么汉堡

如果某一个汉堡被选完了，就不抛了

问最后两个人吃到同种汉堡的概率是多少

有抛硬币，想办法去掉抛硬币的干扰

要么都抛，要么都不抛

后者不大可能，考虑前者

如果前n-2个人都抛硬币，那么前n-2个人中，

有（n-2）/2 个人吃到牛肉煲，剩下的吃到鸡肉堡

所以，正难则反

计算最后两个人吃到不同种汉堡的概率

a[n]表示有n个人，最后两个人吃到不同汉堡的概率

a[n]=C（n-2，n/2-1）* （1/2）^（n-2）

C（n-2，n/2-1） 是所有可能情况有多少种

（1/2）^（n-2）n-2个人都要抛硬币，概率1/2

n很大，不能直接算组合数

考虑递推

#include<cstdio>#define N 100001using namespace std;double a[N];int main(){    a[2]=1;    for(int i=4;i<N;i+=2) a[i]=a[i-2]*(i-3)/(i-2);     int t,n;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        printf("%.4lf\n",1-a[n]);    }}

uva 557 Burger