概率计算 (习题): 蒜头君王国

雨点打透心脏的1/2处 2022-02-15 04:25 102阅读 0赞

### 蒜头君王国 ###

*  题目
 *  基础知识
 *  思路
 *  代码
 *   *  C语言
     *  Python
 *  总结

# 题目 #

给你 N 个节点, 任意一对节点之间相连的概率为 p, 求整个图是连通图的概率.  
[题目链接][Link 1]

# 基础知识 #

假设有两个事件,  
事件  X X X 可能的取值是  \{ 1 , 0 \} \\\{1, 0\\\} \{ 1,0\}  
事件  Y Y Y 可能的取值是  \{ y 1 , y 2 , . . . , y n \} \\\{y\_1, y\_2, ... , y\_n\\\} \{ y1,y2,...,yn\}

那么概率  
 P ( X = 1 ) = ∑ i = 1 n P ( X = 1 , Y = y i ) P(X=1) = \\sum\_\{i=1\}^nP(X = 1, Y=y\_i) P(X=1)=∑i=1nP(X=1,Y=yi)

# 思路 #

首先, 记事件  X = \{ 1 , 0 \} X = \\\{1, 0\\\} X=\{ 1,0\} 表示给定图是否连通, 如对于一个  n = 5 n=5 n=5 的节点的图, 其为连通图的概率为  P 5 ( X = 1 ) P\_5(X=1) P5(X=1)  
显然  
 P 1 ( X = 1 ) = 1 P\_1(X=1) = 1 P1(X=1)=1  
 P 2 ( X = 1 ) = p P\_2(X=1) = p P2(X=1)=p  
(p 表示任意两个结点之间连通的概率)  
那么这道题的解法是构造如下关系:  
首先, 对每个结点标号  1 , 2 , . . . , n 1, 2, ..., n 1,2,...,n  
设一个新的事件  Y = \{ y 1 , y 2 , . . . , y n − 1 \} Y=\\\{y\_1, y\_2,...,y\_\{n-1\}\\\} Y=\{ y1,y2,...,yn−1\} **表示的是最后一个节点所在的连通分量的节点个数, 比如  y 1 y\_1 y1 表示这个图中最后一个结点是孤立的,  y 3 y\_3 y3 表示最后一个节点和另外的两个节点构成一个连通分量**  
那么  
 P n ( X = 1 ) = 1 − P n ( X = 0 ) P\_n(X=1) = 1 - P\_n(X=0) Pn(X=1)=1−Pn(X=0)  
 P n ( X = 0 ) = ∑ i = 1 n − 1 P n ( X = 0 , Y = y i ) P\_n(X=0) = \\sum\_\{i=1\}^\{n-1\}P\_n(X=0, Y=y\_i) Pn(X=0)=∑i=1n−1Pn(X=0,Y=yi) (公式一)  
上式的意思是, 一个图连通的概率等于 1 − 1- 1−这个图不连通的概率.  
而这个图不连通的时候, 最后一个结点可能与任意的 0 ~ n-2 个其结点相连, 所以这个图不连通的概率等于**最后一个节点在与 0, 1, … n-2 个其他节点相连时图不连通的概率总和**.  
如果 i < n, 那么  P n ( X = 0 ∣ Y = y i ) = 1 P\_n(X=0|Y=y\_\{i\})=1 Pn(X=0∣Y=yi)=1, 因为 Y = y i Y=y\_\{i\} Y=yi 表示最后一个节点所在的连通分量的节点数 = i < n, 所以此时整个图必定不是连通图.  
所以公式一可以改写为  
 P n ( X = 0 ) = ∑ i = 1 n − 1 P n ( Y = y i ) P\_n(X=0) = \\sum\_\{i=1\}^\{n-1\}P\_n(Y=y\_i) Pn(X=0)=∑i=1n−1Pn(Y=yi)  
现在求  P n ( Y = y i ) P\_n(Y=y\_i) Pn(Y=yi):  
对于指定的 k - 1 个节点, 最后一个节点和这 k - 1 个节点所构成的 k 个节点是连通图 (相连) 的概率是  P k ( X = 1 ) P\_\{k\}(X=1) Pk(X=1), 如果这个连通图仅包含 k 个节点, 那么其余的 n - k 个节点必定不与这 k 个节点中的任何一个节点相连, 因此**对于指定的 k - 1 个节点**, 有:  
 P n ( Y = y k ) = P k ( X = 1 ) × ( 1 − p ) ( n − k ) k P\_n(Y=y\_k)=P\_k(X=1)\\times(1-p)^\{(n-k)k\} Pn(Y=yk)=Pk(X=1)×(1−p)(n−k)k  
而在除了最后一个节点以外的其余 n - 1 个节点中, 一共有  C n − 1 k − 1 C\_\{n-1\}^\{k-1\} Cn−1k−1 种可能的组合, 所以对于**一般情况**, 有:  
 P n ( Y = y k ) = C n − 1 k − 1 × P k ( X = 1 ) × ( 1 − p ) ( n − k ) k P\_n(Y=y\_k)=C\_\{n-1\}^\{k-1\}\\times P\_k(X=1)\\times(1-p)^\{(n-k)k\} Pn(Y=yk)=Cn−1k−1×Pk(X=1)×(1−p)(n−k)k  
综上,  
 P n ( X = 1 ) = 1 − P n ( X = 0 ) = 1 − ∑ i = 1 n − 1 P n ( Y = y i ) = 1 − ∑ i = 1 n − 1 ( C n − 1 k − 1 × P k ( X = 1 ) × ( 1 − p ) ( n − k ) k ) P\_n(X=1) = 1- P\_n(X=0) =1- \\sum\_\{i=1\}^\{n-1\}P\_n(Y=y\_i)=1-\\sum\_\{i=1\}^\{n-1\} (C\_\{n-1\}^\{k-1\}\\times P\_k(X=1)\\times(1-p)^\{(n-k)k\}) Pn(X=1)=1−Pn(X=0)=1−∑i=1n−1Pn(Y=yi)=1−∑i=1n−1(Cn−1k−1×Pk(X=1)×(1−p)(n−k)k)  
即  
 P n ( X = 1 ) = 1 − ∑ i = 1 n − 1 ( C n − 1 k − 1 × P k ( X = 1 ) × ( 1 − p ) ( n − k ) k ) P\_n(X=1)=1-\\sum\_\{i=1\}^\{n-1\} (C\_\{n-1\}^\{k-1\}\\times P\_k(X=1)\\times(1-p)^\{(n-k)k\}) Pn(X=1)=1−∑i=1n−1(Cn−1k−1×Pk(X=1)×(1−p)(n−k)k)  
上式中  P k ( X = 1 ) P\_k(X=1) Pk(X=1) 可以通过动态规划建表推出来.

# 代码 #

## C语言 ##

#include <stdio.h>
    #define MAXN 21
    
    double jiecheng[MAXN];
    double dp[MAXN];
    
    double C(int m, int n) { 
        return jiecheng[m] / jiecheng[n] / jiecheng[m-n];
    }
    
    double qpow(double a, int b) { 
        double result = 1.0;
        while (b) { 
            if (b&1) result *= a;
            a *= a;
            b >>= 1;
        }
        return result;
    }
    
    int main() { 
        jiecheng[0] = 1;
        for (int i = 1; i < MAXN; i++) jiecheng[i] = jiecheng[i-1] * i;
        int n;
        double p;
        scanf("%d %lf", &n, &p);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = p;
        for (int i = 3; i < MAXN; i++) { 
            double ans = 1;
            for (int k = 1; k < i; k++) { 
                ans -= C(i-1, k-1) * dp[k] * qpow(1-p, k*(i-k));
            }
            dp[i] = ans;
        }
        printf("%.7lf\n", dp[n]);
    }

## Python ##

MAXN = 21
    jiecheng = [1]
    for i in range(1, MAXN):
        jiecheng.append(i * jiecheng[i-1])
    
    def c(m, n):
        return jiecheng[m] // jiecheng[n] // jiecheng[m-n]
    
    def qpow(a, b):
        result = 1.0
        while b != 0:
            if (b & 1) == 1:
                result *= a 
            a *= a 
            b >>= 1
        return result
    
    inputs = input().split()
    n = int(inputs[0])
    p = float(inputs[1])
    
    dp = [0, 1, p]
    
    for i in range(3, MAXN):
        ans = 1
        for k in range(1, i):
            ans -= c(i-1, k-1) * dp[k] * qpow(1-p, k*(i-k))
        dp.append(ans)
    
    print('%.7f' % dp[n])

# 总结 #

这道题构造的思路太刁钻了…  
感觉还需要再多做几道这种题才能真正具备这种能力…

[Link 1]: https://nanti.jisuanke.com/t/A1596