巴什博奕

有一堆物品,个数为n,两个人轮流从其中拿物品,最少取一个,最多取m个,最后取光者获胜。

  1. 当物品的个数1<=n<=m时,那么先手拿物品的人必胜。
  2. 当物品的个数n=m+1时,先手无论拿几个,后手必胜。
  3. 当物品的个数m+2<=n<=2m,先手可以拿走若干个剩下m+1个给后手,那么先手必胜。

因此,无论先手还是后手,只要其面临的物品个数为m+1时,其必败。

推广:

  • 当物品个数为n=k*(m+1)+b时

   先手拿走b个,后手拿走x个,那么先手再拿走m+1-x个,即除了先手第一次拿的个外,每轮取走的物品都是m+1,即留给后手的个数总为m+1的整数倍个,那么先手必胜。

  • 当物品个数n=k*(m+1)时

    这种情况先手必败(请读者自行分析)。

C++代码示例:

int main()
{
    int n,m;
    cin>>n>>m;if(n % (m+1) !=0) 
    cout<<"First"; else
    cout<<"Second"; return 0; }
原文地址:https://www.cnblogs.com/LMIx/p/10699922.html