|
здраствуйте...
помогите пожалуста с решением одной задачки... мне нужно составить таблицу игр чемпионата для 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]
вроде бы всё просто, однако порой вознивает ситуация, когда "не из чего выбирать", то есть те команды, с которыми текущая команда ещё не играла, уже участвуют в данном туре
И вот тут то я и застрял... мне кажется что должно быть какоето решение проще и "красивее" из комбинаторики или теории множеств, но, увы, я в этом не силён... может мне кто подскажет как это сделать?
|
15.04.2008, 21:17 
