Pythonのゲームで勝つかどうかを調べるプログラム

n個のビー玉があり、各ラウンドで、プレーヤーが正の平方数のビー玉を取る必要がある2人用ゲームをプレイしているとします。プレイヤーがその正方形のビー玉をとることができない場合、彼/彼女は負けます。したがって、数字nが与えられた場合、ゲームに勝つことができるかどうかを確認する必要があります。私たちは常に最初のターンを行い、最適な数のビー玉を選択します。

したがって、入力が14のような場合、出力はTrueになります。最初のターンでは、9個のビー玉を取ります。これにより、5個のビー玉が残り、他のプレーヤーは最大4個のビー玉を取り、1個のビー玉を残すことができます。したがって、次のターンでは、最後のビー玉を取り、相手の後ろに0個のビー玉を残して移動できません。したがって、私たちは勝ちます。

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

• n <=0の場合、
  • Falseを返す
• ans：=False
• （（n）の平方根）の整数部分から-1までの範囲のiの場合、1ずつ減少します。
  • i * i> nの場合、
    • ループから抜け出す
  • ans：=ans OR（解決しない（n-i * i））
  • ansがTrueの場合、
    • 回答を返す
• 回答を返す

例

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

from math import sqrt

def solve(n):
   if n <= 0:
      return False
   ans = False
   for i in range(int(sqrt(n)), 0, -1):
      if i * i > n:
         break
      ans = ans | (not solve(n - i * i))
      if ans:
         return ans
   return ans

print(solve(14))

入力

14

出力

True