โปรแกรมตรวจสอบการแปลงจุด (sx,sy) เป็น (tx,ty) ใน Python

ปัญหา

จุดเริ่มต้น (sx, sy) จุดเป้าหมาย (tx, ty) Move: (x, y) → (x, x+y) หรือ (x+y, y) ตรวจสอบว่าสามารถไปถึงได้หรือไม่

ตัวอย่าง

(1,1) → (4,5): True

Path: (1,1)→(2,1)→(3,1)→(4,1)→(4,5)

อัลกอริทึม (Work Backwards - Euclidean Algorithm)

ยากที่จะ Forward (Branch Factor = 2) แต่ง่ายถ้า Backward: จาก (tx, ty) ถ้า tx > ty → มาจาก (tx-ty, ty) ถ้า ty > tx → มาจาก (tx, ty-tx) คล้าย Euclidean GCD

ตัวอย่างโค้ด (Recursive)

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)

print(solve(1, 1, 4, 5))  # True

Iterative Version (แนะนำ ป้องกัน Stack Overflow)

def solve_iter(sx, sy, tx, ty):
    while tx >= sx and ty >= sy:
        if tx == sx:
            return (ty - sy) % sx == 0
        if ty == sy:
            return (tx - sx) % sy == 0
        if tx > ty:
            tx %= ty
        else:
            ty %= tx
    return False

ความซับซ้อน

• Time: O(log max(tx, ty)) - คล้าย Euclidean Algorithm
• Space: O(1) Iterative, O(log max) Recursive