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 ;

}

/*

*/

巴特西

概率论 --- Uva 11181 Probability|Given

Uva 11181 Probability|Given

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

最新文章

热门文章