面试题

题目一：

你不断掷一个骰子，把点数累加，不限制次数，总分超过m就停止，求总分落在[m,n]区间的概率。

class Solution {
public:
    double get_res(int n, int m) {
        if (m == 0) {
            return 1.0;
        }
        vector<double> dp(m + 6);
        for (int i = m; i <= n && i < m + 6; i++) {
            dp[i] = 1.0;
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j <= 6; j++) {
                dp[i] += dp[i + j] / 6;
            }
        }
        return dp[0];
    }
};

题目二：

使用一个均匀的六面骰子，不断投掷，直到连续两次掷出6，求期望投掷次数。

E0 = 42

我们只需要关心“当前连续背面个数”：

• 状态 S0：一次没扔
• 状态 S1：扔了一次6，还差一次
• 状态 S2：终止状态

转移关系：

• 从 S0：
  • 1/6：扔到6，进入S1
  • 5/6：未扔到，仍然是S0
• 从 S1：
  • 5/6：回到 S0
  • 1/6：进入 S2（游戏结束）
• S2：吸收态（游戏结束）

设：

• E0 = 从 S0 到 S2 的期望步数
• E1 = 从 S1 到 S2 的期望步数

列方程：

E0 = 1 + E1/6 + 5E0/6
E1 = 1 + 5E0/6   （因为从S1抛背面就结束了）