Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Алгоритм жеребьевки |
Автор: BlackWolf 7.4.2003, 15:32 |
Есть ли какой-то математический алгоритм проведения жеребьевок команд? Например: Есть n - команд, все команды выступают на одном поле. каждая команда должна провести встречи со всеми другими командами. Задача: Нужно найти порядок проведения встреч между командами таким образом чтобы ни одна команда не играла несколько игр подряд, т.е. чтобы между играми одной команды были паузы. Достоверно известно: Формула количества встреч: (n*(n-1)) / 2 Также проверил что для 4 команд рассчитать порядок без "передышек" нельзя. Если кто может помочь очень прошу... |
Автор: pike 8.4.2003, 09:31 |
Будем обозначать каждую игру числом из 0 и 1. Позиция цифры в числе - № команды. Сначала распределяем пары 11 (рядом стоящие), потом 101 и т.д. Алгоритм довольно просто составляется. Единственная проблема (легко решаемая) - вставить последнюю (10000001). А ее вставляем между первыми! Смотри пример! 11000000 00110000 10000001 00001100 00000011 01100000 00011000 00000110 10100000 01010000 00101000 00010100 00001010 00000101 10010000 01001000 00100100 00010010 00001001 01000100 10001000 00100010 00010001 10000100 01000010 00100001 10000010 01000001 |
Автор: neutrino 9.4.2003, 10:40 |
Хмм... Я посмотрел решение выше, и подумал, может быть прокатит вот так: если у нас количество команд n, то за i возьмем номер одной команды, а за j другой, далее: i=0, j=0; n mod 2 = 0 => i=(i+1) mod n, j=(j+3) mod n n mod 2 != 0 => i=(i+2) mod n, j=(j+4) mod n игра(i, j) Другими словами, если количество команд четное, то воспользоваться первой формулой, иначе второй. |
Автор: pike 9.4.2003, 12:29 |
...нет, не получится i и j скорее всего совпадут. Или я что-то не понял? |
Автор: neutrino 9.4.2003, 14:20 | ||
Приветствую! Я написал программу и все заработало!!! Но! Потом посмотрел и оказалось, что я всего лишь повторил алгоритм господина pike ![]() ![]()
Esli Вы запустите программу, то увидете сначала список турниров между номерами команд и матрицу количества игр. Ни одного повторения. Браво, pike !!! |
Автор: Lexa_ch 13.8.2005, 03:26 |
А если требуется составить жеребьевку с учетом туров (т.е. составить расписание игр для какого-либо числа команд наподобие футбольных, хоккейных и т.д. расписаний). В каждом туре команда играет только один раз, число игр в туре = кол-во команд/2, число туров - кол-во команд-1 (для однокругового турнира). Если не тяжело, приведите код или подробный алгоритм. |
Автор: Ostalex 8.9.2010, 14:49 | ||
up. то, что сейчас и мне нужно. пожалуйста, если кто может подскажите, не дайте потратить время на го*нокод) |
Автор: nmn 8.9.2010, 22:05 |
а если число команд нечетное? |
Автор: Ostalex 9.9.2010, 14:04 | ||
условие такое, что число команда всегда остается четным <4-16> |
Автор: nmn 9.9.2010, 15:38 |
не очень понял я всю схему похоже вот смотрите: если в одном туре команда играет 1 раз, то можно их просто разбить на пары, тогда получим необходимое количество игр в туре и каждая команда будет играть только 1 раз, а что дальше? |
Автор: Ostalex 9.9.2010, 18:38 |
вот пример: http://www.fc-anji.ru/calendar.php здесь команда <анжи> выступает то в гостях, то дома. получается почти "шахматка", т.к. не всегда совпадает. там есть ссылка и на весь календарь по всем командам. вот реализацию такого календаря какраз и нужно сделать. но пока без успехов |
Автор: nmn 9.9.2010, 21:43 |
не нашел ссылку на весь календарь, но там в туре всего лишь одна игра вобщем расскажите подробно что надо |
Автор: Ostalex 11.9.2010, 18:47 |
заюзал алгоритм, в котором есть ограничение: команд может быть только 2^n, но это компенсируется скоростью работы |
Автор: nmn 11.9.2010, 23:47 |
а можно ссылку? |