Привет! В последнее время стало появляться много задач с дополнительным условием, то есть когда для победы нужно не только набрать необходимое число камней в куче, но и чтобы это количество не превышало определённое значение. В противном случае победит противник. В этой статье я расскажу, как решать такие задачи с помощью рекурсии.
Для примера возьму задачу 4111 с сайта Константина Полякова.
Условие задачи
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Если при этом в куче оказалось не более 100 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 64.
Ответьте на следующие вопросы:
Вопрос 1. Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно.
Вопрос 2. Определите, два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Вопрос 3. Найдите значение S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ №1
Функция f принимает 2 аргумента: x - число камней в куче, p - чей ход (1 - начало игры, 2 - ход Пети, 3 - ход Вани, 4 - ход Пети и т.д.).
Строки 2-3. Если количество камней в куче в диапазоне [65, 100] и ход Вани (p=3), то вернуть истину.
Строки 4-5. Если количество камней в куче >100 и ход Пети, то победа отдаётся Ване, а значит, нужно вернуть истину.
Строки 6-7, 8-9 (их можно объединить в одно условие). Если количество камней в куче >100 или <65 и ход Вани, то вернуть ложь.
Строки 10-11. Если кто-то выиграл раньше, чем Ваня (Петя своим первым ходом). Вернуть ложь.
Строка 12. Продолжаем игру: функция вызывает саму себя по двум направлениям, увеличивая при этом ход. Функция OR служит связкой этих направлений и означает "Хотя бы одно из этих направлений должно выдать истину". Если бы в условии было сказано что "Ваня должен выиграть своим первым ходом при любом ходе Пети", то мы бы использовали функцию AND вместо OR.
Строки 14-17. Подбираем число X (число камней в куче), если при таком значении функция выдает истину, печатаем его.
Ответ №2.
Для ответа на второй вопрос нужно немного изменить программу. Петя должен выиграть вторым ходом (p = 4). Значит, Петя ходит как ему нужно (достаточно одного правильного хода из четырёх), а Ваня - как ему вздумается (все два хода должны привести Петю к выигрышу). Ходы Пети чётные (2, 4), ходы Вани - нечётные (3, 5). Значит после нечётного p (после Вани ходит Петя) мы будем использовать "или" (OR), а после чётного - "и" (AND).
Ответ №3
Теперь должен выиграть Ваня первым или вторым ходом (p = 3 или p = 5). Значит, Ваня ходит так, как ему нужно, а Петя - как ему вздумается. Ваня ходит после чётного, таким образом, если p чётный, то пишем "или", а если нечётный - "и".
Попробуйте воспользоваться этим шаблоном для решения подобных задач. Есть нюанс: при ответе на 3 вопрос стоит отсеивать варианты, при которых Ваня выиграет первым ходом. То есть запускать этот код, но с условием p==3 (во 2й, 6й, 8й строках), p==2(в 4й строке) и p<3(в 10й строке). Запоминаем эти варианты, и, если есть повторы с предыдущим запуском (при p==3 or p==5), то их не учитываем при ответе.
Удачи!