uva11181 條件機率

N friends go to the local super market together. The probability of their buying something from the

market is p1, p2, p3, . . . , pN respectively. After their marketing is finished you are given the information

that exactly r of them has bought something and others have bought nothing. Given this information

you will have to find their individual buying probability.

Input

The input file contains at most 50 sets of inputs. The description of each set is given below:

First line of each set contains two integers N (1 ≤ N ≤ 20) and r (0 ≤ r ≤ N). Meaning of N and

r are given in the problem statement. Each of the next N lines contains one floating-point number pi

(0.1 < pi < 1) which actually denotes the buying probability of the i-th friend. All probability values

should have at most two digits after the decimal point.

Input is terminated by a case where the value of N and r is zero. This case should not be processes.

Output

For each line of input produce N +1 lines of output. First line contains the serial of output. Each of the

next N lines contains a floating-point number which denotes the buying probability of the i-th friend

given that exactly r has bought something. These values should have six digits after the decimal point.

Follow the exact format shown in output for sample input. Small precision errors will be allowed. For

reasonable precision level use double precision floating-point numbers.

Sample Input

3 2

0.10

0.20

0.30

5 1

0.10

0.10

0.10

0.10

0.10

0 0

Sample Output

Case 1:

0.413043

0.739130

0.847826

Case 2:

0.200000

0.200000

0.200000

0.200000

0.200000

【紫書分析】：

有n個人準備去超市逛，其中第i個人買東西的機率是Pi。逛完以後你得知有r個人買了東 西。根據這一資訊，請計算每個人實際買了東西的機率。輸入n（1≤n≤20）和r（0≤r≤n）， 輸出每個人實際買了東西的機率。

【分析】

“r個人買了東西”這個事件叫E，“第i個人買東西”這個事件為Ei，則要求的是條件概 率P(Ei|E)。根據條件機率公式，P(Ei|E) = P(EiE) / P(E)。

P(E)依然可以用全機率公式。例如，n=4，r=2，有6種可能：1100, 1010, 1001, 0110, 0101, 0011，其中1100的機率為P1*P2*(1-P3)*(1-P4)，其他類似，設定A[k]表示第k個人是否買 東西（1表示買，0表示不買），則可以用遞歸的方法枚舉恰好有r個A[k]=1的情況。

如何計算P(EiE)呢？方法一樣，隻是枚舉的時候要保證第A[i]=1。不難發現，其實可以 用一次枚舉就計算出所有的值。用tot表示上述機率之和，sum[i]表示A[i]=1的機率之和，則答 案為P(Ei)/P(E)=sum[i]/tot。

我這裡把所有2^20種狀态預處理了，存入vector。

【代碼】：

#include<bits/stdc++.h>
using namespace std;
double p[25];
vector<int>v[22];
int main()
{
    for(int i=0,t=(1<<20);i<t;i++)
    {
        int j=0;
        for(int n=i;n;n>>=1)
            j+=n%2;
        v[j].push_back(i);
    }
    for(int j=0;j<=20;j++)//j for mount of 1
        sort(v[j].begin(),v[j].end());
    int ca=1,n,r;
    while(cin>>n>>r,n)
    {
        for(int i=1;i<=n;i++)
            cin>>p[i];
        double PE=0;
        for(int i=0,t=(1<<n);v[r][i]<t&&i<v[r].size();i++)
        {
            double P=1;
            for(int x=v[r][i],j=1;j<=n;j++)
            {
                P*=x%2?p[j]:(1-p[j]);x>>=1;
            }
            PE+=P;
        }//PE
        printf("Case %d:\n",ca++);
        for(int k=1;k<=n;k++)
        {
            double PEE=0;
            for(int i=0,t=(1<<n);v[r][i]<t&&i<v[r].size();i++)
            {
                double P=1;
                int flag=1;
                for(int x=v[r][i],j=1;j<=n;j++)
                {
                    if(j==k&&x%2==0){flag=0;break;}
                    P*=x%2?p[j]:(1-p[j]);
                    x>>=1;
                }
                if(flag)PEE+=P;
            }
            printf("%.6lf\n",PE?PEE/PE:0);
        }

    }
}