|
|
|
|
|
|
|
Вернуться
| 1 Бабушкин Олег, 27 декабря 2009 г. 19:56:13 | |
|
Спасибо) вроде понятно
|
|
|
| 2 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 27 декабря 2009 г. 19:52:15 | |
заметим что транспозиция строк, не влияет на дальнейшую транспозицию столбцов и наоборот. Значит эту задачу можно разбить на две и делать сначала транспозиции строк, а потом столбцов. найдем столбец где стоит число 1. будем делать транспозицию строк, исходя из данных по этому столбцу, ведь у нас решение существует. для первой строки найдем строку где стоит 1 в этом столбце поменяем их местами, для второй строку с числом 1 + M, для i-той строку с числом 1 + M * (i - 1), будем делать такие транспозиции, пока все строки не встали на свои места. Потом проделаем так же со столбцами пользуясь, например, первой строкой.
Доказательство минимальности транспозиций, я думаю, можно где-нибудь прочитать.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
