|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Paul Yanchenko 2:5080/151 23 Sep 2001 21:09:13
To : All
Subject : поменять две цепочки местами.
--------------------------------------------------------------------------------
При написании одного своего модуля мне потребовался алгоритм, который, если
опустить все детали, сводится к следующей задаче:
Есть некая последовательность элементов (байтов). В этой последовательности
известны две неперекрывающиеся цепочки элементов. Hеобходимо оптимальным образом
поменять эти цепочки местами.
Если цепочки одинаковой длины - все тривиально. Если же разной - у меня возникли
трудности. Условимся, что первая цепочка расположена раньше второй. Очевидно,
что для работы нам можно ограничиться лишь фрагментом всей последовательности -
от начала первой цепочки и до конца второй. Схемотично покажу это так:
| цепочка 1 | элементы между ними |цепочка 2|
|a b c d e f g h i|j k l m n o p q r s t u|v w x y z|
1 2 3 4 5 6 7 8 91011121314151617181920212223242526
В результате у нас должно получиться следующее:
|цепочка 2| элементы между ними | цепочка 1 |
|v w x y z|j k l m n o p q r s t u|a b c d e f g h i|
1 2 3 4 5 6 7 8 91011121314151617181920212223242526
Для перестановки нам досточно будет буфера из одного элемента (одного байта) и
количество перестановок будет равно длине фрагмента плюс количество копирований
в буфер, т.е. минимальное. Приведу частное решение:
buf:=[1]
[1]:=[22]
[22]:=[5]
[5]:=[26]
[26]:=[9]
[9]:=[13]
[13]:=[17]
[17]:=[21]
[21]:=[4]
[4]:=[25]
[25]:=[8]
[8]:=[12]
[12]:=[16]
[16]:=[20]
[20]:=[3]
[3]:=[24]
[24]:=[7]
[7]:=[11]
[11]:=[15]
[15]:=[19]
[19]:=[2]
[2]:=[23]
[23]:=[6]
[6]:=[10]
[10]:=[14]
[14]:=[18]
[18]:=buf
Эта последовательность получена на бумажке, понятно, надеюсь каким методом я ее
получил, но у меня возникли трудности с написанием общего алгоритма. Я уже
примерно знаю как, но просто может быть кто-нибудь уже решал такую задачу и
будет так добр, что поделится со мной решением?
P.S. В данном случае, мы вначале скопировали первый элемент в буфер, а в самом
конце вставили из него. Hо я могу также привести случай, когда нам это придется
делать несколько раз, проблема в том - как используя дополнительной памяти найти
следующий неперемещенный элемент. Интуиция мне подсказывает, что он будет
следующим, т.е. вторым, потом третьим и так далее. А об окончании процесса мы
узнаем проверив некий счетчик присваиваний в элементы последовательности - он
должен быть равен длине всего фрагмента. Hо от чего это все зависит я пока не
могу понять, а также возможно ли выбрать такой стартовый элемент, чтобы нам не
пришлось делать повторное присваивание в буфер...
Virtually yours. Paul.
--- Good byte! pusher@mail.ur.ru, http://pusher.nm.ru
* Origin: garbage (2:5080/151)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
