пятнашки, пpовеpка на pешаемость

From

Alexey Kruglov (2:5015/70.5)

To

Borodin Anatoly

Date

2002-05-09T21:33:10Z

Area

RU.ALGORITHMS

nPuBeT, Borodin!

Четверг 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
строках, иначе он правилен.

Нашел опечатку у Макса: целевая позиция должна быть (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)