Этюды для программистов - [15]

Длительность исполнения. Одному исполнителю на 2 недели.

Развитие темы. Большинство расширений включает более подробный анализ и сравнение систем проведения турниров. Во-первых, заметьте, что нижняя часть классификации по итогам турнира с немедленным выбыванием носит довольно произвольный характер. Кроме того, соперникам, попавшим в эту часть классификации, весьма тоскливо, ибо они рано вылетели. Для утешения можно организовать турниры с немедленным выбыванием среди неудачников каждого круга. Результаты этих турниров, а не приведенное выше правило, расставят неудачников по местам. Поскольку и в этих побочных турнирах будут проигравшие, организуйте турниры неудачливых неудачников, и так до посинения. Заметьте, что турнир по-прежнему пройдет в n кругов, но теперь все соперники будут участниками всех кругов. Если во всех встречах побеждают сильнейшие, этот, более тщательно организованный турнир превращается в законченный алгоритм сортировки.

Вообще, турниры — это сортировка участвующих в них соперников, хотя правило сравнения и носит вероятностный характер. На основе любого метода сортировки, не нарушающего двух основных правил турниров, можно организовать состязание. Вот основные правила:

1. Ни один из соперников не должен участвовать более чем в одном матче одного круга, а число кругов должно примерно равняться логарифму числа участников.

2. Никакие два соперника не должны встречаться больше одного раза.

Используя изложенные идеи, вы можете оценить и классические способы проведения турниров, такие, как отложенное выбывание, и способы, придуманные вами.

В голову приходит также несколько статистических вопросов. Как влияет частичное или полное рассеивание на турниры с немедленным выбыванием? Как влияет случайная жеребьевка (т. е. случайное составление начальных пар) на ход турниров по швейцарской системе? Каков будет эффект введения иной функции превосходства? Наконец, поскольку для получения итоговой статистики по нескольким экспериментам, видимо, нельзя просто усреднять две наши статистики, спрашивается: какая статистическая операция должна быть использована?

Литература

Харкнесс (Harkness К.). Official Chess Handbook. David McKay, New York, NY, 1967.

Книга Харкнесса содержит исчерпывающее изложение шахматной юрисдикции. Поскольку швейцарская система сделала возможным проведение в Соединенных Штатах больших открытых турниров, автор чрезвычайно подробно излагает все ее тонкости. В книге содержится много предложений по разрешению неясных ситуаций и упорядочению игроков.

Кнут (Knuth D. E.). The Art of Computer Programming/Seminumerical Algorithms. Addison-Wesley, Reading, MA, 1969. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. — М.: Мир, 1977.]

Глава 3 этой «библии» посвящена случайным числам, их порождению и использованию. Вы узнаете об опасности трюкачества в этой области. Рекомендуем вам воспользоваться генератором Макларена — Марсальи, который Д. Кнут описывает в алгоритме М.

Хоэль (Hoel G.) Introduction to Mathematical Statistics. Wiley, New York, NY, 1971.

Для нестатистиков корреляция и прочая статистическая магия кажутся совершенно недоступными человеческому разуму. Автор строго излагает основы статистики, не обманывая читателя.

* Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск», п. 5.3.3. Пер. с англ. — М.: Мир, 1978.

* Шахматный кодекс СССР. — М.: Физкультура и спорт, 1977.

6 Финансовые воротилы, или Управление предприятиями и машинное моделирование

Моделирование нередко оказывается удобным средством для изучения тех или иных ситуаций, которые характерны для реальной жизни. Процесс моделирования дает нам кроме множества курьезов некоторые знания об изучаемом объекте. В самом деле, многие так увлекаются исследованием модели, что уже не возвращаются к объекту как таковому. Попробуйте, что получится у вас.

Деловая игра Менеджмент [12]

Решением совета директоров крупного промышленного концерна вы назначены президентом компании. Компания владеет несколькими фабриками. Каждый месяц компания покупает сырье, обрабатывает его и продает изготовленную продукцию публике, ждущей ее с нетерпением. Вам теперь придется решать, сколько и каких товаров выпускать, стоит ли и когда именно расширять производственные мощности, как финансировать их расширение и как принять скромно-застенчивый вид, отчитываясь о незаконных прибылях. Перед тем как приступить к работе, вы строите модель промышленности в целом, чтобы в частном порядке отработать свою линию поведения. И вот какую игру вы в результате изобрели.

Начальная ситуация

Моделирование ведется с шагом по времени в один месяц. В начале игры каждый игрок (президент компании) получает две обычные фабрики, четыре единицы сырья и материалов (сокращенно ЕСМ), две единицы готовой продукции (сокращенно ЕГП) и 10000 долл. наличными. Игроки занумерованы от 1 до N, и в первом круге игрок 1 — старший. С каждым кругом (т. е. ежемесячно) роль старшего переходит к следующему по порядку номеров игроку, после N-го старшим становится опять первый (так что номер старшего в круге Т вычисляется по формуле (Т mod N) + 1). На торгах при прочих равных условиях выигрывает самый старший игрок (тот, кто будет старшим в следующем круге).