紫书习题 10-12 UVa 557（概率计算）

开始的时候我没有考虑1/2的概率，直接一波组合数，然后WA

后来去看题解发现我们可以反过来想，求最后两个人不一样的情况

这个时候肯定会抛到最后的

所以每一种可能就是（0.5）^(n - 2),然后一共有C（n-2，n/2-1）种

乘起来就ok了。

但是这样会超时而且结果太大

所以我们可以尝试递推

通过计算可以发现d[i+2] = d[i] * (i-1) / i

所以就递推出所有值然后直接输出就好了。

#include<cstdio>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112345;

double d[MAXN];

void init()

{

	d[2] = 1.0;

	REP(i, 2, MAXN)

		d[i+2] = d[i] * (i-1) / i;

}

int main()

{

	init();

	int T, n;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d", &n);

		printf("%.4lf\n", 1 - d[n]);

	}

	return 0;

}

巴特西

紫书习题 10-12 UVa 557（概率计算）

最新文章

热门文章

巴特西

紫书 习题 10-12 UVa 557（概率计算）

最新文章

热门文章

紫书习题 10-12 UVa 557（概率计算）