|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Kruglov 2:5015/70.5 09 May 2002 21:33:10
To : Borodin Anatoly
Subject : пятнашки, пpовеpка на pешаемость
--------------------------------------------------------------------------------
Четверг 09 Мая 2002 12:48, Alexey Kruglov wrote to Borodin Anatoly:
>>> всегда pешабельно, можно ли быстpо пpовеpить на pешаемость и
>>> соответсвенно
BA>> Выписать все числа в строку (не обращая внимание на пустышку) и
BA>> подсчитать число инверсий. В конечном состоянии
BA>> 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 - число инверсий 0, чётно
BA>> Чётность числа инверсий в процессе игры не меняется
AK> Передвигаем в конечном состоянии 12 на свободное место, получится:
AK> 1,2,...,11,13,14,15,12. Число инв. с участием первых 11 чисел = 0,
AK> для оставшихся: (13,12),(14,12),(15,12) => число инв. = 3. Вот и
AK> изменилось. Чтобы не менялось надо их выписывать так, как написал Max
AK> Alekseyev.
Подумал еще: эта перестановка отличается от максовской умножением на
перестановку, зависящую от положения пустого поля, поэтому правильность
результата зависит только от положения этого поля. Если посчитать, оказывается,
что результат будет противоположен правильному, когда пустое поле в 1 или 3
строках, иначе он правилен.
Hашел опечатку у Макса: целевая позиция должна быть (1,2,3,4, 8,7,6,5,
9,10,11,12, 15,14,13). В конце про ее нечетность написано правильно.
nOkA. Alexey.
--- GoldED+/386 1.1.4.7
* Origin: 6DFA 1186 7576 DE60 6CCB EB39 AD81 1733 EEBB 970A (2:5015/70.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
