UVA - 11181 數學

UVA - 11181

題意：

n個人去買東西，其中第i個人買東西的概率是p[i],最后只有r個人買了東西，求每個人實際買了東西的概率

代碼：

//在r個人買東西的概率下每個人買了東西的概率，這是條件概率，因為最多20個人可以枚舉所有的狀態
//然后找到所有的r個人買東西的狀態，算出總的概率，某個人在此條件下的概率就是這個人參與了的狀態
//的概率和除以總概率。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sta[1<<21],n,r,nu;
double p[22],sum[22];
void init(){int N=(1<<n);nu=0;for(int i=0;i<N;i++){int t=i,cnt=0;while(t){cnt+=(t&1);t>>=1;}if(cnt==r) sta[++nu]=i;}
}
int main()
{int cas=0;while(scanf("%d%d",&n,&r)==2&&(n+r)){for(int i=1;i<=n;i++)scanf("%lf",&p[i]);init();memset(sum,0,sizeof(sum));double tot=0;for(int i=1;i<=nu;i++){int x=sta[i];double tmp=1.0;for(int j=1;j<=n;j++){if(x&(1<<(j-1))) tmp*=p[j];else tmp*=(1-p[j]);}tot+=tmp;for(int j=1;j<=n;j++)if(x&(1<<(j-1))) sum[j]+=tmp;}printf("Case %d:\n",++cas);for(int i=1;i<=n;i++)printf("%.6lf\n",sum[i]/tot);}return 0;
}

?