Задачник по алгоритмам

Программа курса:

Задача 1: Игра в делитель

Напишите определение функции divisorGame(n), которая принимает одно целое число n — начальное число на доске.

Функция должна вернуть:

  • True, если Алиса выигрывает игру, играя оптимально.
  • False, если Алиса проигрывает игру, играя оптимально.

Описание задачи:

Алиса и Боб играют по очереди, начиная с Алисы.

  1. Изначально на доске записано число n.
  2. На каждом ходе игрок выбирает число x, удовлетворяющее условиям:
    • 0 < x < n
    • n % x == 0 (то есть x является делителем числа n).
  3. После выбора числа x, игрок заменяет число n на доске на n - x.
  4. Если игрок не может сделать ход (не существует подходящего x), он проигрывает.

Необходимо вернуть True, если Алиса выигрывает игру, предполагая, что оба игрока играют оптимально, и False в противном случае.

Примеры:

Пример 1:
Входные данные: n = 2
Выходные данные: True
Объяснение:
Алиса выбирает x = 1, после чего на доске остаётся n = 1. Боб не может сделать ход и проигрывает.

Пример 2:
Входные данные: n = 3
Выходные данные: False
Объяснение:
Алиса выбирает x = 1, после чего на доске остаётся n = 2. Боб выбирает x = 1, и на доске остаётся n = 1. Алиса больше не может сделать ход и проигрывает.

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии