Статические массивы

символов, строк и т.п.), рассматриваемое как единое целое.
var
a: array

[1..10] of real;
b: array[0..50] of integer;
c: array[-3..4] of boolean;

Объявление массива

b[17] := 123;
c[-2] := a[1]>a[2];
for k := 1 to 10 do a[k] := 0;

Обращение к элементу массива

real;
var
a: array[1..3, –2..2, 1..5] of real;
или более компактная запись
Многомерные

массивы

of real;
...
a := b;
Можно передать все элементы одного массива другому

массиву

var
a: array[1..5] of real;
b: array[1..5] of real;
...
a := b; {Здесь возникнет ошибка несоответствия типов}

i: integer;
...
eq := true;
for i := 1 to 5 do

if a[i]<>b[i] then eq := false;
if eq then ...

Над массивами не определены операторы отношения

диапазоне от 0 до maxValue-1
Random(a,b: integer): integer;         Возвращает случайное

целое в диапазоне от a до b
Random: real;         Возвращает случайное вещественное в диапазоне [0..1)

Пример: заполнить массив вещественными числами из отрезка [5;10]

2. Заполнение значениями

2. Заполнение значениями

// массив
i : integer;

// счетчик цикла
begin
// заполнение массива значениями
for i := 1 to N do
m[i] := random(50+1)/10 + 5;
// вывод значений на экран
for i := 1 to N do
writeln('m[',i:2,'] =',m[i]:4:1);
end.

Вариант 1 (используя Random(maxValue: integer): integer)

m[ 1] = 9.1
m[ 2] = 9.9
m[ 3] = 6.0
m[ 4] = 5.7
m[ 5] = 7.3
m[ 6] = 5.0
m[ 7] = 9.0
m[ 8] = 9.4
m[ 9] = 5.9
m[10] = 7.0

2. Заполнение значениями

Статические массивы

// массив
i : integer;

// счетчик цикла
begin
// заполнение массива значениями
for i := 1 to N do
m[i] := random(50,100)/10;
// вывод значений на экран
for i := 1 to N do
writeln('m[',i:2,'] =',m[i]:4:1);
end.

Вариант 2 (используя Random(a,b: integer): integer)

m[ 1] = 7.2
m[ 2] = 6.4
m[ 3] = 5.0
m[ 4] = 5.0
m[ 5] = 6.2
m[ 6] = 5.9
m[ 7] = 8.5
m[ 8] = 7.9
m[ 9] = 7.1
m[10] = 9.5

2. Заполнение значениями

Статические массивы

// массив
i : integer;

// счетчик цикла
begin
// заполнение массива значениями
for i := 1 to N do
m[i] := random*5 + 5;
// вывод значений на экран
for i := 1 to N do
writeln('m[',i:2,'] =',m[i]:4:1);
end.

Вариант 3 (используя Random: real)

m[ 1] = 6.0
m[ 2] = 5.9
m[ 3] = 5.5
m[ 4] = 6.1
m[ 5] = 7.7
m[ 6] = 9.3
m[ 7] = 9.6
m[ 8] = 9.0
m[ 9] = 7.4
m[10] = 5.2

2. Заполнение значениями

Статические массивы

один цикл, в нем формировать и выводить на экран значения.

В общем случае на операции формирования, обработки и вывода требуется свой цикл;
в вариантах 1 и 2 результат вещественный с точностью до десятых, в 3 – 11-12 значимых.

2. Заполнение значениями

2. Заполнение значениями

Nr = 2; Nc = 4;
var
a, b

: array [1..Nr,1..Nc] of integer;
i,j : integer;
begin
writeln('После объявления массива a');
for i := 1 to Nr do
begin
for j := 1 to Nc do write (a[i,j]:3);
writeln;
end;
for i := 1 to Nr do
for j := 1 to Nc do a[i,j] := random(11);

i := 1 to Nr do
begin
for j

:= 1 to Nc do write (a[i,j]:3);
writeln;
end;
b := a;
writeln('Содержимое массива b');
for i := 1 to Nr do
begin
for j := 1 to Nc do write (b[i,j]:3);
writeln;
end;
end.

После объявления массива a
0 0 0 0
0 0 0 0
После заполнения массива a
0 9 1 4
2 7 5 5
Содержимое массива b
0 9 1 4
2 7 5 5

математические вычисления
3. Вычисления
3. Вычисления

Вычисления

известных значений
3. Вычисления
3. Вычисления

(массив аргументов, массив значений)
Задать точку, для которой вычисляется значение функции.
Найти

в массиве аргументов ближайший к заданной точке.
Вычисление коэффициентов полинома первого порядка (y=kx+b)
Вычисление значения функции в заданной точке.

Пример: вычислить значение функции в точке заданной таблично

[1..N] of real; // массив аргументов
my : array

[1..N] of real; // массив значений
x,y : real; // точка, для которой вычисляется
k,b : real; // коэффициенты полинома
i : integer; // счетчик цикла
findPoint: boolean; // маркер поиска точки

i := 1 to N do
begin

write('Точка ',i,' (x,y) ');
read(mx[i], my[i]);
end;
write('Введите значение аргумента, для которого необходимо вычислить значение функции, x=');
readln(x);

:= false;
while not findPoint do // поиск ближайшего

аргумента
begin
if (x >= mx[i]) and (x < mx[i+1]) then
begin // ближайший аргумент найден
findPoint := true;
k := (my[i+1] - my[i])/(mx[i+1] - mx[i]);
b := my[i] - k*mx[i];
y := k*x+b;
writeln('Значение функции в точке x=',x,' равно y=',y:0:2);
end;
if i = N-1 then // точки кончились
findPoint := true;
else
i := i + 1;
end;
end.

1.23%

поиск цепочек

четных элементов
Определение самой длинной из них

Пример: Найти и вывести самую

длинную цепочку четных элементов массива

[1..N] of integer;
i : integer;
c, l :

integer; //позиции и длина текущей цепочки
cm, lm : integer; //позиции и длина самой длинной цепочки
flag1, flag2 : boolean; // флаги цепочки
begin
for i := 1 to N do
begin //заполним и распечатаем массив
m[i] := random(10 + 1);
write(m[i],' ');
end; П
Writeln;

позиций цепочки и их макс знач.
c := 0; l

:= 0;
cm := 0; lm := 0;
flag1 := false; flag2 := false;
for i := 2 to N do
begin
flag2 := (m[i-1] mod 2=0) and (m[i] mod 2=0); // два соседних элемента четные
if flag2 then
begin
if not flag1 then begin c := i-1; l := 2; end //два подряд четных, а пред - нет
else l := i - c + 1; //больше двух подряд четных
if l > lm // длина текущей цепочки больше предыдущей
then cm := c; lm := l;
end
else
begin
// сброс параметров текущей цепи в нуль
l := 0; c := 0;
end;
flag1 := flag2;
writeln(c,'-',l,'|',cm,'-',lm);
end;

for i := cm to cm+lm-1 do write(m[i],' ')

else writeln('Цепочек нет')
end.

точки
Обойти все исходные точки, определить расстояние до каждой их них
Запомнить

минимальное расстояние

Пример: Найти точку на плоскости, ближайшую заданной

на плоскости
var
px,py : array [1..N] of real; // координаты

исходных точек
x,y : real;
i, imin : integer;
L, Lmin : real; //текущее и минимальное расстояние
begin
writeln('Исходные точки');
for i := 1 to N do // заполняем координаты точек
begin
px[i] := 5 - 10*random;
py[i] := 5 - 10*random;
writeln('(',px[i]:5:2,',',py[i]:5:2,')');
end;
writeln('Введите координаты точек');
write('x=');readln(x);
write('y=');readln(y);

imin := 1;
writeln('Точка #1 расстояние ',Lmin:5:2);
for i :=

2 to N do
begin
L := sqrt(sqr(x-px[i]) + sqr(y-py[i]));
if Lmin > L then begin Lmin := L; imin := i; end;
writeln('Точка #',i,' расстояние ',L:5:2);
end;
writeln('Ближайшая точка #',imin,' расстояние ',Lmin:5:2);
end.

#1 расстояние 4.08
Точка #2 расстояние 3.33
Точка #3 расстояние 5.47
Точка #4

расстояние 6.05
Точка #5 расстояние 2.87
Наиближайшая точка #5 расстояние 2.87

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

от количества обрабатываемых элементов.

O(…) – вычислительная сложность «О-большое», значит не хуже чем …

Примеры:
O(1) – операция взятия значения по индексу
O(n) – поиск в массиве конкретного значения методом последовательного перебора
O(logN) – бинарный поиск
O(N^2) – поиск пары самых близко расположенных точек на плоскости
O(2^N), O(N!) – unreal

операций в секунду

алгоритма поиска минимального числа?
начало; поиск минимального элемента массива array из

N элементов
min := array[1]
для i от 2 до N выполнять:
если array[i] < min
min := array[i]
конец; вернуть min

N – 1 операция присваивания счетчику цикла i нового значения;
N – 1 операция сравнения счетчика со значением N;
N – 1 операция сравнения элемента массива со значением min;
от 1 до N операций присваивания значения переменной min.

O(f(N)) = O(N-1+N-1+N-1+N +1) = O(4N-2) = O(N)

в таком порядке
a'1,a'2, … ,a'n,
что при заданной функции f справедливо

отношение:
f(a'1)   f(a'2)  …  f(a'n)
f(x) – функция упорядочивания, её значение называется ключом

Типы сортировки:
внутренний (все элементы находятся в памяти машины);
внешний (часть в памяти, часть на внешних носителях);
устойчивая сортировка (не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи)

Основные характеристики:
время;
дополнительный объем памяти (без привлечения, с привлечением, необходимо копировать массив).

6. Сортировка

6. Сортировка

41 564 165 685 815 764 827
41 165 564

685 764 815 827
41 165 564 685 764 815 827
41 165 564 685 764 815 827
41 165 564 685 764 815 827
41 165 564 685 764 815 827

6. Сортировка

5. Сортировка

array[1..N] of integer;
i, j, k: integer;
begin

write ('Исходный массив: ');
for i := 1 to N do begin
arr[i] := random(101);
write (arr[i]:4);
end;
writeln; writeln;
for i := 1 to N-1 do
for j := 1 to N-i do
if arr[j] > arr[j+1] then begin
k := arr[j];
arr[j] := arr[j+1];
arr[j+1] := k
end;
write ('Отсортированный массив: ');
for i := 1 to N do write (arr[i]:4);
writeln;
end.

этого значения со значением первой не отсортированной позиции 3) сортируется

хвост списка, исключив из рассмотрения уже отсортированные элементы

195 700 949 274 444 108 698
108 700 949 274 444 195 698
108 195 949 274 444 700 698
108 195 274 949 444 700 698
108 195 274 444 949 700 698
108 195 274 444 698 700 949
108 195 274 444 698 700 949

6. Сортировка

5. Сортировка

335 33 355 217 536
3 10 335 33 355

217 536
3 10 33 335 355 217 536
3 10 33 335 355 217 536
3 10 33 217 335 355 536
3 10 33 217 335 355 536

6. Сортировка

6. Сортировка

(quicksort);
и тд

6. Сортировка
5. Сортировка