LightOJ1408(数学期望与概率)

时间:2021-07-17 08:12:58

题意:

求投丢的概率为p;

那么如果一直投到连续中k1个,或者连续丢k2个,所需要的球的期望;

给出p,k1,k2;


思路

首先我们算出投中的概率q = 1 - p;

假设f[k] 表示已经连续投中k个了,结束比赛还需要多少球的期望;

而g[k]表示是投丢的;

那么f[k1] = g[k2] = 0;

那么我们可以知道f[k] = q * f[k +1] +p *g[1] +1;

那么最后一直递推到f[1];

设x = p *g[1] +1;

最后整理一下就是q^k-1 * x + q ^ k - 2 * x .....q^0 * x = f[1];

用等比公式就能求出一个式子,同样对g做一边就能求出第二个式子,然后解方程;



#include<cstdio>
#include<cstring>
#include<cmath>

const int N = 50;
const double MIN = 1e-10;
double u[N];
double v[N];

double p, q;
int k1, k2;
int main() {
	int t;
	int cas = 1;
	scanf("%d",&t);
	while(t--) {
		scanf("%lf%d%d", &p, &k1, &k2);
		if(p < MIN) {
			printf("Case %d: %d\n",cas++, k1);
			continue;
		}
		if(1 - p < MIN) {
			printf("Case %d: %d\n",cas++, k2);
			continue;
		}
		q = 1.0 - p;
		double s1 = 1 - pow(q, k1 - 1);
		double s2 = 1 - pow(p, k2 - 1);		
		double tmp1 = s1 / p;
		double tmp2 = s2 / q;
		double g = (tmp1 * tmp2 * q +tmp2) / (1 - tmp1 * tmp2 * p * q);
		double f = tmp1 * (p * g + 1);
		printf("Case %d: %lf\n",cas++, q * f + p * g + 1);
	}
}