Понятие и обработка массива

В практической деятельности человека часто используются таблицы и списки.
Например:
Список учеников в журнале;
Список среднесуточной температуры месяца;
Таблица умножения.

Иванов
Петров
Сидоров
Кошкин
Мышкин

100
120
120
130
140
140
120
150
160
140
...
180

Элементы списков и номера строк и столбцов всегда нумеруются

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

Массив

это упорядоченный по номерам набор значений, объединенных общим типом и именем

Каждое значение в массиве называется элементом.Номер элемента в списке называется индексом.

Тип элемента может быть любым (символьные или числовые), принятым в языке ПАСКАЛЬ, кроме файлового типа.
Тип элемента называется базовым типом.
Элемент массива представляется как переменная с индексом или с индексами: A[5] S[k+1] B[3,5].

Одномерный
(содержит одну строку или один столбец)

Двумерный(содержит N строк,
M столбцов)

Например, температура воздуха за неделю.

Например, значение функции y=x2

x y

Многомерный

В качестве иллюстрации можете представить себе шкаф, имеющий множество нумерованных ящиков.

Шкаф – это массив.

Ящики – это индексы.

Содержимое ящиков – элементы массива.

Доступ к содержимому конкретного ящика (элемента массива) осуществляется после указания шкафа –имени массива – и номера ящика – индекса массива.

Одномерный массив

НОМЕР элемента массива
(ИНДЕКС)

ЗНАЧЕНИЕ элемента массива

НОМЕР (ИНДЕКС) элемента массива: 2

ЗНАЧЕНИЕ элемента массива: 10

Имя задается правилами задания имен идентификаторов.
Индекс (порядковый номер элемента массива) – местоположение элемента в массиве.
Размер - количество элементов массива.
Размерность - количество индексов массива.

Обращение к любому элементу массива происходит по имени массива и его номеру.

Обращение к конкретному элементу массива осуществляется путем указания имени массива и индекса этого элемента в [ ] :

В качестве индексов массивов можно использовать переменные целого типа:

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

Name[15]:= ‘ Иванов ‘;
Sum:=Sum+Temperature[10];
Kino[5,6]:=‘Свободно ‘ ;

Целый

температура воздуха за месяц

вес учеников класса

список класса

Основные этапы работы с массивами

2. Заполнение массива данными

3. Обработка (преобразование) массива

4. Вывод массива или
отдельных данных на экран

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

Для того, чтобы использовать массив в программе, его нужно описать в разделе описаний:
Var имя_массива : array [тип индексов] of тип_элементов;
Имя массива выбираем по основным правилам имен идентификаторов.
Тип индексов: [начальный_индекс . . конечный_индекс ]
Например: [1..5 ] [10..100 ] [-10..10 ]

Зачем объявлять?
определить имя массива
определить тип массива
определить число элементов
выделить место в памяти
Массив целых чисел:


Размер через константу:

имя

начальный индекс

конечный индекс

тип
элементов

var A: array[1.. ] of integer;

var A : array[ 1 .. 5 ] of integer ;

var X, Y: array [1..10] of real;
C: array [1..20] of char;

var Q: array [0..9] of real;
C: array [-5..13] of char;

var A: array ['A'..'Z'] of real;
B: array [False..True] of integer;
...
A['C'] := 3.14259*A['B'];
B[False] := B[False] + 1;

Не обязательно начинается с 0 или с 1.
Необходимо, чтобы номер последнего элемента был больше, чем номер первого элемента:
var А: array [-5..4] of integer;
Нумеровать элемент массива можно не только целыми числами. Нумератором может быть любой порядковый тип данных (перечисляемый, интервальный, символьный, логический), а также произвольный тип, созданный на их основе.

В языке Паскаль имеется другая форма описания, состоящая из 2-х этапов.
Сначала в разделе описания типов TYPE указывается тип массива.
Затем в разделе переменных VAR перечисляются массивы, относящиеся к указанному типу.
Форма объявления массива имеет вид:
TYPE имя типа = ARRAY[t1] OF t2;
VAR имя массива: имя типа;
где t1 – тип индекса; t2 – базовый тип элементов массива.
Например:

Команда присваивания:
непосредственное присваивание значений элементам A[1]:=7; A[2]:=77; A[3]:=33; и т. д.;
часто требуется обнуление ячеек массива;
с помощью формул;
генерация (randomize) и присваивание значений с помощью функции A[I]:=random(q-p+1)+p; qp;
с помощью CONST;
ввод значений элементов с клавиатуры;

Этот способ применяется в том случае, когда информация в таблице не меняется.

BEGINTEMP[1]:=10;TEMP[2]:=12;TEMP[3]:=8;TEMP[4]:=10;TEMP[5]:=9;TEMP[6]:=8;TEMP[7]:=8;

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

Алгоритм состоит из трех пунктов:

Перезапустить генератор случайных чисел.
Ввести количество элементов n (или сгенерировать случайное значение n).
Сгенерировать значения для всех элементов.
{1 - перезапускаем генератор случайных чисел}randomize;{2 - генерируем случайное значение n}n:=random(maxN);{3 - генерируем n элементов массива}for i:=1 to n doa[i]:=random(100); {каждый элемент примет значение из интервала 0..99}

Информация об используемых стандартных процедурах и функциях:

Randomize - инициализирует генератор случайных чисел случайным значением (случайное значение зависит от момента перезапуска, т.е. зависит от времени).
Язык Pascal имеют функцию – датчик случайных чисел:
Random(N) - возвращает случайное целое число, находящееся в интервале 0 .. (N-1)
Random, тип REAL присваивается случайное значение от 0 до 0.99999999.
Если N<=0, то Random всегда будет возвращать 0. Чтобы получить значения в интервале, отличном от [0..N-1], необходимо к значению, возвращаемому Random, прибавить смещение начала интервала.
Общий случай функции на [p;q]: random(q-p+1)+p; qp;

Вывод массива на экран

Program Random_mas;
Var i: integer;
Ran : array [1..10] of integer;
Begin
Randomize;
For i:=1 to 10 do
begin
ran[i]:=random(101);
writeln(ran[i]);
end;
end.

Как изменить программу, чтобы выводились числа [-20;20]?

Как изменить программу, чтобы выводились числа типа REAL?

Как изменить программу, чтобы выводились элементы массива в строку?

Заполнить и вывести на экран одномерный массив целых чисел.
{******* заполнение массива c случайными числами *******}
Заполнить и вывести на экран одномерный массив целых чисел.
{******* заполнение массива c клавиатуры *******}
Заполнить и вывести на экран одномерный массив символов.
{******* заполнение массива c в разделе CONST *******}

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

Итоги урока:

На этом уроке мы узнали:
Массив – это структура данных, представляющая собой совокупность элементов одного типа.
Массив должен быть объявлен в разделе объявления переменных.
Доступ к элементу массива осуществляется путем указания имени массива и индекса (номера) элемента.
Для ввода, вывода и обработки массивов удобно применять команды цикла.
Существуют несколько способов ввода элементов массива в память.

В оглавление

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

задачи заполнения

задачи подсчета

задачи анализа

задачи поиска

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

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

Вставка и удаление элементов массива

вычисление суммы и произведения элементов массива (для числовых массивов);
вычисление среднего арифметического, геометрического элементов массива;
замена элементов массива по условию;
подсчет заданных элементов в массиве;
нахождение в массиве заданного элемента;
поиск в массиве максимального (минимального) элемента;
определение индекса максимального (минимального) значения;
сортировка элементов массива;
перестановка элементов массива по заданному правилу;
удаление и вставка элемента.

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

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

Program Sum_mas;
uses Crt;
Var i: integer;
Sum : real;
M : array [1..5] of Real;
begin
Clrscr;
For i:=1 to 5 do
begin
write ('m[',i,']=');
readln(m[i]);
end;
sum:=0;
For i:=1 to 5 do
Sum:=sum+m[i];
Writeln ('Sum=',sum:6:2);
readln;
end.

Подсчет заданных элементов в массиве

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

Введите температуру воздуха за неделю.
1 день= 2
2 день= 0
3 день= -3
4 день= 1
5 день= 3
6 день= -2
7 день= 0
Средняя температура: 0.00 град.

Задание для практической работы:

Задача 2
Написать программу, которая определяет, сколько раз в массиве случайных чисел A[1..100] встречается число Х, введенное с клавиатуры.

Задания для практической работы:

program my;
var
i,s:integer;
mas:array[1..10] of integer;
begin
s:=0;
for i:=1 to 10 do
begin
mas[i]:=random(201)-100;
writeln(mas[i]);
s:=s+mas[i];
end;
writeln('summa=',s);
i:=1;
s:=0;
while mas[i]>0 do
begin
s:=s+mas[i];
end;
writeln('summa2=',s);
end.

Домашнее задание

Задача 2.
Написать программу, которая вычисляет среднее арифметическое ненулевых элементов массива М[1..100], элементы которого вычисляются по формуле:
М[i]=sin(i)*cos(i)
Задача 3.
Написать программу, которая проверяет, образуют ли элементы массива Х[1..10], введенного с клавиатуры неубывающую последовательность.

Домашнее задание

(продолжение)

Перечислить основные типы задач на обработку массива.
Написать формулу нахождения суммы элементов массива (произведения).
Написать формулу подсчета количества элементов по условию.
Каковы условия поиска элементов?

Значения элементов двух массивов А и В размером 1 х 100 задаются с помощью следующего фрагмента программы:
for i:=1 tо 100 do
A[i] := 50 – i;
for i:=1 tо 100 do
B[i] := A[i] + 49;
Сколько элементов массива В будут иметь отрицательные значения?
1) 1 2) 10 3) 50 4) 100

ЗАДАЧА
Требуется из данного массива А, состоящего из N элементов, выбрать элементы, удовлетворяющие заданному (пусть А(i)>T (с клавиатуры)), и сформировать из них массив B.
Исходный массив А: 4 6 8 2 23 1 9
Условие: A(i)>=8
Новый массив B: 8 23 9
Особенность решения: Индексы элементов массивов A и B не совпадают, так как не все элементы массива A включаются в массив B.

Задача: найти в массиве максимальный элемент.
Алгоритм:

Дополнение: как найти номер максимального элемента?

случайные числа в интервале [50,150)

поиск максимального

(продолжение)

Задача: переставить элементы массива в обратном порядке.
Алгоритм:
поменять местами A[1] и A[N], A[2] и A[N-1], …
Псевдокод:

сумма индексов N+1

Задача: поменять местами содержимое двух чашек.

Задача: поменять местами содержимое двух ячеек памяти.

Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего.
Алгоритм:
A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N];
Цикл:

почему не N?

УДАЛЕНИЕ И ВСТАВКА ЭЛЕМЕНТОВ

program perestanovka;
var
i,buf,maxi:integer;
mas:array[1..10] of integer;
begin
buf:=0;
for i:=1 to 10 do
begin
mas[i]:=random(21);
writeln(mas[i]);
end;
for i:=1 to 10 do
begin
if mas[i]>buf then
buf:=mas[i];
maxi:=i;
end;
mas[maxi]:=mas[1];
mas[1]:=buf;
for i:=1 to 10 do
writeln(mas[i]);
еnd.

Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Алгоритмы:простые и понятные, но неэффективные для больших массивов; метод пузырька метод выборасложные, но эффективные; «быстрая сортировка» (Quick Sort) сортировка «кучей» (Heap Sort) сортировка слиянием пирамидальная сортировка

Метод пузырькаДля массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»). Начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами.За 1 проход по массиву один элемент (самый маленький) становится на свое местоДля сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

program sortirovka_puzyrek;
const N = 10;
var A: array[1..N] of integer;
i, j, c: integer;
begin
{ заполнить массив }
{ вывести исходный массив }
for i:=1 to N-1 do begin
for j:=N-1 downto i do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
end;
end;
{ вывести полученный массив }
end.

Метод пузырька с флажкомИдея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход.

i := 0;
Repeat
i := i + 1;
flag := False; { сбросить флаг }
for j:=N-1 downto i do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
flag := True; { поднять флаг }
end;
until not flag; { выход при flag=False }

Метод выбораИдея:найти минимальный элемент и поставить на первое место (поменять местами с A[1]):из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2]), и т.д.

program sortirovka_vebor;
const N = 10;
var A: array[1..N] of integer;
i, j, c, nMin: integer;
begin
{ заполнить массив }
{ вывести исходный массив }
for i := 1 to N-1 do begin
nMin = i ;
for j:= i+1 to N do
if A[j] < A[nMin] then nMin:=j;
if nMin <> i then begin
c:=A[i];
A[i]:=A[nMin];
A[nMin]:=c;
end;
{ вывести полученный массив }
End.