Функция циклического сдвига

сб, 10/11/2014 - 16:36 — tech

Задача:

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

Например, дан массив:
1 2 3 4 5 6
Кольцевой сдвиг вправо на 2 единицы:
5 6 1 2 3 4

Описание переменных:

a, m - массив (m - в функции);
q, p - количество единичных сдвигов (p - в функции);
b - переменная для хранения первого или последнего элемента массива.

Алгоритм решения задачи:

Если переменной p будет присвоено отрицательное значение, то пусть сдвиг будет выполняться влево. Если положительное, то вправо.

Абсолютное значение переменной p - это количество шагов сдвига. Если за одну итерацию внешнего цикла выполняется сдвиг на один шаг, то значение p определяет количество итераций внешнего цикла.

Далее идет описание одного шага внешнего цикла:

Если сдвиг происходит влево, то на место первого элемента становится второй, на место второго - третий и так далее. При кольцевом сдвиге на место последнего должен стать первый. Так как на место очередного элемента записывается следующий за ним, то первый элемент затрется. Поэтому его надо сохранить отдельно до выполнения внутреннего цикла. Внутренний цикл выполняется до предпоследнего элемента включительно. На предпоследнем элементе на его место записывается последний. После внутреннего цикла на место последнего элемента записывается ранее сохраненный первый элемент.

Если же сдвиг происходит вправо, то первый элемент уйдет на место второго, второй сдвинется на место третьего и т. д. В данном случае, чтобы не затирать элементы, лучше сдвигать с конца. На место последнего записать предпоследний, потом на место предпоследнего - тот что перед ним и т.д. В таком случае затирается только последний элемент, его следует сохранить до выполнения внутреннего цикла. Цикл будет выполняться от последнего элемента до второго. На последней итерации внутреннего цикла на место второго элемента запишется первый элемент. После цикла следует на место первого элемента записать ранее сохраненный последний.

Программа на языке Паскаль:

const N = 10;
type
    arr = array[1..N] of integer;
var
    a: arr;
    i,j: byte;
    q: integer;
procedure shift(var m: arr; p: integer);
    var b: integer;
    begin
        if p then 
            for j:=1 to abs(p) do begin
                b := m[1];
                for i:=1 to N-1 do 
                    m[i] := m[i+1];
                m[N] := b;
            end
        else 
            for j:=1 to p do begin
                b := m[N];
                for i:=N downto 2 do 
                    m[i] := m[i-1];
                m[1] := b;
            end;
    end;
begin
    for i:=1 to N do begin
        a[i] := i;
        write(a[i],' ');
    end;
    writeln;
    readln(q);
    shift(a,q);
    for i:=1 to N do 
        write(a[i],' ');
    writeln;
end.

Примеры выполнения программы:

1 2 3 4 5 6 7 8 9 10 
-3
4 5 6 7 8 9 10 1 2 3

1 2 3 4 5 6 7 8 9 10 
4
7 8 9 10 1 2 3 4 5 6

Добавить комментарий

Язык Pascal. Программирование для начинающих

Решение задач

Программы

Функция циклического сдвига

Комментарии

я всё понял только запомнить

я тоже) спасибо за информацию

Лучше не запоминать, а самому

окей выложишь потом как

Учебник

Последние комментарии

Облако тегов