CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Динамическая очистка выпадающего списка (select) на javascript. (90721 hits)
#Сортировка выбором, общий подход. (72736 hits)
#Динамическое формирование выпадающего списка. (51789 hits)
#Создание простейшей таблицы. (37043 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (45719 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (100775 hits)
#Сапер. (53312 hits)
#Синус. (60630 hits)
#Вычисление медианы заданной выборки. (49142 hits)
#Валидация, динамическая проверка заполнения html форм. (209087 hits)
#Создание нестандартного (custom-ного) окна браузера. (35852 hits)
#Циклический сдвиг массива или строки - 3 уникальных алгоритма. (388820 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (38810 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (58451 hits)
#Двусторонняя карта. (33969 hits)
#Таймер. (40693 hits)
#Простой генератор случайных чисел. (133855 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (147171 hits)
#Хранение иерархических деревьев. (53222 hits)
#Вычисление среднего, среднего отклонения, среднеквадратического отклонения и дисперсии заданной выборки. (46352 hits)


Главная >> Каталог задач >> Последовательности >> Массивы >> Циклический сдвиг массива или строки - 3 уникальных алгоритма

Циклический сдвиг массива или строки - 3 уникальных алгоритма

Aвтор:
Дата:
Просмотров: 388819
реализации(C#: 3шт...) +добавить

Вступление

Циклический сдвиг массива влево - довольно понятная задача когда внутри массива из 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) Последовательный обмен на C#, code #64[автор:this]
2) Перестановка блоков на C#, code #69[автор:this]
3) Функцией переворота на C#, code #71[автор:this]