当前位置: 代码迷 >> 综合 >> POJ 3716 Panda's Birthday Present 条件概率
  详细解决方案

POJ 3716 Panda's Birthday Present 条件概率

热度:93   发布时间:2024-01-13 17:12:51.0

看了http://hi.baidu.com/bfcdygoporbjuxr/item/569897ddc1fc561d21e2503f 这个题解

感觉写的有点费劲 , 而且虽然写了一点关于公式(m+n+10)/7的,但我感觉还是不好理解啊。

不过其中讲的主要思路还是有用的。


对于一个骰子 有t个面为1的概率是 P(T=t)=C(6,t)/64。

在有t个面为1的情况下,投n次,有k个1,假设这k个1的位置已经固定了,则概率为 t ^ k * (6 - t) ^ (n - k) / 6 ^ n 

则P (S) = sigma(t ^ k * (6 - t) ^ (n - k) / 6 ^ n * C(6,t)/64)(t = 0, 1. 2...6, S为01串,n的长度k个1)

对于任意一种有k个1的情况, 概率都是这个。也就是说  在计算上,这些情况都是等价的,可以互换的,

那么也就是说,第一次有m个1,第二次有n个1,对于任意的情况,只要满足第一次x个1,第二次y个1,x+y=m+n,x<=4 && y<=4, 就是等价的。


而在游戏中,对于一个骰子, 前两次的状态无非是 00, 01, 10, 11

然后我们要计算在这些状态下第3次投出1的概率

即P(1 | 00)  P (1 | 01)  P (1 | 10)  P(1 | 11)

 以 P (1 | 11)为例子

由条件概率 P( 1 | 11) = P (111) /  P(11)

其中P(111)= sigma(t ^ 3/ 6^3 * C(6, t) /64 ) (t = 0,1,2...6)

P(11)= sigma(t ^ 2/ 6^2 * C(6, t) /64 ) (t = 0,1,2...6)

然后可以求出P(1 | 11) = 9 /14

同理P( 1 | 10) = 1 / 2

P( 1 | 00) = 5 /14


我们之前也知道了  任意情况只要满足 两次投的和等于m+n,求出的答案就跟原题是等价的

那么我们就找最简单的情况。

先满足11,然后满足10,剩余的满足00

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <ctime>
#define MAXN 52222
#define MAXM 222222
#define INF 1000000001
using namespace std;
double p11, p10, p00;
int ct[] = {1, 6, 15, 20, 15, 6, 1};
int main() {double sum1 = 0, sum2 = 0;for(int i = 0; i <= 6; i++) sum1 += i * i * i * ct[i], sum2 += i * i * ct[i];sum1 /= 216.0, sum2 /= 36.0;p11 = sum1 / sum2;sum1 = 0, sum2 = 0;for(int i = 0; i <= 6; i++) sum1 += i * i * (6 - i) * ct[i], sum2 += i * (6 - i) * ct[i];sum1 /= 216.0, sum2 /= 36.0;p10 = sum1 / sum2;sum1 = 0, sum2 = 0;for(int i = 0; i <= 6; i++) sum1 += i * (6 - i) * (6 - i) * ct[i], sum2 += (6 - i) * (6 - i) * ct[i];sum1 /= 216.0, sum2 /= 36.0;p00 = sum1 / sum2;int T, m, n;scanf("%d", &T);while(T--) {scanf("%d%d", &m, &n);int s = m + n;int num1 = s / 2;int num2 = s % 2;int num3 = 4 - num1 - num2;printf("%.3f\n", p11 * num1 + p10 * num2 + p00 * num3);}return 0;
}


然后 接着看  为什么有这样一个简单公式(m+n+10)/7

假设m+n是偶数。

那么最后答案即为 (m+n) / 2 * 9/14 + (4 - (m+ n) / 2) * 5 / 14 = (m + n + 10 ) / 7

假设m+n是偶数

最后答案为(m+n-1) /2 * 9/14 + 1/2 + (3 - (m+ n -1) / 2) * 5 /14 = (m + n+10) /7

最后发现不管怎么搞 答案都是(m + n + 10 ) / 7


  相关解决方案