Задача Баше

Приведем пример алгоритма принятия решения (игровой стратегии) в игре «Залача Баше».

Задача 1. Игра Баше для 11 предметов. На столе 11 предметов, например, карандашей. Первый играющий может взять 1, 2 или 3 карандаша. Затем второй играющий может взять 1, 2 или 3 карандаша из оставшихся, затем берет первый и т.д. Итак, поочередно, оба играющих берут не более, чем по 3 карандаша. Проигрывает тот, которому приходится взять последний карандаш. Напишите алгоритм выигрышной стратегии начинающего в этой игре игрока.

Решение. Пусть первый игрок A, второй – B. Здесь мы опишем выигрышную стратегию игрока A. Проведем анализ игры. Чтобы выиграл игрок A, он должен оставить игроку B в последнем ходе 1 предмет. Очевидно, что в предыдущем ходе A должен оставить на столе 5 предметов, иначе он проиграет. В третьем ходе от конца A должен оставить 9 предметов, а всего 11 предметов, следовательно, в третьем ходе от конца или в первом ходе A должен взять 2 предмета.

Алгоритмдостижения игроком A победы формулируется так:

1. Первый ход. A берет 2 предмета.

2. Очередной ход. Если B в своем ходе берет K карандашей (1≤K≤3), причем не все карандаши взяты, то A берет 4-K карандаша.

Задача 2.Игра Баше для N предметов.Сформулируем задачу в общем виде: имеется n предметов, двое играющих берут по очереди 1, 2 или 3 предмета, проигрывает тот, кто забирает последний предмет, написать алгоритм выигрышной стратегии в этой игре начинающего игрока.

Решение. Разобьем все возможные первоначальные количества предметов n на 4 класса в зависимости от остатка, полученного от деления на 4. К первому классу отнесем количество предметов n, которые можно представить как 4m, ко второму классу отнесем количество предметов n, которые можно представить как 4m+1, к третьему классу отнесем количество предметов n, которые можно представить как 4m+2, к четвертому классу отнесем количество предметов n, которые можно представить как 4m+3. Если первоначальное количество предметов представлено как 4m, то, взяв один предмет, начинающий игрок оставит количество предметов, принадлежащих классу 4m+3, взяв 2 предмета – 4m+2, взяв 3 предмета – 4m+1. Составим соответствующую таблицу перехода из одного класса в другой, в зависимости от взятых в очередной ход предметов.

Если первоначальное количество предметов 4m+1, то это проигрышное количество предметов для начинающего игрока, потому что сколько бы начинающий не взял предметов, противник вернет его в этот же класс. Единица принадлежит этому классу, тогда возникает необходимость в последней раз начинающему взять один последний предмет. Если первоначальное количество предметов 4m, 4m+2, 4m+3, то выигрышная стратегия начинающего игрока, взять в очередной ход столько предметов, чтобы оставить партнеру количество предметов, принадлежащих классу 4m+1.

Обозначим данные, используемые для составления алгоритмов и программ и выразим зависимость между данными в виде формул. Число предметов – N. Число предметов, взятых первый раз первым игроком (человеком или компьютером) – P, где P = (N-1) mod 4 (остаток от деления N-1 на 4). Число предметов, взятых вторым игроком (человеком) – Y. Число предметов, взятых первым игроком (человеком или компьютером) – С. Между значениями переменных имеется зависимость Y+C = 4. Число оставшихся предметов после очередных ходов N-C-Y. Первый и второй игрок берут в сумме 4 предмета, пока остается больше одного предмета.

Таким образом, исходным данным является первоначальное количество предметов N. Для создания более интересной игровой ситуации целесообразно задавать число N случайным образом в некотором разумном, наперед заданном интервале, например, от 10 до 30.

Составим алгоритм и программу выигрышной стратегии для начинающего игрока, если начальное количество предметов N.Рассмотрим один из подходов к составлению алгоритма решения поставленной задачи: начинает игру первый игрок (человек или компьютер), игра прерывается, если при заданном количестве предметов N, первый игрок при правильной игре выиграть не может.

Словесное описание алгоритма игры Баше, если первый ход Ваш и Вы знаете выигрышную стратегию в этой игре:

1 шаг. Попросите Вашего партнера назвать начальное количество предметов N (если партнер назвал неверное количество предметов, попросите выбрать количество предметов еще раз) и идите на шаг 2.

2 шаг. Найдите остаток от деления N-1 на 4 и присвойте значение остатка переменной P (P:=(N-1) mod 4). Идите на шаг 3.

3 шаг. Сравните P с 0. Если P=0, то сообщите партнеру, что при правильной игре Вы выиграть не можете и идите на шаг 12. Если P<>0, то идите на шаг 4.

4 шаг. Сообщите «Я делаю первый ход» и идите на шаг 5.

5 шаг. Переменной C (количество предметов, взятых Вами за один ход) присвойте значение P (C:=P). Сообщите «Я беру C предметов» и идите на шаг 6.

6 шаг. Переменной N присвойте значение N-C (N:=N-C). Сообщите «Осталось N предметов» и идите на шаг 7.

7 шаг. Сравните N с 1. Если N = 1, то идите на шаг 11. Если N>1, то сообщите «Ваш ход» и идите на шаг 8.

8 шаг. Спросите партнера «Сколько предметов Вы берете?». Переменной Y присвойте значение количества предметов, взятых партнером (Y может равняться 1 или 2, или 3, если партнер взял неверное количество предметов, попросите повторить ход) и идите на шаг 9.

9 шаг. Вычислите 4-Y. Сообщите «Я беру 4-Y предметов» и идите на шаг 10.

10 шаг. Переменной N присвойте значение N-4 (N:=N-4). Сообщите «Осталось N предметов» и идите на шаг 7.

11 шаг. Сообщите «Ваш ход. Вы проиграли» и идите на шаг 12.

12 шаг. Спросите партнера «Хотите сыграть еще?». Если партнер ответил «Да», то идите на шаг 1, иначе – на шаг 13.

13 шаг. Закончите игру.