1. 背景

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

2. 题目描述

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

3. 代码解法

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

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; 1xy>0(1)x > 0;\ y > 0;\ 1 - x -y > 0\tag{1}

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

x+y>1xy; x+1xy>y; y+1xy>x(2)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(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.htmlopen in new window [2] https://blog.csdn.net/nickkissbaby_/article/details/95621403open in new window

Last Updated:
Contributors: bbruceyuan