Python遊戲勝負判斷程式

假設我們正在玩一個兩人遊戲，遊戲中有n顆彈珠，每一輪，玩家必須拿走正方形數量的彈珠。如果玩家無法拿走正方形數量的彈珠，則該玩家輸。因此，給定一個數字n，我們必須確定我們能否贏得遊戲。我們總是先走，並選擇最佳數量的彈珠。

因此，如果輸入是14，則輸出為True。因為在第一輪，我們拿走9顆彈珠。剩下5顆彈珠，另一位玩家最多可以拿走4顆彈珠，剩下1顆彈珠。因此，在下一輪，我們拿走最後一顆彈珠，對手無法行動，我們獲勝。

為了解決這個問題，我們將遵循以下步驟：

  • 如果 n <= 0，則
    • 返回 False
  • ans := False
  • 對於 i 從 n 的平方根的整數部分到 -1，遞減 1，執行：
    • 如果 i * i > n，則
      • 跳出迴圈
    • ans := ans OR (not solve(n - i * i))
    • 如果 ans 為 True，則
      • 返回 ans
  • 返回 ans

示例

讓我們看看下面的實現以更好地理解：

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

更新於：2021年10月16日

486 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告