Pythonで1つのポイントを別のポイントに変換できるかどうかを確認するプログラム

開始点（sx、sy）と目標点（tx、ty）があるとすると、開始点から終了点までの一連の移動が存在するかどうかを確認する必要があります。ここでの移動は、点（x、y）を取得し、それを（x、x + y）または（x + y、y）に変換することで構成されます。

したがって、入力が（sx、sy）=（1,1）（tx、ty）=（4,5）のようである場合、出力はTrueになります。これは、（1,1）を（2、 1）、次に（3,1）、次に（4,1）、次に（4,5）。

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これにはsx、sy、tx、tyが必要です

• sx>txまたはsy>tyの場合、

  • Falseを返す

• sxがtxと同じ場合、

  • return（ty-sy）modsxは0と同じです

• syがtyと同じ場合、

  • return（tx --sx）modsyは0と同じです

• 戻り値solve（sx、sy、tx-ty、ty）またはsolve（sx、sy、tx、ty-tx）

例

理解を深めるために、次の実装を見てみましょう

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

入力

(1,1), (4,5)

出力

True