Рубрики

Комбинаторная теория игр | Набор 3 (Grundy Numbers / Nimbers и Mex)

Мы представили Комбинаторную теорию игр в наборе 1 и обсудили игру Нима в наборе 2 .

Grundy Number — это число, определяющее состояние игры. Мы можем определить любую беспристрастную игру (пример: игра nim) в терминах числа Гранди.

Числа Гранди или Нимберы определяют, как любая беспристрастная игра (не только игра Нима) может быть решена после того, как мы вычислили числа Гранди, связанные с этой игрой, с использованием теоремы Спрэга-Гранди.

Но прежде чем вычислять числа Гранди, нам нужно узнать еще один термин — мекс.

Что такое Мекс?
«Минимальное исключающее», то есть «Мекс» из набора чисел, является наименьшим неотрицательным числом, отсутствующим в наборе.

Как рассчитать числа Гранди?
Мы используем это определение: число Grundy Number / nimber равно 0 для игры, которая сразу же проигрывается первым игроком, и равно Mex для всех возможных следующих позиций в любой другой игре.

Ниже приведены три примера игр и программ для расчета числа Грунди и Мекса для каждой из них. Вычисление чисел Grundy выполняется в основном с помощью рекурсивной функции, называемой функцией Calculate Grundy (), которая использует функцию calcMex () в качестве своей подпрограммы.

Пример 1
Игра начинается с кучи из n камней, и игрок для перемещения может взять любое положительное количество камней. Вычислите числа Гранди для этой игры. Последний игрок, который будет двигаться, выигрывает. Какой игрок выигрывает игру?

Так как если у первого игрока 0 камней, он сразу проиграет, поэтому Grundy (0) = 0

Если у игрока есть 1 камень, он может взять все камни и выиграть. Таким образом, следующая возможная позиция игры (для другого игрока) — это (0) камни

Следовательно, Grundy (1) = Mex (0) = 1 [Согласно определению Mex]

Точно так же, если у игрока есть 2 камня, он может взять только 1 камень, или он может взять все камни и выиграть. Таким образом, следующая возможная позиция игры (для другого игрока) — это (1, 0) камни соответственно.

Следовательно, Grundy (2) = Mex (0, 1) = 2 [Согласно определению Mex]

Точно так же, если у игрока «n» камней, он может взять только 1 камень, или он может взять 2 камня …… .. или он может взять все камни и выиграть. Таким образом, следующая возможная позиция игры (для другого игрока) — (n-1, n-2,… .1) камни соответственно.

Следовательно, Grundy (n) = Mex (0, 1, 2,… .n-1) = n [Согласно определению Mex]
Мы суммируем первое значение Гранди от 0 до 10 в таблице ниже:

/ * Рекурсивная программа на C ++ для поиска номера Гранди для

   игра, которая похожа на одну версию Nim.

  Описание игры: игра начинается с кучи n камней,

  и игрок для перемещения может взять любое положительное число

  камни. Последний игрок, который будет двигаться, выигрывает. Какой игрок выигрывает

  игра? * /

#include<bits/stdc++.h>

using namespace std;

  
// Функция для вычисления Mex всех значений в
// этот набор

int calculateMex(unordered_set<int> Set)

{

    int Mex = 0;

  

    while (Set.find(Mex) != Set.end())

        Mex++;

  

    return (Mex);

}

  
// Функция для вычисления числа Гранди 'n'
// Только эта функция зависит от игры

int calculateGrundy(int n)

{

    if (n == 0)

        return (0);

  

    unordered_set<int> Set; // Хеш-таблица

  

    for (int i=0; i<=n-1; i++)

            Set.insert(calculateGrundy(i));

  

    return (calculateMex(Set));

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n = 10;

    printf("%d", calculateGrundy(n));

    return (0);

}

Выход :

10

Вышеупомянутое решение может быть оптимизировано с использованием динамического программирования, поскольку существуют перекрывающиеся подзадачи. Реализацию на основе динамического программирования можно найти здесь .

Пример 2
Игра начинается с кучи из n камней, и игрок для перемещения может взять любое положительное количество камней только до 3. Последний игрок, который будет двигаться, выигрывает. Какой игрок выигрывает игру? Эта игра — версия Nim с 1 кучей.

Так как если у первого игрока 0 камней, он сразу проиграет, поэтому Grundy (0) = 0

Если у игрока есть 1 камень, он может взять все камни и выиграть. Таким образом, следующая возможная позиция игры (для другого игрока) — это (0) камни

Следовательно, Grundy (1) = Mex (0) = 1 [Согласно определению Mex]

Точно так же, если у игрока есть 2 камня, он может взять только 1 камень, или он может взять 2 камня и выиграть. Таким образом, следующая возможная позиция игры (для другого игрока) — это (1, 0) камни соответственно.

Следовательно, Grundy (2) = Mex (0, 1) = 2 [Согласно определению Mex]

Аналогично, Grundy (3) = Mex (0, 1, 2) = 3 [Согласно определению Mex]

Но как насчет 4 камней?
Если у игрока 4 камня, он может взять 1 камень или 2 камня или 3 камня, но он не может взять 4 камня (см. Ограничения игры). Таким образом, следующая возможная позиция игры (для другого игрока) — это (3, 2, 1) камни соответственно.

Следовательно, Grundy (4) = Mex (1, 2, 3) = 0 [Согласно определению Mex]

Таким образом, мы можем определить число Гранди для любого n> = 4 рекурсивно как

Grundy (n) = Mex [Grundy (n-1), Grundy (n-2), Grundy (n-3)]

Мы суммируем первое значение Гранди от 0 до 10 в таблице ниже:

C ++

/ * Рекурсивная программа на C ++ для поиска номера Гранди для

   игра, которая представляет собой версию Nim с одной кучей.

  Описание игры: игра начинается с кучи

  п камней, и игрок может двигаться любой

  положительное количество камней до 3 только.

  Последний игрок, который будет двигаться, выигрывает. * /

#include<bits/stdc++.h>

using namespace std;

  
// Функция для вычисления Mex всех значений в
// этот набор

int calculateMex(unordered_set<int> Set)

{

    int Mex = 0;

  

    while (Set.find(Mex) != Set.end())

        Mex++;

  

    return (Mex);

}

  
// Функция для вычисления числа Гранди 'n'
// Только эта функция зависит от игры

int calculateGrundy(int n)

{

    if (n == 0)

        return (0);

    if (n == 1)

        return (1);

    if (n == 2)

        return (2);

    if (n == 3)

        return (3);

  

    unordered_set<int> Set; // Хеш-таблица

  

    for (int i=1; i<=3; i++)

            Set.insert(calculateGrundy(n - i));

  

    return (calculateMex(Set));

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n = 10;

    printf("%d", calculateGrundy(n));

    return (0);

}

Джава

/ * Рекурсивная Java-программа для поиска
Номер Гранди для игры, которая
версия Nim с одной стопкой
Описание игры: игра начинается с
куча из n камней, а игрок
ход может занять любое положительное число
только до 3 камней. Последний игрок
двигаться побед. * /

import java.util.*;

  

class GFG

{

  

    // Функция для вычисления Mex всего

    // значения в этом наборе.

    static int calculateMex(HashSet<Integer> Set) 

    {

        int Mex = 0;

  

        while (Set.contains(Mex)) 

        {

            Mex++;

        }

        return (Mex);

    }

  

    // Функция для вычисления Grundy

    // номер n только эта функция

    // варьируется в зависимости от игры

    static int calculateGrundy(int n) 

    {

        if (n == 0

        {

            return (0);

        }

        if (n == 1

        {

            return (1);

        }

        if (n == 2

        {

            return (2);

        }

        if (n == 3)

        {

            return (3);

        }

  

        // Хеш-таблица

        HashSet<Integer> Set = new HashSet<Integer>(); 

  

        for (int i = 1; i <= 3; i++) 

        {

            Set.add(calculateGrundy(n - i));

        }

        return (calculateMex(Set));

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int n = 10;

        System.out.printf("%d", calculateGrundy(n));

    }

  
// Этот код предоставлен 29AjayKumar

python3

# Рекурсивная программа на Python3 для поиска Grundy Number
# для игры, которая представляет собой версию Nim с одной кучей.
# Описание игры: игра начинается с кучи
количество камней, и игрок может двигаться
# любое положительное количество камней до 3-х.
# Последний игрок, который будет двигаться, выигрывает.

  
# Функция для расчета Mex
# всех значений в этом наборе.

def calculateMex(Set): 

   

    Mex = 0 

    while Mex in Set

        Mex += 1

  

    return Mex 

   
# Функция для вычисления числа Гранди 'n'
# Только эта функция зависит от игры

def calculateGrundy(n): 

  

    if 0 <= n <= 3:

        return n

  

    Set = set() # Хеш-таблица

  

    for i in range(1, 4): 

        Set.add(calculateGrundy(n - i)) 

  

    return calculateMex(Set)

   
# Драйверная программа для проверки вышеуказанных функций

if __name__ == "__main__"

   

    n = 10 

    print(calculateGrundy(n)) 

      
# Этот код предоставлен Rituraj Jain

C #

/ * Рекурсивная Java-программа для поиска Grundy Number
для игры, которая является версией Nim с одной кучей.
Описание игры: игра начинается с кучи
п камней, и игрок может двигаться любой
только положительное количество камней до 3
игрок для перемещения выигрывает. * /

using System; 

using System.Collections.Generic;

  

class GFG 

  

    // Функция для вычисления Mex всего

    // значения в этом наборе.

    static int calculateMex(HashSet<int> Set) 

    

        int Mex = 0; 

  

        while (Set.Contains(Mex)) 

        

            Mex++; 

        

        return (Mex); 

    

  

    // Функция для вычисления числа Гранди

    // 'n' Только эта функция меняется в зависимости от

    // к игре

    static int calculateGrundy(int n) 

    

        if (n == 0) 

        

            return (0); 

        

        if (n == 1) 

        

            return (1); 

        

        if (n == 2) 

        

            return (2); 

        

        if (n == 3) 

        

            return (3); 

        

  

        // Хеш-таблица

        HashSet<int> Set = new HashSet<int>(); 

  

        for (int i = 1; i <= 3; i++) 

        

            Set.Add(calculateGrundy(n - i)); 

        

        return (calculateMex(Set)); 

    

  

    // Код драйвера

    public static void Main(String[] args) 

    

        int n = 10; 

        Console.Write(calculateGrundy(n)); 

    

  
// Этот код предоставлен Rajput-JI

Выход :

2

Вышеупомянутое решение может быть оптимизировано с использованием динамического программирования, поскольку существуют перекрывающиеся подзадачи. Реализацию на основе динамического программирования можно найти здесь .

Пример 3
Игра начинается с числа «n», и игрок для перемещения делит число «n» на 2, 3 или 6, а затем берет слово. Если целое число становится 0, оно удаляется. Последний игрок, который будет двигаться, выигрывает. Какой игрок выигрывает игру?

Мы суммируем первое значение Grundy от 0 до 10 в таблице ниже:

Подумайте, как мы создали эту таблицу.

C ++

/ * Рекурсивная программа на C ++ для поиска номера Гранди для

   игра.

 Описание игры: игра начинается с цифры "n"

 и игрок для перемещения делит число - 'n' на 2, 3

 или 6, а затем берет слово. Если целое число становится 0,

 это удалено. Последний игрок, который будет двигаться, выигрывает. * /

#include<bits/stdc++.h>

using namespace std;

  
// Функция для вычисления Mex всех значений в
// этот набор

int calculateMex(unordered_set<int> Set)

{

    int Mex = 0;

  

    while (Set.find(Mex) != Set.end())

        Mex++;

  

    return (Mex);

}

  
// Функция для вычисления числа Гранди 'n'
// Только эта функция зависит от игры

int calculateGrundy (int n)

{

    if (n == 0)

        return (0);

  

    unordered_set<int> Set; // Хеш-таблица

  

    Set.insert(calculateGrundy(n/2));

    Set.insert(calculateGrundy(n/3));

    Set.insert(calculateGrundy(n/6));

  

    return (calculateMex(Set));

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n = 10;

    printf("%d", calculateGrundy (n));

    return (0);

}

Джава

/ * Рекурсивная Java-программа для поиска Grundy Number для
игра.
Описание игры: игра начинается с цифры "n"
и игрок для перемещения делит число - 'n' на 2, 3
или 6, а затем берет слово. Если целое число становится 0,
это удалено. Последний игрок, который будет двигаться, выигрывает. * /

import java.util.*;

  

class GFG 

{

  

    // Функция для вычисления Mex всех значений в

    // этот набор

    static int calculateMex(HashSet<Integer> Set) 

    {

        int Mex = 0;

  

        while (Set.contains(Mex)) 

        {

            Mex++;

        }

  

        return (Mex);

    }

  

    // Функция для вычисления числа Гранди 'n'

    // Только эта функция зависит от игры

    static int calculateGrundy(int n) 

    {

        if (n == 0

        {

            return (0);

        }

  

        HashSet<Integer> Set = new HashSet<Integer>(); // Хеш-таблица

  

        Set.add(calculateGrundy(n / 2));

        Set.add(calculateGrundy(n / 3));

        Set.add(calculateGrundy(n / 6));

  

        return (calculateMex(Set));

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int n = 10;

        System.out.printf("%d", calculateGrundy(n));

    }

  
// Этот код предоставлен PrinciRaj1992

python3

# Рекурсивная программа Python3 для
# найти номер Гранди для игры.
# Описание игры: игра начинается с цифры 'n'
# и игрок для перемещения делит число - 'n' на 2, 3
# или 6, а затем взять слово. Если целое число становится 0,
# это удалено. Последний игрок, который будет двигаться, выигрывает.

  
# Функция для расчета Mex
# всех значений в этом наборе.

def calculateMex(Set): 

   

    Mex = 0 

    while Mex in Set

        Mex += 1

  

    return Mex 

   
# Функция для вычисления числа Гранди 'n'
# Только эта функция зависит от игры

def calculateGrundy(n): 

   

    if n == 0:

        return 0 

  

    Set = set() # Хеш-таблица

  

    Set.add(calculateGrundy(n // 2)) 

    Set.add(calculateGrundy(n // 3)) 

    Set.add(calculateGrundy(n // 6)) 

  

    return (calculateMex(Set)) 

   
# Драйверная программа для проверки вышеуказанных функций

if __name__ == "__main__"

   

    n = 10 

    print(calculateGrundy(n)) 

      
# Этот код предоставлен Rituraj Jain

C #

/ * Рекурсивная программа C # для поиска номера Гранди для
игра.
Описание игры: игра начинается с цифры "n"
и игрок для перемещения делит число - 'n' на 2, 3
или 6, а затем берет слово. Если целое число становится 0,
это удалено. Последний игрок, который будет двигаться, выигрывает. * /

using System;

using System.Collections.Generic;

  

class GFG 

  

    // Функция для вычисления Mex

    // все значения в этом наборе.

    static int calculateMex(HashSet<int> Set) 

    

        int Mex = 0; 

  

        while (Set.Contains(Mex)) 

        

            Mex++; 

        

  

        return (Mex); 

    

  

    // Функция для вычисления числа Гранди 'n'

    // Только эта функция зависит от игры

    static int calculateGrundy(int n) 

    

        if (n == 0) 

        

            return (0); 

        

  

        // Хеш-таблица

        HashSet<int> Set = new HashSet<int>(); 

  

        Set.Add(calculateGrundy(n / 2)); 

        Set.Add(calculateGrundy(n / 3)); 

        Set.Add(calculateGrundy(n / 6)); 

  

        return (calculateMex(Set)); 

    

  

    // Код драйвера

    public static void Main() 

    

        int n = 10; 

        Console.WriteLine(calculateGrundy(n)); 

    

  
// Этот код предоставлен PrinciRaj1992

Выход :

0

Вышеупомянутое решение может быть оптимизировано с использованием динамического программирования, поскольку существуют перекрывающиеся подзадачи. Реализацию на основе динамического программирования можно найти здесь .

Ссылки-
https://en.wikipedia.org/wiki/Mex_(mathematics)
https://en.wikipedia.org/wiki/Nimber

В следующем посте мы будем обсуждать решения беспристрастных игр с использованием Grundy Numbers или Nimbers.

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Комбинаторная теория игр | Набор 3 (Grundy Numbers / Nimbers и Mex)

0.00 (0%) 0 votes