Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Алгоритм жеребьевки


Автор: 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 smile.gif (правда, немного в другой форме - смешанной с моей идеей wink.gif )


Цитата

#include <iostream.h>
#define n 10

void main() {
  int i=0, j=0, k, m;
  int arr[n][n]={0};

  for (m=1; m<n; m++) {
    for (k=0; k<n; k++) {
      i=(i+1)%n;
      j=(i+m)%n;
      arr[i][j]++;
      cout<<endl<<i<<"-"<<j;
    }
  }
  cout<<endl;
  for (m=0; m<n; m++) {
    for (k=0; k<n; k++) {
      cout<<" "<<arr[m][k];
    }
    cout<<endl;
  }
}


Esli Вы запустите программу, то увидете сначала список турниров между номерами команд и матрицу количества игр. Ни одного повторения. Браво, pike !!!

Автор: Lexa_ch 13.8.2005, 03:26
А если требуется составить жеребьевку с учетом туров (т.е. составить расписание игр для какого-либо числа команд наподобие футбольных, хоккейных и т.д. расписаний). В каждом туре команда играет только один раз, число игр в туре = кол-во команд/2, число туров - кол-во команд-1 (для однокругового турнира). Если не тяжело, приведите код или подробный алгоритм.

Автор: Ostalex 8.9.2010, 14:49
Цитата(Lexa_ch @ 13.8.2005,  03:26)
А если требуется составить жеребьевку с учетом туров (т.е. составить расписание игр для какого-либо числа команд наподобие футбольных, хоккейных и т.д. расписаний). В каждом туре команда играет только один раз, число игр в туре = кол-во команд/2, число туров - кол-во команд-1 (для однокругового турнира). Если не тяжело, приведите код или подробный алгоритм.

up.
то, что сейчас и мне нужно. пожалуйста, если кто может подскажите, не дайте потратить время на го*нокод)

Автор: nmn 8.9.2010, 22:05
Цитата(Ostalex @  8.9.2010,  14:49 Найти цитируемый пост)
В каждом туре команда играет только один раз

а если число команд нечетное?

Автор: Ostalex 9.9.2010, 14:04
Цитата(nmn @ 8.9.2010,  22:05)
Цитата(Ostalex @  8.9.2010,  14:49 Найти цитируемый пост)
В каждом туре команда играет только один раз

а если число команд нечетное?

условие такое, что число команда всегда остается четным <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
а можно ссылку?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)