时间戳

首页 > 解决方案 > 简化 Nim 游戏的递归算法

python - 简化 Nim 游戏的递归算法

问题描述

在一个简化的 Nim 游戏中，两名玩家轮流从一堆 n 块石头中取 1 块或 2 块石头，取最后一块的玩家获胜，稍微思考或实验表明，在哪里n % 3 == 0，第一个玩家可以' t 赢，但对于n % 3 == 1or n % 3 == 2，他们可以。

在达到上述解决方案时，我注意到我使用的是递归思维过程，所以我不想编写一个只使用模运算符的程序，而是想编写一个递归版本，告诉我我是否能赢，以及如何移动在每一步制作。

我已经从下面的 Python 代码开始，但我一直坚持如何打印每一步要拿多少石头的指令。我可能犯了一个很大的概念错误，因为我没有考虑玩家 2 在每个步骤中会做什么——我无法判断这些信息是否是必不可少的，我是否可以使用我已经做出的观察。非常感谢您对完成我的程序的任何帮助。

def last_stone(n):
    # Base cases that guarantees player 1 will lose
    if n == 0:
        print("You can't win.")
        return False
    # Base cases that guarantees player 1 will win
    elif n == 1 or n == 2:
        return True
    else:
        return last_stone(n - 3)


for i in range(10):
    print(last_stone(i))

标签： pythonalgorithmrecursion

解决方案

这里的想法很简单。玩家 1 开始游戏。玩家 1 总是会采取行动以使他获胜，同样适用于玩家 2。

现在，这个问题就是这样。

  • n=1 -> 当前玩家获胜！
  • n=2 -> 当前玩家获胜！
  • n=3 -> 替补玩家获胜！
  • n=4 -> 当前玩家获胜！
  • 很快...

因此，只需以交替动作交换玩家并以最佳方式取石。

def get_current_player(moves):
    return "1" if moves%2==0 else "2"

def play_game(n,moves):
    if n==1:
        print("Player "+str(get_current_player(moves))+" moves 1 stone and wins!")
    elif n==2:
        print("Player "+str(get_current_player(moves))+" moves 2 stones and wins!")
    else:
        if n%3==0:
            print("Player "+str(get_current_player(moves))+" moves 1 stone")
            moves+=1
            play_game(n-1,moves)
        else:
            if n%3==1:
                #Move 1 stone and make the opponent lose
                print("Player "+str(get_current_player(moves))+" moves 1 stone")
                moves+=1
                play_game(n-1,moves)

            if n%3==2:
                #Move 2 stones and make the opponent lose
                print("Player "+str(get_current_player(moves))+" moves 2 stones")
                moves+=1
                play_game(n-2,moves)



play_game(6,0)
play_game(5,0)
play_game(3,0)

推荐阅读