- Массив. Описание на языке программирования Паскаль, структура
- Стандартные задачи на обработку массива
- Сортировка массива
- знать, что такое массив, уметь организовать массив средствами языка программирования Паскаль
- уметь реализовывать стандартные алгоритмы обработки массивов (линейный поиск, перестановка, удаление, вставка элемента в массив) на языке программирования Паскаль
- уметь реализовывать алгоритмы сортировки массива средствами языка программирования Паскаль
- Какие типы данных вам известны?
- Вспомните, почему принято делить типы данных на простые и составные?
Массив. Описание на языке программирования Паскаль, структура
В программах, с которыми мы работали раньше, использовались только простые структуры данных. Переменных было немного, каждой из них мы давали имя, определяли тип данных и значение. Однако бывают задачи, в которых необходимо обработать большое количество однотипных объектов, и присваивать каждому индивидуальную переменную — сложное занятие, в котором легко запутаться. Поэтому принято объединять данные одного типа в составную структуру данных с одним общим именем, которая называется массивом. Примером массива может быть любой список числовых или символьных констант, например, результаты измерения температуры воздуха или список книг.
Массив — это набор однотипных величин, упорядоченных по индексам, определяющим место элемента в массиве, и обозначаемых одним именем.
Чтобы использовать массив в программе, необходимо его описать. Массив на языке программирования Паскаль описывается в разделе Var. При этом фиксируется его имя, в квадратных скобках через две точки записывают границы индексов — номеров элементов массива, затем идёт тип данных элементов массива.
Рассмотрим описание целочисленного массива X, состоящего из 5 элементов с индексами от 1 до 5:
Var X: array [1..5] of integer;
Чтобы обработать определённый элемент массива, нужно знать его индекс. Например, Х[3] — обращение к третьему элементу массива Х.
Таблица 1. Массив из 5 элементов
|
Индексы массива
|
1
|
2
|
3
|
4
|
5
|
|
Массив Х
|
11
|
13
|
24
|
34
|
4
|
|
Обращение к элементу
|
Х[1]
|
Х[2]
|
Х[3]
|
Х[4]
|
Х[5]
|
Обработка элементов массива всегда происходит в цикле.
Ввод элементов массива может происходить как с клавиатуры (в цикле), так и в самой программе. Вывод элементов массива возможен командой writeln(x).
Пример 1
Заполним массив числами от 1 до 10 и найдём сумму их квадратов.
Решение
Для решения задачи нужно ввести в массив данные и осуществить перебор элементов массива с одновременным нахождением суммы.
var
a:array [1..10] of integer;
s,i :integer;
begin
s:=0; # начальное значение суммы
for i:=1 to 10 do begin #перебор всех элементов массива
a[i]:=i; #заполнение массива числами
s:=s+a[i]*a[i]; # нахождение суммы квадрата
end;
writeln (s);
end.
Ответ: 385.
Упражнение 1
Заполнить массив двузначными числами и найти их сумму.
Стандартные задачи на обработку массива
К стандартным задачам обработки массива можно отнести:
- Задачи на линейный поиск некоторого элемента в массиве;
- Задачи на соответствие элементов массива некоторым условиям;
- Задачи на удаление, вставку и перестановку элементов массива;
Перебор элементов массива — это выполнение некоторой операции с каждым его элементом. Для организации перебора элементов используют цикл.
Пример 2
Рассмотрим последовательный поиск элемента, введённого с клавиатуры, в неупорядоченном массиве (тип задачи № 1).
Решение
В результате работы программы может быть два возможных варианта развития событий: нужный элемент найден и нужный элемент не найден.
Поэтому алгоритм работы программы может быть таким:
- Перебираем каждый элемент массива в цикле.
- Проверяем, является ли элемент нужным.
- Если элемент является нужным, выводим номер его индекса.
- Если элемент не найден, выводим сообщение, что такого элемента нет.
var
a:array [1..10] of integer;
x, i, f : integer;
begin
writeln('Введите элемент, который нужно найти:');
readln(x);
writeln('Введите элементы в массив:');
for i := 1 to 10 do
read(a[i]);
f := 0;
for i := 1 to 10 do begin
if (a[i] = x) and (f = 0) then
begin
writeln('Элемент найден, его индекс ',i);
f: = 1;
end;
end;
if f = 0 then writeln('Элемент не найден');
end.
Упражнение 2
Найдите значение минимального элемента массива. Массив состоит из 10 чисел, которые вводятся с клавиатуры.
Пример 3
Подсчитаем количество положительных элементов массива (тип задачи № 2).
Решение
Для решения задачи нужно ввести в массив данные и осуществить перебор элементов массива с одновременной проверкой условия положительности. Если найден положительный элемент, то к счётчику добавляется 1.
var
a:array [1..10] of integer;
x,i,k :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
k:=0;
for i:=1 to 10 do begin
if a[i] > 0 then
begin
k:=k+1;
end;
end;
writeln('В массиве ', k , ' положительных элемента');
end.
Упражнение 3
Сосчитайте количество чётных элементов в массиве X. Массив состоит из 10 чисел, которые вводятся с клавиатуры.
Пример 4
Переставим все элементы массива в обратном порядке (тип задачи № 3).
Решение
Для решения задачи нужно поменять местами первый и последний элементы, второй и предпоследний и т. д. до середины массива. В нашем массиве 10 элементов, поэтому середина равна 5.
var
a:array [1..10] of integer;
x,i,k :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
k:=0;
for i:=1 to 5 do begin
k:=a[i];
a[i]:=a[10 - i + 1];
a[10 - i + 1]:=k;
end;
writeln(a);
end.
Упражнение 4
Массив состоит из 10 чисел, которые вводятся с клавиатуры. Переставьте местами элементы массива т. о.: первый со вторым, третий с четвёртым
и т. д.
Сортировка массива
Для более эффективного решения множества различных задач требуется расставить элементы массива в определённом порядке. Для этого существуют сортировки.
Сортировка (упорядочение) массива — это перераспределение элементов массива в соответствии с определёнными правилами в некотором порядке.
Сортировка бывает по возрастанию, убыванию, неубыванию, невозрастанию.
Пример 5
Рассмотрим сортировку массива по возрастанию самым простым способом — методом «пузырька».
Решение
Метод «пузырька» состоит в том, что обрабатывается пара соседних элементов массива, больший элемент ставится справа, а меньший оставляется слева. Этот процесс нужно повторять (n − 1) раз, где n — размер массива.
var
a:array [1..10] of integer;
j,i,k :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
k:=0;
for i:=1 to 9 do begin
for j:=1 to 9 do begin
if a[j]>a[j+1] then begin
k:=a[j];
a[j]:=a[j+1];
a[j+1]:=k;
end;
end;
end;
writeln(a);
end.
Упражнение 5
Массив состоит из 10 чисел, которые вводятся с клавиатуры. Отсортируйте массив по неубыванию методом «пузырька».
Итоги
- Массив — это набор однотипных величин, упорядоченных по индексам, определяющим место элемента в массиве, и обозначенный одним именем.
- Индекс элемента массива — это номер элемента в массиве.
- При обращении к элементу индекс указывают в квадратных скобках.
- Обработка (перебор) элементов массива происходит в цикле.
- Стандартными задачами обработки массива являются поиск элементов; соответствие элементов условиям; удаление, вставка и перестановка элементов.
- Чтобы ускорить поиск элементов в массиве, можно использовать сортировки (распределение значений элементов в определённом порядке).
- Сортировки бывают: по возрастанию, по убыванию, по невозрастанию, по неубыванию.
Контрольные вопросы
- Переведите на русский язык английское слово array.
- Приведите пример задачи, в которой можно использовать массив.
- Каким образом происходит описание массива на языке паскаль?
- Что такое индекс элемента и для чего он нужен?
- Что такое перебор элементов в массиве и как его организовать?
Упражнение 1
4 905
Упражнение 2
Возможна следующая реализация программы на Паскаль.
var
a:array [1..10] of integer;
x,i,min :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
min:=1000000;
for i:=1 to 10 do begin
if a[i] < min then
min:=a[i];
end;
writeln('MIN = ',min);
end.
Упражнение 3
Возможна следующая реализация программы на Паскаль.
var
a:array [1..10] of integer;
x,i,k :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
k:=0;
for i:=1 to 10 do begin
if a[i] mod 2 = 0 then
begin
k:=k+1;
end;
end;
writeln('В массиве ',k, 'четных элемента');
end.
Упражнение 4
var
a:array [1..10] of integer;
x,i,k :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
k:=0;
i:=1;
while i<11 do begin
k:=a[i];
a[i]:=a[i+1];
a[i+1]:=k;
i:=i+2;
end;
writeln(a);
end.
Упражнение 5
var
a:array [1..10] of integer;
j,i,k :integer;
begin
writeln('Введите элементы в массив:');
for i:=1 to 10 do
read(a[i]);
k:=0;
for i:=1 to 9 do begin
for j:=1 to 9 do begin
if a[j] >= a[j+1] then begin
k:=a[j];
a[j]:=a[j+1];
a[j+1]:=k;
end;
end;
end;
writeln(a);
end.