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.