概率与期望学习心得

Love The Way You Lie 2022-06-01 12:53 229阅读 0赞

修正信息备注：  
1.【2018-01-30】创作博文基础  
2.【2018-01-30】增加样例2.2

一、基本定义  
1.数学期望：在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。（百度百科）

二、例题解析  
2.1【求期望：转化为n重伯努利实验】  
2.2【求期望：递推式移项化简得到动态规划转移方程(转化为概率DP求解)】

#### 2.1[【The Keys Gym - 101063J】——vjudge题目链接][The Keys Gym - 101063J_vjudge] ####

##### 题意： #####

n个门，k个钥匙串，n个门的钥匙随机放在k个钥匙串上，多个门可能对应一把钥匙。科学家需要依次打开n个门，初始时第一个钥匙所在的钥匙串在科学家手里，其它钥匙串在科学家口袋里。当科学家来到第i个门(1 < i <= n)，若此时手中的钥匙串含有的钥匙无法打开门，则随机从口袋里选择一串钥匙与手中的钥匙串交换。询问，科学家打开所有们钥匙串交换次数的数学期望。

##### Input: #####

第一行输入整数n(1 <= n <= 1e5)和k(1 <= 1 <= n)，表示门的个数和钥匙串的个数。  
第二行输入n个以空格隔开的整数ai(1 <= ai <= 1e6)，表示打开第i个门需要钥匙ai。

##### Output: #####

单独一行，输出交换次数的数学期望，误差小于1e-6认为可接受。

##### Sample: #####

###### 1.Input: ######

3 3
    1 2 3

###### 1.Output: ######

1.333333333

###### 2.Input: ######

1 1
    2

###### 2.Output: ######

0.000000000

###### 3.Input: ######

5 2
    1 2 3 2 1

###### 3.Output: ######

2.000000000

题目分析：  
1.转换为n重伯努利实验求解  
对于单次实验：\{  
打开每个门只有两种状态：需要交换和不需要交换  
p\{需要交换\} = (k-1)/k  
p\{不需要交换\} = 1/k  
\}

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <iomanip>
    #include <algorithm>
    
    using namespace std;
    
    typedef long double LD;
    
    int main(){
        int m, k, n, i, a, b;
        while(~scanf("%d %d", &m, &k)){
            /*思路：转化为n-1次独立重复实验*/
            LD e = (LD)(k-1)/(LD)k;
            n = 0;
            for(i = 0; i < m; i++){
                scanf("%d", &b);
                if(i > 0 && b != a) n++;
                a = b;
            }
            LD E = (LD)n*e;
            cout << setiosflags(ios::fixed) << setprecision(9);
            cout << E << endl;
        }
        return 0;
    }

#### [Race to 1 Again LightOJ - 1038——vjudge题目链接][Race to 1 Again LightOJ - 1038_vjudge] ####

##### 题意： #####

输入一个数D，要求每次选择D的一个因子ni，使得D = D/ni，直到D等于１时停止，询问变成1的期望步数

##### Input: #####

第一行输入测试组数T(T <= 1e4)  
之后T行，每行输入一个数D(1 <= D <= 1e5)

##### Output: #####

每组测试数据单独一行，输出D按规则变为1的期望步数

##### Sample Input: #####

3
        1
        2
        50

##### Sample Output: #####

Case 1: 0
        Case 2: 2.00
        Case 3: 3.0333333333

解题思路：  
1.通过递推得到动态转移方程  
1.1设数D，含有n个因子n(1)、n(2)、… n(n)  
1.2则选到每个因子的概率为1/n  
1.3通过每个因子的期望步数加1步则到达所求D  
1.4即：

*d**p*\[*D*\]=1/*n*∗∑(*d**p*\[*D*/*n**i*\]\+1)、\[1,*n*\]  d p \[ D \] = 1 / n ∗ ∑ ( d p \[ D / n i \] + 1 ) 、 \[ 1 , n \]

即：*n*∗*d**p*\[*D*\]=∑(*d**p*\[*D*/*n**i*\]\+1)、\[1,*n*\]  即 ： n ∗ d p \[ D \] = ∑ ( d p \[ D / n i \] + 1 ) 、 \[ 1 , n \]

即：*n*∗*d**p*\[*D*\]=(*d**p*\[*D*/1\]\+1)\+(*d**p*\[*D*/*D*\]\+1)\+∑(*d**p*\[*D*/*n**i*\]\+1)、\[2,*n*−1\]  即 ： n ∗ d p \[ D \] = ( d p \[ D / 1 \] + 1 ) + ( d p \[ D / D \] + 1 ) + ∑ ( d p \[ D / n i \] + 1 ) 、 \[ 2 , n − 1 \]

又因为*d**p*\[1\]=0  又 因 为 d p \[ 1 \] = 0

即：(*n*−1)∗*d**p*\[*D*\]=*n*\+∑*d**p*\[*D*/*n**i*\]、\[2,*n*−1\]  即 ： ( n − 1 ) ∗ d p \[ D \] = n + ∑ d p \[ D / n i \] 、 \[ 2 , n − 1 \]

即：*d**p*\[*D*\]=(*n*\+∑*d**p*\[*D*/*n**i*\])/(*n*−1)、\[2,*n*−1\]  即 ： d p \[ D \] = ( n + ∑ d p \[ D / n i \] ) / ( n − 1 ) 、 \[ 2 , n − 1 \]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    double dp[104014];
    
    void init(int N);
    
    int main(){
        init(1e5);
        int k = 1, T, D;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &D);
            printf("Case %d: %.9lf\n", k++, dp[D]);
        }
        return 0;
    }
    void init(int N){
        int i, j, cnt; double sum;
        dp[1] = 0.0;
        for(i = 2; i <= N; i++){
            cnt = 2, sum = 0.0;
            for(j = 2; j*j <= i; j++){
                if(i % j != 0) continue;
                if(j*j == i) {
                    cnt += 1, sum += dp[j];
                }
                else {
                    cnt += 2, sum += (dp[j] + dp[i/j]);
                }
            }
            dp[i] = (sum + cnt)/(double)(cnt-1);
        }
        return;
    }

[The Keys Gym - 101063J_vjudge]: https://vjudge.net/problem/Gym-101063J
[Race to 1 Again LightOJ - 1038_vjudge]: https://vjudge.net/problem/LightOJ-1038