概率与期望学习心得-蒲公英云

概率与期望学习心得

修正信息备注：
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题目链接

题意：

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题目链接

题意：

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

Input:

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

Output:

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

Sample Input:

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;
}