概率论 --- Uva 11181 Probability|Given

梦里梦外; 2022-03-31 16:41 189阅读 0赞

# 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: **

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*
    * 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[25],ans[25];
    bool vis[25];
    void dfs(int N,int K) // 从N~n中选K个数的全部组合
    {
            if(!K)
            {
                    double tmp=1;
                    for(int i=1;i<=n;++i)
                            if(vis[i]) tmp*=p[i];
                            else tmp*=(1-p[i]);
                    ans[0]+=tmp;
                    for(int i=1;i<=n;++i)
                            if(vis[i]) ans[i]+=tmp;
            }
            else
            {
                    for(int i=N;i<=n;++i)
                    {
                            vis[i]=1;
                            dfs(i+1,K-1);//从i+1~n中再选K-1个数
                            vis[i]=0;
                    }
            }
    }
    
    int main()
    {
            ios_base::sync_with_stdio(false);
            cin.tie(0);
            int Cas=1;
            while(cin>>n>>k,n+k)
            {
                    for(int i=1;i<=n;++i) cin>>p[i];
                    memset(vis,0,sizeof vis);
                    memset(ans,0,sizeof ans);
                    dfs(1,k);
                    printf("Case %d:\n",Cas++);
                    for(int i=1;i<=n;++i) printf("%.6lf\n",ans[i]/ans[0]);
            }
            return 0;
    }
    /*
    
    */

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220331/f4dc1fbec34549918cb14b3b91b5ca31.png