Симуляция: Hot Potato¶

Одно из типичных приложений для демонстрации очереди в действии - это симуляция реальной ситуации, которая требует управления данными в манере FIFO. Для начала давайте рассмотрим детскую игру Hot Potato. В этой игре (см. рисунок 2) дети выстраиваются в круг и перебрасывают предмет от соседа к соседу так быстро, как только могут. В некоторый момент игры действие останавливается, и ребёнок, у которого в руках остался предмет (картошка), выбывает из круга. Игра продолжается до тех пор, пока не останется единственный победитель.

Рисунок 2: Игра Hot Potato с шестью игроками

Эта игра - современный вариант знаменитой считалки Джозефуса. Основываясь на легенде о знаменитом историке первого века Иосифе Флавии, рассказывается, что когда евреи восстали против Рима, Иосиф и 39 его товарищей оборонялись против римлян в пещере. Осознав, что поражение неизбежно, они решили, что лучше умереть, чем стать рабами империи. Воины встали в круг, и один из них был назначен первым номером. Затем, следуя по часовой стрелке, они убивали каждого седьмого. Иосиф, как говорит легенда, кроме всего прочего был прекрасным математиком. Он сразу сообразил, где нужно встать, чтобы оказаться последним. Когда подошло время, то вместо того, чтобы убить себя, он перешёл на сторону римлян. Вы можете найти множество различных версий этой истории. Одни считают каждого третьего человека, а другие полагают, что последний мог сбежать на лошади. В любом случае, смысл остаётся прежним.

Мы реализуем общую симуляцию игры Hot Potato. Наша программа будет получать на входе список имён и константу num, используемую для подсчёта. Она будет возвращать имя последнего человека, оставшегося после повторяющегося отсчёта num. Что случится в этот момент - зависит уже от вас.

Для симуляции круга мы будем использовать очередь (см. рисунок 3). Предположим, что игрок, держащий картошку, - первый в очереди. После переброса картошки мы просто извлечём его оттуда и тут же поставим обратно, но уже в хвост. Игрок будет ждать, пока все, кто перед ним, побудут первыми, а затем вернётся на это место снова. После num операций извлечений/постановок участник, стоящий впереди, будет удалён окончательно, и цикл начнётся заново. Этот процесс будет продолжаться до тех пор, пока не останется всего одно имя (размер очереди станет равным 1).

Рисунок 3: Реализация Hot Potato в виде очереди

Программа показана в ActiveCode 1. Вызов функции hotPotato, использующий 7 в качестве константы для подсчёта, возвращает Susan.

Обратите внимание, что в этом примере значение константы подсчёта больше количества имён в списке. Это не является проблемой, поскольку очередь работает как круг и продолжает считать с начала до тех пор, пока не будет достигнуто нужное значение. Также заметьте, что список загружается в очередь таким образом, чтобы его первое имя было в её начале. В данном случае первым элементом в списке будет Bill, поэтому он помещается в начало очереди. Варианты этой реализации, описанные в упражнениях, позволяют выбирать счётчик случайным образом.