Циклический сдвиг

При Циклическом Сдвиге Влево каждый элемент в массиве становится на место своего соседа слева. Первый же элемент, которому двигаться некуда, займет место в хвосте массива, то есть из массива.

0

-6

13

3

8

-5

-1

7

получится массив

-6

13

3

8

-5

-1

7

0

Для реализации этого алгоритма нужно в первую очередь спасти первый элемент массива, записав его во вспомогательную ячейку через r:=a[1], потом переставить элементы

For i:=1 to N-1 Do a[i]:=a[i+1]

ИЛИ

For i:=2 to N Do a[i-1]:=a[i]

и, наконец, спасенное значение записать на место последнего элемента a[N]:= r. Тогда текст процедуры:

Имя файла: Sdvig_Lt.pas

Procedure Sdvig_Lt (Var aa:Massive);

Var ii: byte; rr: real;

Begin

rr:=aa[1];

For ii:=1 to n-1 do a[ii]:=aa[ii+1];

aa[n]:=rr;

End;

Если нужно несколько раз циклически сдвинуть массив, то эту процедуру ставят в цикл. Так, после выполнения оператора

For i:=1 to 3 do Sdvig_Lt (a);

из исходного массива будет получен массив

3

8

-5

-1

7

0

-6

13

При Циклическом Сдвиге Вправо массив

7

0

-6

13

3

8

-5

-1

получается из исходного чуть иным путем. Убедитесь самостоятельно, что алгоритм

r:=a[N];

For i:=2 to N do a[i]:=a[i-1];

a[N]:=r;

Не приводит к цели, а текст процедур должен иметь вид:

Имя файла: Sdvig_Rt.pas

Procedure Sdvig_Rt (Var aa:Massive);

Var ii: byte; rr: real;

Begin

rr:=aa[n];

For ii:=n downto 2 do a[ii]:=aa[ii-1];

aa[1]:=rr;

End;

Вычисление среднее арифметическое, среднее геометрическое, среднее квадратичное среднее гармоническое

Иногда в задачах требуется вычислить некоторые характеристики массива. Пусть b[i] – некоторыqмассив данных произвольного (но числового!) типа. Тогда для набораb[1],b[2],…,b[k] определены:

среднее арифметическое:

среднее геометрическое:

среднее квадратичное:

среднее гармоническое:

Замечание 1. Для вычисления среднего гармонического потребуется выполнение условия b[i]<>0.

Замечание 2.Для вычисления среднего геометрического необходимо, чтобы произведение, которое должно возводиться в степень 1/k, было положительно.

Сортировка массива

Сортировкой массива называется его упорядочивание по какому-либо принципу. Существуют разные способы сортировки: по убыванию, по возрастанию, по убыванию модулей, по возрастанию моделей, по уменьшению количества делителей (для целых чисел) и т.д.

Пример:

При сортировке исходный массив

0

-7

15

2

8

-5

-1

6

по возрастанию превратится в

-7

-5

-1

0

2

6

8

15

по убыванию превратится в

15

8

6

2

0

-1

-5

-7

Сортировка одномерного массива методом пузырька

Рассмотрим алгоритм сортировки методом пузырька (Метод назван "методом пузырька", потому что большие элементы, подобно пузырькам, "всплывают" на соответствующую позицию в противоположность "методу погружения" (т. е. методу простых вставок), в котором элементы погружаются на соответствующий уровень. Метод пузырька известен также под более прозаическими именами, такими, как "обменная сортировка с выбором" или метод "распространения".) на следующем примере:

На занятии по физкультуре присутствовала 1 группа, состоящая из 5 студентов. Преподаватель по физкультуре в начале занятия должен их расставить по росту (т.е. – по его убыванию). Определим следующий алгоритм:

1. Преподаватель двигается вдоль шеренги слева направо.

2. Если левый студент в паре, ниже правого, преподаватель меняет их местами и переходит к следующей паре.

Рассмотрим в качестве примера массив

1

2

3

4

5

И разработаем алгоритм для обработки такого массива, тем более он подойдет и для массива, где ряд элементов уже стоит на своих местах

1	2	3	4	5	Массив перед сортировкой
2	1				1-ый проход вдоль шеренги преподавателя (k=1)
	3	1
		4	1		Номер левого элемента в паре меняется
			5	1	от 1-го до 4-го (i=1..4)
2	3	4	5	1	Массив после 1-го прохода. Один элемент занял свое место
3	2
	4	2			2-ой проход вдоль шеренги преподавателя физкультуры
		5	2		k=2, i=1..3
3	4	5	2	1	Массив после второго прохода. Два элемента заняли свои места
4	3
	5	3			3-ий проход (k=3, i=1..2)
4	5	3	2	1	Массив после 3-го прохода.
5	4				4-ый проход (k=4, i=1)
5	4	3	2	1	Сортировка массива завершена.

Для 5-ти элементов массива понадобилось четыре прохода (т.е. N-1). При этом номер левого элемента в пара от прохода к проходу менялся от 1 доN-K(где К –номер прохода). Исходя, из этого напишем текст процедуры сортировки массива по убыванию элементов:

(Имя файлa: Sort_Dec.pas)

Procedure Sort_Dec(Var aa:Massive);

Var ii,kk:byte;

Begin

For kk:=1 to n-1 Do Begin

For ii:=1 to n-kk Do Begin

If (aa[ii]<aa[ii+1]) Then Begin

Swap (aa[ii],a[ii+1]);

End;

End;

End;

End;

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

Сортировка пузырьком

Примечание. Этот вид сортировки отличается от обменной тем, что за каждый проход большого цикла захватывается различное количество элементов массива, на каждом шаге более тяжелые опускаются на одну позицию вниз, а более легкие поднимаются на одну позицию вверх. Собственно тоже самое происходит и в обменной сортировке, но там на каждом шаге большого внешнего цикла обработке подвергается весь массив. Трудоемкость пузырьковой сортировки ограничена числом N*(N-1)/2. Пузырьковая сортировка обладает свойством устойчивости.

Program Z;

uses crt;

var a:array[1..100] of integer;

i,j,n,c:integer;

begin

clrscr;

write('количество элементов массива ');

read(n);

for i:=1 to n do read(a[i]);

for i:=n-1 downto 1 do

for j:=1 to i do if a[j]>a[j+1] then begin c:=a[j];

a[j]:=a[j+1];a[j+1]:=c;

end;

for i:=1 to n do write(a[i],' ');

end.

Чем отличаются две программы?