Chương trình tìm phân số chung gần pi nhất trong khoảng cho trước Python

Cho min, max. Tìm phân số n/d với min ≤ d ≤ max sao cho |n/d - π| nhỏ nhất. Nếu nhiều, chọn mẫu số nhỏ nhất. Dùng dãy Farey và xấp xỉ liên tục.

Thuật toán

• Xây dãy Farey đến mẫu số ≤ max-min.
• Dùng phân số 5706674932067741/1816491048114374 ≈ π.
• Tìm phân số tốt nhất trong khoảng bằng cách duyệt dãy Farey.

Ví dụ

from fractions import Fraction

def solve(minimum, maximum):
    P = Fraction(5706674932067741, 1816491048114374) - 3
    a, b, c, d = 0, 1, 1, 1
    farey = [(a, b), (c, d)]
    while True:
        f = b + d
        if f > maximum - minimum:
            break
        e = a + c
        farey.append((e, f))
        if P < Fraction(e, f):
            c, d = e, f
        else:
            a, b = e, f
    p_min = int(P * minimum)
    while minimum <= maximum:
        c, d = 0, 0
        for a, b in farey:
            if minimum + b > maximum:
                break
            if abs(Fraction(p_min + a, minimum + b) - P) < abs(Fraction(p_min, minimum) - P):
                c, d = a, b
                break
        if d == 0:
            break
        p_min += c
        minimum += d
    return f"{p_min + 3 * minimum}/{minimum}"

print(solve(1, 10))  # Output: 22/7

Giải thích

min=1, max=10 → 22/7 ≈ 3.142857 gần π nhất.