Ах, эти бесконечные игры с кучей камней! Если бы Петр и Иван знали, что их судьба решится не на песке у речки, а в дебрях Python-кода, они бы, наверное, взяли с собой ноутбук вместо палок.
В прошлой статье мы уже с энтузиазмом ковырялись ручками в задачах 19-21, словно дети в песочнице — методично перебирали варианты ходов и вычисляли стратегии. Но сегодня мы решили пойти дальше: забудьте про мозговую гимнастику с листиком и ручкой — теперь всё решит одна-единственная программа на Python.
Да-да, именно та магия, что заставляет компьютеры думать быстрее нас!
Итак, напомним сюжет нашей драмы: есть куча камней (не спрашивайте зачем), и двое друзей — Петя и Ваня — по очереди делают ходы. Представьте себе: «Петя бросил один камень», «Ваня добавил три», «Петя удвоил кучу» — звучит как начало эпического баттла в стиле «Камни против Камней». Ну а правила просты: кто первым доведёт количество камней до 67 или больше — тот и чемпион.
Забавно, что ход у нас определяется просто: нечётные числа — это Петины ходы (он же первый), чётные — Ванины.
Как говорится, нечётное – значит мужское! А теперь представьте диалог между ними:
— Петя: «Я добавлю один камень!»
— Ваня: «А я удвою!»
— Петя: «Ну тогда я сразу три!»
— Ваня: «Хорошо… вот тебе 67 камней!»
Играем мы не ради забавы; наша цель – написать такую программу на Python, которая переберёт все возможные варианты ходов и скажет нам: при каком начальном количестве камней Петя проиграет уже на старте?
Или когда Ванин гений стратегии приведёт его к победе за пару ходов?
Начинаем с самой простой функции moves(). Она словно волшебник Гарри Поттер среди функций — принимает текущее число камней h и возвращает три варианта следующего шага: добавить один камень (как будто подкинуть монету другу), добавить три (подарок побольше) или удвоить количество (в духе фокуса с кроликом из шляпы).
Например, если у нас сейчас 10 камешков, moves(10) вернёт 11, 13 и 20. Это как выбрать между маленьким пирожком или огромным тортом.
Теперь переходим к главной функции игры.
Тут всё просто (ну почти): функция принимает два параметра — x (текущие камни) и s (номер хода). И угадайте кто ходит? Если s нечётное – это Петин момент блеснуть умом; если чётное – время для Ваниных стратегий.
Почему так?
Потому что Петя стартует первым — он как ведущий на вечеринке. А теперь внимание! Когда количество камушков достигает или превышает 67, игра заканчивается.
И тут начинается самое интересное: кто же выиграл? Проверяем остаток от деления s на 2 – если он равен единице (то есть s нечётное), значит победитель – тот игрок, который сделал последний ход.
Звучит сложно?
Вот анекдот для разрядки:
Приходит программист домой после работы и говорит жене:
– Сегодня играл с другом в игру про кучи камней.
– И кто выиграл?
– Я!
– Как ты понял?
– Моя программа сказала.
– А если бы программа ошиблась?
– Тогда я бы написал другую программу!
Вот так программисты решают жизненные задачи!
Возвращаясь к нашим задачам из серии 19-21… Задание номер 1907 звучит словно загадка Сфинкса для детей-программистов: найти минимальное S от 1 до 66 такое, чтобы Петя не мог выиграть за один ход, но при любом его ходе Ваня выигрывал своим первым ходом. Это вам не просто складывать яблоки в корзину — тут нужна настоящая стратегия.