巴什博弈

说明

有一堆石子,石子个数为n,两人轮流从石子中取石子出来,最少取一个,最多取m个。最后不能取的人输,问你最后的输赢情况。

结果:当n%(m+1)==0时,先手输,否则先手赢

这种就是可以直接判断必败态的问题。如果这堆石子少于或者等于m个,那么先手赢。如果石子数目为m+1个,那么先手必输,因为无论先手怎么拿石子,后手都可以直接把剩下的石子全部拿走。如果石子数目为m+1<n<2(m+1),那么先手就可以拿走n-(m+1)个石子,使得对手面对m+1的必败态,这样先手必赢。所以如此推算下去,我们就知道当n%(m+1)==0时,先手输,否则先手赢。

使用方法

int ans = bash(n, m); n为总棋子数目,m为单次可取的最大石子数量,返回值为0表示先手输,返回1表示先手赢。

模版

int bash(int n, int m)
{
    if(n%(m+1) != 0)
        return 1;
    else
        return 0;
}

results matching ""

    No results matching ""