BBruceyuan

01之间均匀分区取两点构成三角形的概率-证明加代码实现

1. 背景

这是一道我面试字节Data某搜索部门NLP算法工程师岗位出的一道题,可能是由于前面回答问题不是尽如人意,所以一看到这题的时候有点紧张,大概嗯嗯啊啊半分钟,直接心里面觉得自己不会做,便对面试官说想换一个题。等我面试完和同学交流的时候,念完题目就差不多想到了该怎么做,就是个高中的简单整数线性规划问题。

2. 题目描述

假设有一个区间 [0, 1],通过均匀分布取两个点,把区间分成三段,那么这三段构成三角形的概率是多少?

3. 代码解法

既然这是一道编程题,那么其实这个解法就太简单了,根本什么也不用想,直接用代码实现就行了。

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
import numpy as np

def can_construct_triangle(a, b):
# 使用 任意两边之和大于第三边的性质
a, b = min(a, b), max(a, b)

x = a
y = b - a
z = 1 - b

if x + y > z and x + z > y and y + z > x:
return True
else:
return False

def main():
total_cnt = 0
cnt_be_triangle = 0
for _ in range(1000000):
# 大量随机试验
a = np.random.uniform(0, 1)
b = np.random.uniform(0, 1)
if can_construct_triangle(a, b):
cnt_be_triangle += 1
total_cnt += 1

print(cnt_be_triangle / total_cnt)
# answer is approximate 1/4

if __name__ == "__main__":
main()

用程序跑一下,答案大概是 0.24968,把循环放大一点,就能得到更接近1/4的答案,所以这题的答案应该是1/4。以后遇到不会的数学题,直接用过大量试验求近似解是一个很好的想法。(比如计算机实现牛顿迭代其实就是这么一个思想)

4. 数学解法

4.1 抽丝剥茧看条件

均匀分布取两个点,那么说明两个点是独立同分布,两个点有可能出现在任意位置,任意两个不重合的点可以构成三条边,那么如果要构成三角形,就需要满足构成三角形的条件。

任意两边之和大于第三边 或者是 任意两边之差小于第三边,且每条边大于0。

因此该问题可以转化为不等式求解问题。

4.2 转化为数学表达式

假设随机抽样的两点把 [0, 1] 分成三段,分别是 x, y, 1 - x - y。
因此可以构成一个公式
$$x > 0;\ y > 0;\ 1 - x -y > 0\tag{1}$$

然后要满足构成三角形的条件,两边之和大于第三边,所以就相当于在上述可行域中找到问题的解空间,这不就是高中非常熟悉的整数线性规划问题吗?只是套了一个均匀分布取两个点的背景。那么看一下三角形两边之和大于第三边的公式是什么?

$$x + y > 1 - x - y;\ x + 1 - x - y > y;\ y + 1 - x - y > x\tag{2}$$

公式(2)可以进行化简,可以推导出公式(3)

$$x < 1/2;\ y < 1/2;\ x + y > 1/2\tag{3}$$

结合公式(1)(3),那么该问题显然是一个简单的数学问题,只要画出图,问题就可以轻易的求解。我的解法配图如下
image.png

5. Reference

[1] https://www.cnblogs.com/xudong-bupt/p/4032639.html
[2] https://blog.csdn.net/nickkissbaby_/article/details/95621403


专题:

本文发表于 2020-08-02,最后修改于 2020-08-06。

本站永久域名bbruceyuan.github.io,也可搜索「 BBruceyuan 」找到我。

期待关注我的 知乎专栏微博 ,查看最近的文章和动态。


上一篇 « Transition-based Directed Graph Construction for Emotion-Cause Pair Extraction (中文介绍) 下一篇 » 简单方法增加Query召回的多样性

赞赏支持

谢谢支持~

i ali

支付宝

i wechat

微信

推荐阅读

Big Image