Смежные строки (Re: Сортировка)

From

Comoderator Of Ru Algorithms (2:5002/46.4)

To

Valentin Davydov

Date

2002-05-07T16:38:04Z

Area

RU.ALGORITHMS

Hello Valentin.

06 Май 02 16:19, you wrote to Evgeniy Jirnov:

Offtopic
Изменение сабжа ничего не меняет, этот спор объявлен оффтопиком.

 >>   From: Evgeniy Jirnov
 >> <Evgeniy.Jirnov@p13.f1230.n5030.z2.fidonet.org>  Date: Sun, 05 May
 >> 2002 10:35:40 +0400
 >> AB> В Пузырьке они смежные.  Смежные можно объменять местами без
 >> AB> дополнительных затрат.
 >>
 >> Да? Ну тогда "обменяй" пожалуйста эти две строчки,
 >> без дополнительных затрат ресурсов:
 >> evgeniy\0jirnov\0

 VD> Пусть элементарная операция - это копирование одного байта. Тогда
 VD> получается:

 VD> evgeniy0jirnov0
 VD> evgeniyejirnov0
 VD> jvgeniyejirnov0
 VD> jvgeniyevirnov0
 VD> jigeniyevirnov0
 VD> jigeniyevgrnov0
 VD> jireniyevgrnov0
 VD> jireniyevgenov0
 VD> jirnniyevgenov0
 VD> jirnoiyevgenov0
 VD> jirnoiyevgeniv0
 VD> jirnovyevgeniv0
 VD> jirnovyevgeniy0
 VD> jirnov0evgeniy0,

 VD> то есть всего 13 шагов. Правда, я чуток съоптимизировал,
 VD> воспользовавшись тем, что строчка "jirnniyevgenov0" переходит сама в
 VD> себя при переносе буквы 'n' с пятого места на двенадцатое. В общем же
 VD> случае количество потребных шагов равно суммарной длине обеих строк за
 VD> вычетом единицы (последний ноль в перестановках не участвует).

 VD> Вал. Дав.
 VD> --- ifmail v.2.15dev5
 VD>  * Origin: St. Petersburg State University (2:5020/400)

Comoderator

... . Один лишь шаг может все решить. (q) Ария
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)