Chương trình kiểm tra xem một điểm có thể được chuyển đổi sang điểm khác hay không bằng Python

Giả sử chúng ta có điểm bắt đầu (sx, sy) và điểm đích (tx, ty), chúng ta phải kiểm tra xem có tồn tại một chuỗi các bước di chuyển từ điểm bắt đầu đến điểm kết thúc hay không. Ở đây di chuyển bao gồm lấy một điểm (x, y) và biến đổi nó thành (x, x + y) hoặc (x + y, y).

Vì vậy, nếu đầu vào là (sx, sy) =(1,1) (tx, ty) =(4,5), thì đầu ra sẽ là True, điều này là do di chuyển (1,1) thành (2, 1), sau đó (3,1), sau đó (4,1), sau đó (4,5).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm giải quyết (). Điều này sẽ lấy sx, sy, tx, ty

• nếu sx> tx hoặc sy> ty, thì

  • trả về Sai

• nếu sx giống với tx thì

  • return (ty-sy) mod sx giống như 0

• nếu sy giống với ty, thì

  • return (tx - sx) mod sy giống như 0

• trả về giải quyết (sx, sy, tx-ty, ty) hoặc giải quyết (sx, sy, tx, ty-tx)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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))

Đầu vào

(1,1), (4,5)

Đầu ra

True