Leetcode概率题面试突击系列11~15

目录

11. 完美手牌

问题描述

思路与算法

 蒙特卡洛仿真

12. 双骰子赌博

问题描述

思路与算法

蒙特卡洛仿真

13. 收集优惠券

问题描述

思路与算法

蒙特卡洛仿真

14. 第 2 强的选手拿亚军

 问题描述

思路与算法

蒙特卡洛仿真

---

11. 完美手牌

问题描述

从一副洗好的牌（52张）中抽 13 张，拿到完美手牌（拿到的 13 张是同花色）的概率是多少。

思路与算法

        从52张任取13张的总的（因为与顺序无关）组合数为.

其中13张均同色的只有4种情况。

        所以概率为

 蒙特卡洛仿真

import numpy as np

# 注意，如果不指定'float32'的数据类型会出现溢出而导致计算错误
nomi  = np.prod(range(52,39,-1),dtype='float32')
denom = np.prod(range(1,14),dtype='float32')
combinations_52_13 =  nomi/ denom
p     = 4/combinations_52_13
print(nomi, denom, combinations_52_13,p) 

from math import factorial as fac

p = 4.0 * fac(13) * fac(39) / fac(52)
print("{:.6e}".format(p))

12. 双骰子赌博

问题描述

双骰子赌博是美国的流行游戏，规则如下：

每次同时投掷两个骰子并且只看点数和。第一次投掷的点数和记为 x。若 x 是 7 或 11，玩家获胜，游戏结束；若 x 是 2、3 或 12，则输掉出局，其余情况则需要继续投掷。从第二次投掷开始，如果投掷出第一次的点数和 x，则获胜；如果投掷出 7，则输掉出局。重复投掷直至分出胜负。

问：获胜的概率是多少？

思路与算法

        用一个状态机来表示游戏的进行状态。

        每次投掷的点数的可能取值为{2,3,4,...,12}，其概率则分别为{1/36, 2/36, 3/36, 4/36, 5/36, 6/36, 5/36, 4/36, 3/36, 2/36, 1/36}。

        由以上状态机可以看出，第一次投掷获胜结束的概率为2/9，失败的概率为1/9。

        第一次投掷后进入CONTINUE状态的概率为2/3，其中有{4,5,6,8,9,10}这6种可能的值。进入CONTINUE状态后，有1/6的概率投中7输掉游戏，需要投中和第一次相同的值获胜，其概率为,这个概率依赖于第一次投掷值；另外有的概率回保持在CONTINUE状态继续游戏，因此针对每一个可能的 值（以下计算失败的概率，这个比计算胜的概率容易一些）：

        第二次投掷后失败的概率为1/6

        第三次投掷后失败的概率为，因为需要在第二次投掷后保持在CONTINUE状态

        依此同理。。。

        在第k次投掷后失败的概率为...

        由此得到 第一次投掷值的条件下，从（第一次投掷后进入）CONTINUE状态开始总的失败的概率为。

        由此可以得到总的获胜概率为第一次投掷后获胜的概率加上其后的投掷中获胜的概率之和，第2部分为6种可能的的条件下的条件概率之和，如下所示：

                

        计算可得 ，

        因此，

蒙特卡洛仿真

from multiprocessing import Pool
import numpy as np

def throw2(x0):
    # 第二次以后的投掷
    x1 = np.random.randint(1, 7)
    x2 = np.random.randint(1, 7)
    x = x1 + x2
    if x == 7:
        return 0
    elif x == x0:
        return 1
    else:
        return throw2(x0)

def throw1():
    # 第一次投掷
    x1 = np.random.randint(1, 7)
    x2 = np.random.randint(1, 7)
    x = x1 + x2
    if x == 7 or x == 11:
        return 1
    elif x == 2 or x == 3 or x == 12:
        return 0
    else:
        return throw2(x)

def test(T):
    np.random.seed()
    n = 0
    for _ in range(T):
        n += throw1()
    return  n / T

T = int(1e7)
args = [T] * 8
pool = Pool(8)
probs = pool.map(test, args)
for prob in probs:
    print("Probability of win: {:.6f}".format(prob))

作者：FennelDumplings
链接：https://leetcode.cn/leetbook/read/probability-problems/no5h33/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

13. 收集优惠券

问题描述

每个盒子中有一张优惠券，优惠券共有 5 种，编号为 1 到 5。必须收集所有5张优惠券才能获得奖品。

问：收集到一套完整的优惠券平均需要打开多少盒子？

思路与算法

        收集第一张，只需要打开一个盒子。因为每个盒子必有一张优惠券。

        收集第二张，要求所打开得盒子中所包含得优惠券与已经收集的不同。有1/5的概率相同，4/5的概率不同。。。

        由此可以得到以下状态转移图：

        其中，状态k表示已经收集到k张不同的优惠券。 边上的数值表示转移概率。

        记表示从状态出发到收集满5张优惠券（即到达状态5）所需要打开的盒子数的数学期望，则可以列出如上图所示的方程，最后求解可以得到即为收集满5张优惠券所需要总的打开盒子数的数学期望。

        官解给出的是另一种思路，摘录如下供参考：

        以下依此类推。。。

蒙特卡洛仿真

import numpy as np
import operator
from multiprocessing import Pool
from functools import reduce

def run():
    setting = set()
    n = 0
    while True:
        n += 1
        x = np.random.randint(1, 6)
        if x in setting:
            continue
        setting.add(x)
        if len(setting) == 5:
            break
    return n

def test(T):
    np.random.seed()
    y = (run() for _ in range(T))
    n = reduce(operator.add, y)
    return n / T

T = int(1e7)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("{:.6f} coupons on average are required".format(t))

作者：FennelDumplings
链接：https://leetcode.cn/leetbook/read/probability-problems/no5h33/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

14. 第 2 强的选手拿亚军

 问题描述

        一场由 8 个人组成的淘汰赛，对阵图如上图。8 个人随机被分到图中的 1~8 号位置。
第二强的人总是会输给最强的人，同时也总是会赢剩下的人。决赛输的人拿到比赛的亚军。
问: 第二强的人拿到亚军的概率是多少？

思路与算法

        此题隐含的一个前提是胜负关系确定性地由实力排名决定。

 

        因此，排名第2的选手拿到亚军的概率其实就是他和排名第1的选手分在不同半区的概率。8个人随机分到1~8号位置的总的分配数为排列数，其中多少种排列中两者分在不同半区呢？

        令表示1号选手分在上半区；表示1号选手分在下半区；表示2号选手分在上半区；表示2号选手分在下半区。则两者分在不同半区的概率由以下全概率公式得到：

                

        考虑1号选手分在下半区的前提下2号选手分在上半区的条件概率。1号选手已经占据了下半区的某个位置，接下来分配2号选手，有7个位置可选，其中选择到上半区的概率自然是 。同理可得（或者由对称性可知）1号选手分在上半区的前提下2号选手分在下半区的条件概率同样为 。代入以上全概率公式可得两者分配在不同半区的概率为：

蒙特卡洛仿真

import numpy as np
import operator
from multiprocessing import Pool
from functools import reduce

ladder = range(8)

def run():
    l = np.random.permutation(ladder)
    x = int(np.where(l == 0)[0][0])
    y = int(np.where(l == 1)[0][0])
    return (x <= 3 and y >= 4) or (x >= 4 and y <= 3)

def test(T):
    np.random.seed()
    y = (run() for _ in range(T))
    n = reduce(operator.add, y)
    return n / T

T = int(1e7)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("P(the second-best player wins the runner-up cup): {:.6f}".format(t))

作者：FennelDumplings
链接：https://leetcode.cn/leetbook/read/probability-problems/no5b8m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

题目出处（题解及代码也部分参考）：

概率题面试突击 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

另参见：

Leetcode概率题面试突击系列1~5

Leetcode概率题面试突击系列6~10

Leetcode每日一题总目录(动态更新。。。)