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博客,格式可能有所偏差。 **