Лічильник
Сьогодні Разом
Відвідувань 294 5264128
Авторізацій 57 421555
Користувачів 30 2709
Статья

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


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

Циклический сдвиг используется в битовых операциях с числом.

Большинство компьютеров не могут напрямую адресовать биты, которые содержатся группами по 8, 16, 32 или 64 битов в словах. Для обеспечения работы с битами существует множество машинных инструкций, включающие различные типы сдвигов. Все сдвиги похожи друг на друга поведением средних битов, которые просто сдвигаются влево или вправо на определённую величину. Однако, поведение крайних битов, которые уходят из слова и которые появляются в слове, зависит от типа сдвига. (wiki)

Рассмотрим два случая: циклический сдвиг влево и вправо на один элемент.

23. Циклический сдвиг влево на один элемент


1. Запоминаем во временной переменной первый элемент массива
2. Начиная со второго элемента и до последнего текущий элемент массива копируем в предыдущий элемент
3. В последний элемент массива записываем значение, сохраненное во временной переменной

Фрагмент программы, выполняющий циклический сдвиг влево на один элемент приведен ниже:
 temp := a[1];
 for i := 2 to n do
  a[i - 1] := a[i];
 a[n] := temp;
Переменная temp - временно хранит первый элемент массива, пока остальные элементы смещаются на один влево.

24. Циклический сдвиг вправо на один элемент


1. Запоминаем во временной переменной последний элемент массива
2. Начиная с последнего элемента и до второго предыдущий элемент массива копируем в текущий элемент
3. В первый элемент массива записываем значение, сохраненное во временной переменной

Фрагмент программы, выполняющий циклический сдвиг вправо на один элемент приведен ниже:
 temp := a[n];
 for i := n downto 2 do
  a[i] := a[i - 1];
 a[1] := temp;
Переменная temp - временно хранит последний элемент массива, пока остальные элементы смещаются на один вправо.

25. Циклический сдвиг на несколько элементов


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

Для примера рассмотрим задачу: Пусть задан массив на n элементов и выполнить циклический сдвиг его элементов влево пока первый элемент не станет равным нулю. Нулевой элемент обязательно существует.

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

Наиболее удачным выбором будет цикл while, так как прежде чем сдвигать, мы проверим значение первого элемента, и если он окажется равным нулю, то завершаем работу цикла:

 while a[1] <> 0 do
  begin
   <Циклический сдвиг влево на один элемент>
  end;
PS: Приведенный выше алгоритм справедлив только для случая, если нулевой элемент массива обязательно существует. В противном случае цикл будет выполняться бесконечно.