Лекция_№7_Массивы_2024

1. Задача

Вводится N целых чисел. Определить количество
чисел, меньших среднего арифметического
значения последовательности.

2. Многократная обработка данных

Задача:
Вводится N целых чисел. Определить количество чисел, меньших
среднего арифметического значения последовательности.
Проблемы
1. Последовательность данных необходимо просмотреть два
раза, следовательно необходимо хранение всех чисел
последовательности.
2. Сколько переменных потребуется? Как их объявить?
3. Алгоритмы вычисления суммы и количества требуют
циклов, а следовательно вводить числа надо в одну и ту же
переменную.
Решение проблемы – нужна структура данных,
которая позволяет хранить не одно число, а много. И
при этом в одной переменной!

3. Структурный тип данных МАССИВ

Лекция №7

4.

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

5. Основные понятия

Массив данных обозначается одним именем.
Например, всю совокупность действительных чисел
6, 149, -5, 85, 46
можно считать массивом и обозначить одним именем,
например А.
А =(6, 149, -5, 85, 46)
Каждый элемент массива обозначается именем массива и
индексом, заключенным в квадратные скобки. Индекс
определяет положение элемента массива :
A[1]=6,
A[2]=149,
A[3]=-5,
A[4]=85,
A[5]=46

6. Доступ к элементу массива

Индекс элемента
1
2
3
4
5
6
149
-5
85
46
Элемент массива
Чтобы обратиться к какому-либо элементу массива,
необходимо назвать имя массива и индекс (позицию)
элемента:
A[2]:=149;
Writeln (A[1]);
S:=S+A[i];

7. Задача. Вводится N целых чисел. Определить количество чисел, меньших среднего арифметического значения последовательности.

Var a:array of integer; N:integer;
Begin
N:=readlninteger(‘Кол-во чисел? ’);
Setlength(a,N);//выделяем память под массив
S:=0; k:=0;
For i:=0 to N-1 do begin
readln(a[i]);
S:=S+a[i]);
End;
Sr:=S/N;
For i:=0 to N-1 do
if a[i]<Sr then inc(k);
Writeln(k);
End.

8. Задачи

1)
2)
Вводится последовательность натуральных чисел (N≈1030),
числа не превышают 100. Определить, какое число встречается
чаще всего.
Вводится последовательность целых чисел N≈1030 (числа не
превышают 100). Определить медиану последовательности.

9. Двумерные массивы

ДВУМЕРНЫЕ МАССИВЫ

10. Двумерный массив Temp

,
1
2
3
4
5
6
7
8
31
1
0
2
3
15
4
…
12
Для доступа к элементу двумерного массива необходимо указать имя
массива и два индекса – номер строки и номер столбца:
Temp[4,8]:=15;
Temp[2,31]:=0;

11. Трехмерный массив Temp

Для доступа к элементу трехмерного массива необходимо указать имя
массива и три индекса:
Temp[4,8,2]:=15;
Temp[2,31,1]:=0;

12. Массивы

Статический
Память выделяется при
объявлении переменной
в сегменте данных (SD).
Var a: array [1..10] of integer;
В качестве индексов можно
использовать любой порядковый тип
Динамический
Память под массив
выделяется по мере
необходимости в коде.
Память выделяется в Heapпамяти.
Var a: array of integer;
Индексы всегда
начинаются с 0

13. Описание массива

Var
<перемен> : array [тип индекса] of <тип элементов>;
А: array[1..5] of integer;
Temp: array[-10..-1] of real;
T:array[‘a’..’z’] of byte;
A:array[1..1000] of string;
D: array of integer;
Поэтому стандартного идентификатора для типа массив нет.

14. Создание типа

Стандартного идентификатора для типа массив нет. Программист
сам конструирует тип массив в разделе TYPE:
Type
<идентиф.типа>=array[диапазон индекса] of <тип элементов>;
любой порядковый тип,
а также диапазоны этих
типов: 1..10, ‘a’…’z’,
false..true, -1000..1000
любой (в том числе и
массив), кроме
файлового.

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

Сначала конструируется тип массив в разделе типов Type, где
описывается структура массива. Затем нужно выделить память под
переменные этого типа.
Type
Mas=array[1..10] of integer;
Mass_Char=array of char; //динамический массив
Matr=array[‘A’..’C’] of Mas;
Var
A:Mas; B1,B2:Mass_Char; C:Matr;

16. Двумерный массив

Первый способ: прямое указание диапазонов строк и столбцов в
квадратных скобках:
Type Matr=array[1..3,1..5] of byte;
Matr_N=array[,] of integer; // динамический массив
Var A:Matr;
//Сначала указывается диапазон строк, затем диапазон столбцов

17. Двумерный массив 1 способ

Второй способ: описание одномерного массива, содержащего
элементы типа массив.
Type Matr=array[1..3] of array [1..5] of byte;
или
Type
Stroka_matr=array [1..5] of byte;
Matr=array[1..3] of Stroka_matr;
Matr2=array of array of integer;
Var А:Matr;

18. Внутреннее представление двумерного массива

В памяти компьютера массив любой размерности, в том числе и двумерный,
хранится в виде одномерных (линейных) массивов.
Т.е. двумерный массив представляет собой массив массивов, т.е. линейный
массив элементов, которые в свою очередь также являются линейными
массивами.
Массив А:
1
1
2
3
4
5
2
3
1
2
3

19. Инициализация массива

(заполнение массива
элементами)

20. Значения элементов массива в программе можно определить тремя способами:

◼
◼
Элементы массива могут быть введены с клавиатуры
или из файла;
Элементы массива могут быть определены в
программе:
❑
❑
С помощью датчика случайных чисел;
Заданы правилом/формулой/скопированы из
другого массива.

21. Инициализация массива

Массив может быть инициализирован просто присваиванием
значений элементам:
var b:array[1..5]of integer:=(1,3,24,-15,16);
var c:=|12,3,45|; //динамический массив
Var a:=|false|*10; //динамический массив

22. Типизированные константы

CONST
<имя константы>:<описание структуры>=(<список значений>);
CONST
D:array[1..10]of integer=(9,-2,0,0,-5,6,2,-13,76,9);
А:Mass=((0, -3.6, 7),( 8.3, 0.4,52.0),(-9,7.2,-13));
B:array[1..4]of char=(‘+’, ’-‘, ’*’, ‘/’);
Menu:array [1..5]of string=(‘Ввод данных’,’Вывод
данных’,’Поиск данных’,’Удаление данных’,’Выход’);

23.

Значения элементов многомерных массивов перечисляют в порядке
возрастания индексов справа налево, заключая в скобки каждый
подмассив.
CONST
B: array [1..2, 1..6] of real=
( (0, -3, 7, 2.3, 5.0, -9), (0,0,0,0,0,0) );
S: array [1..3, 0..1, 1..4] of byte=
(((0,0,0,0),(1,1,1,1)),
((2,2,2,2),(3,3,3,3)),
((4,4,4,4),(5,5,5,5)));

24. Заполнение массива с клавиатуры

Type
MyMass=array of integer;
Var A:MyMass;
i,n:Integer;
Begin
n:=readlninteger(‘Введите кол-во элементов: ’);
Setlength(A,n); //выделение памяти под массив
for i:=0 to n-1 do
readln(A[i]);
… …
end.

25. Заполнение массива с помощью генератора случайных чисел

Const n=10;
Type MyMass=array[1..n] of integer;
Arr_real:array of real;
Var A:MyMass; b:arr_real;
Begin
for var i:=1 to n do
A[i]:=random(100,999);
//заполнение динамического массива
b:=ArrRandomReal(100,0.1,0.2)
….
end.
Кол-во
элементов
Диапазон

26. задания

1)
2)
3)
Заполните двумерный массив из 5 строк и 3 столбцов
случайными числами в диапазоне -50…50.
Заполнить массив А(20) числами Фибоначчи.
Сформируйте двумерный массив N*N по следующему правилу:
элементы главной диагонали равны 1, элементы ниже главной
диагонали – 0, а выше – сумме индексов соответствующего
элемента.
Дополнительно:
1)
Заполните массив М(20) случайными числами в диапазоне от 100 до 100, при этом чтобы все элементы были различны.

27. Основные операции над массивами

28. Присваивание статических массивов

Данную операцию можно
применять только к массивам
одного типа.
TYPE Mas=array [1..2] of real;
CONST A:Mas=(3.0, 0.12);
VAR B:Mas;
C,D: array [1..6] of char;
Begin
B:=A;
C:=D;
Данная операция не
выполнима для массивов
различных типов, даже, если
у них одинаковая структура.
Var А:array [1..10]of
integer;
B:array[1..10]of
integer;
Begin
…
А:=В;

29. Присваивание динамических массивов

Динамические массивы совместимы по типу элементов:
var a:array of integer;
var b:array of integer;
var r:array of real;
begin
a:=Arrrandominteger(10,1,1000);
b:=a;
a:=r;
a:=Copy(b);
println(a);
println(r);
end.
а
6
14
2
28
3
55
а
6
14
2
28
3
55
b
6
14
2
28
3
55
b

30. Основные операции с массивами:

◼
◼
◼
◼
◼
Ввод элементов массива,
Вывод элементов массива на экран или в файл,
Поиск элемента (элементов),
Упорядочивание элементов массива,
Вставка/удаление элемента массива.
Все эти операции требуют последовательной обработки всех
элементов массива, а поэтому требуют использования циклов.

31. Вывод линейного массива

Команда
На экране
Print(a);
[1,2,3,4,5,6]
for var i:=low(a) to high(a) do
Write (A[i]:3);
1 2 3 4 5 6
foreach var i in a do
print(i);
123456
a.Print(‘ : ’)
1 : 2 : 3: 4 : 5 : 6

32. Вывод двумерного массива

for var i:=1 to N do
begin
for var j:=1 to n do
write (a[i,j]:4);
writeln;
End;
Переход на
новую строку
Вывод строки
матрицы

33. Поиск элемента массива по заданному критерию

Существует несколько методов поиска. Наиболее
распостраненные:
◼ Линейный поиск (поиск максимума, поиск нулевого
элемента и т.д.)
◼ Двоичный поиск

34. Алгоритм линейного поиска

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

35. Разработать программу поиска заданного элемента массива А(20).

var A:array of integer;
i,n:byte;
begin
//Заполнение массива
setlength(a,n);
…
Readln(key);
//Поиск элемента
i:=-1;
repeat
inc(i);
until (i>high(a)) or (a[i]=key);
if
end.
i=N then writeln (‘NO’)
else writeln (a[i], ‘ стоит
на позиции
‘, i);

36. Алгоритм двоичного поиска

Имеется упорядоченный по возрастанию массив целых чисел:
2, 5, 8, 11, 13, 14, 19, 23, 33, 45, 49. Необходимо найти значение
b=23
2, 5, 8, 11, 13, 14, 19, 23, 33, 45, 49
2, 5, 8, 11, 13, 14, 19, 23, 33, 45, 49
2, 5, 8, 11, 13, 14, 19, 23, 33, 45, 49
2, 5, 8, 11, 13, 14, 19, 23, 33,

37.

Type mass=array of integer;
Var a:mass:=|2,6,8,17,24,39|;
key:integer;
Begin
Key:=readlninteger('Введите значение поиска: ');
//поиск элемента:
var lev := 0; var prav := length(a)
;
while prav - lev > 1 do begin
var sered := (lev + prav) div 2 ; //Определяем середину интервала
поиска
if key < a[sered]
then prav := sered
//меняем правую границу интервала
else lev := sered ;
//Меняем левую границу
end;
//Проверяем
if a[lev] = key
then print('Такое значение в списке есть. Его индекс:', lev)
else print('Такого значения в списке нет');
end.

38.

Type mass=array of integer;
Var a:mass:=|2,6,8,17,24,39|;
key,sered:integer;
i,j,d:byte;
fl:boolean;
Begin
Key:=readlninteger('Введите значение поиска: ');
//поиск элемента:
var lev := 0; var prav := high(a) ;
repeat
sered := (lev + prav) div 2 ; //Определяем середину интервала поиска
if key = a[sered] then fl:=true
else if key<a[sered]
then prav := sered-1
//меняем правую границу интервала
else lev := sered+1 ;
//Меняем левую границу
until fl or (lev>prav);
//Проверяем
if fl
then print('Такое значение в списке есть. Его индекс:',sered)
else print('Такого значения в списке нет');
end.

39. Переформирование массива

ПЕРЕФОРМИРОВАНИЕ
МАССИВА

40. Переформирование массива

Переформирование массивов предполагает изменение порядка
элементов массива посредством их перемещения, удаления
или вставки.
Вставка или удаление элементов осуществляется за счет
сдвига всех элементов той части массива, которая
расположена после удаляемого или до вставляемого
элемента.
Задание
Дан массив А (n), где N<=10. Разработать программу
удаления элемента с индексом k.

41. Задача

Дан массив А (n), где N<=10. Разработать программу
удаления элемента с индексом k.
k
1
2
3
4
5
6
7
8
9
10
12
15
-8
0
7
44
30
-6
0
27
k:=find(key,a);
for i:=k to high(a)-1 do
a[i]:=a[i+1];
setlength(a,length(a)-1);

42. Задание

Заполнить массив А(20) случайными числами. Удалить из
массива минимальный элемент массива.

43. Перестановка элементов массива

2
1
2
3
4
5
6
7
8
9
10
11
12
28
1
10 14 25
3
78
-5
16
9
-2
0
1
буфер
Buf:=A[2];
A[2]:=A[10];
A[10]:=buf
3
или
swap(a[2],a[10])

44. Задача

1)
2)
Напишите алгоритм, который переставляет первый и
последний элементы массива.
Напишите алгоритм, который максимальный элемент
массива переставляет в конец массива.

45. Задача

Дана матрица A(n,n), n<=20. Выполнить перестановку строк,
номера которых вводятся с клавиатуры.
Type Matr=array [,] of Integer;
Var A:Matr; n,n1,n2:byte;
Begin
For var i:=1 to n do
setlength(a[i],n)
….
//Перестановка строк
n1
n2
Writeln(‘строка 1, строка 2?');
readln(n1,n2);
for var j:=0 to a.high do //цикл по столбцам
begin
swap(a[n1,j],a[n2,j])
end;

46.

Из многомерных массивов допускается выделять подмассивы,
отбрасывая индексы, записанные справа, и оставляя индексы,
определяющие данный подмассив.
Например, из двумерного массива можно выделять строки, но
нельзя – столбцы.
Поэтому задачу перестановки строк можно решить одним
оператором. При этом необходимо учесть совместимость
массивов по присваиванию.
(n1,n2):=(‘строка 1, строка 2?’);
Swap(a[n1], a[n2]);

47. «Слияние (объединение) списков»

«Из двух списков а и b, каждый из которых упорядочен по возрастанию,
получить новый список z, состоящий из элементов двух заданных
списков, таким же образом упорядоченный. При этом сортировку не
использовать»
a = [1, 12, 22, 34, 59, 200, 201, 202, 800]
b = [4, 5, 6, 35, 80, 87, 89]
i = 0
//Начальные значения индексов
j = 0
//сравниваемых элементов списков
while (i < length(a)) and (j < len(b)) do
if a[i] > b[j] then begin
z[?] := b[j] //Записываем в список c элемент b[j]
j := j + 1
end
else begin
z[?] := a[i] //Записываем в список c элемент а[i]
i := i + 1
end;

48. «Слияние (объединение) списков»

После этого для решения задачи необходимо переписать в список C все
оставшиеся элементы в одном из исходных списков (в каком – не
знаем!):
while i < length(a)do begin
z[i + j] := a[i]
i := i + 1
end;
while j < length(b) do begin
z[i + j] := b[j]
j := j + 1
end;

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

Сортировка – это процесс упорядочивания информации по
определенному признаку.
◼
◼
◼
◼
◼
По возрастанию,
По убыванию,
По невозрастанию,
По неубыванию.
По алфавиту
Цель сортировки – повышение скорости поиска данных в больших
объемах.

50. Сортировка простым обменом (Пузырьковая сортировка)

Сортировка простым обменом основана на многократном обходе
массива
a1, a2,… an., при котором сравниваются два соседних
элемента ai и ai+1. Если элементы неупорядочены, то они меняются
местами.
7, 5, 8, 4, 1, 3, 2.

51. Как можно повысить эффективность алгоритма?

for j:=high(a) downto 1 do
for i:=1 to j-1 do
if a[i]>a[i+1] then swap(a[i],a[i+1]);

52. Задание

Упорядочить последовательность чисел 3, 0, 5, 1, 2
по возрастанию.
Как можно ускорить работу алгоритма?

53. Как можно ускорить работу алгоритма?

Repeat
fl:=false;
for i:=1 to j-1 do
if A[i]>A[i+1] then begin
fl:=true;
buf:=A[i];
A[i]:=A[i+1];
A[i+1]:=buf;
end;
Until fl=false;

54. Сортировка простым выбором

Идея сортировки простым выбором заключается в поиске
граничного элемента, например, максимального и водворении
его на «свое место» в конец массива (если сортировка по
возрастанию). Далее последний элемент «исключаем» (длина
массива как бы укорачивается) и повторяется поиск
максимума. Процесс повторяется до тех пор, пока длина
массива не станет равна одному элементу.

55. Сортировка простыми вставками

В исходном состоянии считают, что сортируемая
последовательность элементов состоит из двух частей:
отсортированной (она на первом шаге состоит из единственного
элемента – первого) и неотсортированной.
На каждом шаге из неотсортированной части последовательности
берется очередной элемент и вставляется в уже
отсортированную часть.
Поиск места вставки осуществляется с правого конца
отсортированного подмассива путем сравнения вставляемого
элемента (назовем его ключом key) с элементами aj. Если ключ
меньше элемента aj (при сортировке по возрастанию), то ключ
key и элемент aj меняются местами, и ключ продолжает
сравнение с последующим элементом подмассива aj-1. Поиск
места вставки завершается, если элемент вставлен или если
достигнут левый конец массива.

56. Дана последовательность чисел: 5 2 3 8 6 1

5 2 3 8 6 1
2 5 3 8 6 1
2 3 5 8 6 1
2 3 5 8 6 1
2 3 5 6 8 1
2 3 5 6 1 8
2 3 5 1 6 8
2 3 1 5 6 8
2 1 3 5 6 8
1 2 3 5 6 8

57. Сортировка простыми вставками

for i:=1 to high(M) do
begin
key:=M[i];
{определяем ключ}
j:=i-1; {определяем правый элемент отсорт. подмассива}
while (j>=0)and(M[j]>key) do {поиск места для вставки}
begin
M[j+1]:=M[j];
dec(j);
end;
M[j+1]:=key;
{вставка ключа}
end;