首页 > 代码库 > UVa 11181 (条件概率) Probability|Given
UVa 11181 (条件概率) Probability|Given
题意：
有n个人买东西，第i个人买东西的概率为Pi。已知最终有r个人买了东西，求每个人买东西的概率。
分析：
设事件E为r个人买了东西，事件Ei为第i个人买了东西。所求为P(Ei|E) = P(EiE) / P(E)
用一个buy数组记录每个人买或没买东西，然后dfs。
枚举所有r个人买了东西的情况的概率prob，累加到sum[n]中，对于buy[i] == true，再将prob加到sum[i]中。
最后答案为sum[i] / sum[n]
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 25; 5 int n, r; 6 double P[maxn], sum[maxn]; 7 bool buy[maxn]; 8 9 void dfs(int d, int c, double prob)10 {11 if(c > r || d - c > n - r) return; //有太多的1或者012 if(d == n)13 {14 sum[n] += prob;15 for(int i = 0; i < n; ++i)16 if(buy[i]) sum[i] += prob;17 return;18 }19 buy[d] = 0;20 dfs(d+1, c, prob * (1-P[d]));21 buy[d] = 1;22 dfs(d+1, c+1, prob * P[d]);23 }24 25 int main()26 {27 //freopen("in.txt", "r", stdin);28 29 int kase = 0;30 while(scanf("%d%d", &n, &r) == 2 && n)31 {32 for(int i = 0; i < n; ++i) scanf("%lf", &P[i]);33 memset(sum, 0, sizeof(sum));34 dfs(0, 0, 1.0);35 printf("Case %d:\n", ++kase);36 for(int i = 0; i < n; ++i)37 printf("%.6f\n", sum[i] / sum[n]);38 }39 40 return 0;41 }
UVa 11181 (条件概率) Probability|Given
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。