Алгоритмы обработки строк и массивов — практическая работа (9/21)

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

Выполните циклический сдвиг массива вправо на k позиций и сравните два алгоритма.

Лаборатория

1. Если массив пуст, верните пустой результат; иначе вычислите k := k mod n.
2. Разверните весь диапазон 0…n−1.
3. Разверните диапазоны 0…k−1 и k…n−1.
4. Сравните результат с k-кратным сдвигом на одну позицию.
5. Проверьте n=0, n=1, k=0, k=n и k>n.

Метод трёх разворотов выполняет O(n) операций и использует O(1) дополнительной памяти.

Выходной билет

[4,9,1,3,6], k=2 → [3,6,4,9,1].

Pascal

Реализуйте процедуру ReverseRange(var a; left, right) и вызовите её три раза.