Теоретические сведения. Цель работы–изучение способов описания и особенностей работы одномерных и двумерных массивов, закрепление навыков в составлении простейших разветвляющихся и

Лабораторная работа № 5

МАССИВЫ

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

Постановка задачи

1. Выполнить каждый из двух пунктов задания в виде консольного приложения Delphi с использованием массивов.

2. Ввод данных осуществить с клавиатуры.

3. Вывести результаты на экран.

Теоретические сведения

Простые типы данных определяют различные множества атомарных (неразделимых) значений. Составные или структурированные типы, в отличие от простых, задают множества «сложных» значений; каждое значение из такого множества образует некоторый агрегат (совокупность) нескольких значений другого типа (или других типов). Можно сказать, что составные типы определяют некоторый способ образования новых типов из уже имеющихся, причем отдельные элементы составных значений могут иметь любой, в том числе составной, тип. Таким образом, Delphi допускает образование структур произвольной сложности, позволяя тем самым достичь адекватного представления в программе данных, с которыми она оперирует.

Одним из основных структурированных типов алгоритмических языков программирования является тип-массив. Каждое значение типа-массива состоит из фиксированного числа элементов одного и того же базового типа. Такой способ образования новых значений (фиксированное число однотипных компонент) позволяет обозначать значения этих типов одним (групповым) именем, а доступ к отдельным элементам массивов организовать посредством указания этого группового имени и индекса необходимого элемента.

Для корректного определения типа-массива необходимо задать две характеристики: тип элементов массива, а также количество и способ «нумерации» элементов. Последние характеристики задаются посредством указания типа индекса. Определение регулярного типа имеет следующий общий вид:

Type

A: array [ t1 ] of t2;

где array и of – служебные слова, t1 обозначает тип индекса массива, t2 – тип компонент массива. В дальнейшем идентификатор этого типа может быть использован в описании переменных.

В качестве типа индекса может выступать любой дискретный тип, кроме Longint и ограниченных типов, построенных из типа Longint; в частности, допустимы перечислимые и ограниченные типы. Элементами массива могут быть значения любого типа.

Ниже приведены несколько примеров описания массивов.

Type

M1 = array [1..100] of real;

M2 = array [char] of boolean;

Matrix = array [1..10] of array [1..20] of integer;

Var

Vector: M1;

Sym_Table: M2;

Arr1,Arr2: Matrix;

Следует подчеркнуть некоторые различия между массивами в языке Delphi и в некоторых других языках программирования.

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

Для задания количества элементов массива используется имя типа; число элементов определяется количеством возможных значений указанного типа, что отличает Delphi от многих других языков, в которых размер массива задается либо целым числом (или выражением целого типа), либо диапазоном целых чисел. Такая особенность языка Delphi придает ему дополнительную гибкость, позволяя “нумеровать” элементы массива не только целыми числами, но и значениями произвольного дискретного типа. Например, массив Sym_Table из предыдущего примера может адекватно моделировать некоторую логическую шкалу, в которой каждому символу (с типом char) соответствует некоторое логическое значение, а доступ к элементам этого массива может быть организован следующим образом:

Sym_Table [‘a’]:= true;

If Sym_Table [‘.’] then …;

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

Var

V2: array [1..10] of array [1..20] of byte;

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

Var

V2: array [1..10,1..20] of byte;

Количество индексов в определении (то есть размерность массива) в языке не ограничивается.

Delphi допускает единственно возможное действие над массивом в целом: использование его в операторе присваивания, например:

Vect1:=Vect2;

причем оба массива в данном случае должны иметь идентичный тип.

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

Так, доступ к элементам массива, описанного в первом примере, строится следующим образом:

Vector[1];

Vector[(i+1)*2].

Двумерный массив V2, описанный выше, допускает такой доступ к своим элементам:

V2[3,7]

V2[i,j]

Рассмотрим подробнее массив V2. Вследствие того, что его можно трактовать как «массив массивов», то, например, конструкция V2[ k ] вполне допустима в языке и в данном случае обозначает k –й массив в группе из 10 массивов байтовых элементов. Для того чтобы адресоваться, скажем, к 5-му элементу этого массива, можно записать V2[ k ][5].

Такая запись корректна, но ее более привычный эквивалент – V2[ k,5] – можно считать сокращением первоначальной записи.

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

Рассмотрим примеры решения некоторых типовых задач, связанных с обработкой массивов.

1. Упорядочивание массива по возрастанию.

Упорядочивание массива по какому-либо признаку называется сортировкой. Существуют различные методы сортировки, они различаются в основном по скорости получения результата. Рассмотрим один из них – метод “пузырька”. Это наиболее простой (но и наиболее медленный) метод сортировки. Его еще называют «сортировка обменом пар».

Рассмотрим алгоритм этого метода подробно. Пусть имеется последовательность из шести чисел, содержащих следующие значения: 1, 3, 4, 2, 6, 5.

Пройдем по массиву, сравнивая первый элемент со вторым, второй с третьим и так далее до пятого. Будем проверять упорядоченность, и если она нарушена (т.е. если значение некоторого элемента больше значения следующего элемента), то поменяем эти значения местами. Например, дойдя до третьего элемента, значение которого равно 4, мы обнаружим, что оно больше значения четвертого элемента, равного 2. Выполнив обмен, получим новую последовательность значений: 1, 3, 2, 4, 6, 5.

После этого перейдем к четвертому элементу. Теперь его значение равно 4. Значение следующего элемента равно 6, оно больше 4, поэтому обмена значениями не происходит. Перейдя к пятому, обнаруживаем, что его значение больше шестого, и производим обмен. Итак, выполнив один проход по массиву, получим последовательность значений: 1, 3, 2, 4, 5, 6.

Эта последовательность до конца не отсортирована. Однако мы можем с уверенностью сказать, что наибольший элемент находится на своем месте – на правой границе массива. Выполняя новые проходы, каждый раз сокращая количество просматриваемых элементов на 1, мы в конечном счете отсортируем все значения. Данный алгоритм получил название «пузырьковая сортировка», так как в процессе каждого прохода элемент как бы «всплывает» на свое место, подобно пузырьку воздуха в воде.

Приведем пример программы, реализующей описанный алгоритм сортировки.

program Sort;

{$APPTYPE CONSOLE}

Uses

SysUtils;

Const

n=7;

Var

a: array [1..n] of real;

x,i,j:integer;

Begin

For i:=1 to n do Begin

write(‘a[‘,i,’]=’);

readln(a[i]);

end;

For i:=1 to n-1 do

For j:=1 to n-i do

If a[j]>a[j+1] then Begin

x:=a[j];

a[j]:=a[j+1];

a[j+1]:=x

end;

For i:=1 to n do

write(a[i]:5);

readln;

End.

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

Одна из важных невычислительных задач – поиск данного значения среди элементов массива. Такой поиск также называется поиском по ключу. На практике поиск осуществляется в упорядоченном массиве. Имеются различные алгоритмы поиска. В данном учебном примере осуществим поиск путем сплошного перебора. Если элемент найден, напечатаем его номер, если нет – выдадим соответствующее сообщение. Существенным является то, какой из одинаковых элементов массива, равных данному, нас интересует: первый, встретившийся при поиске, или последний. В данном примере будем искать первый. Поиск осуществляется в цикле. Как только элемент найден, надо выйти из цикла. Для досрочного выхода из цикла используем оператор безусловного перехода goto. Если досрочный выход не произойдет, значит, элемент, равный данному, в массиве отсутствует. В таком случае выдача сообщения об отсутствии элемента должна быть сразу после цикла поиска. Следовательно, чтобы обойти печать номера элемента, надо использовать еще один оператор goto и еще одну метку в программе.

Возможный вариант программы поиска:

program poisk;

{$APPTYPE CONSOLE}

Uses

SysUtils;

Const

n=7;

label 1,2;

Var

a: array [1..n] of real;

x:real;i:integer;

Begin

For i:=1 to n do

Begin

write(‘a[‘,i,’]=’);

readln(a[i]);

end;

write(‘введите искомое x=’);

readln(x);

For i:=1 to n do

If a[i]=x then goto 1;

writeln(‘такого числа в массиве нет’);

goto 2;

1: write(‘номер элемента массива, равного данному значению ’,i)

2: readln;

End.

3.Алгоритмы обработки матриц.

Двумерный массив или прямоугольная матрица B из n строк и m столбцов в общем виде выглядит следующим образом:

b₁₁ b₁₂ b_1m

b₂₁ b₂₂ b_2m

b_n1 b_n2 b_nm

На языке Delphi имена элементов массива записываются также с двумя номерами (индексами):

b[1,1],b[1,2],…,b[1,m],b[2,1],b[2,2],…,b[2,m],…,b[n,1],b[n,2],…,b[n,m].

В памяти компьютера элементы двумерного массива расположены один за другим: после элементов первой строки следуют элементы второй строки матрицы и т.д. Если количество строк матрицы равно количеству столбцов, то такая матрица называется квадратной. Главная диагональ квадратной матрицы проходит из левого верхнего угла в правый нижний.

Рассмотрим задачи обработки матриц и алгоритмы их решения.

3.1. Вычисление суммы элементов главной диагонали квадратной матрицы.

Для решения задачи надо выполнить следующие шаги: ввести матрицу в память; найти сумму элементов главной диагонали; напечатать результат. Описание матрицы, как и описание одномерного массива, используется для резервирования памяти. В описании матрицы указываются диапазоны для двух номеров: строк и столбцов.

При обработке массивов в разделе описания переменных программы появляются имена индексов элементов: для одномерных массивов – одной, для двумерного – двух целочисленных переменных.

При вычислении суммы элементов диагонали следует обратить внимание на имена суммируемых элементов: оба индекса имеют одинаковое значение, т.е. в общем виде имя элемента диагонали будет b[i,i]. Это означает, что можно рассматривать диагональ как одномерный массив и использовать один цикл для вычислений.

Программа имеет следующий вид:

program Sum_Diagonal;

{$APPTYPE CONSOLE}

Uses

SysUtils;

Const

N=3;

Var

b: array [1..n,1..n] of real;

I,j:interger;

S:real;

Begin

writeln(‘введите значения элементов матрицы по строкам’);

writeln(‘в конце каждой строки нажимайте Enter’);

for i:=1 to n do

Begin

for j:=1 to n do read(b[i,j]);

writeln;

end;

S:=0;

for i:=1 to n do

S:=S+b[i,i];

write(‘сумма элементов диагонали матрицы s=’,s);

readln;

End.

3.2.Нахождение наибольших элементов каждой строки матрицы.

Каждую строку матрицы можно рассматривать как одномерный массив и использовать идею нахождения наибольшего значения в программе maxim из предыдущего раздела. Найденные значения будем помещать в одномерный массив a.

program Max_In_Rows;

{$APPTYPE CONSOLE}

Uses

SysUtils;

Const

n=3;

Var

b: array [1..n,1..n] of real;

I,j:interger;

a: array [1..n] of real;

Begin

writeln(‘введите значения элементов матрицы по строкам’);

writeln(‘в конце каждой строки нажимайте Enter’);

for i:=1 to n do

Begin

for j:=1 to n do read(b[i,j]);

writeln;

end;

for i:=1 to n do

Begin

a[i]:=b[i,1];

for j:=2 to n do

if a[i]<b[i,j] then a[i]:=b[i,j];

end;

writeln (‘Наибольшие значения строк матрицы S’);

writeln (‘Номер строки Наибольшее значение’);

for i:=1 to n do

writeln (i:6,’ ’:20,a[i]);

readln;

End.

3.3. Нахождение сумм элементов столбцов матрицы.

При обработке матриц можно осуществлять операции как над строками, так и над столбцами. При нахождении суммы элементов столбцов можно использовать алгоритм из программы summa предыдущего раздела. Для лучшего понимания работы программы введем переменную S для вычисления суммы, а затем для каждого столбца запишем полученный результат в массив a, т.е. присвоим его переменной a[j], где j – текущий номер столбца матрицы.

Ниже приводится возможный вариант программы.

program Sum_By_Columns;

{$APPTYPE CONSOLE}

Uses

SysUtils;

Const

n=3;

Var

b: array [1..n,1..n] of real;

I,j:interger;

S:=real;

a: array [1..n] of real;

Begin

writeln(‘введите значения элементов матрицы по строкам’);

writeln(‘в конце каждой строки нажимайте Enter’);

for i:=1 to n do

Begin

for j:=1 to n do read(b[i,j]);

writeln;

end;

for j:=1 to n do

Begin

S:=0;

for i:=1 to n do S:=S+b[i,j];

a[,j]:=S;

end;

write(‘сумма элементов столбцов матрицы: ’);

for i:=1 to n do

write(a[i]);

readln;

End.

3.4. Перестановка строк матрицы.

В прямоугольной матрице b из n строк и m столбцов требуется поменять местами две строки. При решении этой задачи можно использовать алгоритм обмена значениями двух переменных из программы сортировки. Для этого достаточно организовать цикл по переменной столбца и, используя промежуточную (буферную) переменную, менять местами каждую пару элементов, стоящих в одном столбце. При заданных номерах строк K и L решение выглядит так:

program P;

{$APPTYPE CONSOLE}

Uses

SysUtils;

Const

n=3;m=4;

Var

b: array [1..n,1..m] of real;

c:real;

K,L,i,j:interger;

Begin

write(‘Введите номера меняемых местами строк матрицы’);

readln(K,L);

writeln(‘введите значения элементов матрицы по строкам’);

writeln(‘в конце каждой строки нажимайте Enter’);

for i:=1 to n do

Begin

for j:=1 to n do read(b[i,j]);

writeln;

end;

for j:=1 to m do

Begin

c:=b[K,j];

b[K,j}:=b[L,j};

b[L,j}:=c;

end;

writeln;

writeln(‘матрица с переставленными строками:’);

for i:=1 to n do

Begin

for j:=1 to m do

write(b[i,j]);

wtiteln

end;

readln;

End.

Пример

Задача 1.

Рассчитать сумму отрицательных элементов массива А(n), если известно, что
n = 5, A = (1.5, -4.6, 10, -1.7, -4.9).

Задача 2.

Найти разность R между максимальным и минимальным элементами массива

Не нашли, что искали? Воспользуйтесь поиском: