|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Comoderator Of Ru Algorithms 2:5002/46.4 07 May 2002 16:38:04
To : Valentin Davydov
Subject : Смежные строки (Re: Сортировка)
--------------------------------------------------------------------------------
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> дополнительных затрат.
>>
>> Да? Hу тогда "обменяй" пожалуйста эти две строчки,
>> без дополнительных затрат ресурсов:
>> 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
