Python
 Computer >> コンピューター >  >> プログラミング >> Python

PythonでちょうどNステップで(0, 0)から(x, y)へ移動できるか判定する方法

座標点 (x, y) と整数 n が与えられたとき、ちょうど n ステップで原点 (0, 0) から (x, y) へ移動できるかどうかを判定します。移動は上下左右の4方向のいずれかに、1回につき1ステップずつ行うことができます。

例えば、入力が p = (2, 1)、n = 3 の場合、出力は True になります。右に2ステップ、上に1ステップ進むことで、合計3ステップで目的の点に到達できるからです。

解法のアプローチ

この問題は以下の手順で解くことができます。

  • n が |x| + |y| 以上であり、かつ n − (|x| + |y|) が偶数である場合は True を返す
  • それ以外の場合は False を返す

なぜ「偶数」という条件が必要なのか

|x| + |y| は原点から目的地までのマンハッタン距離、つまり最短で必要なステップ数です。もし余分なステップがある場合は、「1ステップ進んで1ステップ戻る」といった無駄な往復移動で消費するしかありません。往復は必ず2ステップずつ消費するため、余分なステップ数が偶数でない限り、ちょうど n ステップで到達することはできません。

実装例

以下のコードで実際の動作を確認してみましょう。

def solve(p, n):
    if n >= abs(p[0]) + abs(p[1]) and (n - (abs(p[0]) + abs(p[1]))) % 2 == 0:
        return True
    return False

p = (2, 1)
n = 3
print(solve(p, n))

入力

(2, 1), 3

出力

True

  1. Pythonでベクトルxを90度回転・加算してベクトルyに到達できるか判定するアルゴリズム

    2次元平面上に3つのベクトル x、y、z があるとします。ベクトル x を起点として、「90度(時計回り)の回転」または「ベクトル z の加算」を必要な回数だけ繰り返すことで、ベクトル y に到達できるかどうかを判定するのがこの問題です。 たとえば、入力が x = (-4, -2)、y = (-1, 2)、z = (-2, -1) である場合、出力は True になります。x に対して z を加算する操作と 90 度の時計回り回転を組み合わせることで、y = (-1, 2) の位置に到達できるからです。 解法のアプローチ この問題は、次の手順に沿って解くことができます。 1. util()

  2. Pythonで配列内のゼロを右端に移動するアルゴリズム

    数値を格納する配列を考えてみましょう。この配列には、ゼロ以外の値とゼロの値が混在しています。ここでの課題は、他の数値の相対的な順序を変えずに、すべてのゼロを配列の右端（末尾）へ移動させることです。 例えば、配列が [0, 1, 5, 0, 3, 8, 0, 0, 9] の場合、処理後の最終的な配列は [1, 5, 3, 8, 9, 0, 0, 0, 0] となります。 解決手順 この問題は、次の手順で解くことができます。 挿入位置を記録するためのインデックス index を 0 で初期化します。 i = 0 から配列 A の長さまで繰り返します。 A[i] != 0 の場合： A[in