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

From

Alexey Kruglov (2:5015/70.5)

To

Borodin Anatoly

Date

2002-05-09T11:48:27Z

Area

RU.ALGORITHMS

nPuBeT, Borodin!

Вторник 07 Мая 2002 10:52, Borodin Anatoly wrote to Ilya V Bursov:

 >> всегда 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> Чётность числа инверсий в процессе игры не меняется

Передвигаем в конечном состоянии 12 на свободное место, получится:
1,2,...,11,13,14,15,12. Число инв. с участием первых 11 чисел = 0, для
оставшихся: (13,12),(14,12),(15,12) => число инв. = 3. Вот и изменилось. Чтобы
не менялось надо их выписывать так, как написал Max Alekseyev.

nOkA. Alexey.

--- GoldED+/386 1.1.4.7
 * Origin:  6DFA 1186 7576 DE60 6CCB  EB39 AD81 1733 EEBB 970A  (2:5015/70.5)