首页 > 其他 > 详细

UVA 11427 - Expect the Expected(概率递推期望)

时间:2014-07-17 16:30:23      阅读:422      评论:0      收藏:0      [点我收藏+]

UVA 11427 - Expect the Expected

题目链接

题意:玩一个游戏,赢的概率p,一个晚上能玩n盘,如果n盘都没赢到总赢的盘数比例大于等于p,以后都不再玩了,如果有到p就结束

思路:递推,dp[i][j]表示玩i盘,赢j盘的概率,那么一个晚上玩了n盘小于p的概率递推式为:
dp(i,j)=dp(i?1,j)?(1?p)+dp(i?1,j?1)?p
总和为Q=dp(n,0)+dp(n,1)+...+dp(n,x)(x/n<p)

那么每个晚上失败的概率Q就求出来了,那么平均玩的天数的期望就利用全期望公式求得为1/Q

代码:

#include <stdio.h>
#include <string.h>

const int N = 105;
int t, pz, pm, n;
double f[N][N], p;

int main() {
	int cas = 0;
 	scanf("%d", &t);
	while (t--) {
		scanf("%d/%d%d", &pz, &pm, &n);
		p = pz * 1.0 / pm;
		memset(f, 0, sizeof(f));
		f[0][0] = 1;
		double Q = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j * pm <= i * pz; j++) {
				f[i][j] = f[i - 1][j] * (1 - p);
				if (j) f[i][j] += f[i - 1][j - 1] * p;
				if (i == n) Q += f[i][j];
			}
  		}
  		printf("Case #%d: %d\n", ++cas, (int)(1/Q));
  	}
	return 0;
}


UVA 11427 - Expect the Expected(概率递推期望),布布扣,bubuko.com

UVA 11427 - Expect the Expected(概率递推期望)

原文:http://blog.csdn.net/accelerator_/article/details/37904181

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!