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

Задача

 

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

Например, дан массив:
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 < 0 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

 

Тема

Процедуры, функции, рекурсии

Уровень

Сложные задачи

Комментарии

Я нашел еще способ, он более эффективный. И как люди докапались до этого? Я два дня сидел, рисовал кучу схем, и всегда не работало как надо.
Вот ссылка: math.msu.su/~vvb/1course/index.html#CyclicShiftKOrbits
Там выше описан и способ с инвертированием, правда все для Си, но главное алгоритм.

Вот я переписал для паскаля:
С инвертированием (сдвиг вправо):

{ 
  b - первый элемент
  e - последний элемент
 }
procedure invert(b,e:Integer;var a:Array of Integer) 
var i,j,tmp:Integer;
begin
    i := b; 
    j := e;
    while (i < j)
    begin
        tmp:= a[i];
        a[i] := a[j]; 
        a[j] := tmp;
        Inc(i);
        Dec(j);
    end;
end;
 
 
procedure shiftk(k:Integer; var a:Array of Integer;)
var n:Integer;
begin
    n:=High(a);
    if n <= 1 then
    begin     {Вырожденный случай}
        WriteLn('Неправильный размер массива');
        Exit;
    end;
 
    {Пользуясь периодичностью, приведем k
     к интервалу 0 <= k < n}
    k:= k mod n;
    if k < 0 then  { Сдвиг влево на k эквивалентен}
        Inc(k,n); { сдвигу вправо на n-k}
 
    invert(0, n-k-1, a);   { Инвертируем начало массива длины n-k}
    invert(n-k,  n-1, a); { Инвертируем конец массива длины k}
    invert(0, n-1);     { Инвертируем весь массив}
end;

А вот код для способа, на который я дал ссылку:

procedure shiftk(n,k:Integer; var a: Array of Integer);
begin
var i,j,d,x,l:Integer;
    k := k mod n;
    if (k == 0) then Exit;
    if (k < 0) then Inc(k,n);
    i := 0;     {индекс первого элемента текущей орбиты}
    d = gcd(n, k); {число орбит = НОД(n, k)}
    while (i < d)     { цикл для каждой орбиты}
    begin                 { i - первый элемент орбиты}
        j := i-k;       {  j - последний элемент орбиты}
        if (j < 0) then
            Inc(j,n);
        x := a[j];  // запомним значение последнего элемента
 
        while (j <> i)  { // цикл для каждого элемента j орбиты}
        begin
            l := j-k;    {   l - предыдущий элемент к j}
            if (l < 0) then
                Inc(l,n);
            a[j] := a[l]; //   копируем предыдущий элемент в текущий
            j := l;       //   переходим к предыдущему элементу
        end;
        a[i] := x; // копируем значение последнего элемента в первый
        Inc(i);
    end;
end;
 
function gcd(int x, int y) :Integer;
var r:Integer;
begin
    while (y != 0)
    begin
        r := x iv y;
        x := y; y := r;
    end;
    gcd := x;
end;

P.S: В коде могут быть очепятки - я пол года не писал на паскале ( забыть бы его совсем... но память хорошая).

Только сдвиг вправо и без процедуры - с функцией:-), кстати намного проще и можно вводить любые элементы и любое их количество в массиве:
program CiclSdvig;
var
 a:array[1..100]of integer;
 i,n,s:integer;
function CSdvig(var a:array[1..100]of integer;s:integer):array[1..100]of integer;
var k:integer;
begin
 k:=((s+n)mod n)+1;
 for i:=1 to n do
 begin
  result[k]:=a[i];
  k:=(k+1)mod n;
  if k=0 then k:=n;
 end;
end;
begin
 read(n,s);
 for i:=1 to n do read(a[i]);
 for i:=1 to n do write(a[i],' ');
 a:=CSdvig(a,s); writeln;
 for i:=1 to n do write(a[i],' ');
 writeln;
end.

Ответ на от Гость

Я забыл написать о выборе двух списков: Если сдвиг влево - то первый список - от начала до количества сдвигов включительно, второй - все остальное. Если вправо - наоборот.

И параметры функции: e - начальный элемент, s - конечный. Т.е. можно инвертировать списки, не создавая других массивов.

Ответ на от Гость

Спасибо. Тот вариант что в статье тривиален и неоптимален. Я делал почти то что и вы, но чего-то не выходило - я k не изменял в цикле. Но у вас второй массив, это существенное упрощение алгоритма. Мой препод придрался бы, типа память не экономно используется, он всегда говорит - "Вот будете программировать стиральную машинку... или холодильник... там память критична."

Вот алгоритм без массива:
Например надо сдвинуть влево на 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.

Я его не разрабатывал (а жаль). Не понимаю как, но он работает.
Как перевернуть массив(хотел на C, но сайт о паскале...):

procedure Inverse(arr:Array of Integer[]; s,e:Integer );
ns,c1,c2:Integer;
begin
   c1:=s;
   c2:=e;
   while(c1<c2)
   begin
      swap(c1,c2); { поменять местами элементы, не помню есть ли это в паскале }
      Inc(c1);
      Dec(c2);
   end;
end;

Пишется простая функция сдвига на на 1 шаг.
(Можно доработать до вправо-влево);
Вызывается s раз;

const n=12;
Type Tarray=array[1..n] of integer;
var
 a:Tarray;
 i,s:integer;
{===========================}
function Sdvig1(var a:Tarray):Tarray;
var j:integer;
begin
  for j:=1 to n-1 do  result[j]:=a[j+1];
  result[n]:=a[1];
end;
{------------}
procedure InitArray(var a:Tarray);
var j:integer;
begin
  for j:=1 to n do a[j]:=j;
end;
{------------}
procedure OutPutArray(var a:Tarray);
var j:integer;
begin
  writeln ('Массив имеет вид: ');
  for j:=1 to n do write(a[j],' ');
  writeln;
end;
{===========================}
begin
 InitArray(a);
 OutPutArray(a);
 write('На сколько сдвигать '); readln(s);
 for i:=1 to s do a:=Sdvig1(a);
 OutPutArray(a);
 writeln;
end.

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