c# - 递归算法检查 Nim 游戏中是否有可能获胜

Question

我找到了以下代码来检查游戏 Nim 是否有可能获胜。评论表明它是由了解他们在做什么的人编写的，但输出似乎是错误的，除非我完全误解了代码的目的。给定特定数量的剩余棋子（值），我想使用递归来确定下一个玩家是否可能获胜n。谁能解释一下为什么代码不能正常工作？即true除了 2 种情况外，它都会返回。

using System;

public class Program
{
    public static void Main(String[] args)
    {
        for (int numStix = 1; numStix <= 20; numStix++)
        {
            bool willWin = nimCalc(numStix);
            Console.WriteLine("Number of sticks: " + numStix + " Will win: " + willWin);
        }
    }

    public static bool nimCalc(int n)
    {
        bool x = false;
        //Base cases that guarantees player 1 will lose
        if (n == 1 || n == 4)
        {
            x = false;
        }
        //Base cases that guarantees player 1 will win
        else if (n == 2 || n == 3 || n == 5 || n == 6)
        {
            x = true;
        }
        else
        {
            //If n>6, it calls this recursively to subtract number of sticks to get to winning position
            x = nimCalc(n - 2);
            //If above method does not guarantee a win, it uses this recursively to obtain win
            if (x == false)
            {
                x = nimCalc(n - 1);
            }
        }

        //Returns boolean
        return x;
    }
}

https://dotnetfiddle.net/25MeDc

标签： c#recursion