Последний урок паскаль был написан аж 7 марта, тогда мы разбирали . Сегодня мы узнаем, что такое двумерный массив в паскале , как он описывается и что он из себя представляет. Подробнее далее.
Итак, что же такое двумерный массив? Для лёгкого восприятия представим одномерный массив как линию, а которой все элементы идут друг за другом горизонтально, а двумерный как квадрат, в котором элементы расположены как горизонтально, так и вертикально. Двумерный массив состоит из строчек и столбцов, их также называют матрицей или матричным массивом.
Как описываются двумерные массивы? Для записи двумерных массивов есть несколько способов, я рассмотрю 2 из них.
1 способ описание массива: array of тип переменных в массиве (integer/real/byte);
2 способ описания массива: array of array of тип переменных в массиве;
Сначала описываются строки (1..m), а потом столбцы (1..n).
Во втором способе описывается как бы два одномерных массива, которые вместе образуют один двумерный.
Двумерный массив может описываться в разделе Type, для последующего обращения к нему несколько раз или же в разделе описания переменных Var, хочу обратить внимание, что вместо m и n можно подставить и числа, а можно и пользоваться константами.
Пример задания двумерного массива в разделе описания переменных:
Const
m = 100;
n = 100;
var
a: Array of integer;
В этом случае мы задали двумерный массив a размера 100 на 100, то есть у нас получилась квадратная матрица.
Пример задания матричного массива при помощи раздела Type:
Const
m = 100;
n = 100;
Type
Matrix = Array of integer;
var
a: Matrix;
b:Matrix;
Во втором примере мы задали два одинаковых матричных массива размерами 100 на 100, при описании массива b нам не пришлось снова описывать его размеры и тип данных.
Как обращаться к ячейке-переменной двумерного массива?
Чтобы обратиться к двумерному массиву, нужно указать сначала номер строки, а потом номер столбца следующим образом:
x-любая переменная, a - название массива, i-номер строки, j - номер столбца.
Причём i и j может быть как переменными, так и целыми числами.
Пример записи данных в массив:
For i:= 1 to n do //задание в цикле номера строки
For j:=1 to m do //задание в цикле номера столбца
a:=random (100);
//присваивание ячейке с номером строки i и номером столбца j случайного значения
Мы заполнили массив случайными числами от 1 до 100.
Пример программы с использованием двумерного массива, в котором мы заполняем массив случайными числами и выводим его на экран:
Var //описание переменных и массива
Matrix: Array of integer;
i, j: integer;
Begin //начало основной программы
writeln ("Двумерный массив: "); //Диалог с пользователем
For i:= 1 to 10 do //заполнение массива
for j:= 1 to 10 do
Matrix:=random (100);
For i:= 1 to 10 do begin //Вывод массива
for j:= 1 to 10 do
write (matrix, " ");
writeln
writeln ("сайт"); //При желании можно удалить
end; //Конец программы
//readln //используется в Турбо паскаль
Двумерный массив структура данных, хранящая прямоугольную матрицу вида:
A 11 a 12 a 13 a 14 a 15 ... a 1m a 21 a 22 a 23 a 24 a 25 ... a 2m a 31 a 32 a 33 a 34 a 35 ... a 3m a 41 a 42 a 43 a 44 a 45 ... a 4m a 51 a 52 a 53 a 54 a 55 ... a 5m ... ... ... ... ... ... ... a n1 a n2 a n3 a n4 a n5 ... a nm
- В матрице каждый элемент определяется номером строки и номером столбца, на пересечении которых он находится
- В Паскале двумерный массив расматривается как массив, элементы которого есть линейные массивы (массив массивов). Два следующих описания двумерных массивов тождественны var mass:array of array of real; var mass:array of real;
- Матрица, в которой число строк равно числу столбцов называется квадратной матрицей .
- Для обращения к элементу матрицы, необходимо использовать два индекса обозначающие номер строки и номер столбца. Например MyArr1 . В данном случае элемент массива (MyArr1) находится в четвертой строке и пятом столбце.
- Все, что было сказано об основных действиях с одномерными массивами, справедливо и для матриц. При поэлементном переборе масива в цикле, в качестве индексов выступают переменные целочисленного типа. Традиционно, для обозначения индекса строки используют идентификатор “i “, а столбца – “j “.
- Обработка матрицы заключается в том, что вначале поочередно рассматриваются элементы первой строки (столбца), затем второй и т. д. до последней.
- Если номер строки элемента совпадает с номером столбца (i = j ), это означает, что элемент лежит на главной диагонали матрицы.
- Если элемент лежит на побочной диагонали, то индексы связаны с числом элементов (n ) следующим равенством: i + j = n + 1
Описание двумерного массива
Существует несколько способов объявления (описания) двумерного массива в Pascal.
Предварительное описание типа массива
type matrix = array of integer; {массив целых чисел} var mass:matrix;Определение переменной как массив без предварительного описания типа массива
var mass:array of integer;Инициализация двумерного массива
При инициализации двумерных массивов каждая строка заключается в дополнительную пару круглых скобок:
Const mass:array = ((2,3,1,0), (1,9,1,3), (3,5,7,0));
Ввод/вывод значений элементов двумерного массива
Очень часто значения элементов массива вводятся с клавиатуры. Этот способ задания информации слишком трудоемок при работе с массивами больших размеров. Для отладки широкого класса алгоритмов такой ввод информации должен быть заменен формированием элементов массива случайным образом. Для этого используют процедуру randomize и функцию random . При работе с двумерными массивами используются вложенные циклы (обычно цикл с параметром for ).
Заполнение массива случайными числами
const n = 5; m = 10; var i, j:integer; matrix:array of integer; begin randomize; for i:= 1 to n do {обращение к строкам массива} for j:= 1 to m do {обращение поэлементно к столбцам} matrix := random(100); {помещаем в текущий элемент случайное число из интервала :4); writeln {переход на новую строку по выходу из внутреннего цикла} end;Примеры решения задач
Пример 1
Постановка задачи. Даны целые положительные числа M и N. Сформировать целочисленную матрицу размера M × N, у которой все элементы J-го столбца имеют значение 5·J (J = 1, …, N).
Const m = 7; n = 10; var i, j:byte; matrix:array of integer; begin for i:= 1 to m do for j:= 1 to n do matrix := 5 * j; ... {Вывод массива}
Пример 2
Постановка задачи. Даны целые положительные числа M, N и набор из M чисел. Сформировать матрицу размера M × N, у которой в каждом столбце содержатся все числа из исходного набора (в том же порядке).
Const m = 5; n = 7; vector:array of integer = (3, 5, 2, 7, 4); var i, j:byte; matrix:array of integer; begin for j:= 1 to n do {берем j-ый столбец} for i:= 1 to m do {обращаемся к элементам j-го столбца по строкам} matrix := vector[i]; {реализация} ... {Вывод полученного двумерного массива}
Домашнее задание
- Даны целые положительные числа M и N. Сформировать целочисленную матрицу размера M × N, у которой все элементы I-й строки имеют значение 10·I (I = 1, …, M).
- Даны целые положительные числа M, N и набор из N чисел. Сформировать матрицу размера M × N, у которой в каждой строке содержатся все числа из исходного набора (в том же порядке).
- Дополнительно. Даны целые положительные числа M, N, число D и набор из M чисел. Сформировать матрицу размера M × N, у которой первый столбец совпадает с исходным набором чисел, а элементы каждого следующего столбца равны сумме соответствующего элемента предыдущего столбца и числа D (в результате каждая строка матрицы будет содержать элементы арифметической прогрессии).
- Дополнительно. Дана матрица размера M × N. Вывести ее элементы, расположенные в строках с четными номерами (2, 4, …). Вывод элементов производить по строкам, условный оператор не использовать.
Двумерный массив в Паскале трактуется как одномерный массив, тип элементов которого также является массивом (массив массивов). Положение элементов в двумерных массивах Паскаля описывается двумя индексами. Их можно представить в виде прямоугольной таблицы или матрицы.
Рассмотрим двумерный массив Паскаля размерностью 3*3, то есть в ней будет три строки, а в каждой строке по три элемента:
Каждый элемент имеет свой номер, как у одномерных массивов, но сейчас номер уже состоит из двух чисел – номера строки, в которой находится элемент, и номера столбца. Таким образом, номер элемента определяется пересечением строки и столбца. Например, a 21 – это элемент, стоящий во второй строке и в первом столбце.
Описание двумерного массива Паскаля.
Существует несколько способов объявления двумерного массива Паскаля.
Мы уже умеем описывать одномерные массивы, элементы которых могут иметь любой тип, а, следовательно, и сами элементы могут быть массивами. Рассмотрим следующее описание типов и переменных:
Пример описания двумерного массива ПаскаляType
Vector = array of <тип_элементов>;
Matrix= array of vector;
Var m: matrix;
Мы объявили двумерный массив Паскаля m, состоящий из 10 строк, в каждой из которых 5 столбцов. При этом к каждой i -й строке можно обращаться m [ i ], а каждому j -му элементу внутри i -й строки – m [ i , j ].
Определение типов для двумерных массивов Паскаля можно задавать и в одной строке:
Type
Matrix= array of array of < тип элементов >;
или еще проще:
type
matrix = array of <тип элементов>;
Обращение к элементам двумерного массива имеет вид: M [ i , j ]. Это означает, что мы хотим получить элемент, расположенный в i -й строке и j -м столбце. Тут главное не перепутать строки со столбцами, а то мы можем снова получить обращение к несуществующему элементу. Например, обращение к элементу M имеет правильную форму записи, но может вызвать ошибку в работе программы.
Основные действия с двумерными массивами Паскаля
Все, что было сказано об основных действиях с одномерными массивами, справедливо и для матриц. Единственное действие, которое можно осуществить над однотипными матрицами целиком – это присваивание. Т.е., если в программе у нас описаны две матрицы одного типа, например,
type
matrix= array of integer;
var
a , b: matrix ;
то в ходе выполнения программы можно присвоить матрице a значение матрицы b (a:= b). Все остальные действия выполняются поэлементно, при этом над элементами можно выполнять все допустимые операции, которые определены для типа данных элементов массива. Это означает, что если массив состоит из целых чисел, то над его элементами можно выполнять операции, определенные для целых чисел, если же массив состоит из символов, то к ним применимы операции, определенные для работы с символами.
Ввод двумерного массива Паскаля.
Для последовательного ввода элементов одномерного массива мы использовали цикл for, в котором изменяли значение индекса с 1-го до последнего. Но положение элемента в двумерном массиве Паскаля определяется двумя индексами: номером строки и номером столбца. Это значит, что нам нужно будет последовательно изменять номер строки с 1-й до последней и в каждой строке перебирать элементы столбцов с 1-го до последнего. Значит, нам потребуется два цикла for , причем один из них будет вложен в другой.
Рассмотрим пример ввода двумерного массива Паскаля с клавиатуры:
Пример программы ввода двумерного массива Паскаля с клавиатурыtype
matrix= array of integer;
var
a, : matrix;
i, j: integer; { индексы массива }
begin
for i:=1 to 5 do {цикл для перебора всех строк}
readln (a [ i , j ]); {ввод с клавиатуры элемента, стоящего в i -й строке и j -м столбце}
Двумерный массив Паскаля можно заполнить случайным образом, т.е. использовать функцию random (N), а также присвоить каждому элементу матрицы значение некоторого выражения. Способ заполнения двумерного массива Паскаля выбирается в зависимости от поставленной задачи, но в любом случае должен быть определен каждый элемент в каждой строке и каждом столбце.
Вывод двумерного массива Паскаля на экран.
Вывод элементов двумерного массива Паскаля также осуществляется последовательно, необходимо напечатать элементы каждой строки и каждого столбца. При этом хотелось бы, чтобы элементы, стоящие в одной строке, печатались рядом, т.е. в строку, а элементы столбца располагались один под другим. Для этого необходимо выполнить следующую последовательность действий (рассмотрим фрагмент программы для массива, описанного в предыдущем примере):
Пример программы вывода двумерного массива Паскаляfor i:=1 to 5 do {цикл для перебора всех строк}
begin
for j:=1 to 10 do {перебор всех элементов строки по столбцам}
write (a [ i , j ]:4); {печать элементов, стоящих в i -й строке матрицы в одной экранной строке, при этом для вывода каждого элемента отводится 4 позиции}
writeln ; {прежде, чем сменить номер строки в матрице, нужно перевести курсор на начало новой экранной строки}
end ;
Замечание (это важно! ): очень часто в программах студентов встречается ошибка, когда ввод с клавиатуры или вывод на экран массива пытаются осуществить следующим образом: readln (a), writeln (a), где а – это переменная типа массив. При этом их удивляет сообщение компилятора, что переменную этого типа невозможно считать или напечатать. Может быть, вы поймете, почему этого сделать нельзя, если представите N кружек, стоящих в ряд, а у вас в руках, например, чайник с водой. Можете вы по команде «налей воду» наполнить сразу все кружки? Как бы вы ни старались, но в каждую кружку придется наливать отдельно. Заполнение и вывод на экран элементов массива также должно осуществляться последовательно и поэлементно, т.к. в памяти ЭВМ элементы массива располагаются в последовательных ячейках.
Представление двумерного массива Паскаля в памяти
Элементы абстрактного массива в памяти машины физически располагаются последовательно, согласно описанию. При этом каждый элемент занимает в памяти количество байт, соответствующее его размеру. Например, если массив состоит из элементов типа integer , то каждый элемент будет занимать по два байта. А весь массив займет S^2 байта, где S – количество элементов в массиве.
А сколько места займет массив, состоящий из массивов, т.е. матрица? Очевидно: S i^S j , где S i - количество строк, а S j – количество элементов в каждой строке. Например, для массива типа
Matrix = array of integer ;
потребуется 12 байт памяти.
Как будут располагаться в памяти элементы этого массива? Рассмотрим схему размещения массива M типа matrix в памяти.
Под каждый элемент M типа integer выделяется две ячейки памяти. Размещение в памяти осуществляется «снизу вверх». Элементы размещаются в порядке изменения индекса, что соответствует схеме вложенных циклов: сначала размещается первая строка, затем вторая, третья... Внутри строки по порядку идут элементы: первый, второй и т.д.
Как мы знаем, доступ к любой переменной возможен, только если известен адрес ячейки памяти, в которой хранится переменная. Конкретная память выделяется для переменной при загрузке программы, то есть устанавливается взаимное соответствие между переменной и адресом ячейки. Но если мы объявили переменную как массив, то программа «знает» адрес начала массива, то есть первого его элемента. Как же происходит доступ ко всем другим элементам массива? При реальном доступе к ячейке памяти, в которой хранится элемент двумерного массива, система вычисляет ее адрес по формуле:
Addr + SizeElem * Cols *(I -1)+ SizeElem *(J -1),
где Addr – фактический начальный адрес, по которому массив располагается в памяти; I , J – индексы элемента в двумерном массиве; SizeElem – размер элемента массива (например, два байта для элементов типа integer); Cols – количество элементов в строке.
Выражение SizeElem * Cols *(I -1)+ SizeElem *(J -1) называют смещением относительно начала массива.
Сколько памяти выделяется для массива?
Рассмотрим не столько вопрос о том, сколько памяти выделяется под массив (это мы разобрали в предыдущем разделе), а о том, каков максимально допустимый размер массива, учитывая ограниченный объем памяти.
Для работы программы память выделяется сегментами по 64 Кбайт каждый, причем как минимум один из них определяется как сегмент данных . Вот в этом-то сегменте и располагаются те данные, которые будет обрабатывать программа. Ни одна переменная программы не может располагаться более чем в одном сегменте. Поэтому, даже если в сегменте находится только одна переменная, описанная как массив, то она не сможет получить более чем 65536 байт. Но почти наверняка, кроме массива в сегменте данных будут описаны еще некоторые переменные, поэтому реальный объем памяти, который может быть выделен под массив, находится по формуле: 65536- S , где S – объем памяти, уже выделенный под другие переменные.
Зачем нам это знать? Для того чтобы не удивляться, если при компиляции транслятор выдаст сообщение об ошибке объявления слишком длинного массива, когда в программе встретит описание (правильное с точки зрения синтаксиса):
Type myArray= array of integer;
Вы уже знаете, что, учитывая двухбайтовое представление целых чисел, реально можно объявить массив с количеством элементов равным 65536/2 –1=32767. И то лишь в том случае, если других переменных не будет. Двумерные массивы должны иметь еще меньшие границы индексов.
Примеры решения задач с двумерными массивами Паскаля
Задача: Найти произведение ненулевых элементов матрицы.
Решение:
- Для решения данной задачи нам потребуются переменные: матрица, состоящая, например, из целочисленных элементов; P – произведение элементов, отличных от 0; I , J – индексы массива; N , M – количество строк и столбцов в матрице.
- Входными данными являются N , M – их значения введем с клавиатуры; матрица – ввод матрицы оформим в виде процедуры, заполнение матрицы осуществим случайным образом, т.е. с помощью функции random ().
- Выходными данными будет являться значение переменной P (произведение).
- Чтобы проверить правильность выполнения программы, необходимо вывести матрицу на экран, для этого оформим процедуру вывода матрицы.
- Ход решения задачи:
обсудим сначала выполнение основной программы, реализацию процедур обговорим чуть позже:
- введем значения N и M ;
- Введем двумерный массив Паскаля, для этого обращаемся к процедуре vvod (a), где а – матрица;
- Напечатаем полученную матрицу, для этого обращаемся к процедуре print (a);
- Присвоим начальное значение переменной P =1;
- Будем последовательно перебирать все строки I от 1-й до N -й, в каждой строке будем перебирать все столбцы J от 1-го до M -го, для каждого элемента матрицы будем проверять условие: если a ij ? 0, то произведение P будем домножать на элемент a ij (P = P * a ij);
- Выведем на экран значение произведения ненулевых элементов матрицы – P ;
А теперь поговорим о процедурах.
Замечание (это важно!) Параметром процедуры может быть любая переменная предопределенного типа, это означает, что для передачи в процедуру массива в качестве параметра, тип его должен быть описан заранее. Например:
Type
Matrix=array of integer;
procedure primer (a: matrix);
..............................
Вернемся теперь к нашим процедурам.
Процедура ввода матрицы называется vvod , параметром процедуры является матрица, причем она должна быть, как результат, передана в основную программу, следовательно, параметр должен передаваться по ссылке. Тогда заголовок нашей процедуры будет выглядеть так:
Procedure vvod (var m: matrix);
Для реализации вложенных циклов в процедуре нам потребуются локальные переменные-счетчики, например, k и h . Алгоритм заполнения матрицы уже обсуждался, поэтому не будем его повторять.
Процедура вывода матрицы на экран называется print , параметром процедуры является матрица, но в этом случае она является входным параметром, следовательно, передается по значению. Заголовок этой процедуры будет выглядеть следующим образом:
Procedure print (m: matrix);
И вновь для реализации вложенных циклов внутри процедуры нам потребуются счетчики, пусть они называются так же – k и h . Алгоритм вывода матрицы на экран был описан выше, воспользуемся этим описанием.
Пример программы двумерного массива ПаскаляProgram proizvedenie;
Type
Matrix=array of integer;
Var
A: matrix;
N, m, i, j: byte;
P: integer;
Procedure vvod (var m: matrix);
Var k , h: byte ;
Begin
For i:=1 to n do {переменная n для процедуры является глобальной, а значит «известной»}
For j:=1 to m do {переменная m для процедуры является глобальной, а значит «известной»}
M:= random(10);
End;
Procedure print (m: matrix);
Var k, h: byte;
Begin
For i:=1 to n do
begin
For j:=1 to m do
Write (M: 4);
Writeln;
end ;
End ;
Begin {начало основной программы}
Writeln ("Введите размерность матрицы:");
Readln(N, M);
Vvod(a);
Print(a);
P:=1;
For i:=1 to N do
For j:=1 to M do
If a<>0 then p:=p*a;
Writeln (p);
End .