Этюды для программистов - страница 17
1/2 + (j − i)/2>n+1.
Тем самым более сильный соперник побеждает с вероятностью, превышающей половину. Упорядочим соперников в соответствии с набранным в круговом турнире количеством очков. Внутри каждой группы команд с равным количеством очков упорядочим их по среднему числу очков, набранных побежденными ими соперниками. Если и здесь наблюдаются совпадения, соперники упорядочиваются по исходным номерам. В результате получается круговая классификация, которую мы будем считать самой «справедливой»; она используется для оценки других способов организации турниров.
Следующий шаг состоит в том, чтобы с одной и той же базой данных провести турниры по швейцарской системе и с немедленным выбыванием. Для разбиения соперников на пары в каждом из этих турниров берутся результаты кругового турнира. Заметьте, что в обоих турнирах два соперника могут встретиться лишь однажды. Швейцарская классификация — это упорядочение после заключительного круга (всего n кругов), причем все оставшиеся неясности разрешаются в соответствии с начальным упорядочением. Затем начните турнир с немедленным выбыванием, составив пары для первого круга случайным образом. В классификации по выбыванию победитель финальной встречи идет первым, побежденный — вторым, и, вообще, проигравшие в i-м круге располагаются перед ранее выбывшими и после всех победивших в i-м и следующих кругах. Внутри группы побежденных в i-м круге соперники располагается в соответствии с итоговыми местами победивших их команд.
Чтобы сравнить эти классификации, используем новую и старую статистики, Старая статистика — это корреляция мест определяемая как
R = 1 − 6
где x>i — место соперника i в одной классификации, у>i — место в другой классификации, N — общее число соперников (в данном случае 2>n). Другая статистика подсчитывает совпадения и определяется как
М = max>i (∀j) (j ≤ i ⊃ х>j = у>j).
Тем самым М равно максимальному числу мест (считая от сильнейших к слабейшим), в которых обе классификации в точности совпадают. Статистика R характеризует близость двух классификаций в целом, а M — совпадение верхних частей классификаций[11].
Тема. Напишите программу, читающую исходное значение n, проводящую каждый из трех турниров для 2n соперников и вычисляющую статистики R и M для каждой из трех пар классификаций. Проведите эксперимент большое число раз с постоянным значением n и подсчитайте средние значения M и R. Сравните, какая из двух систем — швейцарская или с немедленным выбыванием — лучше повторяет результаты кругового турнира.
Указания исполнителю. Разумеется, нужно досконально разбираться в разных системах проведения турниров, нужно эффективно программировать подбор пар. Но не упустите из виду еще один момент. Размеры кругового турнира заставляют эффективно запрограммировать внутренний цикл и экономно расходовать память для хранения результатов встреч. Разумеется, вам понадобится хороший генератор случайных чисел для определения результатов встреч. Наконец, при швейцарской системе возможны попытки дважды свести одну и ту же пару соперников, поэтому либо докажите, что такого не произойдет, либо измените алгоритм, избегая повторных встреч, но подчиняясь общему правилу: старайтесь сводить в пары соперников, набравших почти равное количество очков.
Инструментовка. Годится алгебраический процедурный язык с хорошими управляющими структурами цикла. Возможно, подойдет и APL или другой язык обработки массивов, если только вы сумеете так организовать турниры, чтобы стала выгодной параллельная обработка всех соперников.
Длительность исполнения. Одному исполнителю на 2 недели.
Развитие темы. Большинство расширений включает более подробный анализ и сравнение систем проведения турниров. Во-первых, заметьте, что нижняя часть классификации по итогам турнира с немедленным выбыванием носит довольно произвольный характер. Кроме того, соперникам, попавшим в эту часть классификации, весьма тоскливо, ибо они рано вылетели. Для утешения можно организовать турниры с немедленным выбыванием среди неудачников каждого круга. Результаты этих турниров, а не приведенное выше правило, расставят неудачников по местам. Поскольку и в этих побочных турнирах будут проигравшие, организуйте турниры неудачливых неудачников, и так до посинения. Заметьте, что турнир по-прежнему пройдет в n кругов, но теперь все соперники будут участниками всех кругов. Если во всех встречах побеждают сильнейшие, этот, более тщательно организованный турнир превращается в законченный алгоритм сортировки.
