UVa 557 - Burger(概率+递推)

给出一个偶数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博客 ,格式可能有所偏差。