|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 06 May 2002 17:19:48
To : Evgeniy Jirnov
Subject : Смежные строки (Re: Сортировка)
--------------------------------------------------------------------------------
> From: Evgeniy Jirnov <Evgeniy.Jirnov@p13.f1230.n5030.z2.fidonet.org>
> Date: Sun, 05 May 2002 10:35:40 +0400
> AB> В Пузырьке они смежные. Смежные можно объменять местами без
> AB> дополнительных затрат.
>
>Да? Hу тогда "обменяй" пожалуйста эти две строчки,
>без дополнительных затрат ресурсов:
>evgeniy\0jirnov\0
Пусть элементарная операция - это копирование одного байта. Тогда получается:
evgeniy0jirnov0
evgeniyejirnov0
jvgeniyejirnov0
jvgeniyevirnov0
jigeniyevirnov0
jigeniyevgrnov0
jireniyevgrnov0
jireniyevgenov0
jirnniyevgenov0
jirnoiyevgenov0
jirnoiyevgeniv0
jirnovyevgeniv0
jirnovyevgeniy0
jirnov0evgeniy0,
то есть всего 13 шагов. Правда, я чуток съоптимизировал, воспользовавшись
тем, что строчка "jirnniyevgenov0" переходит сама в себя при переносе буквы
'n' с пятого места на двенадцатое. В общем же случае количество потребных
шагов равно суммарной длине обеих строк за вычетом единицы (последний ноль
в перестановках не участвует).
Вал. Дав.
--- ifmail v.2.15dev5
* Origin: St. Petersburg State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
