Chương trình kiểm tra chuyển đổi điểm này sang điểm khác trong Python

Cho điểm xuất phát (sx, sy) và điểm đích (tx, ty). Kiểm tra có tồn tại chuỗi phép biến đổi từ start đến end. Phép biến đổi: (x, y) → (x, x+y) hoặc (x+y, y).

Ví dụ: (1,1) → (4,5) → True (1,1)→(2,1)→(3,1)→(4,1)→(4,5).

Giải thuật (Đệ quy ngược / Euclidean-like)

• Nếu sx > tx hoặc sy > ty → False.
• Nếu sx == tx → kiểm tra (ty - sy) % sx == 0.
• Nếu sy == ty → kiểm tra (tx - sx) % sy == 0.
• Ngược lại: đệ quy solve(sx, sy, tx-ty, ty) OR solve(sx, sy, tx, ty-tx).

Code Python

def solve(sx, sy, tx, ty):
    if sx > tx or sy > ty:
        return False
    if sx == tx:
        return (ty - sy) % sx == 0
    if sy == ty:
        return (tx - sx) % sy == 0
    return solve(sx, sy, tx - ty, ty) or solve(sx, sy, tx, ty - tx)

sx, sy = 1, 1
tx, ty = 4, 5
print(solve(sx, sy, tx, ty))  # True

Đầu vào / Đầu ra

Input: (1,1), (4,5)
Output: True