Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
D. Процедуры перестановки и обмена
D.1. Перестановки D.1.1 Однородные или остаточные очковые группы Пример: В подгруппе S1 пять игроков 1, 2, 3, 4 и 5 (в такой последовательности), в подгруппе S2 шесть игроков 6, 7, 8, 9, 10 и 11 (в такой последовательнос-ти). Перестановки в подгруппе S2 должны начинаться с самого нижнего игрока по убыванию приритета:
D.1.2 Неоднородные очковые группы
Алгоритм - в принципе тот же самый, что и для однородных очковых групп (См. D.1.1), особенно, когда S1 = S2. Если S1<S2, алгоритм должен быть адаптирован к разному количеству игроков в S1 и S2. Пример: В S1 включены 2 игрока 1, 2 (в этой последовательности). В S2 включены 6 игроков 3, 4, 5, 6, 7, 8 (в этой последовательности). Перестановки внутри S2 такие же самые как в D.1.1. Но с подгруппой S1 могут быть спарены только S1 первых перечисленных игроков перестановки. Остальные S2 – S1 игроков останутся в этой попытке без жеребьёвки. D.2. Обмен игроков (только однородные и остаточные очковые группы) При обмене между S1 и S2 разность между участвующими в обмене номерами должна быть по возможности меньше. Когда различий между разными вариантами нет, прини-мается вариант, относящийся к самому нижнему игроку в списке S1. Затем принимает-ся вариант, относящийся к самому верхнему игроку в списке S2.
Общая процедура: Ø Сортируем в понижающем лексикографическом порядке группу игроков в подгруппе S1, которые могут быть обменены, как показано ниже в примерах (Список обменов в S1). Ø Сортируем в возрастающем лексикографическом порядке группу игроков в подгруппе S2, которые могут быть обменены, как показано ниже в примерах (Список обменов в S2). Ø Разность номеров игроков, участвующих в обмене равна: (Сумма номеров игроков в S2) – (Сумма номеров игроков в S1). Эта разность должна быть по возможности наименьшей. Ø Если различия между разными вариантами нет: · Сначала принимают вариант сверху вниз из списка обменов S1. · Затем принимают вариант сверху вниз из списка обменов S2.
Ø Согласно А.2. после каждого обмена как S1, так и S2 должны быть упорядочены. Замечание: При выполнении этой процедуры может случиться, что снова появятся уже проверенные пары. Эти повторения безопасны, потому что они не дают лучших пар, чем при их первом появлении.
Пример обмена одним игроком:
Пример обмена двумя игроками:
1. Обмен 5,4 из S1 с 6,7 из S2: разность = 4; 2. Обмен 5,4 из S1 с 6,8 из S2: разность = 5; 3. Обмен 5,3 из S1 с 6,7 из S2: разность = 5; 4. Обмен 5,4 из S1 с 6,9 из S2: разность = 6; 5. Обмен 5,4 из S1 с 7,8 из S2: разность = 6; 6. Обмен 5,3 из S1 с 6,8 из S2: разность = 6; и т.д.
Пример обмена тремя игроками:
Список обменов S1: 5,4,3 5,4,2 5,4,1 5,3,2 5,3,1 5,2,1 4,3,2 4,3,1 4,2,1 3,2,1 Список обменов S2: 6, 7, 8 6, 7, 9 6, 7,10 6, 7,11 6 8, 9 6, 8,10 6, 8,11 6, 9,10 6, 9,11 6,10,11 7, 8, 9 7, 8,10 7, 8,11 7, 9,10 7, 9,11 7,10,11 8, 9,10 8, 9,11 8,10,11 9,10,11 1. Обмен 5,4,3 из S1 с 6,7,8 из S2: разность = 9; 2. Обмен 5,4,3 из S1 с 6,7,9 из S2: разность = 10; 3. Обмен 5,4,2 из S1 с 6,7,8 из S2: разность = 10; 4. Обмен 5,4,3 из S1 с 6,7,10 из S2: разность = 11; 5. Обмен 5,4,3 из S1 с 6,8,9 из S2: разность = 11; 6. Обмен 5,4,2 из S1 с 6,7,9 из S2: разность = 11; и т.д. Точные процедуры обмена N (N= 1, 2, 3, 4...) игроков очковой группы из Р игроков Ø Сортируем все возможные подмножества N игроков из S1 в понижающем лексико-графическом порядке во множество S1LIST, которое может иметь элементы S1NLIST.
Ø Сортируем все возможные подмножества N игроков из S2 в возрастающем лексико-графическом порядке во множество S2LIST, которое может иметь элементы S2NLIST. Ø Для каждого возможного обмена между S1 и S2 может быть определенa разность, которая рассчитывается как: (Сумма номеров игроков из S1, включенных в этот обмен) – (Сумма номеров игроков из S2, включенных в этот обмен).
В функциональном отношении: DIFFERENZ (I, J) = (сумма номеров игроков S2 в подмножестве J – сумма номеров игроков S1 в подмножестве I). У этой разности есть минимум: DIFFMIN = DIFFERENZ(1,1) и максимум DIFFMAX = DIFFERENZ(S1NLIST, S2NLIST) Далее правильный алгоритм процедуры нахождения обменов: 1 DELTA = DIFFMIN 2 I=1 J=1 3 If DELTA = DIFFERENZ(I,J) then делаем этот обмен, after that goto 4
4 If J<S2NLIST then J=J+1 goto 3 5 If I<S1NLIST then I=I+1, J=1 goto 3 6 DELTA =DELTA+1 7 If DELTA > DIFFMAX goto 9 8 goto 2 9 Возможности обмена N игроков исчерпаны. В соответствии с A.2 после каждого обмена как S1, так и S2 должны быть упорядочены. D.3. Обмен спущенных игроков Пример: M0 равняется 5. Первоначальное положение игроков в S1 {1, 2, 3, 4, 5}.
Элементы в S1 начинаются с M1 самых вышестоящих игроков, далее в порядке понижения приоритета:
D.4. Примечание для программистов: В-3 фактор в самой низшей очковой группе После повторных применений правила C.13 вполне возможно, что в самой низшей очко-вой группе (СНОГ) соберутся игроки, набравшие различное количество очков, и жеребь-ёвку этой группы можно выполнить множеством способов. Такая группа будет или однородной (когда количество игроков, вошедших из предпос-ледней очковой группы равно или больше количества игроков СНОГ), или в конечном счете образуется однородный остаток. В программах жеребьёвки должно применяться следующее правило: Лучшей жеребьёвкой для такой однородной очковой группы или однородного ос-татка будет жеребьёвка, которая минимизирует сумму среднеквадратических от-клонений между очками двух игроков в каждой паре (называемую B.3‐фактором). Получение освобождения от игры эквивалентно встрече с соперником, имеющим на одно очко меньше, чем игрок с наименьшим количеством очков (даже если это приводит к ‐1).
Пример: Пусть в СПОГ входят следующие игроки:
3.0: A 2.5: B, C 2.0: D 1.5: E 1.0: F Игрок F может играть только с игроком А. Первоначально жеребьёвка начинается с S1 = {A, B, C} S2 = {D, E, F} и после некоторых перестановок приводит к Png1: [S1 = {A, B, C} S2 = {F, D, E}]. Однако, работа не закончена. Должны быть использованы некоторые обмены, которые приводят к Png2: [S1 = {A, B, D} S2 = {F, C, E}], что является самой лучшей жеребьёвкой. Это из-за B.3‐ фактора. Давайте вычислим его: Png1: (A‐F, B‐D, C‐E) => (2.0*2.0 + 0.5*0.5 + 1.0*1.0) = 5.25 Png2: (A‐F, B‐C, D‐E) => (2.0*2.0 + 0.0*0.0 + 0.5*0.5) = 4.25 Предупреждение: если есть седьмой игрок (G), набравший меньше 2.5 очков, который единственный может получить освобождение от игры, СНОГ является неоднородной, и никакие обмены в S1не допускаются. В таком случае жеребьёвка СНОГ имеет вид: A‐F, B‐D, C‐E, G (свободен). Замечание: Этот алгоритм ничего особенного не представляет. Это наилучший мате-матический метод нахождения жеребьёвки, которую естественно достигнет арбитр, ви-дящий все данные игроков.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-01-20; просмотров: 239; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.129.45.92 (0.038 с.) |