http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18546
题意:有n个人会去超市,其中只有r个人会买东西,每个人独自买东西的概率会给出,问这一群人去买东西,第i个人属于r之中的概率是多少
思路:首先得了解什么是条件概率.
条件概率:事件A在事件B成立的基础上再成立的概率,公式为:P(A|B)=P(A*B)/P(B)
可以照着题目案例1进行分析:
输入
0.10
0.20
0.30
输出
0.413043
0.739130
0.847826
由于是哪r个人是未知的,那么就得进行枚举
把这三个人编号为1 2 3
P(1 2)=0.1*0.2*0.7=0.014,那么P(1)=0.014,P(2)=0.014,P(B)=0.014
P(1 3)=0.1*0.3*0.8=0.024,那么P(1)=0.014+0.024=0.038 P(3)=0.024 P(B)=0.038
P(2 3)=0.2*0.3*0.9=0.054,那么P(2)=0.014+0.054=0.068 P(3)=0.024+0.054=0.078 P(B)=0.092
因此
P(A1|B)=P(1)/P(B)=0.413043
P(A2|B)=P(2)/P(B)=0.739130
P(A3|B)=P(3)/P(B)=0.847826
所以这道题的解法就出来啦:枚举所有排列,累加概率,循环输出
#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int maxn=;
double sum[maxn];
double ans;
double P[maxn];
int buy[maxn];
int n,r;
void Init()
{
for(int i=;i<n;i++)
{
scanf("%lf",&P[i]);
}
memset(sum,,sizeof(sum));
fill(buy,buy+maxn,);
ans=;
}void DFS(int d,int c,double pro)
{
if(c>r||d-c>n-r) return;
if(d==n)
{
ans+=pro;
//cout<<pro<<endl;
for(int i=;i<n;i++)
if(buy[i]) {sum[i]+=pro;}
//cout<<endl;
}
buy[d]=;
DFS(d+,c,(-P[d])*pro);
buy[d]=;
DFS(d+,c+,P[d]*pro);
}int main()
{
int ca=;
while(scanf("%d%d",&n,&r)&&n)
{
Init();
DFS(,,1.0);
cout<<"Case "<<ca++<<':'<<endl;
for(int i=;i<n;i++)
printf("%.6f\n",sum[i]/ans);
}
return ;
}
O(0_0)O