На этом шаге мы рассмотрим общий принцип реализации таких игр с использованием взаимной рекурсии.

При написании подпрограмм хорошей общепринятой практикой программирования является то, чтобы сделать их по возможности короткими и простыми, что заметно повышает удобочитаемость кода. В этом смысле взаимная рекурсия может быть полезной для реализации различных действий или способов поведения. Например, в играх со многими игроками различные роли игроков можно реализовать отдельными методами. Следующий пример моделирует две различные стратегии поведения игроков в простой игре. Из кучки, состоящей изначально из n камешков, два игрока по очереди убирают один или два камешка. Выигрывает тот, кто уберёт последние камешки. Допустим, первый игрок (Боб) решил всякий раз убирать по одному камешку, тогда как второй игрок (Элис) убирает один камешек, если оставшееся их число нечётно, и два - если чётно.

Эту простую игру можно легко закодировать, используя всего один метод. Однако в примере 9.2 приводится решение, основанное на двух взаимно-рекурсивных методах, в каждом из которых реализована своя стратегия игры. В частности, в начальных условиях проверяется, выиграет ли игрок игру, тогда как в рекурсивных условиях очередь передаётся другому игроку. Параметр функции, реализующей стратегию другого игрока, уменьшается на число убранных из кучки камешков. Важно отметить, что каждая стратегия реализована отдельной процедурой, что упрощает понимание и изменение кода. Наконец, более сложная стратегия Элис явно лучше, чем у Боба. В частности, Боб победит только тогда, когда исходная кучка состоит из одного камешка.

Пример 9.2. Взаимно-рекурсивные процедуры, реализующие игровые стратегии Элис и Боба

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def play_Alice(n):
    if n <= 2:
        print('Элис победила')
    elif n & 1:
        # Элис убирает один камень
        play_Bob(n - 1)  # Ход переходит к Бобу
    else:
        # Элис убирает два камня
        play_Bob(n - 2)  # Ход переходит к Бобу


def play_Bob(n):
    if n == 1:
        print('Боб победил')
    else:
        # Боб убирает один камень
        play_Alice(n - 1)  # Ход переходит к Элис

Архив с файлом можно взять здесь.

На следующем шаге мы рассмотрим задачу размножения кроликов.

Предыдущий шаг Содержание Следующий шаг