Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Генерация таблицы игр чемпионата
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

krinart


Новичок

здраствуйте...

помогите пожалуста с решнием одной задачки... мне нужно составить таблицу игр чемпионата для n команд, таким образом, чтобы строки это были туры, а столбцы команды...

например, может получиться такая таблица
    1 2 3 4 5 6
------------------
1 | 2 1 6 5 4 3
2 | 3 5 1 6 2 4
3 | 6 4 5 2 3 1
4 | 4 3 2 1 6 5
5 | 5 6 4 3 1 2

то есть в результате каждая команда сыграет с каждой по одному разу...

на самом деле вся задача сводится к построению матрицы размером (N-1)*N таким образом, чтобы числа в столбцах и строках не повторялись, а-ля магический квадрат, но плюс к этому, добавляется ещё одно условие - каждому элементу k, находящемуся на позиции [i, j] должен соответствовать элемент j, находящийся на позиции [i, k], чтобы каманды "играли друг с другом" в каждом туре..

я написал алгоритм, который действует следующим образом:
1. обнуляем матрицу

2. проходим всю матрицу по строкам

3. если элемент [i, j] равен нулю, то составляем список команд, с которыми эта команда ещё не играла(то есть этого элемента не было в столбце j) и которые ещё не играли в этом туре(строка i).

4. случайным образом выбираем из этого списка одну команду k и записываем число k ячейку [i, j] и соответственно j в ячейку [i, k]

вроде бы всё просто, однако порой вознивает ситуация, когда "не из чего выбирать", то есть те команды, с которыми текущая команда ещё не играла, уже участвуют в данном туре

И вот тут то я и застрял...  мне кажется что должно быть какоето решение проще и "красивее" из комбинаторики или теории множеств, но, увы, я в этом не силён... может мне кто подскажет как это сделать?

Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 14 апр. 2008 18:34 | IP
Guest



Новичок

{7, 3, 2, 5, 4, 9, 1, 10, 6, 8, 13, 14, 11, 12},
{2, 1, 4, 3, 6, 5, 12, 11, 13, 14, 8, 7, 9, 10},
{3, 4, 1, 2, 7, 10, 5, 12, 11, 6, 9, 8, 14, 13},
{4, 5, 6, 1, 2, 3, 13, 14, 12, 11, 10, 9, 7, 8},
{5, 6, 7, 8, 1, 2, 3, 4, 14, 13, 12, 11, 10, 9},
{6, 7, 5, 9, 3, 1, 2, 13, 4, 12, 14, 10, 8, 11},
{8, 9, 10, 6, 11, 4, 14, 1, 2, 3, 5, 13, 12, 7},
{9, 8, 11, 12, 13, 14, 10, 2, 1, 7, 3, 4, 5, 6},
{10, 11, 8, 13, 14, 12, 9, 3, 7, 1, 2, 6, 4, 5},
{11, 10, 9, 14, 12, 13, 8, 7, 3, 2, 1, 5, 6, 4},
{12, 13, 14, 7, 8, 11, 4, 5, 10, 9, 6, 1, 2, 3},
{13, 14, 12, 10, 9, 8, 11, 6, 5, 4, 7, 3, 1, 2},
{14, 12, 13, 11, 10, 7, 6, 9, 8, 5, 4, 2, 3, 1}

Такая подойдет?

Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2008 17:46 | IP
krinart


Новичок

круть... я ожидал увидеть всё что угодно но только не готовую таблицу для 14 команд))  спасибо конечно тебе, Guest, но вобще я расчитывал на алгоритм, ну или хотябы идею, мне ведь нужно её случайным образом заполнять...

мне вот только интересно только как ты её получил?...

Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 16 апр. 2008 21:02 | IP
Guest



Новичок

{9, 3, 2, 5, 4, 7, 6, 14, 1, 13, 12, 11, 10, 8, 17, 18, 15, 16},
{2, 1, 4, 3, 6, 5, 8, 7, 14, 15, 13, 16, 11, 9, 10, 12, 18, 17},
{3, 4, 1, 2, 7, 8, 5, 6, 16, 14, 15, 17, 18, 10, 11, 9, 12, 13},
{4, 5, 6, 1, 2, 3, 9, 17, 7, 16, 18, 14, 15, 12, 13, 10, 8, 11},
{5, 6, 7, 8, 1, 2, 3, 4, 17, 18, 14, 13, 12, 11, 16, 15, 9, 10},
{6, 7, 5, 9, 3, 1, 2, 18, 4, 17, 16, 15, 14, 13, 12, 11, 10, 8},
{7, 8, 9, 6, 10, 4, 1, 2, 3, 5, 17, 18, 16, 15, 14, 13, 11, 12},
{8, 9, 10, 7, 11, 12, 4, 1, 2, 3, 5, 6, 17, 16, 18, 14, 13, 15},
{10, 11, 8, 12, 9, 13, 15, 3, 5, 1, 2, 4, 6, 18, 7, 17, 16, 14},
{11, 10, 12, 13, 8, 15, 16, 5, 18, 2, 1, 3, 4, 17, 6, 7, 14, 9},
{12, 13, 11, 10, 14, 17, 18, 16, 15, 4, 3, 1, 2, 5, 9, 8, 6, 7},
{13, 12, 14, 11, 16, 18, 17, 15, 10, 9, 4, 2, 1, 3, 8, 5, 7, 6},
{14, 15, 13, 17, 18, 16, 10, 11, 12, 7, 8, 9, 3, 1, 2, 6, 4, 5},
{15, 14, 16, 18, 17, 9, 11, 13, 6, 12, 7, 10, 8, 2, 1, 3, 5, 4},
{16, 17, 18, 14, 15, 10, 13, 12, 11, 6, 9, 8, 7, 4, 5, 1, 2, 3},
{17, 18, 15, 16, 12, 11, 14, 10, 13, 8, 6, 5, 9, 7, 3, 4, 1, 2},
{18, 16, 17, 15, 13, 14, 12, 9, 8, 11, 10, 7, 5, 6, 4, 2, 3, 1}

Вот для 18-ти. Что значит случайная - тут компонент связанности ~2n(n-1)/3. А перестановка строк? Например, таблиц 5x6 всего 5*144. Можно случайно выбирать из них.

Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2008 21:23 | IP
krinart


Новичок

хорошо, допустим я могу переставлять строки и получать "случайную" таблицу... но как мне получать исходную неслучайную?.. я же не могу вручную вбить в алгоритм все варианты, начиная от 4-ёх команд и заканчивая к примеру 30-ю, а потом в зависимости от условия использовать только ту которая мне нужна...

Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 16 апр. 2008 22:03 | IP
Guest



Новичок

{8, 4, 7, 2, 6, 5, 3, 1},
{2, 1, 8, 5, 4, 7, 6, 3},
{3, 5, 1, 6, 2, 4, 8, 7},
{4, 8, 6, 1, 7, 3, 5, 2},
{5, 3, 2, 7, 1, 8, 4, 6},
{6, 7, 5, 8, 3, 1, 2, 4},
{7, 6, 4, 3, 8, 2, 1, 5}
-----------------------------
{3, 5, 1, 7, 2, 8, 4, 6},
{2, 1, 6, 8, 7, 3, 5, 4},
{4, 6, 7, 1, 8, 2, 3, 5},
{5, 3, 2, 6, 1, 4, 8, 7},
{6, 7, 8, 5, 4, 1, 2, 3},
{7, 8, 4, 3, 6, 5, 1, 2},
{8, 4, 5, 2, 3, 7, 6, 1}
Давайте рассмотрим две таблицы 7x8. Сколько в каждой из них случайных компонент, а сколько связанных? Каждая порождает 7! таблиц. Так, что здесь нужно уточнение. Как генерируются не случайные, вопрос решаемый, но, например, таблиц 7x8 больше 7*26000.

Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2008 22:45 | IP
krinart


Новичок

прошу прощения за временное молчание...

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

я был бы очень признателен, если бы ты мне привел пример алгоритма генерации этих неслучаных таблиц, хотя бы в крупных командах, как я в самом первом посте написал свой алгоритм

Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 21 апр. 2008 21:37 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com