Условие: Номер 19

Задача 19. Дан массив X[1..N]. Необходимо циклически сдвинуть его на k элементов вправо (т.е. элемент X[i] после сдвига должен стоять на месте X[i+k]; тут мы считаем что за X[N] следует X[1]). Разрешается использовать только несколько дополнительных слов памяти (Дополнительного массива заводить нельзя!).

  Решение задачи: Номер 19

Решение задачи 19. Пусть A - это k первых элементов массива X, а B - последних N-K. Нам необходимо из вектора AB получить вектор BA. Пусть у нас есть подпрограмма REVERRSE(I,j), которая реверсирует (меняет порядок элементов на обратный) часть массива x с индексами от i до j. Начав с массива AB реверсируем часть A, получаем (Ar)B; реверсируrем B, получаем (Ar)(Br); реверсируем весь массив, получаем((Ar)(Br))r =BA. Продемонстрируем описанный алгоритм на примере. Пусть X есть последовательность 1,2,3,4,5, k=3: REVERSE(1,K); {3,2,1,4,5} REVERSE(K+1,N); {3,2,1,5,4} REVERSE(1,K); {4,5,1,2,3}

Назад