Задача: игра в ним
2026-02-21 05:39 Diff

#статьи

  • 6 фев 2023
  • 0

Задача: игра в ним

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли выиграть в ним с заданными условиями.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Вы играете с оппонентом в ним. Вот правила этой игры:

  • На старте перед вами лежит кучка камней.
  • Вы с оппонентом по очереди делаете ходы — причём первый ход всегда за вами.
  • На каждом ходу игрок убирает из кучи от одного до трёх камней на свой выбор.
  • Побеждает игрок, который уберёт последний камень.

Дано число камней — n. Вернуть true, если вы сможете выиграть, учитывая, что ваш оппонент будет играть максимально рационально, иначе вернуть false.

Ввод: n = 4 Вывод: false Пояснение: примерный исход игры: 1. Вы убираете 1 камень. Ваш оппонент убирает 3, включая последний камень. Ваш оппонент побеждает. 2. Вы убираете 2 камня. Ваш оппонент убирает 2 камня, включая последний. Ваш оппонент побеждает. 3. Вы убираете 3 камня. Ваш оппонент убирает последний камень. Ваш оппонент побеждает. В каждом из вариантов ваш оппонент побеждает. Ввод: n = 1 Вывод: true Ввод: n = 2 Выво��: true

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

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

Поэтому есть три сценария развития событий:

  • Камней меньше, чем 4, и сейчас наш ход — мы побеждаем.
  • Камней ровно 4, и сейчас наш ход — мы точно проиграли.
  • Камней больше, чем 4, но при этом остаток от деления общего числа камней на 4 равен 0 — значит, мы тоже проиграем, так как по условию наш соперник будет играть честно.
public boolean canWinNim(int n) { if (n < 4){ return true; } if (n == 4){ return false; } if (n % 4 == 0){ return false; } return true; }

Результаты

Временная сложность: O(1) — так как мы проверяем условие всего один раз.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

Научитесь: Профессия Java-разработчик + ИИ Узнать больше