数概率

【Puzzle】圆周上随机取3个点形成锐角三角形

字数统计: 704字   |   阅读时长: 3分
,

摘要: 圆周上随机取3个点形成锐角三角形

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

这是概率面试题连载第 23 期，我们看一个面试题。

往期的内容整理在这篇文章里；或者看这个 github 仓库。

本题是关于几何概型的，题目提供者是个前同事，他前不久面试美团算法岗社招时候遇到的，我们来看一下这个题。

问题

在一个圆环上随机取3点，求这3个点组成一个锐角三角形的概率。

思路参考

如图，在圆周上取不同的两个点 X, Y，当 X, Y 确定后，再在圆周上取点 Z，要 XYZ 构成锐角三角形，需要 X 在圆弧 AB 上，如果超出圆弧 AB 的范围，有以下几种情况，哪一种都会使得 XYZ 不成为锐角三角形。

  • Z 如果在圆弧 AX 上，则角 X 就会变成钝角
  • Z 如果在圆弧 YB 上，则角 Y 就会变成钝角
  • Z 如果在圆弧 XY 上，则角 Z 就会变成钝角

当弧 XY 确定后，对应的圆心角为 $\theta$，该圆心角的范围是 [0, pi)，其概率密度函数为

此时再取点 Z 落在弧 AB 上的概率为 AB 对应的圆心角，也就是 $\theta$ 与整个圆的角度范围的比值

由连续型随机变量的全概率公式

蒙特卡洛模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import numpy as np
import math
from multiprocessing import Pool

def dist(x, y):
    return (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2

def test(T):
    n = 0
    np.random.seed()
    for _ in range(T):
        theta_x = np.random.uniform(0.0, 2 * math.pi)
        theta_y = np.random.uniform(0.0, 2 * math.pi)
        theta_z = np.random.uniform(0.0, 2 * math.pi)
        x = (math.cos(theta_x), math.sin(theta_x))
        y = (math.cos(theta_y), math.sin(theta_y))
        z = (math.cos(theta_z), math.sin(theta_z))
        d_xy = dist(x, y)
        d_yz = dist(y, z)
        d_zx = dist(z, x)
        if not d_xy + d_yz > d_zx:
            continue
        if not d_yz + d_zx > d_xy:
            continue
        if not d_zx + d_xy > d_yz:
            continue
        n += 1
    return n / T

T = int(1e6)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("锐角三角形的概率: {:.6f}".format(t))

模拟结果

1
2
3
4
5
6
7
8
锐角三角形的概率: 0.249651
锐角三角形的概率: 0.250418
锐角三角形的概率: 0.249653
锐角三角形的概率: 0.249947
锐角三角形的概率: 0.250386
锐角三角形的概率: 0.250427
锐角三角形的概率: 0.250429
锐角三角形的概率: 0.250860
Share