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

From

Borodin Anatoly ()

To

Ilya V Bursov

Date

2002-05-07T11:52:27Z

Area

RU.ALGORITHMS

From: Borodin Anatoly <fractal@viii.ntu-kpi.kiev.ua>

Hi!

> всегда pешабельно, можно ли быстpо пpовеpить на pешаемость и соответсвенно

Выписать все числа в строку (не обращая внимание на пустышку) и подсчитать число инверсий.
В конечном состоянии 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 - число инверсий 0, чётно

Чётность числа инверсий в процессе игры не меняется

Инверсия: ситуация, когда в последовательности появляется большее число раньше меньшего. Например:
4,3,1,2

4,3
4,1
4,2
3,1
3,2

5 инверсий

-- 
Digitally yours,
    Borodin Anatoly			mailto:fractal@viii.ntu-kpi.kiev.ua
					http://viii.ntu-kpi.kiev.ua/~fractal
У меня сегодня радость- я соседу сделал гадость!
--- ifmail v.2.15dev5
 * Origin: I N F E R N O (2:5020/400)