Probability|Given UVA - 11181 ——全概率公式

骑猪看日落 2022-06-15 12:13 162阅读 0赞

Think:  
1>全概率公式:对任一事件A有 P(A)=P(A|B1)\*P(B1)+P(A|B2)\*P(B2)+…+P(A|Bn)\*P(Bn).(或者：p(A)=P(AB1)+P(AB2)+…+P(ABn)).(其中A与Bn的关系为交)——参考自互动百科  
[全概率公式互动百科链接][Link 1]  
理解:将样本空间有二进制字符串表示，1代表元素事件发生的概率，0代表元素事件不发生的概率，例如，n = 4, r = 2, 有6种可能:1100, 1010, 1001, 0110, 0101, 0011., 其中1100发生的概率为P1 \* P2 \* (1 - P3) \* (1 - P4);  
计算分析:![这里写图片描述][SouthEast]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int n, r, v[2], tp, u[24];
    double tot, P[24][2], sum[24];
    
    void DFS(int step);
    
    int main(){
        int k = 1;
        while(scanf("%d %d", &n, &r) && (n || r)){
            v[1] = r, v[0] = n-r;
            for(int i = 0; i < n; i++){
                scanf("%lf", &P[i][1]);
                P[i][0] = 1.0 - P[i][1];
            }
            tot = 0.0;
            for(int i = 0; i < 24; i++)
                sum[i] = 0.0;
            tp = 0;
            DFS(1);
            printf("Case %d:\n", k++);
            for(int i = 0; i < n; i++)
                printf("%.6lf\n", sum[i]/tot);
        }
        return 0;
    }
    void DFS(int step){
        if(step == n+1){
            double ans = 1.0;
            for(int i = 0; i < n; i++){
                ans *= P[i][u[i]];
            }
            tot += ans;
            for(int i = 0; i < n; i++){
                if(u[i]){
                    sum[i] += ans;
                }
            }
        }
        for(int i = 0; i < 2; i++){
            if(v[i]){
                u[tp++] = i;
                v[i]--;
                DFS(step+1);
                tp--;
                v[i]++;
            }
        }
    }

[Link 1]: http://www.baike.com/wiki/%E5%85%A8%E6%A6%82%E7%8E%87%E5%85%AC%E5%BC%8F
[SouthEast]: /images/20220615/4fbfcb8d36c4449b9d9dfbb4a5774446.png
[vjudge]: https://vjudge.net/problem/UVA-11181