Функция циклического сдвига
Написать функцию, которая циклически сдвигает одномерный массив вправо или влево на указанное число позиций. Сдвиг также должен быть кольцевым, то есть те элементы, которые уходят вправо или влево за пределы массива, должны помещаться с другого его конца.
Например, дан массив:
1 2 3 4 5 6
Кольцевой сдвиг вправо на 2 единицы:
5 6 1 2 3 4
Решение
Описание переменных:
- a , m — массив ( m — в процедуре);
- q , p — количество единичных сдвигов ( p — в процедуре);
- b — переменная для хранения первого или последнего элемента массива.
Алгоритм решения задачи:
Если переменной p будет присвоено отрицательное значение, то пусть сдвиг будет выполняться влево. Если положительное, то вправо.
Абсолютное значение переменной p — это количество шагов сдвига. Если за одну итерацию внешнего цикла выполняется сдвиг на один шаг, то значение p определяет количество итераций внешнего цикла.
Далее идет описание одного шага внешнего цикла.
Если сдвиг происходит влево, то на место первого элемента становится второй, на место второго — третий и так далее. При кольцевом сдвиге на место последнего должен стать первый. Так как на место очередного элемента записывается следующий за ним, то первый элемент затрется. Поэтому его надо сохранить отдельно до выполнения внутреннего цикла. Внутренний цикл выполняется до предпоследнего элемента включительно. На предпоследнем элементе на его место записывается последний. После внутреннего цикла на место последнего элемента записывается ранее сохраненный первый элемент.
Если же сдвиг происходит вправо, то первый элемент уйдет на место второго, второй сдвинется на место третьего и так далее. В данном случае, чтобы не затирать элементы, лучше сдвигать с конца. На место последнего записать предпоследний, потом на место предпоследнего — тот что перед ним. В таком случае затирается только последний элемент, его следует сохранить до выполнения внутреннего цикла. Цикл будет выполняться от последнего элемента до второго. На последней итерации внутреннего цикла на место второго элемента запишется первый элемент. После цикла следует на место первого элемента записать ранее сохраненный последний.
Программа на языке Паскаль:
Примеры выполнения программы:
Описанный выше алгоритм проще для понимания, но не является оптимальным. Существуют другие алгоритмы сдвига. Например:
Надо сдвинуть влево на 3 элемента массив: 1 2 3 4 5 6 7 8
Выделяем два подсписка: (1 2 3)(4 5 6 7 8)
Переворачиваем списки: (3 2 1)(8 7 6 5 4).
Переворачиваем весь массив: 4 5 6 7 8 1 2 3
Циклический сдвиг массива
Например, нужно осуществить циклический сдвиг вправо на n элементов. А как осуществить циклический сдвиг вправо на -n элементов? Каким получится массив?
Напишите просто какой правильный ответ: Массив — 1 2 3 4 5 Сдвинуть вправо на -2 (отрицательное число)
Правильным будет ответ 3 4 5 1 2 или 3 4 5 2 1 ?
Правильным будет ответ 3 4 5 1 2
update
Циклический сдвиг вправо на -2 это то же самое, что и циклический сдвиг влево на 2.
Есть удивительный по своей простоте алгоритм из трех reverse(array, size) для циклического сдвига влево, который легко запомнить и в реализации которого практически невозможно ошибиться.
Вот как он работает с 12345 (s[] = 12345, size = 5, dist = 2)
Пишут, что Кен Томпсон (Ken Thompson) написал редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.
Напишите программу, которая выполняет циклический сдвиг части массива, начиная с элемента с номером K и заканчивая элементом с н
Прямоугольник х1, у1, х2, у2 — нарисовать прямоугольник, где (x1, у1) — координаты левого верхнего, а (х2, у2) — правого нижнего угла этого прямоугольника.
По имеющимся описаниям восстановите рисунки.
Установить 60, 20
Прямоугольник 60, 80, 100, 60
Прямоугольник 100, 120, 150, 60
Окружность 140, 40, 10
Установить 20, 50 Линия к 40, 70 Линия к 50, 70 Линия к 90, 110 Линия к 120, 120 Линия к 110, 90 Линия к 70, 50 Линия к 70, 40 Линия к 50, 20 Линия к 50, 40 Линия к 40, 50 Линия к 20, 50 Окружность 80, 80, 10 Окружность 100, 100, 10
Установить 20, 80 Линия к 65, 110 Линия к 110, 80 Линия к 20, 80 Прямоугольник 20, 30, 110, 10 Прямоугольник 30, 80, 40, 30 Прямоугольник 50, 80, 60, 30 Прямоугольник 70, 80, 80, 30 Прямоугольник 90, 80, 100, 30
Установить 30, 40 Линия к 40, 10 Линия к 60, 10 Линия к 70, 40 Прямоугольник 20, 50, 80, 40 Установить 50, 50 Линия к 50, 80 Окружность 40, 80, 10 Окружность 60, 80, 10 Окружность 30, 100, 10 Окружность 50, 100, 10 Окружность 70, 100, 10 Окружность 40, 120, 10 Окружность 60, 120, 10