Циклический сдвиг массива влево

Циклический сдвиг массива влево

Под циклическим сдвигом понимается перестановка значений всех элементов массива на одну или несколько позиций влево или вправо. При этом значение первого (последнего) элемента массива заносится в последний (первый) элемент массива в зависимости от направления сдвига.

Схематичное изображение циклического сдвига элементов массива вправо на одну позицию, выполняемого в три этапа, показано на рис. 5.4.1. Блок-схема алгоритма, выполняющего такой сдвиг, показана на рис. 5.4.2.

На 1-м этапе значение последнего элемента массива XN заносится в дополнительную переменную А (блок 1). На 2-м этапе организовывается цикл «Для» на основе блока модификации (блок 2), который перебирает элементы массива Х в обратном порядке, т.е. с правого края (шаг -1), начиная с N-го и заканчивая 2-м элементом. На каждом шаге цикла текущему элементу Xi присваивается значение предыдущего элемента Xi-1 (блок 3). В результате выполнения 2-го этапа значение предварительно сохраненного последнего элемента массива будет удалено. Значения остальных элементов массива будут смещены на одну позицию вправо. Значение первого элемента массива будет продублировано во втором элементе. На 3-м этапе алгоритма значение дополнительной переменной А, в которой хранится последний элемент исходного массива, будет занесено в первый элемент массива X1. В итоге будет выполнен циклический сдвиг элементов массива Х на одну позицию вправо.

Следует обратить внимание на граничные значения параметра цикла i, который изменяется от N до 2. При подстановке этих значений в формулу сдвига не должно происходить обращение к несуществующим элементам массива. При i =N формула сдвига принимает вид XN =XN 1, при i =2 – X2 =X1. В случае если бы правая граница параметра i была равна 1, то в формуле сдвига происходило бы обращение к несуществующему элементу массива с индексом 0: X1=X, что недопустимо.

Схематичное изображение циклического сдвига элементов массива влево на одну позицию, также выполняемого в три этапа, показано на рис. 5.4.3. Блок-схема алгоритма, выполняющего такой сдвиг, показана на рис. 5.4.4.

На 1-м этапе значение первого элемента массива X1 заносится в дополнительную переменную А (блок 1). На 2-м этапе организовывается цикл «Для» (блок 2), который перебирает элементы массива Х в прямом порядке, т.е. с левого края (шаг +1), начиная с 1-го и заканчивая N-1-м элементом. На каждом шаге цикла текущему элементу Xi присваивается значение последующего элемента массива Xi+1 (блок 3). В результате выполнения 2-го этапа значение предварительно сохраненного первого элемента массива будет удалено. Значения остальных элементов массива будут смещены на одну позицию влево. Значение последнего элемента массива будет продублировано в предпоследнем элементе. На 3-м этапе алгоритма значение дополнительной переменной А, в которой хранится первый элемент исходного массива, будет занесено в последний элемент массива XN. В итоге будет выполнен циклический сдвиг элементов массива Х на одну позицию влево.

Читайте также:  Двач нет звука в webm

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

Сдвиг элементов массива находит применение при удалении или добавлении элементов в массив, а также в других задачах.

Не нашли то, что искали? Воспользуйтесь поиском:

Задача

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

Например, дан массив:
1 2 3 4 5 6
Кольцевой сдвиг вправо на 2 единицы:
5 6 1 2 3 4

Решение

  • a, m — массив (m — в функции);
  • q, p — количество единичных сдвигов (p — в функции);
  • b — переменная для хранения первого или последнего элемента массива.

Алгоритм решения задачи:

Если переменной p будет присвоено отрицательное значение, то пусть сдвиг будет выполняться влево. Если положительное, то вправо.

Абсолютное значение переменной p — это количество шагов сдвига. Если за одну итерацию внешнего цикла выполняется сдвиг на один шаг, то значение p определяет количество итераций внешнего цикла.

Далее идет описание одного шага внешнего цикла:

Если сдвиг происходит влево, то на место первого элемента становится второй, на место второго — третий и так далее. При кольцевом сдвиге на место последнего должен стать первый. Так как на место очередного элемента записывается следующий за ним, то первый элемент затрется. Поэтому его надо сохранить отдельно до выполнения внутреннего цикла. Внутренний цикл выполняется до предпоследнего элемента включительно. На предпоследнем элементе на его место записывается последний. После внутреннего цикла на место последнего элемента записывается ранее сохраненный первый элемент.

Если же сдвиг происходит вправо, то первый элемент уйдет на место второго, второй сдвинется на место третьего и т. д. В данном случае, чтобы не затирать элементы, лучше сдвигать с конца. На место последнего записать предпоследний, потом на место предпоследнего — тот что перед ним и т.д. В таком случае затирается только последний элемент, его следует сохранить до выполнения внутреннего цикла. Цикл будет выполняться от последнего элемента до второго. На последней итерации внутреннего цикла на место второго элемента запишется первый элемент. После цикла следует на место первого элемента записать ранее сохраненный последний.

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

Читайте также:  Как пользоваться morphvox pro в скайпе

И вот если использовать очевидное решение в лоб: использовать 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] и так далее, до достижения конечного результата:

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

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

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

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

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

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

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

Ссылка на основную публикацию
Функция датазнач в excel
Возвращает числовой формат даты, представленной в виде текста. Функция ДАТАЗНАЧ используется для преобразования даты из текстового представления в числовой формат....
Файловый менеджер для ubuntu server
Работа с файлами в операционной системе Ubuntu осуществляется через соответствующий менеджер. Все дистрибутивы, разработанные на ядре Linux, позволяют юзеру всячески...
Файлы dll чем открыть
Файлы формата DLL открываются специальными программами. Существует 2 типа форматов DLL, каждый из которых открывается разными программами. Чтобы открыть нужный...
Функция если ячейка содержит определенный текст
Функция ЕСЛИ СОДЕРЖИТ Наверное, многие задавались вопросом, как найти функцию в EXCEL«СОДЕРЖИТ» , чтобы применить какое-либо условие, в зависимости от...
Adblock detector