本文概述

• C ++
• Java
• Python3
• C#

先决条件：
肮脏的数字/木材和墨西哥
我们已经在Set 2中看到, 我们可以找到谁在Nim游戏中获胜而无需实际玩游戏。
假设我们稍微改变了经典的Nim游戏。这次, 每个玩家只能移除1、2或3个宝石(不能像Nim的经典游戏中那样移除任意数量的宝石)。我们可以预测谁会赢吗？
是的, 我们可以使用Sprague-Grundy定理预测获胜者。
什么是Sprague-Grundy定理？
假设有一个由N个子游戏和两个玩家A和B组成的复合游戏(不止一个子游戏)。那么Sprague-Grundy定理说, 如果A和B都玩得最优(即, 他们没有(如果有任何错误), 那么如果在游戏开始时每个子游戏中排名靠前的位置的异或数为非零, 则保证先赢的玩家获胜。否则, 如果XOR取值为零, 那么玩家A肯定会输, 无论如何。
如何应用Sprague Grundy定理？
我们可以将Sprague-Grundy定理应用于任何
公正博弈
并解决它。基本步骤如下：

1. 将复合游戏分为子游戏。
2. 然后, 对于每个子游戏, 计算该位置的脏号码。
3. 然后计算所有计算出的脏数的异或。
4. 如果XOR值不为零, 那么将要转牌的玩家(第一个玩家)将获胜, 否则他注定会失败。

示例游戏：游戏从3个具有3、4和5块石头的堆开始, 并且要移动的玩家可以从任意一个堆中取出最多3个正数的石头(前提是该堆中有那么多石头)。最后一个移动的玩家获胜。假设两个玩家都发挥最佳状态, 那么哪个玩家会赢得比赛？
如何通过应用Sprague-Grundy定理判断谁将获胜？
【组合博弈论 4（Sprague – Grundy定理）】如我们所见, 该游戏本身是由几个子游戏组成的。
第一步 ：
子游戏可以视为每堆游戏。
第二步 ：
我们从下表中看到

Grundy(3) = 3 Grundy(4) = 0 Grundy(5) = 1

文章图片
我们已经了解了如何在游戏中计算该游戏的Grundy数
以前
文章。
第三步：
3, 0, 1 = 2的XOR
第四步：
由于XOR是非零数字, 因此可以说第一个玩家将获胜。
下面是实现以上4个步骤的程序。
C ++

/*Game Description- "A game is played between two players and there are N piles of stones such that each pile has certain number of stones. On his/her turn, a player selects a pile and can take any non-zero number of stones upto 3 (i.e- 1, 2, 3) The player who cannot move is considered to lose the game (i.e., one who take the last stone is the winner). Can you find which player wins the game if both players play optimally (they don't make any mistake)? " A Dynamic Programming approach to calculate Grundy Number and Mex and find the Winner using Sprague - Grundy Theorem. */ #include< bits/stdc++.h> using namespace std; /* piles[] -> Array having the initial count of stones/coins in each piles before the game has started. n-> Number of piles Grundy[] -> Array having the Grundy Number corresponding to the initial position of each piles in the game The piles[] and Grundy[] are having 0-based indexing*/ #define PLAYER1 1 #define PLAYER2 2 // A Function to calculate Mex of all the values in that set int calculateMex(unordered_set< int > Set) { int Mex = 0; while (Set.find(Mex) != Set.end()) Mex++; return (Mex); } // A function to Compute Grundy Number of 'n' int calculateGrundy( int n, int Grundy[]) { Grundy[0] = 0; Grundy[1] = 1; Grundy[2] = 2; Grundy[3] = 3; if (Grundy[n] != -1) return (Grundy[n]); unordered_set< int > Set; // A Hash Table for ( int i=1; i< =3; i++) Set.insert (calculateGrundy (n-i, Grundy)); // Store the result Grundy[n] = calculateMex (Set); return (Grundy[n]); } // A function to declare the winner of the game void declareWinner( int whoseTurn, int piles[], int Grundy[], int n) { int xorValue = https://www.lsbin.com/Grundy[piles[0]]; for ( int i=1; i< =n-1; i++) xorValue = xorValue ^ Grundy[piles[i]]; if (xorValue != 0) { if (whoseTurn == PLAYER1) printf ("Player 1 will win\n" ); else printf ( "Player 2 will win\n" ); } else { if (whoseTurn == PLAYER1) printf ( "Player 2 will win\n" ); else printf ( "Player 1 will win\n" ); } return ; } // Driver program to test above functions int main() { // Test Case 1 int piles[] = {3, 4, 5}; int n = sizeof (piles)/ sizeof (piles[0]); // Find the maximum element int maximum = *max_element(piles, piles + n); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy[maximum + 1]; memset (Grundy, -1, sizeof (Grundy)); // Calculate Grundy Value of piles[i] and store it for ( int i=0; i< =n-1; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER1, piles, Grundy, n); /* Test Case 2 int piles[] = {3, 8, 2}; int n = sizeof(piles)/sizeof(piles[0]); int maximum = *max_element (piles, piles + n); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy [maximum + 1]; memset(Grundy, -1, sizeof (Grundy)); // Calculate Grundy Value of piles[i] and store it for (int i=0; i< =n-1; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER2, piles, Grundy, n); */ return (0); }

Java

import java.util.*; /* Game Description- "A game is played between two players and there are N piles of stones such that each pile has certain number of stones. On his/her turn, a player selects a pile and can take any non-zero number of stones upto 3 (i.e- 1, 2, 3) The player who cannot move is considered to lose the game (i.e., one who take the last stone is the winner). Can you find which player wins the game if both players play optimally (they don't make any mistake)? " A Dynamic Programming approach to calculate Grundy Number and Mex and find the Winner using Sprague - Grundy Theorem. */ class GFG { /* piles[] -> Array having the initial count of stones/coins in each piles before the game has started. n-> Number of piles Grundy[] -> Array having the Grundy Number corresponding to the initial position of each piles in the game The piles[] and Grundy[] are having 0-based indexing*/ static int PLAYER1 = 1 ; static int PLAYER2 = 2 ; // A Function to calculate Mex of all the values in that set static int calculateMex(HashSet< Integer> Set) { int Mex = 0 ; while (Set.contains(Mex)) Mex++; return (Mex); } // A function to Compute Grundy Number of 'n' static int calculateGrundy( int n, int Grundy[]) { Grundy[ 0 ] = 0 ; Grundy[ 1 ] = 1 ; Grundy[ 2 ] = 2 ; Grundy[ 3 ] = 3 ; if (Grundy[n] != - 1 ) return (Grundy[n]); // A Hash Table HashSet< Integer> Set = new HashSet< Integer> (); for ( int i = 1 ; i < = 3 ; i++) Set.add(calculateGrundy (n - i, Grundy)); // Store the result Grundy[n] = calculateMex (Set); return (Grundy[n]); } // A function to declare the winner of the game static void declareWinner( int whoseTurn, int piles[], int Grundy[], int n) { int xorValue = https://www.lsbin.com/Grundy[piles[ 0 ]]; for ( int i = 1 ; i < = n - 1 ; i++) xorValue = xorValue ^ Grundy[piles[i]]; if (xorValue != 0 ) { if (whoseTurn == PLAYER1) System.out.printf("Player 1 will win\n" ); else System.out.printf( "Player 2 will win\n" ); } else { if (whoseTurn == PLAYER1) System.out.printf( "Player 2 will win\n" ); else System.out.printf( "Player 1 will win\n" ); } return ; } // Driver code public static void main(String[] args) {// Test Case 1 int piles[] = { 3 , 4 , 5 }; int n = piles.length; // Find the maximum element int maximum = Arrays.stream(piles).max().getAsInt(); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy[] = new int [maximum + 1 ]; Arrays.fill(Grundy, - 1 ); // Calculate Grundy Value of piles[i] and store it for ( int i = 0 ; i < = n - 1 ; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER1, piles, Grundy, n); /* Test Case 2 int piles[] = {3, 8, 2}; int n = sizeof(piles)/sizeof(piles[0]); int maximum = *max_element (piles, piles + n); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy [maximum + 1]; memset(Grundy, -1, sizeof (Grundy)); // Calculate Grundy Value of piles[i] and store it for (int i=0; i< =n-1; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER2, piles, Grundy, n); */ } } // This code is contributed by PrinciRaj1992

Python3

'''Game Description- "A game is played between two players and there are N piles of stones such that each pile has certain number of stones. On his/her turn, a player selects a pile and can take any non-zero number of stones upto 3 (i.e- 1, 2, 3) The player who cannot move is considered to lose the game (i.e., one who take the last stone is the winner). Can you find which player wins the game if both players play optimally (they don't make any mistake)? "A Dynamic Programming approach to calculate Grundy Number and Mex and find the Winner using Sprague - Grundy Theorem.piles[] -> Array having the initial count of stones/coins in each piles before the game has started. n-> Number of pilesGrundy[] -> Array having the Grundy Number corresponding to the initial position of each piles in the gameThe piles[] and Grundy[] are having 0-based indexing''' PLAYER1 = 1 PLAYER2 = 2 # A Function to calculate Mex of all # the values in that set def calculateMex( Set ):Mex = 0 ; while (Mex in Set ): Mex + = 1return (Mex) # A function to Compute Grundy Number of 'n' def calculateGrundy(n, Grundy): Grundy[ 0 ] = 0 Grundy[ 1 ] = 1 Grundy[ 2 ] = 2 Grundy[ 3 ] = 3if (Grundy[n] ! = - 1 ): return (Grundy[n])# A Hash Table Set = set ()for i in range ( 1 , 4 ): Set .add(calculateGrundy(n - i, Grundy))# Store the result Grundy[n] = calculateMex( Set )return (Grundy[n])# A function to declare the winner of the game def declareWinner(whoseTurn, piles, Grundy, n): xorValue = https://www.lsbin.com/Grundy[piles[ 0 ]]; for i in range ( 1 , n): xorValue = (xorValue ^ Grundy[piles[i]])if (xorValue ! = 0 ):if (whoseTurn = = PLAYER1): print ("Player 1 will win\n" ); else : print ( "Player 2 will win\n" ); else :if (whoseTurn = = PLAYER1): print ( "Player 2 will win\n" ); else : print ( "Player 1 will win\n" ); # Driver code if __name__ = = "__main__" :# Test Case 1 piles = [ 3 , 4 , 5 ] n = len (piles)# Find the maximum element maximum = max (piles)# An array to cache the sub-problems so that # re-computation of same sub-problems is avoided Grundy = [ - 1 for i in range (maximum + 1 )]; # Calculate Grundy Value of piles[i] and store it for i in range (n): calculateGrundy(piles[i], Grundy); declareWinner(PLAYER1, piles, Grundy, n); ''' Test Case 2 int piles[] = {3, 8, 2}; int n = sizeof(piles)/sizeof(piles[0]); int maximum = *max_element (piles, piles + n); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy [maximum + 1]; memset(Grundy, -1, sizeof (Grundy)); // Calculate Grundy Value of piles[i] and store it for (int i=0; i< =n-1; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER2, piles, Grundy, n); ''' # This code is contributed by rutvik_56

C#

using System; using System.Linq; using System.Collections.Generic; /* Game Description- "A game is played between two players and there are N piles of stones such that each pile has certain number of stones. On his/her turn, a player selects a pile and can take any non-zero number of stones upto 3 (i.e- 1, 2, 3) The player who cannot move is considered to lose the game (i.e., one who take the last stone is the winner). Can you find which player wins the game if both players play optimally (they don't make any mistake)? " A Dynamic Programming approach to calculate Grundy Number and Mex and find the Winner using Sprague - Grundy Theorem. */ class GFG { /* piles[] -> Array having the initial count of stones/coins in each piles before the game has started. n -> Number of piles Grundy[] -> Array having the Grundy Number corresponding to the initial position of each piles in the game The piles[] and Grundy[] are having 0-based indexing*/ static int PLAYER1 = 1; //static int PLAYER2 = 2; // A Function to calculate Mex of all the values in that set static int calculateMex(HashSet< int > Set) { int Mex = 0; while (Set.Contains(Mex)) Mex++; return (Mex); } // A function to Compute Grundy Number of 'n' static int calculateGrundy( int n, int []Grundy) { Grundy[0] = 0; Grundy[1] = 1; Grundy[2] = 2; Grundy[3] = 3; if (Grundy[n] != -1) return (Grundy[n]); // A Hash Table HashSet< int > Set = new HashSet< int > (); for ( int i = 1; i < = 3; i++) Set.Add(calculateGrundy (n - i, Grundy)); // Store the result Grundy[n] = calculateMex (Set); return (Grundy[n]); } // A function to declare the winner of the game static void declareWinner( int whoseTurn, int []piles, int []Grundy, int n) { int xorValue = https://www.lsbin.com/Grundy[piles[0]]; for ( int i = 1; i < = n - 1; i++) xorValue = xorValue ^ Grundy[piles[i]]; if (xorValue != 0) { if (whoseTurn == PLAYER1) Console.Write("Player 1 will win\n" ); else Console.Write( "Player 2 will win\n" ); } else { if (whoseTurn == PLAYER1) Console.Write( "Player 2 will win\n" ); else Console.Write( "Player 1 will win\n" ); } return ; } // Driver code static void Main() {// Test Case 1 int []piles = {3, 4, 5}; int n = piles.Length; // Find the maximum element int maximum = piles.Max(); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int []Grundy = new int [maximum + 1]; Array.Fill(Grundy, -1); // Calculate Grundy Value of piles[i] and store it for ( int i = 0; i < = n - 1; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER1, piles, Grundy, n); /* Test Case 2 int piles[] = {3, 8, 2}; int n = sizeof(piles)/sizeof(piles[0]); int maximum = *max_element (piles, piles + n); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy [maximum + 1]; memset(Grundy, -1, sizeof (Grundy)); // Calculate Grundy Value of piles[i] and store it for (int i=0; i< =n-1; i++) calculateGrundy(piles[i], Grundy); declareWinner(PLAYER2, piles, Grundy, n); */ } } // This code is contributed by mits

输出： 

Player 1 will win

参考文献：
https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
读者练习：
考虑下面的游戏。
"一场比赛是由两名玩家使用N个整数A1, A2, .., AN进行的。在回合中, 玩家选择一个整数, 将其除以2、3或6, 然后发言。如果整数变为0, 则将其删除。最后一个移动的玩家获胜。如果双方都发挥最佳状态, 哪个玩家会赢得比赛？"
提示：请参阅示例3
以前
文章。
本文作者：
拉奇特·贝尔瓦里亚(Rachit Belwariar)
。如果你喜欢lsbin并希望做出贡献, 那么你也可以写一篇文章并将你的文章邮寄到contribution@lsbin.org。查看你的文章出现在lsbin主页上, 并帮助其他Geeks。
如果发现任何不正确的地方, 或者你想分享有关上述主题的更多信息, 请发表评论

推荐阅读

• 

  最近感觉得了外阴瘙痒，请问一下这个症状是怎么形成的！
• 

  抗原自测盒使用方法
• 

  详细教程及注意事项 佳能ts6080清零废墨
• 

  表分析影响insert,SWOT分析表
• 

  重庆蛋糕烘焙培训哪里好 烘焙培训培训哪里好
• 

  脊髓型颈椎病怎么治 脊髓型颈椎病是什么意思
• 

  烤红薯需要什么配方吗
• 

  松下FZ平板电脑电池续航短的原因是什么
• 

  中大型材塑钢窗多少一平 普通塑钢窗一平方价格
• 

  比115更高的投诉电话 怎么投诉联通公司
• 

  复旦大学的校训是什么意思 复旦大学的校训是什么
• 

  小白windows7系统32位旗舰版最新推荐
• 

  海尔冰箱质保期及维修指南：了解海尔冰箱质保期、常见故障及维修方法
• 

  阿里巴巴采购津贴是什么意思
• 

  佳能g2810怎么轻松更换墨盒，让你的打印机焕发新生
• 

  南昌第六医院进口2价宫颈癌疫苗专场预约
• 

  西瓜糖分高吗西瓜的糖分含量高吗
• 

  中年人怎么饮食才能够防止早衰
• 

  结婚倒茶的四言八句
• 

  数据库 筛选 mysql数据库筛选

• PHP |日历功能完整参考
• JavaScript Math log()方法介绍
• 算法设计（金矿问题解析和代码实现）
• 算法设计（扔鸡蛋问题 – 动态规划）
• Python MongoDB –查找数据用法介绍
• jQuery :最后一个子元素选择器用法介绍
• 优先队列（priority queue）和堆（heap）详解（二叉堆、d-堆、左式堆、斜堆和二项堆）
• vue filters过滤器的理解和使用
• vue各种属性的意义详细分析