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

本文主要是介绍UVA 11427 - Expect the Expected(概率递推期望)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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(概率递推期望)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---