概率论 --- Uva 11181 Probability|Given

时间:2022-10-27 00:46:17

Uva 11181 Probability|Given

Problem's Link:   http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18546


Mean:

n个人去逛超市,第i个人会购买东西的概率是Pi。出超市以后发现有r个人买了东西,问你每个人购买东西的实际概率是多少。

analyse:

转换模型:

有n个员工,每个员工被选出来的概率是Pi。最后选出了r个,问你第i个员工在这r个中的概率是多少。

设:

事件A----第i个员工在这r个员工中。

事件B----从n中选出r个员工。

求的就是在B事件发生的情况下,A事件发生的概率。

Pb为从n个员工中选出r个员工的概率总和,也就是C(n,r)中选中的r个算的是pi,未选中的算(1-pi)。

Pa为第i个员工在选中的r个员工中的概率总和,这个可以在算上面那个的时候一并算出。

最后的答案就是Pa/Pb.

数据很小,直接用递归枚举所有的组合数就行。

Time complexity: O(n^2)

Source code: 

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-05-17-21.37
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std; int n,k;
double p[],ans[];
bool vis[];
void dfs(int N,int K) // 从N~n中选K个数的全部组合
{
if(!K)
{
double tmp=;
for(int i=;i<=n;++i)
if(vis[i]) tmp*=p[i];
else tmp*=(-p[i]);
ans[]+=tmp;
for(int i=;i<=n;++i)
if(vis[i]) ans[i]+=tmp;
}
else
{
for(int i=N;i<=n;++i)
{
vis[i]=;
dfs(i+,K-);//从i+1~n中再选K-1个数
vis[i]=;
}
}
} int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
int Cas=;
while(cin>>n>>k,n+k)
{
for(int i=;i<=n;++i) cin>>p[i];
memset(vis,,sizeof vis);
memset(ans,,sizeof ans);
dfs(,k);
printf("Case %d:\n",Cas++);
for(int i=;i<=n;++i) printf("%.6lf\n",ans[i]/ans[]);
}
return ;
}
/* */