Đây là một câu hỏi tôi đã gặp trong buổi phỏng vấn cho vị trí kỹ sư thuật toán NLP tại một bộ phận tìm kiếm của công ty ByteDance. Có lẽ do phần trả lời trước đó không được tốt lắm, nên khi nhìn thấy câu hỏi này, tôi cảm thấy hơi căng thẳng. Sau khoảng nửa phút bối rối, tôi tự nhủ rằng mình không thể giải được và yêu cầu đổi sang một câu hỏi khác. Tuy nhiên, sau buổi phỏng vấn, khi trao đổi với bạn bè, tôi nhận ra rằng đây chỉ là một bài p88 nhà cái toán lập trình tuyến tính đơn giản thường gặp ở bậc trung học.

2. Mô tả bài toán

Giả sử có một đoạn [0, 1], chúng ta chọn ngẫu nhiên hai điểm theo phân phối đều để chia đoạn này thành ba phần. Hỏi xác suất để ba phần này có thể tạo thành một tam giác là bao nhiêu?

78win+đăng+nhập 3. Giải pháp bằng mã nguồn

Do đây là một bài toán về lập trình, cách giải quyết rất đơn giản: chỉ cần viết mã để mô phỏng và kiểm tra điều kiện hình thành tam giác.

 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

import numpy as np

def co_the_tao_thanh_tam_giac(a, b):
    # Sử dụng thuộc tính tổng hai cạnh bất kỳ phải lớn hơn cạnh thứ ba
    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 chinh():
    tong_so_lan_thu = 0
    so_lan_tao_thanh_tam_giac = 0
    for _ in range(1000000):
        # Thực hiện nhiều lần thử nghiệm ngẫu nhiên
        a = np.random.uniform(0, 1)
        b = np.random.uniform(0, 1)
        if co_the_tao_thanh_tam_giac(a, b):
            so_lan_tao_thanh_tam_giac += 1
        tong_so_lan_thu += 1
    print(so_lan_tao_thanh_tam_giac / tong_so_lan_thu)

if __name__ == "__main__":
    chinh()

Chạy chương trình, kết quả thu được là khoảng 0.24968. Nếu tăng số lần lặp, giá trị sẽ càng gần với 1/4. Do đó, đáp án chính xác của bài toán này là 1/4. Khi gặp các bài toán toán học khó, việc sử dụng phương pháp thử nghiệm ngẫu nhiên trên máy tính để tìm gần đúng là một ý tưởng tuyệt vời (ví dụ như cách máy tính thực hiện phương pháp lặp Newton).

4. Giải pháp toán học

4.1 Phân tích điều kiện

Hai điểm được chọn theo phân phối đồng nhất, nghĩa là hai điểm độc lập và cùng phân phối. Hai điểm này có thể xuất hiện ở bất kỳ vị trí nào, và mỗi cặp điểm không trùng nhau sẽ tạo thành ba đoạn. Để ba đoạn này có thể tạo thành một tam giác, chúng cần thỏa mãn điều kiện tạo tam giác.

Tổng của hai cạnh bất kỳ phải lớn hơn cạnh còn lại hoặc hiệu của hai cạnh bất kỳ phải nhỏ hơn cạnh còn lại, và mỗi cạnh phải lớn hơn 0.

Vấn đề này có thể được chuyển hóa thành bài toán giải hệ bất phương trình.

4.2 Chuyển hóa thành biểu thức toán học

Giả sử hai điểm ngẫu nhiên chia đoạn [0, 1] thành ba phần, tương ứng là \(x\), \(y\), và \(1 - x - y\). Ta có các điều kiện sau:

(1) \(x > 0\); \(y > 0\); \(1 - x - y > 0\)

Tiếp theo, để thỏa mãn điều kiện tạo tam giác (tổng hai cạnh bất kỳ phải lớn hơn cạnh còn lại), ta có:

(2) \(x + y > 1 - x - y\); \(x + 1 - x - y > y\); \(y + 1 - x - y > x\)

Công thức (2) có thể được đơn giản hóa thành công thức (3):

(3) \(x < 1/2\); \(y < 1/2\); \(x + y > 1/2\)

Kết hợp công thức (1) và (3), vấn đề trở thành một bài toán toán học đơn giản. Chỉ cần vẽ đồ thị, giải pháp có thể dễ dàng tìm ra. Hình ảnh minh họa kèm theo như sau: