Программный метод
В прошлой статье мы подробно разобрали ручной метод решения 19-21 заданий первого типа. А теперь настало время научиться решать задания с одной кучей при помощи всего одной программы на Python.
Для начала освежим в памяти суть этих заданий. Два друга — Петя и Ваня — играют в игру с кучей камней. Они по очереди делают ходы — кидают или убирают из этой кучи определённое количество камней.
Эти три задания имеют следующие условия:
- В первом случае требуется получить победу вторым ходом всей игры (первым ходом Вани)
- Во втором — третьим ходом всей игры (вторым ходом Пети), но не первым
- В последнем же требуется достичь победы четвёртым ходом всей игры (вторым ходом Вани), но не вторым (не первым ходом Ивана)
Так переиначили формулировки мы не просто так. Внимательно запомните эти цифры, означающие ход игры! Именно на них мы будем ориентироваться при поиске нужного значения для каждого задания. Здесь также стоит подметить и чётность ходов: нечётные числа – ходы Пети, чётные — Вани.
От нас же требуется переложить всю логику, описанную в прошлой статье, на нашу программу, которая будет перебором искать значения, удовлетворяющие всем нужным условиям.
Алгоритм решения
Здесь уже не будем тратить время на абстрактные примеры и перейдём сразу к заданию:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
— добавить в кучу один камень;
— добавить в кучу три камня;
— увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 67.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 67 камней или больше. В начальный момент в куче было S камней; 1 ≤ S ≤ 66.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.»
Начнём с самого простого — выпишем все возможные ходы в отдельную функцию moves():
Эта функция принимает число h — текущее количество камней — и возвращает три числа: что получится после каждого возможного хода.
Например, если сейчас в куче 10 камней, то moves(10) вернёт тройку чисел: 11, 13 и 20. Это результаты трёх возможных действий: добавить один камень, добавить три камня, удвоить кучу.
Обратите внимание, что после оператора return через запятую перечислены возвращаемые значения. Это означает, что функция вернёт нам кортеж — неизменяемый набор элементов, которые мы потом сможем перебрать в цикле.
Переходим к основной функции, которая будет воспроизводить ходы нашей игры. Определим её так:
Здесь у нас два параметра. Первый параметр x — это текущее количество камней в куче. Второй параметр s — это количество ходов, которое мы анализируем.
Самое важное, что нужно понять про параметр s: он определяет, чей сейчас ход. Когда s равно 1 или 3 или любому нечётному числу — это ход Пети. Когда s равно 2 или 4 или любому чётному числу — это ход Вани.
Почему так? Потому что Петя ходит первым. Первый ход — s равно 1 — нечётное — Петя. Второй ход — s равно 2 — чётное — Ваня. И так далее. Именно про это мы и говорили в самом начале статьи.
Теперь реализуем блок условия для проверки окончания игры:
Это первое, что проверяет наша функция. Если камней уже 67 или больше, игра закончилась. Но кто победил?
Здесь s % 2 — это типичная проверка на чётность числа s. То есть если остаток от деления s на 2 равен нулю, то число чётное. Например, запись 4 % 2 == 0 вернёт истину (True).
Если игра закончилась (количество камней — x — больше или равно 67), и мы видим, что s чётное, значит, сейчас должен был ходить Ваня. Но ходить уже некуда — игра завершена. Значит, последний ход сделал Петя, и он победитель. Функция возвращает True (результат сравнения s % 2 и нуля).
Если же s нечётное, значит, должен был ходить Петя, но игра уже кончилась. Это означает, что последним ходил Ваня и победил именно он. Функция возвращает False.
Следует еще добавить обработку исключительного случая. Если мы просим функцию проанализировать ноль ходов (s == 0), но игра ещё не закончилась (то есть камней меньше 67), то Петя точно не успевает выиграть. Возвращаем False. Записать это можно так:
Далее перебираем все возможные ходы. Запишем это таким интересным списочным включением:
Сначала вызываем moves(x) и получаем три варианта того, что будет после хода. Например, если x равно 33, получаем 34, 36 и 66.
Дальше для каждого из этих вариантов m мы снова вызываем нашу функцию f(), но уже с новым количеством камней m и уменьшенным на единицу счётчиком ходов s.
Результаты всех трёх вызовов собираются в список h. Этот список будет содержать три значения True или False — результат анализа каждого возможного хода.
Это называется рекурсия — функция вызывает сама себя. Она как бы заглядывает в будущее: «А что будет, если сделать этот ход? А если этот?».
Это работает точно так же, как и наши деревья решений из прошлой статьи: мы проверяем, можно ли по этой траектории дойти до нужного числа. В тот раз это выделялось визуально: оранжевые круги были для проигрышной траектории, зелёные — для победной.
В прошлый раз мы самостоятельно проверяли, есть ли хотя бы один выигрышный ход у игрока, или при всех ли ходах противника есть шанс победить у нашего игрока.
Теперь мы предоставим право анализировать такие ходы программе с помощью такого блока условий:
Если s нечётное, то сейчас ходит Петя. Петя хочет выиграть, поэтому он выберет лучший для себя ход. Ему достаточно, чтобы хотя бы один из вариантов вёл к победе. Функция any проверяет именно это: есть ли в списке хотя бы одно значение True.
Если s чётное, то ходит Ваня. Ваня тоже хочет выиграть, поэтому он выберет худший для Пети ход. Петя победит только если при любом ходе Вани он всё равно выигрывает. Функция all проверяет это: все ли значения в списке равны True.
Другими словами, Петя — оптимист, ему нужен хоть один шанс. А Ваня — пессимист для Пети, он испортит всё что может.
Можно вывести такое мнемоническое правило:
- Если ходов осталось нечетное количество (1, 3…), значит сейчас мой ход, и мне достаточно одного (any) выигрышного хода.
- Если четное (2, 4…), значит сейчас ход противника, и он должен проигрывать при любом (all) своем ходе.
Или кратко: нечет — any, чёт — all.
Всё, логика выстроена, теперь можно подбирать ответы. Начнём с 19 задания:
В задании 19 нас просят найти минимальное S (количество камней), при котором Петя не может выиграть за один ход, но Ваня гарантированно выигрывает своим первым ходом (второй ход всей игры).
Запись f(S, 2) означает: анализируем позицию S за два хода (ход Пети и ход Вани). Если функция возвращает True, то за эти два хода игра завершается победой.
Но чьей победой? При s равном 2 последним ходит игрок на чётном ходу, то есть Ваня. Значит, f(S, 2) == True означает, что Ваня выигрывает своим первым ходом при любой игре Пети.
При этом условие «Петя не может выиграть за один ход» выполняется автоматически — если бы Петя мог выиграть сразу, игра бы закончилась на первом ходу, и мы бы не дошли до второго.
Конструкция min(S for S in range(1, 67) if условие) перебирает все значения S от 1 до 67 и находит минимальное, для которого условие истинно.
Число 67 мы взяли из этой строчки условия: «1 ≤ S ≤ 66». То есть формируем диапазон чисел от 1 до 67 не включительно (в range правая граница не включается!).
Теперь задание 20. Снова вспомним цифры, которые выводили в самом начале. Здесь нужна победа третьим ходом, но не первым. Условие будет такое: if f(S, 3) and not f(S, 1).
Первое условие f(S, 3) проверяет, что Петя выигрывает за три хода. Три хода — это первый ход Пети, ответ Вани и второй ход Пети. Нечётное число ходов, последний ходит Петя.
Второе условие not f(S, 1) проверяет, что Петя не может выиграть за один ход. Если бы f(S, 1) было True, Петя бы сразу победил, а нам нужно обратное.
Запишем полностью строку с формированием ответа:
Она несколько отличается от предыдущей. Дело в том, что для 20 заданий нужно получить два наименьших числа. Поэтому мы формируем список через списочное включение и берём срез [:2] — только первые два элемента этого списка.
В задании 21 ситуация посложнее. Нужно найти S, при котором Ваня выигрывает своим первым или вторым ходом, но при этом не может гарантированно выиграть именно первым ходом. То есть нужна победа четвёртым ходом всей игры, но никак не вторым. Запишем это:
Первое условие f(S, 4) означает, что игра заканчивается за четыре хода. Четыре хода — чётное число, последний ходит Ваня. Значит, Ваня побеждает на своём втором ходу.
Второе условие not f(S, 2) означает, что Ваня не может выиграть за два хода, то есть не может победить своим первым ходом.
Вместе эти условия дают именно то, что требуется: Ваня побеждает, но только на втором своём ходу.
Полный код программы для решения всех трёх заданий выглядит так:
Давайте проследим, как программа анализирует конкретную позицию. Допустим, у нас 33 камня и мы вызываем f(33, 2) — хотим проверить победу Вани по 19 заданию.
Сначала проверяется: 33 больше или равно 67? Нет, игра продолжается.
Затем проверяется: s равно 0? Нет, у нас s равно 2.
Дальше строится список h. Для этого перебираются все ходы из позиции 33: это 34, 36 и 66. Для каждого вызывается f с параметром s — 1, то есть f(34, 1), f(36, 1) и f(66, 1).
Смотрим ходы из f(34,1): это числа 35, 37 и 68.
Считаем:
- f(35, 0) → ходов нет → False
- f(37, 0) → False
- f(68, 0) → 68 >= 67 → возвращаем 0 % 2 == 0 → True
Имеем такой список: h = [False, False, True]
При этом s у нас нечётное, значит срабатывает any(h), который возвращает True. f(34,1) = True, зафиксировали.
Аналогично с f(36,1): числа 37, 39 и 72.
Проверяем:
- f(37,0) → False
- f(39,0) → False
- f(72,0) → True
Снова: h = [False, False, True]. По той же логике f(36,1) = True.
Последнее — f(66, 1): 67, 69 и 132.
Проверяем:
- f(67,0) → True
- f(69,0) → True
- f(132,0) → True
Теперь список h = [True, True, True]. По-прежнему из-за s == 1 срабатывает any(h) и возвращает истину. Тогда f(66,1) = True.
Теперь вернулись на уровень выше к f(33,2). Список h у нас состоит из трёх вызовов функций, которые мы расписали выше: h = [f(34,1), f(36, 1), f(66,1)] = [True, True, True].
Но теперь s у нас равно 2, то есть чётное. Это влечёт за собой срабатывание функции all(h). А, так как в h одни True, то и возвращается так же истина.
Значит, f(33, 2) возвращает истину. А по смыслу это означает, что из 33 камней в куче можно гарантированно выиграть за 2 хода. Для наглядности визуализируем это дерево решений как в прошлой статье.
Запускаем программу и убеждаемся в корректности наших рассуждений. Получаем три ответа: 33; 30, 32 и 29.
Пример 1
Разберём еще одно задание, но уже с уменьшением камней в куче:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Игра завершается, когда количество камней в куче становится не более 60.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 60 или менее камней. В начальный момент в куче было S камней, S ≥ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.»
Выпишем ходы в виде функции moves():
Теперь в первом условии будем проверять, что количество камней в куче (x) не более 60:
А дальше все без изменений вплоть до строчек с перебором значений для ответа:
Весь шаблон далее остаётся тем же, меняем только диапазон чисел: у нас он будет от 61 до 300. Второе число подбирается опытным путём.
Вся программа выглядит так:
Запускаем её и видим на экране такие три строчки:
19: 244
20: [247, 248]
21: 252
Это и будут ответы на данные задания.
Пример 2
Закрепим полученные навыки на еще одном задании:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
— добавить в кучу 2 камня;
— добавить в кучу 4 камня;
— увеличить количество камней в куче в 2 раза.
Игра завершается, когда количество камней в куче становится не менее 125.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 125 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 124.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём
одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два
условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.»
Выписываем ходы:
Теперь основную функцию:
И шаблонный код для вывода итоговых значений:
Весь код выглядит так:
А в ответы запишем следующие числа: 61, 31 и 57, а также 55.
Итоги
Как вы могли заметить, решения заданий 19-21 максимально шаблонные. Давайте выведем такой шаблонный код для увеличения количества камней в куче:
Здесь:
*1 — возможные ходы (добавить два камня — h + 2 и т.п.);
*2 — победное количество камней.
И аналогичный код для уменьшения камней в куче:
Здесь:
*1 — возможные ходы (убрать два камня — h - 2 и т.п.);
*2 — победное количество камней;
*3 — правая граница диапазона. Её нужно подобрать опытным путём, можно брать числа, кратные 100 (100, 200, 300), в зависимости от условия.
В следующей же статье адаптируем этот код для решения 19-21 задания с двумя кучами.