Организация и описание процессов обработки данных с помощью одномерных массивов и подпрограмм, страница 4

//Выполняет циклический сдвиг значений компонентов массива на p //позиций в заданном направлении: p > 0 – вправо, иначе влево.

var

  i: integer;

  b: boolean;

begin

  if p < 0 then b:= False else b:= True;

  p:= abs(p) mod (High(a) + 1);

  if b then

    for i:= 1 to p do shiftr(a)

  else for i:= 1 to p do shiftl(a)

end;

//-------------------------------------------------------------------------------

Если посмотреть внимательно, то сдвиг на k позиций значений компонентов массива вправо эквивалентен сдвигу на n – k позиций влево. В таком случае представленную выше процедуру можно упростить, как показано ниже.

//-------------------------------------------------------------------------------

procedure ShiftS(var a: array of real; p: integer);

//Выполняет циклический сдвиг значений компонентов массива на p //позиций в заданном направлении: p > 0 – вправо, иначе влево.

var

  i: integer;

  n: integer;//длина массива

  b: boolean;

begin

  n:= (High(a) + 1);

  if p < 0

    then p:= n – abs(p) mod n

    else p:= abs(p) mod n;

  for i:= 1 to p do shiftr(a)

end;

//-------------------------------------------------------------------------------

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

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

Давайте вычислим новые значения индекса для одномерного массива длиной 5 при циклическом сдвиге вправо на три позиции. Результат вычисления представлен ниже на рисунке.

Для реализации такого подхода нам понадобится процедура для обмена значениями двух переменных.

Реализация описанного выше алгоритма приведена ниже.

//-------------------------------------------------------------------------------------

procedure swap(var a,b: real);

//Осуществляет обмен значениями a, b.

var t: real;

begin

  t:= a;

  a:= b;

  b:= t;

end;

//-------------------------------------------------------------------------------------

procedure ShiftMp(var a: array of real; p: integer);

//Выполняет циклический сдвиг значений компонентов массива на p //позиций в заданном направлении: p > 0 – вправо, иначе влево.

var

  newi,n: integer;

  t: real;

begin

  n:= high(a) + 1;

  if p < 0 then p:= n + p mod n;//p < 0

  newi:= (low(a) + p) mod n;

  t:= a[low(a)];

  while newi <> 0 do begin

    swap(t,a[newi]);

    newi:= (newi + p) mod n;

  end;

  a[0]:= t;

end;

//-------------------------------------------------------------------------------------

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

Пример. Циклический сдвиг массива на одну позицию вправо.

З а д а ч а   № 10

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

Для упорядочения значений компонентов массива в порядке возрастания необходимо просмотреть массив, попарно сравнивая значения компонентов массива, и обменивать их значениями, если предыдущее значение больше последующего. При первом просмотре массива максимальное значение среди всех значений массива окажется в компоненте с максимальным значением индекса, индекс же будет изменяться от 0 до N – 2 (от первого до предпоследнего компонента). При следующем проходе максимальное из оставшихся N – 1 значений переместится на предпоследнее место, индекс же будет изменяться от 0 до N – 3 и т.д. Для просмотра значений компонентов массива воспользуемся двумя управляющими структурами FORDO, одна вложена в другую. Рисунок, иллюстрирующий алгоритм, представлен ниже.

Блок-схема решения представлена ниже на рисунке.

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

//-------------------------------------------------------------------------------------

procedure SortLR(var a: array of real);

//Осуществляет сортировку значений компонентов массива в возрастающем порядке.

var

  i,j,n: integer;

begin

  n:= high(a) + 1;

  for j:= n – 2 downto 0 do

  for i:= 0 to j do

     if a[i] > a[i + 1] then swap(a[i],a[i + 1]);

end;

//-------------------------------------------------------------------------------------