теория игр | C++ для приматов

Задача:
https://cpp.mazurok.com/word-of-the-week/идём-к-ним/

Изначально я решил написать программу в которой будут соединенны два решения: для задачи в которой можно сесть не более половины зерен, а так же для той задаче в которой максимальное съеденное число зерен задавалось пользователем. Я реализовал это достаточно просто: если m равна нулю во-второй задаче, то задача просто не имеет решения(как и смысла вообщем-то), именно поэтому я решил использовать нулевое m как показатель того что заданы параметры или для первой задачи.

if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n

1	if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n

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

Число зерен	Сколько нужно отнять зерен	Комментарий	Число зерен	Сколько нужно отнять зерен	Комментарий
1	0	П	9	2	В
2	1	В	10	3	В
3	0	П	11	4	В
4	1	В	12	5	В
5	2	В	13	6	В
6	3	В	14	7	В
7	0	П	15	0	П
8	1	В	…

В — Выигрышный вариант существует
П — Нет выигрышного варианта

Исходя из выше описанной таблицы вполне ясно виден алгоритм, так как выигрышный вариант отсутствовал только в случаях, где число зерен соответсвовало данной формуле: [latex]{ 2 }^{ n }-1[/latex]. тогда все что от нас требуется это найти найти такое число по этой формуле при котором количество зерен будет равно или меньше данного числа.

for( int i=1 ; r<n ; i++ ){
									r++;
									r=r<<1;
									r--;    // 2^i-1
						 		  }

for( int i=1 ; r<n ; i++ ){

r++;

r=r<<1;

r--; // 2^i-1

}

Если изначальное число зерен будет меньше полученного числа, то выигрышный вариант существует и все что от нас требуется, так это найти предыдущее число ( иными словами нужно найти [latex]{ 2 }^{ n-1 }-1[/latex]) и узнать сколько же зерен нужно отнять чтобы сделать выигрышный ход:

if ( r!=n ) // если существет  выигрышный ход
		{
			r++;
			r=r>>1; // ... то мы находим 2^(i-1)-1
			r--;
		}
		n-=r; // находим количество зерен которые нужно отнять

if ( r!=n ) // если существет выигрышный ход

{

r++;

r=r>>1; // ... то мы находим 2^(i-1)-1

r--;

}

n-=r; // находим количество зерен которые нужно отнять

Это все что касается первой задачи, но как оказалось вторая задача была совершенно аналогична:
Решение задачи я опять начал с расписывания нескольких вариантов, на этот раз если максимум съеденных зерен равен двум и соответственно трем:

2			3
Число зерен	Сколько нужно отнять зерен	Комментарий	Число зерен	Сколько нужно отнять зерен	Комментарий
1	0	П	1	0	П
2	1	В	2	1	В
3	2	В	3	2	В
4	0	П	4	3	В
5	1	В	5	0	П
6	2	В	6	1	В
7	0	П	7	2	В
…			…

Как вы могли уже заметить здесь тоже можно заметить очевидную тенденцию, в которой выигрышного варианта нет в тех случаях, когда число зерне соответствует этой формуле [latex]1+i(m+1)[/latex], а это значит что нам нужно всего лишь видоизменить алгоритм решения первой задачи просто подставив эту формулу вместо предыдущей.

#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main()
{
	int n, m, r=1;
	cin >> n >> m;
	if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n
	{
		--r;    
		for( int i=1 ; r<n ; i++ ){
									r++;
									r=r<<1;
									r--;    // 2^i-1
						 		  }
		if ( r!=n ) // если существует  выигрышный ход
		{
			r++;
			r=r>>1; // ... то мы находим 2^(i-1)-1
			r--;
		}
		n-=r; // находим количество зерен которые нужно отнять
		if(!n)n=-1;
	}
 
	else	// если введено m
	{
			while( r<n ){
							r += m+1; //1+i*(m+1)
 
					 	}
			if( r!=n )r -= m+1; // если существует  выигрышный ход, то возвращаемся к 1+(i-1)*(m+1)
			n -= r;				// находим количество зерен которые нужно отнять
			if(!n)n=-1;
	}
	cout << n << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main()

{

int n, m, r=1;

cin >> n >> m;

if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n

{

--r;

for( int i=1 ; r<n ; i++ ){

r++;

r=r<<1;

r--; // 2^i-1

}

if ( r!=n ) // если существует выигрышный ход

{

r++;

r=r>>1; // ... то мы находим 2^(i-1)-1

r--;

}

n-=r; // находим количество зерен которые нужно отнять

if(!n)n=-1;

}

else // если введено m

{

while( r<n ){

r += m+1; //1+i*(m+1)

}

if( r!=n )r -= m+1; // если существует выигрышный ход, то возвращаемся к 1+(i-1)*(m+1)

n -= r; // находим количество зерен которые нужно отнять

if(!n)n=-1;

}

cout << n << endl;

}

Related Images:

Задача Идем к ним?
«У крота и землеройки имеется [latex]n[/latex] зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но не более половины оставшегося количества. Можно съедать только целое число зёрен. Если игрок не может сделать очередной ход, то он считается проигравшим и ему приходится бежать в магазин за следующей порцией вкусных зёрен. На каждом шаге можно съедать не более [latex]m[/latex]-й части оставшихся зёрен. Составьте программу, которая определяет величину первого выигрышного хода по заданным числам n и m. Если выигрышного хода нет, то нужно вывести [latex]-1[/latex].»

Анализ задачи:

Первыми в голову приходят методы решения, основанные на полном переборе или на поиске производящей функции (к примеру, для [latex]m = 2[/latex] все позиции [latex]n = 2^{k}-1[/latex] — проигрышные), но количество стратегий растет достаточно быстро, а выделение закономерностей в рекурсивных последовательностях — задача нетривиальная. Следовательно, имеет смысл продолжить анализ, но уже с применением теории игр.
Предложенная игра представляет собой версию игры ним. Отличие в том, что множество объектов одно, а количество допустимых на данном шаге ходов зависит от ситуации на игровом поле.
Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.
Выигрышные позиции отличаются только расстоянием до проигрышной для противника (в зернах), следовательно, можно воспользоваться выигрышно-проигрышным разбиением позиций и ввести соответстенные характеристики позиций: [latex]\left\{ 1, -1 \right\}[/latex].
Если все позиции, в которые можно попасть из данной, являются выигрышными для противника (при условии, что он не играет в поддавки), считать её проигрышной.

Алгоритм решения:

Построение базы анализа: позиция [latex]n = m[/latex] — выигрышная (единственным доступным ходом мы заканчиваем игру), следовательно, [latex]n = m + 1[/latex] — проигрышная.
Если на расстоянии [latex]\left\lfloor \frac {step}{m} \right\rfloor [/latex] от текущей позиции [latex]step[/latex] все значения равны [latex]1[/latex], пометить [latex]step[/latex] как [latex]-1[/latex]. В противном случае пометить как [latex]1[/latex].
Если значение для [latex]step = n-1[/latex], то вывести на экран [latex]-1[/latex]. В противном случае вывести расстояние до ближайшей проигрышной для противника позиции.

Результаты тестирования:
Для всех [latex]n[/latex] при [latex]m = 2[/latex] программа предсказуемо выдает последовательность проигрышных ходов при [latex]n = 2^{k}-1[/latex].
На малых значениях [latex]n[/latex] при [latex]m > 2[/latex] установлена корректность алгоритма.

n	m	Результат
7	2	-1
8	2	1
10	3	3
7	3	-1
12	4	2
10	4	-1

Код программы:

/*Решение WoW_3 при помощи выигрышно-проигрышного разбиения позиций*/
#include <iostream>
using namespace std;
 
int main()
{
    int n; cin >> n; //количество зерен
    int m; cin >> m; //часть, которую можно съесть за ход
    int result[n + 1]; //массив значений
    for(int i = 0; i < m + 1; i++)
        result[i] = -1;	    //все позиции с n = [0; m) - проигрышные
    int take_to_win = 0;    //расстояние до ближайшей выигрышной позиции
    for(size_t step = m; step < n + 1; step++)  //заполнение массива result[]
    {
        bool good = false;  //есть ли возможность перейти на выигрышную позицию из данной
        //проверка всех позиций, в которые можно попасть за ход
        for(int i = step - 1; i >= step - step / m && !good; i--)
        {
            if(result[i] == -1){  //если выигрышная позиция достижима
                good = true;        //уведомить об этом программу
                take_to_win = n - i; //зафиксировать расстояние до позиции
            }
        }
        if(good) result[step] = 1; //если возможно, пометить позицию как выгрышную
        else result[step] = -1;    //иначе пометить как прогрышную
    }
    if(result[n] == 1) //вывести на экран оптимальное количество зерен на первом шаге
        cout << take_to_win << endl;
    else    //или указать, что позиция проигрышная
        cout << -1 << endl;
    return 0;
}

/*Решение WoW_3 при помощи выигрышно-проигрышного разбиения позиций*/

#include <iostream>

using namespace std;

int main()

{

int n; cin >> n; //количество зерен

int m; cin >> m; //часть, которую можно съесть за ход

int result[n + 1]; //массив значений

for(int i = 0; i < m + 1; i++)

result[i] = -1; //все позиции с n = [0; m) - проигрышные

int take_to_win = 0; //расстояние до ближайшей выигрышной позиции

for(size_t step = m; step < n + 1; step++) //заполнение массива result[]

{

bool good = false; //есть ли возможность перейти на выигрышную позицию из данной

//проверка всех позиций, в которые можно попасть за ход

for(int i = step - 1; i >= step - step / m && !good; i--)

{

if(result[i] == -1){ //если выигрышная позиция достижима

good = true; //уведомить об этом программу

take_to_win = n - i; //зафиксировать расстояние до позиции

}

if(good) result[step] = 1; //если возможно, пометить позицию как выгрышную

else result[step] = -1; //иначе пометить как прогрышную

}

if(result[n] == 1) //вывести на экран оптимальное количество зерен на первом шаге

cout << take_to_win << endl;

else //или указать, что позиция проигрышная

cout << -1 << endl;

return 0;

}

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static void main(String args[]) {
    	Scanner in = new Scanner(System.in);
    	int n = in.nextInt();	//количество зерен
    	int m = in.nextInt();	//часть, которую можно съесть за ход
    	int[] result = new int[n-m+1];	//массив значений
    	for(int i = 0; i < n-m+1; i++) result[i] = 0;
    	result[0] = 1;	//в позиции n = m следуте взять одно зерно и выиграть
    	result[1] = -1; //в позиции n = m + 1 выиграть нельзя
    	int takeToWin = 0;
    	for(int step = m+1; step < n+1; step++){
    		boolean good = false;	//есть ли возможность перейти на выигрышную позицию из данной
    		//проверка всех позиций, в которые можно попасть за ход
    		for(int i = step-m; i >= ((step - step/m)-m) && !good; i--){
    			if(result[i] == -1){	//если выигрышная позиция достижима
    				good = true;		//уведомить об этом программу
    				takeToWin = n-m-i;	//зафиксировать расстояние до позиции
    			}
    		}
    		if(good) result[step-m] = 1;	//если возможно, пометить позицию как выгрышную
    		else result[step-m] = -1;		//иначе - пометить как проигрышную
    	}
    	for(int i = 0; i < n-m+1; i++)		//вывод типа позиции
    		System.out.println(i+m+":\t"+result[i]);
    	if(result[n-m] == 1)	//вывести на экран оптимальное количество зерен на первом шаге
    		System.out.println(takeToWin);
    	else	//или указать, что выигрышных ходов нет
    		System.out.println(-1);
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int n = in.nextInt(); //количество зерен

int m = in.nextInt(); //часть, которую можно съесть за ход

int[] result = new int[n-m+1]; //массив значений

for(int i = 0; i < n-m+1; i++) result[i] = 0;

result[0] = 1; //в позиции n = m следуте взять одно зерно и выиграть

result[1] = -1; //в позиции n = m + 1 выиграть нельзя

int takeToWin = 0;

for(int step = m+1; step < n+1; step++){

boolean good = false; //есть ли возможность перейти на выигрышную позицию из данной

//проверка всех позиций, в которые можно попасть за ход

for(int i = step-m; i >= ((step - step/m)-m) && !good; i--){

if(result[i] == -1){ //если выигрышная позиция достижима

good = true; //уведомить об этом программу

takeToWin = n-m-i; //зафиксировать расстояние до позиции

}

if(good) result[step-m] = 1; //если возможно, пометить позицию как выгрышную

else result[step-m] = -1; //иначе - пометить как проигрышную

}

for(int i = 0; i < n-m+1; i++) //вывод типа позиции

System.out.println(i+m+":\t"+result[i]);

if(result[n-m] == 1) //вывести на экран оптимальное количество зерен на первом шаге

System.out.println(takeToWin);

else //или указать, что выигрышных ходов нет

System.out.println(-1);

}

Детали реализации:
Для хранения характеристик позиций использован динамически объявляемый массив (VLA — Variable Length Array). Для упрощения анализа использована булева переменная [latex]good[/latex].При решении применялись методы динамического программирования.
Протестировать работу программы можно по ссылке: http://ideone.com/5nmDxl.
Реализация на Java: http://ideone.com/D5R49n

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: теория игр

WoW 3. Идем к ним?

Related Images:

WoW 3: Идем к ним?

Related Images: