UVa 557 - Burger（概率＋递推）

发表于 分类于 ， Disqus：

给出一个偶数n（2≤n≤100000）。表示一共有2n个汉堡，其中牛肉汉堡和奶酪汉堡各有n个。有2n个人每个人吃之前投硬币，正面吃牛肉汉堡，反面吃奶酪汉堡。 问最后两个人吃到相同汉堡的概率。
设P[n]为有2n个汉堡时最后两个人吃到不同汉堡的概率。
有：
** P[n]=1/(2(2n-2))C(2n-2,n-1)
直接计算会超时，于是要求递推公式：
P[n+1]/P[n]=(C(2n,n)/(2^n))((2(2n-2))/C(2n-2,n-1))=(2n-1)/(2n) **
把P[1]初始化为1之后用公式计算所有值保存，查找输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
const int maxn=50005;
double a[maxn]={1,1};
int main(){
    for(int i=2;i<maxn;++i)
        a[i]=a[i-1]*(2*i-3)/(2*i-2);
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%.4lf\n",1-a[n/2]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章