Что такое циклический сдвиг

Циклический сдвиг

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

Решение задачи на языке программирования Python

Для решения этой задачи можно воспользоваться следующими методами списка:

• append — добавляет элемент в конец списка,
• insert — вставляет элемент по указанному индексу,
• pop — извлекает элемент с конца списка или, если был передан индекс, по индексу.

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

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

def shift(lst, steps): if steps  0: steps = abs(steps) for i in range(steps): lst.append(lst.pop(0)) else: for i in range(steps): lst.insert(0, lst.pop()) nums = [4, 5, 6, 7, 8, 9, 0] print(nums) shift(nums, -2) print(nums) shift(nums, 3) print(nums)

[4, 5, 6, 7, 8, 9, 0] [6, 7, 8, 9, 0, 4, 5] [0, 4, 5, 6, 7, 8, 9]

/dev/energy

Сайт о том, как стать программистом и как с этим жить потом

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

Не так давно стартовал очередной курс Java на одном небезызвестном образовательном портале. И вот, моим студентам досталась задача по работе с массивами. Статья в первую очередь для них, но и для интересующихся, конечно же �� Отдельное спасибо alexandr.baykov@gmail.com за комментарий по поводу массива с чётным количеством элементов и чётным размером сдвига. Я переписал алгоритм и обновил статью.

Итак, задача сформулирована следующим образом

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

Усложняющее условие было введено потому, что можно решить задачу при помощи разделения массивов. В таком случае решение состоит в том, чтобы «отрезать» от массива кусок длиной n справа или слева (в зависимости от того, как n сравнивается с 0) и «прикрепить» отрезанную часть обратно с другой стороны. Это довольно дешёвый алгоритм, который имеет сложность O(n), но он будет требовать дополнительной памяти для хранения временного массива размера n. Поскольку такое решение самое простое, да и не особенно подходит под условие задачи, то мы перейдём сразу к более сложной алгоритмизации.

Разумеется, после первых подходов многие студенты находят следующее довольно логичное и вполне корректное решение. Оно весьма популярно на различных сайтах, описывающих циклический сдвиг. Суть его в том, что любой сдвиг можно представить в качестве n сдвигов на 1 ячейку. Сдвиг на 1 ячейку довольно просто реализуется циклом. В итоге, если изобразить это Java-методом, получается примерно такой метод:

public static int[] shiftArray(int[] incomingArray, int shift) < if(shift != 0)< // Любой сдвиг больше длины массива можно оптимизировать до меньшего сдвига // через деление по модулю int finalShift; if (shift >incomingArray.length) < shift = Math.abs(shift % incomingArray.length); >else < finalShift = shift; >// в зависимости от знака сдвига движение будет происходить // слева направо при положительном сдвиге // справа налево при отрицательном if (shift > 0) < for (int n = 0; n < shift; n++) < // убираем первый элемент в буфер, а на его место ставим хвостовой элемент int buffer = incomingArray[0]; incomingArray[0] = incomingArray[incomingArray.length - 1]; // циклично сдвигаем весь массив for (int j = 1; j < incomingArray.length - 1; j++) < incomingArray[incomingArray.length - j] = incomingArray[incomingArray.length - j - 1]; >// ставим буферный элемент в 1 ячейку incomingArray[1] = buffer; > > else if (shift < 0) < for (int i = 0; i >shift; i--) < int buffer = incomingArray[incomingArray.length - 1]; incomingArray[incomingArray.length - 1] = incomingArray[0]; for (int j = 1; j < incomingArray.length - 1; j++) < incomingArray[j - 1] = incomingArray[j]; >incomingArray[incomingArray.length - 2] = buffer; > > > return incomingArray; >

Хочу отметить, что такое решение имеет место, и оно применимо. Но мы же решаем алгоритмическую задачу, поэтому неплохо бы поговорить о том, какую сложность будет иметь приведенный алгоритм. Если опустить процесс вычислений буферных элементов и обмена ими между ячейками, то сложность алгоритма сводится к O(N * M), где N — размер входного массива, а M — величина сдвига. Очевидно, что для |M| = 1 (т.е. M = -1 или M = 1) сложность снизится до O(N). Это частный случай.

Теперь давайте подумаем, что же тут не так. На самом деле, если мы знаем величину сдвига (а мы её знаем), то вполне можно вычислить, какой элемент будет следующим. Это говорит о том, что можно создать жонглирующий алгоритм следующего вида:

1. Получаем нулевой элемент и кладем его в буфер
2. Начинаем цикл от 0 до длины массива включительно (это обусловлено тем, что в момент, когда мы дойдём до последнего элемента, он будет помещен в буфер, из которого его надо восстановить на месте нулевого элемента, чем полностью закольцевать сдвиг)
3. Дальше мы меняем местами элементы, исходя из размера шага. Например, для шага 3 и массива длиной 7 мы сначала поменяем элементы 0, 3, 6. Затем — 1, 4, 2. И так далее.

Если рассмотреть наборы изменяемых элементов, то мы увидим, что количество таких наборов, внутри которых мы будем итеративно менять местами элементы, будет равно наименьшему общему делителю для размера массива и размера сдвига. К примеру, для массива из 12 элементов при сдвиге 3 мы будем иметь три набора смещаемых элементов

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 - 1, 4, 7, 10 - 2, 5, 8, 11 - 3, 6, 9, 12 4 5 6 7 8 9 10 11 12 1 2 3

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

В реализации нужно учитывать и то, что сдвиг может идти как влево, так и вправо.

Теперь мы можем написать реализацию нашего алгоритма

public class moves < public static void main(String[] args)< int[] in1 = ; int[] out1 = moves(in1, -2); printOut(out1); int[] in2 = ; int[] out2 = moves(in2, 2); printOut(out2); int[] in3 = ; int[] out3 = moves(in3, 5); printOut(out3); int[] in4 = ; int[] out4 = moves(in4, 0); printOut(out4); > /** * Main method, shifts array * @param incoming - user array * @param delta - shift value * @return int[] result array */ static int[] moves(int[] incoming, int delta) < int currentIndex, movedIndex, buffer; for (int i = 0; i < greatestCommonDivisor(delta, incoming.length); i++) < buffer = incoming[i]; currentIndex = i; if(delta >0)< while (true) < movedIndex = currentIndex + delta; if (movedIndex >= incoming.length) movedIndex = movedIndex - incoming.length; if (movedIndex == i) break; incoming[currentIndex] = incoming[movedIndex]; currentIndex = movedIndex; > > else if(delta < 0)< while (true) < movedIndex = currentIndex + delta; if (movedIndex < 0) movedIndex = incoming.length + movedIndex; if (movedIndex == i) break; incoming[currentIndex] = incoming[movedIndex]; currentIndex = movedIndex; >> incoming[currentIndex] = buffer; > return incoming; > /** * Simple printout * @param incoming Array user array */ public static void printOut(int[] incomingArray) < for(int item: incomingArray)< System.out.print(item + " "); >System.out.println(); > /** * Finding the GCD in recoursive function * @param a - first element * @param b - second element * @return int GCD */ static int greatestCommonDivisor(int a, int b) < if (b == 0) return a; else return greatestCommonDivisor(b, a % b); >>

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

Надеюсь, приведенные измышления будут для Вас полезны. Буду рад критике и комментариям!

Дочитавшим до конца, картинка де мотиватор ��

Циклический сдвиг в массиве : 2 комментария

Александр :

Данное решение не работает, если длина массива четная и delta тоже четное число.
На вход подан массив
int[] in =
int[] out3 = moves(in, 6);
printOut(out3); — выводит 45 3 5 2 7 13 5 43 42 46 если delta = 2, вывод — 42 3 5 2 5 13 7 43 9 46

Что такое циклический сдвиг

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

псевдокод: массив циклический сдвиг ссылка

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

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

псевдокод: массив, циклический сдвиг через перестановку блоков ссылка

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

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

псевдокод: Сдвиг через функцию перестановки reverse ссылка

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

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

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

Справочное руководство > Язык CFD > Побитовые логические операции > Циклический сдвиг вправо

Циклический сдвиг вправо. Устанавливает на выходе результат операции логического сдвига вправо двоичного представления значения входа «Значение», на число бит, заданное значением входа «Сдвиг, бит», при этом сдвиге уходящий бит появляется на месте появившегося свободного на другом конце числа.

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

 Значение = 51001 = 0xC739 = 0b1100011100111001 Сдвиг, бит = 2 Результат = 29134 = 0x71CE = 0b0111000111001110 

Особенности

Операция циклического сдвига 16-и битного значения в любую сторону на 8 бит меняет местами его старший и младший байты.

Примеры

Циклический сдвиг на 8 бит — обмен местами старшего и младшего байта:

СМОТРИ ТАКЖЕ

• Побитовое И
• Побитовое ИЛИ
• Побитовое НЕ
• Побитовое исключающее ИЛИ
• Сдвиг влево
• Сдвиг вправо
• Циклический сдвиг влево