состояние ДВА, в котором у вас есть два промежуточных результата,

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

Т2: выбрать случайным образом две шашки и соединить их случайным образом выбранным знаком, чтобы получить промежуточный результат;

Т1: случайным образом выбрать шашку и соединить ее случайным знаком с промежуточным результатом;

Т0: соединить два промежуточных результата между собой случайным образом выбранным знаком.

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

Вы теперь знаете все. Конечные автоматы часто встречаются в программировании. Запомните этот пример, он имеет очень широкую область применения…

Игра 13.

Проблема наиболее длинного пути взятия является типичной возвратной задачей. Когда лиса находится в некотором положении, нужно испытать 4 возможных направления и для каждого из них увидеть, есть ли курица и свободно ли следующее за ней поле. Это легко!

Если вы не обнаружили никакого возможного взятия, то все закончено.

Если вы обнаружили возможное взятие, то результат есть наиболее длинное взятие, возможное при этом новом исходном положении, увеличенное на 1.

Но вы можете также действовать итеративным способом. Вы делаете первое взятие и продолжаете дальнейшие исследования, исходя из этого поля прибытия. Нужно испытать все возможности. Вы снова получаете, таким образом, тип задач, известный по головоломке 8. Упорядочьте четыре направления перемещения. Вы исходите из некоторого положения с направлением перемещения i = 1.

Если все четыре направления испытаны, то все закончено.

В противном случае вы смотрите, возможно ли взятие в направлении i:

— если невозможно, то вы увеличиваете i на 1 и возвращаетесь для нового цикла;

— если возможно, то вы выполняете это взятие, оказываетесь в новом положении и начинаете заново, исходя из него.

Внимание: нужно иметь возможность отменять сделанные вами взятия, потому что они происходят в рамках исследования… Это требует некоторой ловкости. По этой причине рассматриваемая игра — не из самых легких.

Остальное вы исследуете совершенно самостоятельно.

Игра 14.

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

Игра 16. Числа Спрага-Грюнди

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

— выигрывающей позиции вы сопоставляете 0;

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

Образуем числа Спрага-Грюнди для этой игры.

Позиции 0 сопоставляется число 0, SG (0) = 0.

Исходя из 1, можно получить 0 (поскольку мы имеем право удалить одну спичку[19]. Следовательно, SG(1) — наименьшее неотрицательное целое, отличное от 0, или SG(1) = 1. Исходя из 2, можно получить 1 и 0. Следовательно, SG(2) — наименьшее неотрицательное целое, отличное от 0 и 1, поэтому SG(2) = 2.

Так как можно удалять спички вплоть до 6, то точно так же имеем

SG(3) = 3, SG(4) = 4, SG(5) = 5, SG(6) = 6.

Предположим теперь, что имеется 7 спичек. Можно удалить от 1 до 6. Поэтому в результате можно получить от 6 до 1 спичек, но не 0. Число SG(7) — наименьшее неотрицательное целое, отличное от 1, 2, 3, 4, 5, 6, Следовательно, это 0.

SG(7) = 0,

А теперь из 8 можно получить от 2 до 7, поэтому SG(8) — это не 2, не 3, …, не 6 и не 0, поэтому оно равно 1.

SG(8) = 1.

Теперь вы можете установить общий закон:

SG(p) = остаток от деления p на 7.

Как же выигрывать?

Если вы после своего хода можете оставить кучу, для которой число Спрага-Грюнди равно 0, то ваш противник не сможет достичь ситуации с числом нуль, поскольку по определению число, которое он оставит, отлично от исходного числа. Поскольку он не сможет достичь ситуации p с SG (p) = 0, то он и не может выиграть. Ему придется оставить вам ситуацию с SG(p) ≠ 0, исходя из которой, вы всегда сможете получить ситуацию с числом Спрага-Грюнди, равным нулю. Следовательно, вам нужно оставлять вашему противнику число спичек с числом SG, равным нулю, иначе говоря, число спичек, кратное 7.

Одно из двух: либо ваш противник не знает этого правила и играет «по нюху»; при первой возможности вы оставляете ему кратное 7 и из ежовых рукавиц не выпускаете; либо он знает правило и ходит первым: он достигает кратного 7. Вы не сможете выиграть, если он не рассеян или не сделает ошибки в счете. Но компьютер не рассеян и не делает ошибок в счете (если ваша программа верна)…

Игра 17.

Выигрывающее положение — 31 декабря. Возьмите листок бумаги в клетку. Расположите по абсциссе месяцы, а по ординате дни. Так как 31 декабря выигрывает, то вы обозначаете эту точку числом Спрага-Грюнди 0. Из каждого дня декабря можно получить 31, но также и любой другой последующий день. Поэтому вы приписываете значение 1 дате 30 декабря, значение 2 дате 29 декабря, и т, д. То же для любого 31 числа; из него можно получить 31 число всех последующих месяцев. Поэтому 31 октября получает 1, 31 августа 2 и т. д.

После этого вы можете закончить значение таблицы и приписать число Спрага-Грюнди всем дням года. Вы увидите также появление дней со значением 0, которые являются выигрывающими днями. Напоминаю вам правило: каждому игровому положению приписывается наименьшее неотрицательное целое значение, отличное от значений тех положений, которые можно получить, исходя из данного, т. е. в настоящем случае — от значений тех положений, которые расположены правее, и тех, которые расположены ниже.

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

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

д, м' было не эквивалентно д, м при м ≠ м', и

д', м было не эквивалентно д, м при д ≠ д'.

Наконец, для выигрывающей позиции д, м должно быть эквивалентно 31, 12. Что-то похожее на это можно видеть в программах лицеев…

Я прекрасно понимаю, что календарь осложняет все, поскольку длина месяца не постоянна и зависит от м, причем к тому же с непростым законом изменения. Но, к счастью, оказывается, что это никак не сказывается на этом замечательном отношении эквивалентности.

После всего сказанного вы должны выпутаться из этой задачи…

Игра 18.

Эта игра — производная от средневековой игры. Сначала попытайтесь достичь 50 с точностью до кратного 7. Но как только все четыре карты, имеющие одинаковое значение, оказываются использованными, так ситуация сразу меняется. Вот пример начала партии,