В Паскале, кроме простых типов данных (integer, real, char и т.д.), имеются и сложные типы. К ним относятся массивы. Массив (array,от французского – сплошной) – это область памяти, в которой размещается совокупность конечного числа данных одного типа с одним именем. Каждый элемент такой совокупности обозначается именем массива с индексом (номером элемента в массиве).
Элемент массива – отдельная переменная, входящая в массив;
Индекс (index) – это числовая константа или целочисленное арифметическое выражение (частный случай - целочисленная переменная), которым снабжаются элементы массива, чтобы отличать их друг от друга.
Индекс элемента массива – номер элемента в массиве.
Особенность массивов заключается в том, что все элементы массива являются данными одного типа (возможно и структурированного). При назначении массиву имени соблюдаются те же требования, какие предъявляются к именам переменных простых типов.
| a11
| a12
| …
| a1n
| | a21
| a22
| …
| a2n
| | …
| …
| …
| …
| | am1
| am2
| …
| amn
| В зависимости от количества используемых индексов, массивы могут быть одномерные (строка), двухмерные (таблица), трехмерные и т.д.
В одномерном массиве для указания местоположения элемента достаточно одного индекса,
В двухмерном массиве – два индекса, для строк и граф.
Размерность массива определяется количеством индексов.
Размермассива – диапазон изменения индексов массива.
Размер одномерного массива – количество элементов, которое содержит массив.
Размер двухмерного массива - количество элементов в сроках и графах таблицы и т.д.
Описание массивов:
| Описание массива
| | | 1 способ
| 2 способ
| | | одномерный:
| Type t=array[1..n] of тип;
Var a:t;
| Var a: array[1..n] of тип;
| | двухмерный
| Type р=array[1..n,1..m] of тип; Var a:р;
| Var а=array[1..n,1..m] of тип;
| | трехмерный
| Type р=array[1..n,1..m,1..k] of тип; Var a:р;
| Var a=array[1..n,1..m,1..k] of
| Пример описания одномерного массива размерностью 20:
| type mas=array[1..20] of integer;
var a : mas;
| mas – имя типа,
a – имя переменной типа массив.
Границы изменения индексов - от 1 до 20, т.к. размерность 20 элементов
| | const mas : array [1..7]
of byte=(31,–7,4,3,25,–3,2);
| Массив, объявленный как константа, т.е. совмещается объявление массива и занесение в него констант.
| Следует помнить, что значением переменной a является весь массив!
Элемент массива обозначается указанием имени массива, за которым в квадратных скобках следует индекс массива. Например, a[1] – первый элемент одномерного массива; с[5] – пятый элемент одномерного массива; a[i] – i-тый элемент одномерного массива или для двухмерных массивов: с[1,5] – пятый элемент первой строки массива; a[i,j] – j-тый элемент i-й строки двухмерного массива.
В двухмерном массиве первый индекс - номер строки, второй - номер столбца.
Двухмерные массивы иногда называют матрицами. Двухмерные массивы могут быть прямоугольными (количество строк и столбцов разное) или квадратными (одинаковое количество строк и столбцов). В двухмерных массивах элементы, у которых номер строки совпадает с номером столбца, называются диагональными или элементами главной диагонали. Главная диагональ начинается с первой с роки первого столбца и заканчивается на последней строке последней графы. Кроме главной диагонали существует побочная диагональ - с последней графе первой строки до первой графы последней строки.
Базовые алгоритмы работы с одномерными массивами
Будем считать, что объявили массив из 10 элементов, тип элементов в данном случае значение не имеет:
1. заполнение одномерного массива:
Ø заполнение с клавиатуры:
for i:=1 to 10 do
begin
writeln (‘Введите значение элемента’);
readln(a[i]);
end;
Ø заполнение случайным образом:
for i:=1 to 10 do
a[i]:=random(n); {n должно быть задано заранее}
заполнение натуральными числами:
for i:=1 to 10 do
a[i]:=i;
Ø поменять местами два заданных элемента массива:
c:=a[i]; a[i]:= a[j]; a[j]:=c;
Ø заполнение по формуле (например, ai=sin i):
for i:=1 to 10 do
a[i]:=sin(i);
2. вывод массива на экран:
for i:=1 to 10 do
writeln (‘элемент ’, i, ‘ массива ’,a[i]);
3. нахождение суммы элементов одномерного массива:
s:=0;
for i:=1 to 10 do
s:=s+a[i];
4. подсчёт количества элементов, удовлетворяющих заданному условию (например, положительных элементов):
k:=0;
for i:=1 to 10 do
if a[i]>0 then k:=k+1;
5. поиск максимального элемента одномерного массива и его номера:
max:=a[1];
n:=1;
for i:=2 to 10 do
if a[i]>max then begin max:=a[i]; n:=i; end;
Задача MaxMin. Программа для поиска максимального и минимального элемента массива, с указанием их номеров (maxmin.pas).
program maxmin;
uses crt;
var a: array[1..5] of integer; i,max,nmax,min,nmin:integer;
begin
clrscr;
for i:=1 to 5 do { ввод данных }
begin writeln ('Введите значение элемента');
readln (a[i]);
end;
for i:=1 to 5 do { выдача массива на экран } writeln (a[i]:7);
nmax:=1; { задание начальных значений }
max:=a[1];
nmin:=1;
min:=a[1];
for i:=1 to 5 do{ нахождение минимума и максимума}
if a[i]>max then begin max:=a[i]; nmax:=i; end;
if a[i]<min then begin min:=a[i]; nmin:=i; end;
end;
writeln ('Максимальный элемент=',max);
writeln ('Номер максимального элемента=',nmax);
writeln ('Минимальный элемент=',min);
writeln ('Номер минимального элемента=',nmin);
repeat until keypressed; end.
Сортировка массивов
Сортировка массива – это упорядочение по возрастанию/убыванию значений его элементов.
Сортировка методом «пузырька»
Сущность метода: Начиная с 1-го или последнего элемента, производится попарное сравнение элементов и, если предыдущий больше последнего, то они меняются местами. Фрагмент.
for i:=1 to n-1 do
for j:=i+1 to n do
if f[j]<f[i] then
begin
a:=f[i];
f[i]:=f[j];
f[j]:=a;
end;
Сортировка методом выбора
Сущность метода: Находится минимальный элемент, затем 1-ый и минимальный меняются местами, затем ищется минимальный со 2-го по последний и 2-ой с минимальным меняются местами и т.д.
Задача: Сдвинуть элементы массива влево на одну позицию.
uses crt;
const n=10;
var a: array[1..n] of integer;i, c:integer;
begin
for i:=1 to n do { заполнение массива и его вы вод на экран}
begin
a[i]:=random(50); write (a[i]:5);
end;
c:=a[1];
for i:=1 to n-1 do a[i]:=a[i+1];
a[n]:=c; writeln;
for i:=1 to n do write(a[i]:5);
repeat until keypressed; end.
Поиск элемента в упорядоченном массиве
Поиск – нахождение индекса элемента массива, равного заданной величине. Наиболее простой способ – это простой перебор (последовательно сравниваются элементы массива с образцом до тех пор, пока не будет найден нужный элемент).
Поиск ведется методом дихотомии.
Алгоритм:
Находится округлённое значение полусуммы начальных и конечных индексов массива, т.е. индекс среднего элемента.
Вводится искомая величина (m) и сравнивается со средним элементом. Если a[i]>m, то заданный элемент – в левой половине и поэтому индекс k правой границы устанавливается =i, иначе искомый элемент в правой половине и сдвигается начальный индекс p и p:=i.
Процесс повторяется пока (k-p)<=1, т.е. пока p и k не сдвинутся вплотную. При этом величина искомого индекса =p.
Примеры программ:
Задача. Из массива a составить массив b, который содержит только чётные элементы массива a.
program massiv1;
uses crt;
type mas=array[1..5] of integer;
var a,b:mas; i,k,nmin:integer; min:integer;
begin
clrscr;
textcolor (15);
for i:=1 to 5 do {Блок заполнения массива}
begin
writeln ('Введите значение элемента');
readln (a[i]);
end;
k:=0;
for i:=1 to 5 do if a[i] mod 2=0 then {Поиск чётного элемента}
begin k:=k+1; b[k]:=a[i]; end; {Формирование нового массива}
if k=0 then
begin textcolor (12); writeln ('Чётных элементов нет.'); writeln ('Формирование нового массива невозможно!');
end
else begin nmin:=1; min:=b[1]; {Поиск минимального в новом массиве}
for k:=1 to k do if b[k]<min then
begin min:=b[k]; nmin:=k; end;
for i:=1 to 5 do {Вывод элементов массива а}
begin textcolor (14); writeln ('Элемент ',i, ' массива a ',a[i]);
end;
for i:=1 to k do {Вывод элементов массива b}
begin
textcolor (9); writeln ('Элемент ',i, ' массива b ',b[i]);
end;
textcolor (10);
writeln ('Минимальный элемент среди чётных элементов массива=',min);
writeln ('Номер этого элемента=',nmin);
end;
repeat until keypressed; end.
|