Monthly Archives: Декабрь 2015

Циклический сдвиг по кругу

Рассмотрим, линейный массив:
line
По нему мы можем передвигаться вперед и назад, но не выходя за левую и правую границы.
Данный массив можно закольцевать. Допустим, у нас есть массив, состоящий из элементов пронумерованных следующим образом: 0 1 2 3 4, мы находимся в позиции с индексом 3 и нам нужно сместиться на три позиции вправо. Наши действия:

  1. Перемещаемся вправо на 4-ю позицию;
  2. Пытаемся переместиться вправо на 5-ю позиции, но ее — нет. Перескакиваем на началом массива в 0-ю позицию;
  3. Перемещаемся вправо на 1-ю позицию. В итоге мы оказались на 1-й позиции.

Теперь рассмотрим обратную ситуацию. Мы в позиции с индекcом 1 и нужно сместиться на три позиции влево:

  1. Перемещаеся влево на 0-ю позицию;
  2. Пытаемся переместиться влево на -1-ю позицию, которой нет, поэтому перемещаемся в конец массива на позицию с индексом 4.
  3. Перемещаемся влево на 3-ю позицию. В итоге оказываемся на 3-й позиции.

circle
Реализация смещения вправо:

int[] arr = new int[]{10, 20, 30, 40, 50};
int index = 3;
System.out.println("index = " + index);//Вывод: 3
System.out.println("value = " + arr[index]);//Вывод: 40
int step = 3;
int newIndex = (index + step) % arr.length;
System.out.println("newIndex = " + newIndex);//Вывод: 1
System.out.println("value = " + arr[newIndex]);//Вывод: 20

Реализация смещения влево:

int[] arr = new int[]{10, 20, 30, 40, 50};
int index = 1;
System.out.println("index = " + index);//Вывод: 1
System.out.println("value = " + arr[index]);//Вывод: 20
int step = 13;
int newIndex = (arr.length + (index - step) % arr.length) % arr.length;
System.out.println("newIndex = " + newIndex);//Вывод: 3
System.out.println("value = " + arr[newIndex]);//Вывод: 40

Зацикливание массива реализовано с помощью операции взятия остатка от деления %, это позволяет исключить полностью завершенные циклы.