CodeLAB
на главную карта сайта обратная связь
каталог | задачи | паттерны | исходники | стат | форумы | ссылки
 гость
искать в
Главная >> Каталог задач >> Массивы >> Циклический сдвиг одномерного массива или строки, 3 уникальных алгоритма

<< назад
распечатать обсудить >>


Циклический сдвиг одномерного массива или строки, 3 уникальных алгоритма
реализации: C#, количество: 3

Aвтор: this
Дата: 04.06.2003
Просмотров: 226447
Рейтинг: 3/7,4.92(3081)
+
реализации(исходники) +добавить

Вступление

Задача циклического сдвига одномерного массива из n элементов на i позиций влево. Например, если n=8, a i=3, вектор "abcdefgh" должен будет превратиться в "defghabc". Дело в том, что алгоритм решения такой казалось бы ничем не выдающейся задачки играет большую роль, например, во всяческих различного рода текстовых редакторах, в каждом из которых сейчас уже обязательно присутствует такая возможность, как выделение мышкой текста и последующего его перемещения как есть в любое другое место редактируемого файла.

И вот если использовать очевидное решение в лоб: использовать n-элементный вспомогательный массив и сделав n шагов завершить всю перестановку - мы натыкаемся на дополнительный расход памяти, пропорционально растущий от объема этого выделенного, перемещаемого текста. Представьте себе, если выделяется текст большого объема, например, в миллион символов и перемещается. В этом случае весь этот миллион символов(байт) - а это уже мегабайт, будет занимать ценное место в оперативной памяти.

Поэтому было бы неплохо найти решение, которое осуществляло бы эту перестановку без дополнительного расхода памяти, по-крайней мере, чтобы этот расход не рос пропорционально объему сдвигаемого фрагмента.

И такое решение существует, а точнее даже целых 3 интересных и проверенных опытом алгоритма, которые позволяют обойтись лишь несколькими дополнительными переменными и завершить весь сдвиг не за n шагов, а всего лишь за время, пропорциональное n.

По книге Джона Бентли:
"Жемчужины программирования"

"... В некоторых языках программирования операция циклическо­го сдвига является элементарной (то есть выполняется одним оператором). Для нас важно, что циклический сдвиг соответствует обмену соседних блоков памяти разного размера: при перемещении фрагмента текста с помощью мыши из одного места файла в другое осуществляется именно эта операция. Ограничения по времени и объему памяти существенны для многих подобных приложений.

Можно попытаться решить задачу, копируя первые i элементов массива х во временный массив, сдвигая оставшиеся n-i элементов влево на i позиций, а затем копируя данные из временного массива обратно в основной массив на последние i позиций. Однако данная схема использует i дополнительных переменных, что требует дополнительной памяти. Другой подход заключается в том, чтобы определить функцию, сдвигающую массив влево на один элемент (за время, пропорциональное n), а потом вызывать ее i раз, но такой алгоритм будет отнимать слишком много времени.

Алгоритм #1: последовательный обмен

Решение проблемы с указанными ограничениями на использование ресурсов потребует написания более сложной программы. Одним из вариантов решения будет введение дополнительной переменной. Элемент х[0] помещается во временную переменную t, затем x[i] помещается в x[0],x[2*i] — в х[1] и так далее (перебираются все элементы массива х с индексом по модулю n), пока мы не возвращаемся к элементу х [0], вместо которого записывается содержимое переменной t, после чего процесс завершается. Если i = 3, а n = 12, этот этап проходит следующим образом (рис. 2.2):

Если при этом не были переставлены все имеющиеся элементы, процедура повторяется, начиная с х[1] и так далее, до достижения конечного результата:

 псевдокод: циклический сдвиг фрагмента массива  ссылка
  1. /* Сдвигаем массив x[0..n]
  2. * на rotdist позиций влево
  3. */
  4.  
  5.  
  6. /* gcd - наибольший общий делитель
  7. * между n и rotdist
  8. */
  9. for i = 0 to gcd
  10. t = x[i]
  11. j = i
  12. while
  13. k = j + rotdist
  14.  
  15. if k >= n
  16. k -= n
  17.  
  18. if k == i
  19. break
  20.  
  21. x[j] = x[k]
  22. j = k
  23. x[j] = t

 

Алгоритм #2: перестановка блоков

Можно предложить и другой алгоритм, который возникает из рассмотрения задачи с другой точки зрения. Циклический сдвиг массива х сводится фактически к замене ab на bа, где а — первые i элементов х, a b — оставшиеся элементы. Предположим, что а короче b. Разобьем b на bleft и bright, где bright содержит i элементов (столько же, сколько и а). Поменяем местами а и bright, получим brightbleftа. При этом а окажется в конце массива — там, где и полагается. Поэтому можно сосредоточиться на перестановке bright и bleft. Эта задача сводится к начальной, поэтому алгоритм можно вызывать рекурсивно. Программа, реализующая этот алгоритм, будет достаточно красивой , но она требует аккуратного написания кода, а оценить ее эффективность непросто:

 псевдокод: сдвиг через перестановку блоков  ссылка
  1. /* Функция swap(a, b, m) меняем местами:
  2. * x[a..a+m-1] и x[b..b+m-1]
  3. */
  4.  
  5. if rotdist == 0 || rotdist == n
  6. exit
  7.  
  8. i = p = rotdist
  9. j = n - p
  10. while i != j
  11. /* инвариант:
  12. x[0..p-i] двигать не нужно
  13. x[p-i..p-1] = a (нужно поменять с b)
  14. x[p..p+j-1] = b (нужно поменять с a)
  15. x[p+j..n-1] двигать не нужно */
  16.  
  17. if i > j
  18. swap(p-i, p, j)
  19. i -= j
  20. else
  21. swap(p-i, p+j-i, i)
  22. j -= i
  23. swap(p-i, p, i)

 

Алгоритм #3: переворотами

Задача кажется сложной, пока вас не осенит озарение («ага!»): итак, нужно преобразовать массив ab в bа. Предположим, что у нас есть функция reverse, переставляющая элементы некоторой части массива в противоположном порядке. В исходном состоянии массив имеет вид ab. Вызвав эту функцию для первой части, получим аrb (прим. редактора:аr - это модифицированная часть a, к которой применили фукнцию перестановки reverse). Затем вызовем ее для второй части: получим аrbr. Затем вызовем функцию для всего массива, что даст (аrbr)r, а это в точности соответствует bа. Посмотрим, как будет такая функция действовать на массив abcdefgh, который нужно сдвинуть влево на три элемента:

 псевдокод: Сдвиг через функцию перестановки reverse  ссылка
  1. reverse(0, i-1) /* cba|defgh */
  2. reverse(i, n-1) /* cba|hgfed */
  3. reverse(0, n-1) /* defgh|abc */


Дуг Макилрой (Doug Mcllroy) предложил наглядную иллюстрацию циклического сдвига массива из десяти элементов вверх на пять позиций (рис. 2.3); начальное положение: обе руки ладонями к себе, левая над правой:

Код, использующий функцию переворота, оказывается эффективным и малотребовательным к памяти, и настолько короток и прост, что при его реализации сложно ошибиться.

Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения строк в текстовом редакторе в своей книге (В. Kernighan, P. J. Plauger, Software Tools in Pascal, 1981). Керниган пишет, что эта функция заработала правильно с первого же запуска, тогда как их предыдущая версия, использовавшая связный список, содержала несколько ошибок. Этот же код используется в некоторых текстовых редакторах, включая тот, в котором я впервые набрал настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.

..."



Реализации: C#(3)   +добавить реализацию

1) Последовательный обмен, code #64[автор:this]
2) Перестановка блоков, code #69[автор:this]
3) Функцией переворота, code #71[автор:this]


<< назад наверх
распечатать обсудить >>

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.025398 секунд
Количество запросов к БД: 14, gzip: 13.9kb/55.4kb(75%)