Вопрос тем кто разбирается в футболе. Должно быть вы знаете, что в любом чемпионате есть календарь игр. Есть туры - игровые дни. В каждом туре играют все команды по 1 игре. Кол-во туров зависит от кол-ва команд. (если команд 16, то туров 30, играются в два круга по 15 туров, в каждом туре 8 игр. т.е. каждая команда проводит 30 игр.)

Пример для чемпионата из 4 команд:

Команда1
Команда2
Команда3
Команда4

**Календарь**
Круг 1 (все играют со всеми)
**Тур 1**
Команда1 - Команда2
Команда3 - Команда4

**Тур 2**
Команда2 - Команда3
Команда4 - Команда1

**Тур 3**
Команда1 - Команда3
Команда2 - Команда4

Круг 2 (тоже самое но только команды меняются полями, т.е. местами)
**Тур 4**
Команда2 - Команда1
Команда4 - Команда3

**Тур 5**
Команда3 - Команда2
Команда1 - Команда4

**Тур 6**
Команда3 - Команда1
Команда4 - Команда2

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

задан 16 Фев '12 17:33

ну математики хотя бы скажите в какую сторону копать, это ведь похоже на задачу из комбинаторики???

(17 Фев '12 11:28) Марат
10|600 символов нужно символов осталось
2

Вам нужен алгоритм порождения любого турнира или какого-нибудь одного? Для последнего можно попробовать так: строим "турнирную таблицу" 16*16 (например), но в клетки записываем не выигрыш, а номер тура (считаем, что один тур = 8 игр, и всего туров 15).

Таблица получается симметричной (строим только для одного круга). Заполнить ее надо так, чтобы в строках (и в столбцах) не повторялись номера (т.е. это симметричный латинский квадрат). К сожалению, я не знаю теории латинских квадратов и то, насколько произвольно можно их заполнять. Можно попробовать так: заполняем первую строку, симметрично - первый столбец, потом оставшуюся часть второй строки, соблюдая свойство "неповторения", симметрично второй столбец. и т.п. надеюсь противоречия не будет?

После заполнения собираем все пары с одинаковым номером в один тур.

ссылка

отвечен 17 Фев '12 20:47

изменен 17 Фев '12 20:49

Попробовала вручную (на Excel), как попало расставить не удается. Возникают противоречия. Надо посмотреть теорию латинских квадратов.

(17 Фев '12 21:43) DocentI

Видимо, отыскание латинских квадратов идет перебором. Задача NP-сложная. А тут еще симметрия!

(18 Фев '12 9:08) DocentI
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×76
×3

задан
16 Фев '12 17:33

показан
1574 раза

обновлен
18 Фев '12 9:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru