Pythonでジャンプを繰り返して位置nに到達できるかどうかを判定するプログラム

1からnまでの番号が振られた数直線を考えてみましょう。最初は位置0におり、まず1ステップジャンプして位置1へ移動し、次に2ステップジャンプして位置3に到達し、さらに3ステップジャンプして位置6に到達します。このようにジャンプ幅を1ずつ増やしながら進んだとき、最終的に位置nにぴったり到達できるかどうかを判定するのがこの問題です。

例えば、入力が n = 21 の場合、出力は True になります。これは 1+2+3+4+5+6 = 21 となり、6回目のジャンプでちょうど位置21に到達できるためです。

解法のアプローチ

この問題は数学的な性質を利用すると効率的に解けます。手順は以下の通りです。

• j := (1 + √(1+8n)) / 2 を計算する
• j の小数部分が0（つまり j が整数）であれば True を返す
• それ以外の場合は False を返す

この式の背景には「三角数」の概念があります。k回目のジャンプ後の位置は 1+2+…+k = k(k+1)/2 で表されます。これが n に一致するかを確認したいので、k(k+1)/2 = n を変形すると二次方程式 k² + k − 2n = 0 が得られ、解くと k = (−1 + √(1+8n)) / 2 となります。したがって、この値が整数になれば、ちょうどその回数のジャンプで位置 n に到達できることが分かります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from math import sqrt
def solve(n):
   j=(1+sqrt(1+8*n))/2
   if abs(j-int(j))<=0:
      return True
   else:
      return False

n = 21
print(solve(n))

入力

21

出力

True