Python 程式檢查 Amal 是否能贏得石頭遊戲

假設有兩個玩家 Amal 和 Bimal，他們在玩一個遊戲，Amal 先開始。最初，一堆中有 n 個不同的石頭。在每個玩家的回合中，他進行一個操作，從堆中移除任意數量的平方數（非零）的石頭。此外，如果一個玩家無法進行操作，則他輸掉比賽。所以如果我們有 n，我們必須檢查 Amal 是否能贏得比賽。

因此，如果輸入類似於 n = 21，則輸出將為 True，因為首先 Amal 可以取走 16，然後 Bimal 取走 4，然後 Amal 取走 1 並贏得比賽。

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

  • squares := 一個新的列表

  • square := 1

  • increase := 3

  • 當 square <= n 時，執行

    • 將 square 插入 squares 的末尾

    • square := square + increase

    • increase := increase + 2

  • 將 square 插入 squares 的末尾

  • dp := 一個大小為 (n + 1) 的空列表

  • dp[0] := False

  • 對於 k 從 1 到 n，執行

    • s := 0

    • dp[k] := False

    • 當 squares[s] <= k 且 dp[k] 為空時，執行

      • 如果 dp[k - squares[s]] 為空，則

        • dp[k] := True

      • s := s + 1

  • 返回 dp 的最後一個元素

示例

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

def solve(n):
   squares = []
   square = 1
   increase = 3
   while square <= n:
      squares.append(square)
      square += increase
      increase += 2
   squares.append(square)

   dp = [None] * (n + 1)
   dp[0] = False
   for k in range(1, n + 1):
      s = 0
      dp[k] = False
      while squares[s] <= k and not dp[k]:
         if not dp[k - squares[s]]:
            dp[k] = True
         s += 1
   return dp[-1]

n = 21
print(solve(n))

輸入

21

輸出

True

更新於: 2021年10月6日

129 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.