Prerrequisitos:
Teorema de Sprague Grundy
Grundy Numbers
Nim es un famoso juego en el que dos jugadores se turnan para retirar objetos de distintos montones. Durante cada turno, un jugador debe eliminar uno o más artículos de una sola pila que no esté vacía. El ganador del juego es el jugador que retira el último elemento de la última pila no vacía.
Ahora, por cada pila que no esté vacía, cualquiera de los jugadores puede quitar cero elementos de esa pila y hacer que cuente como su movimiento; sin embargo, este movimiento solo puede realizarse una vez por pila por cada jugador.
Dada la cantidad de artículos en cada pila, determine quién ganará el juego; Jugador 1 o jugador 2. Si el jugador 1 comienza el juego y ambos juegan de manera óptima.
Ejemplos:
Input : 3 [18, 47, 34] Output : Player 2 wins G = g(18)^g(47)^g(34) = (17)^(48)^(33) = 0 Grundy number(G), for this game is zero. Player 2 wins. Input : 3 [32, 49, 58] Output : Player 1 wins G = g(31)^g(50)^g(57) = (17)^(48)^(33) = 20 Grundy number(G), for this game is non-zero. Player 1 wins.
Enfoque:
el número de Grundy para cada pila se calcula en función del número de piedras. Para compensar el movimiento cero, tendremos que modificar los valores de Grundy que usamos en el juego estándar de nim.
Si el tamaño de la pila es impar; el número grundy es tamaño+1 y
si el tamaño de la pila es par; número grundy es tamaño-1.
XOR todos los valores numéricos de Grundy para verificar si el número final de Grundy (G) del juego no es cero o no para decidir quién es el ganador del juego.
Explicación:
el número de Grundy de un estado es el entero positivo más pequeño que no se puede alcanzar en un movimiento válido .
Entonces, necesitamos calcular el valor mex para cada n, de abajo hacia arriba para que podamos inducir el número grundy para cada n. donde n es el tamaño de la pila.
Estado ganador : una tupla de valores desde donde el jugador actual ganará el juego sin importar lo que haga el oponente. (Si G! = 0)
Estado perdedor : una tupla de valores desde donde el jugador actual perderá el juego sin importar lo que haga el oponente. (Si G=0)
For a given pile size n, we have two states:
(1) n with no zero moves available,
grundy number will same as standard nim game.
(2) n with zero moves available, we can
reach above state and other states with
zero moves remaining.
For, n = 0, g(0) = 0, empty pile
For, n = 1, we can reach two states:
(1) n = 0 (zero move not used)
(2) n = 1 (zero move used)
Therefore, g(1) = mex{0, 1} which implies
that g(1)=2.
For, n = 2, we can reach :
(1) n = 0 (zero move not used) state
because this is a valid move.
(2) n = 1 (zero move not used) is a valid
move, whose grundy number is 2.
Therefore, g(2) = mex{0,2} which implies
that g(2)=1.
note that n=1 (zero move used) is not a valid
move.
If we try to build a solution bottom-up
like this, it turns out that if n is even,
the grundy number is n - 1 and when it is odd,
the grundy is n + 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the variation
// in nim game
#include <bits/stdc++.h>
using namespace std;
// Function to return final
// grundy Number(G) of game
int solve(int p[], int n)
{
int G = 0;
for (int i = 0; i < n; i++) {
// if pile size is odd
if (p[i] & 1)
// We XOR pile size+1
G ^= (p[i] + 1);
else // if pile size is even
// We XOR pile size-1
G ^= (p[i] - 1);
}
return G;
}
// driver program
int main()
{
// Game with 3 piles
int n = 3;
// pile with different sizes
int p[3] = { 32, 49, 58 };
// Function to return result of game
int res = solve(p, n);
if (res == 0) // if G is zero
cout << "Player 2 wins";
else // if G is non zero
cout << "Player 1 wins";
return 0;
}
Java
// Java program for the variation
// in nim game
class GFG {
// Function to return final
// grundy Number(G) of game
static int solve(int p[], int n)
{
int G = 0;
for (int i = 0; i < n; i++) {
// if pile size is odd
if (p[i]%2!=0)
// We XOR pile size+1
G ^= (p[i] + 1);
else // if pile size is even
// We XOR pile size-1
G ^= (p[i] - 1);
}
return G;
}
//Driver code
public static void main (String[] args)
{
// Game with 3 piles
int n = 3;
// pile with different sizes
int p[] = { 32, 49, 58 };
// Function to return result of game
int res = solve(p, n);
if (res == 0) // if G is zero
System.out.print("Player 2 wins");
else // if G is non zero
System.out.print("Player 1 wins");
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program for the
# variation in nim game
# Function to return final
# grundy Number(G) of game
def solve(p, n):
G = 0
for i in range(n):
# if pile size is odd
if (p[i] % 2 != 0):
# We XOR pile size+1
G ^= (p[i] + 1)
# if pile size is even
else:
# We XOR pile size-1
G ^= (p[i] - 1)
return G
# Driver code
# Game with 3 piles
n = 3
# pile with different sizes
p = [32, 49, 58]
# Function to return result of game
res = solve(p, n)
if (res == 0): # if G is zero
print("Player 2 wins")
else: # if G is non zero
print("Player 1 wins")
# This code is contributed by Anant Agarwal.
C#
// C# program for the variation
// in nim game
using System;
class GFG {
// Function to return final
// grundy Number(G) of game
static int solve(int[] p, int n)
{
int G = 0;
for (int i = 0; i < n; i++) {
// if pile size is odd
if (p[i] % 2 != 0)
// We XOR pile size+1
G ^= (p[i] + 1);
else // if pile size is even
// We XOR pile size-1
G ^= (p[i] - 1);
}
return G;
}
// Driver code
public static void Main()
{
// Game with 3 piles
int n = 3;
// pile with different sizes
int[] p = { 32, 49, 58 };
// Function to return result of game
int res = solve(p, n);
if (res == 0) // if G is zero
Console.WriteLine("Player 2 wins");
else // if G is non zero
Console.WriteLine("Player 1 wins");
}
}
// This code is contributed by vt_m.
PHP
<?php
// php program for the variation
// in nim game
// Function to return final
// grundy Number(G) of game
function solve($p,$n)
{
$G = 0;
for ($i = 0; $i < $n; $i++)
{
// if pile size is odd
if ($p[$i] & 1)
// We XOR pile size+1
$G ^= ($p[$i] + 1);
else // if pile size is even
// We XOR pile size-1
$G ^= ($p[$i] - 1);
}
return $G;
}
// Driver Code
// Game with 3 piles
$n = 3;
// pile with different sizes
$p= array( 32, 49, 58 );
// Function to return result of game
$res = solve($p, $n);
if ($res == 0) // if G is zero
echo "Player 2 wins";
else // if G is non zero
echo "Player 1 wins";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program for the variation
// in nim game
// Function to return final
// grundy Number(G) of game
function solve(p, n)
{
let G = 0;
for(let i = 0; i < n; i++)
{
// If pile size is odd
if (p[i] % 2 != 0)
// We XOR pile size+1
G ^= (p[i] + 1);
// If pile size is even
else
// We XOR pile size-1
G ^= (p[i] - 1);
}
return G;
}
// Driver code
// Game with 3 piles
let n = 3;
// Pile with different sizes
let p = [ 32, 49, 58 ];
// Function to return result of game
let res = solve(p, n);
// If G is zero
if (res == 0)
document.write("Player 2 wins");
// If G is non zero
else
document.write("Player 1 wins");
// This code is contributed by sanjoy_62
</script>
Producción:
Player 1 wins
Complejidad temporal: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por Abhishek rajput y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA