Многие задачи связаны с обработкой многомерных массивов данных. Наиболее распространены при этом двумерные массивы.
В математике двумерные массивы представляются матрицей:
или, в сокращенной записи,
где n — число строк матрицы, m — число столбцов, i , j — индексы (номера) текущих строки и столбца, на пересечении которых находится элемент .
Как и другие объекты данных, матрица описывается в разделе var . От вектора ее описание отличается тем, что в квадратных скобках перечисляются два оператора диапазона, указывающие, соответственно, нумерацию строк и столбцов матрицы:
var ИмяМатрицы : array
[n1..n2, m1..m2] of Тип ;
Здесь n 1.. n 2 — диапазон значений номера строки, n 1 и n 2 — целочисленные константы, m1..m2 — диапазон значений номера столбца, значения m1 и m2 также целочисленные.
Как и векторы, матрицы могут быть образованы из элементов любого существующего в языке типа данных.
Под матрицу из n строк и m столбцов выделяется область памяти размером n * m * k байт, где k — размер в байтах одного элемента. Для известных нам типов данных этот размер можно узнать из табл. 2.1. В оперативной памяти матрица хранится всегда построчно.
Матрица в паскале
Например, для матрицы A , описанной оператором вида
var A:array [1..5,1..4] of real;
выделяется 20 ячеек памяти по 6 байт, причем в следующей за элементом A 1,4 ячейке хранится значение элемента A 2,1 .
Обращение к отдельным элементам матрицы осуществляется с помощью переменной с двумя индексами, например:
Первый индекс, как и в математике, всегда показывает номер строки, а второй — номер столбца.
Поскольку адресация памяти в любом случае линейна, следует понимать матрицу как удобный для программиста структурный тип данных. В отдельных случаях использование матрицы может быть заменено использованием вектора с тем же количеством элементов: так, матрице An , m всегда может быть сопоставлен вектор b из n * m элементов, а обращение к элементу A[i,j] при нумерации строк и столбцов с единицы может быть заменено на обращение к элементу b[(i-1)*m+j] .
Подобно тому, как любая последовательная обработка вектора выполняется в цикле for , обработка матрицы осуществляется в двойном цикле for :
for i :=1 to n do
for j :=1 to m do
Согласно правилу выполнения кратных циклов, переменная j меняется в этом двойном цикле быстрее, чем i , таким образом, обработка всех элементов матрицы будет выполнена построчно. Для последовательной обработки всех элементов матрицы по столбцам достаточно поменять местами циклы по i и j :
for j :=1 to m do
for i :=1 to n do
Теоретически мы могли бы решить эту же задачу и перестановкой индексов в обращении к элементу матрицы (использовать запись A[j,i] вместо A[i,j] ), однако, во избежание путаницы, делать этого не рекомендуется.
Приведем примеры использования двойного цикла for для ввода и вывода элементов матрицы. Пусть матрица c размерностью 4 x 2 (как мы помним, это означает, что в матрице 4 строки и 2 столбца) описана оператором вида
Ввод и вывод матриц на языке Pascal
var c:array [1..4,1..2] of real;
В программе предусмотрено также 2 целочисленных счетчика для строк и столбцов матрицы:
В этом случае типовой ввод матрицы с клавиатуры мог бы выглядеть так:
writeln (‘Введите матрицу c ‘,
for i :=1 to 4 do
for j :=1 to 2 do read ( c [ i , j ]);
Иногда удобнее печатать отдельное приглашение к вводу каждого элемента:
writeln (‘Введите матрицу c[4,2]’);
for j:=1 to 2 do begin
Например, в качестве приглашения к вводу элемента c 1,1 на экране будет напечатано:
Оператор readln используется, поскольку элементы вводятся по одному.
Как и для векторов, возможны альтернативные способы ввода — описание матрицы в разделе констант и формирование ее элементов из случайных чисел. Приведем пример описания матрицы констант размерностью 2 x 3:
const d:array [1..2,1..3] of integer=(
Как видно из примера, для описания матрицы констант создается список ее строк, каждая строка, в свою очередь, представляет собой список значений элементов.
Вывод на экран матрицы небольшой размерности бывает удобно реализовать в виде «одна строка матрицы на одной строке экрана». Для этого элементы матрицы во внутреннем цикле печатаются оператором write , не переводящим строку на экране, а во внешнем цикле выполняется writeln :
writeln (‘ Матрица c:’);
for i:=1 to 4 do begin
for j:=1 to 2 do write (c[i,j]:4:1);
Разумеется, при выводе элементов матрицы можно использовать константы ширины и точности.
Базовые алгоритмы обработки матриц — те же, что мы изучили в гл. 11-15. Отличие состоит в том, что реализацию этих алгоритмов можно условно рассматривать для двух типов задач:
· алгоритмы реализуются при обработке всех элементов матрицы;
· алгоритмы реализуются при обработке отдельных строк или столбцов матрицы.
В первом случае типовая учебная задача на матрицу отличается от аналогичной задачи с вектором лишь тем, что используются двойные циклы ввода, обработки и вывода.
1. Приведем пример реализации алгоритма первого типа.
В матрице A размерностью 4*4 найти сумму ее положительных элементов, произведение элементов, значения которых попадают в интервал [2, 10], а также отношение этих двух величин.
var a:array [1..4,1..4] of real;
writeln (‘Ввод матрицы размерностью 4*4’);
for i :=1 to 4 do
for j :=1 to 4 do read ( a [ i , j ]);
for j:=1 to 4 do begin
if a[i,j]>0 then s:=s+a[i,j];
writeln (‘ Произведение =’,p:6:2);
if p<>0 then begin
writeln (‘ Отношение =’,z:6:2);
else writeln (‘p=0, отношение ‘,
reset (input); readln;
Поскольку о типе матрицы в условии задачи ничего не сказано, выбран «более общий» тип real . Способ ввода также выбран «по умолчанию» — пользователь вводит значения элементов матрицы с клавиатуры. Искомые сумма, произведение и отношение обозначены, соответственно, s , p и z .
2. Рассмотрим пример реализации алгоритма второго типа. Отличие его в том, что алгоритм подсчета или поиска каждый раз заново реализуется во внутреннем цикле, таким образом, искомая в двойном цикле величина заново получает значение на каждом шаге внешнего цикла.
Задана матрица C размерностью 3 x 4. Найти номер строки, сумма элементов которой максимальна.
На этот раз заполним матрицу случайными числами. Обозначим s сумму элементов очередной строки, max — максимальную из этих сумм. В качестве искомого номера строки введем целочисленную переменную imax , в которую будем заносить номер текущей строки i , если для этой строки выполняется соотношение s>max . Переменную s следует инициализировать на каждом шаге внешнего цикла по i (ведь сумма элементов ищется заново в каждой строке), тогда как переменная max ищется для всей матрицы и инициализируется один раз до двойного цикла:
var c:array [1..3,1..4] of real;
write (‘ Матрица C’);
for i:=1 to 3 do begin
for j:=1 to 4 do begin
for i:=1 to 3 do begin
for j:=1 to 4 do s:=s+c[i,j];
if s>max then begin
writeln (‘ Номер строки =’,imax);
Аналогично могут быть реализованы типовые алгоритмы в столбце матрицы — как описано выше, для этого достаточно поменять местами циклы по i и j .
3. Встречаются также задачи, где результаты обработки строк или столбцов матрицы должны быть занесены в вектор. Решим задачу подобного типа.
В матрице S размерностью 20 x 4 приведены оценки 20 студентов за 4 экзамена последней сессии. Подчитать и вывести на экран элементы вектора, содержащего средние баллы каждого студента.
Обозначим искомый вектор как B . Его размерность очевидна, поскольку каждый элемент вектора зависит от одной строки матрицы. Применив алгоритм обработки строк матрицы, получаем следующую программу:
var s : array [1..20,1..4] of integer ;
b:array [1..20] of real;
for i:=1 to 20 do
for j:=1 to 4 do s[i,j]:=3+random(3);
формируя вектор B>
for i:=1 to 20 do begin
for j:=1 to 4 do b[i]:=b[i]+s[i,j];
write (‘ Оценки ‘:8,’ Баллы ‘);
for i:=1 to 20 do begin
for j:=1 to 4 do write (s[i,j]:2);
4. Нередко встречаются задачи, требующие обработки элементов, расположенных под или над главной диагональю матрицы. Главная диагональ характеризуется тем, что номера строк и столбцов расположенных на ней элементов совпадают. Корректно это понятие определено только для квадратных матриц с одинаковым числом строк и столбцов. Соответственно, для обработки элементов, лежащих на главной диагонали матрицы A размерностью n x n было бы достаточно цикла
for i:=1 to n do begin
Когда требуется обработать элементы, лежащие под главной диагональю (для них номер строки больше номера столбца), двойной цикл обработки мог бы выглядеть так:
for j:=1 to n do begin
if i>j then begin
Приведенный код имеет тот недостаток, что в нем выполняются заведомо лишние шаги цикла. Действительно, для квадратной матрицы размерностью n x n мы выполняем n 2 шагов двойного цикла, тогда как имеется всего элементов под главной диагональю. Исправить ситуацию может двойной цикл с переменной границей, подобный изученному выше:
for j:=1 to i-1 do begin
Этот цикл выполняется ровно раз . Для обработки только элементов, лежащих над главной диагональю, этот цикл будет выглядеть следующим образом:
for i :=1 to n do
for j := i +1 to n do begin
5. Распространенный класс задач, связанных с умножением и обращением матриц, мы рассмотрим в гл. 18. Сейчас же ограничимся реализацией хорошо известного алгоритма умножения матрицы A размерностью n x m на вектор b размерности m . Напомним, что в результате умножения получается вектор размерности n (обозначим его c ), а само умножение состоит в том, что каждая строка матрицы скалярно умножается на вектор по формуле и результат заносится в компоненту ci . Применив известные нам типовые алгоритмы, напишем следующую программу:
var a : array [1.. n ,1.. m ] of real ;
b:array [1..m] of real;
c:array [1..n] of real;
Источник: nickolay.info
Двумерные массивы паскаль
Двумерный массив в Паскале представляет собой таблицу, состоящую из нескольких одномерных массивов. Двумерные массивы Pascal называют матрицей. Положение элементов в матрице обозначается двумя индексами.
Рассмотрим матрицу 3*3, то есть она будет состоять из 3 строк и 3 столбцов:
Каждый элемент обладает 2-мя индексами. Первый — номер строки, в котором располагается элемент, а второй – номер столбца. Следовательно, индекс элемента определяется местом пересечением столбца и строки . Например, a13 – это элемент, стоящий в первой строке и в третьем столбце массива.
Описание двумерного массива Паскаля.
Имеется ряд методов объявления двумерного массива.
Рассмотри способ, в котором указывается тип элемента и переменные.
Type Vector = array [1..9] of ; Matrix= array [1..4] of vector; Var mas: matrix;
В данном варианте матрица mas состоит из 4 строк, в каждой из которых 9 столбцов. При этом мы можем обратиться к любой i -й строке через mas [ i ], а к j -му элементу внутри i строки – m [ i , j ].
Во втором и третьем способе матрицу можно задать в одну строку.
Type Matrix= array [1..4] of array [1..9] of < тип элементов >; или еще проще: type matrix = array [1..4, 1..9] of ;
Как и в предыдущем варианте, матрица имеет 4 строки и 9 столбцов, обращение к какому-либо элементу массива имеет вид: mas [ i , j ]. Значит, что элемент, расположен в i -й строке и j -м столбце. Важно не перепутать строки со столбцами, иначе произойдет ошибка в ответе.
Основные действия с двумерными массивами Паскаля
Все основные действия над матрицами выполняются поэлементно, причем типы данных элементов должны быть одинаковыми. То есть, если матрица состоит из чисел, то действия можно выполнять только с числами. Однако для реализации операции присваивания массивам достаточно быть одного размера. Например, дан массив
type matrix= array [1..4, 1..9] of integer; var a , b : matrix ;
в ходе выполнения такой программы матрице а можно присвоить значения матрицы b ( a := b ).
Ввод двумерного массива Паскаля.
Для поочередного ввода элементов в матрицу необходимо перебрать элементы с 1-го столбца 1-ой строки до последнего столбца последней строки. Для этого используется два оператора цикла for, причем один вложен в другой.
Проанализируем образец ввода двумерного массива Паскаля с клавиатуры:
type matrix= array [1..4, 1..9] of integer; var a, : matrix; i, j: integer; < индексы массива >begin for i :=1 to 4 do for j :=1 to 9 do readln ( a [ i , j ]);
Вывод двумерного массива Паскаля на экран.
При выводе элементы должны печатать по порядку индексов, то есть в строках элементы стоят друг за другом, а в столбах один под другим. Для этого необходимо написать следующие элементы кода:
for i :=1 to 4 do begin for j :=1 to 9 do write ( a [ i , j ]:3); writeln ; end ;
Примечание! Использовать операторы readln ( a [ i , j ]), writeln именно в таком виде, в противном случае компилятор не сможет считать и напечатать элемент. Ввод в программу операторов в таком виде readln (a), writeln (a) не допустим, так как а – это переменная типа массив.
Представление двумерного массива Паскаля в памяти
В памяти ЭВМ элементы двумерного массива располагаются последовательно и занимают несколько байт. Например, элементы массива типа integer, будут занимать по 2 байта. А весь массив займет S^2 байта, где S – количество элементов в массиве.
В матрице для каждого элемента типа integer потребуется 2 байта памяти. Рассмотрим пример.
Matrix = array [1..4, 1..3] of integer ;
В данном случае необходимо 24 байт памяти.
Модель размещения массива M типа matrix в памяти.
Для любого элемента предоставляется две ячейки памяти, размещение осуществляется от первой строки до нижней, в порядке изменения индекса.
Между переменной и адресом ячейки устанавливается соответствие, однако, при объявлении матрицы программе известно только адрес начала массива, к остальным элементам адрес вычисляется по формуле:
Addres + SizeElemt * sum *( I -1)+ SizeElem *( J -1),
где Addres – местоположение первого элемента, выделенного для массива; I , J – индексы элемента в двумерном массиве; SizeElemt – размер элемента массива (например, 2 байта для элементов типа integer ); sum – количество элементов в строке.
SizeElemt * sum *( I -1)+ SizeElemt *( J -1) — смещение относительно начала массива.
Какой размер памяти выделяется для массива?
Чтобы программа работала нормально, компьютер выделят память сегментами по 64 Кбайт. Один из сегментов отводится для данных, которые обрабатываются программой. Для каждой переменной отводится свой сегмент. Например, если переменная состоит из массива, то он не сможет занимать места больше, чем 65536 байт. Естественно, кроме массива в сегменте могут находится и другие переменные, поэтому объем памяти вычисляется по формуле 65536- S , где S – размер памяти, ранее отведенные под другие переменные.
Рассмотрим пример, в котором:
Type myArray= array [1..50000] of integer;
С точки зрения синтаксиса запись верная, но компилятор выдаст ошибку об объявлении слишком длинного массива.
Можно без труда подсчитать количество элементов, которые допустимы по формуле: 65536/2 –1=32767. Однако, других переменных не должно быть. Матрицы обладают еще меньшими пределами индексов.
Решим задачу с двумерным массивом Паскаля.
Задача: Вычислить произведение ненулевых элементов матрицы.
Решение:
- Для начала нужно установить переменные: матрицу, состоящую из целочисленных элементов; P – произведение элементов, не равное 0; I , J – индексы массива; N , M – количество строк и столбцов в матрице.
- Входные данные N , M пусть вводятся с клавиатуры, а матрица зададим с помощью функции random ().
- Выходными параметром получим P (произведение).
- Выведем матрицу на экран, для проверки работы программы.
А теперь поговорим о процедурах.
Примечание! Тип массива должен быть определен заранее. Например:
Type Matrix=array [1..10, 1..10] of integer; . procedure primer (a: matrix); .
Для того чтобы вводимая матрица была передана в программу как результат следует воспользоваться процедурой vvod , В таком случае матрица будет передаваться по ссылке. В таком случае процедура выглядит следующее:
Procedure vvod ( var m : matrix );
Print – процедуры вывода на экран матрицы, которая передается по значению.
Procedure print ( m : matrix );
Для реализации вложенных циклов внутри процедуры нужно ввести счетчики – k и h . Алгоритм вывода матрицы на экран был описан выше, используем это описанием.
Итак, опишем ход выполнения программы.
- Ввод значений N и M ;
- Обращаемся к процедурам vvod ( a ) и print ( a ) для ввода и вывода матрицы соответственно, где а – матрица;
- Переменной, которая отвечает за произведение P, присвоим значение 1;
- Поочередно перебираем элементы матрицы с индексом 11 до элемента с индексом Каждый элемент матрицы должен удовлетворять условию: если a ij ? 0, то произведение P умножаем на элемент a ij ( P = P * a ij );
- Выводим на экран результат произведения ненулевых элементов матрицы – P
Program proizvedenie; Type Matrix=array [1..10, 1..10] 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 For j :=1 to m do M[i,j]:= 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[i, j]: 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[i, j]<>0 then p:=p*a[i, j]; Writeln ( p ); End .
Источник: gospodaretsva.com
Матрицы в Pascal
Распространённое понятие в программировании. Матрицы имеют огромное поле для их применения.
Матрицы в программировании рассматриваются как двумерный массив. Это массив состоящих из нескольких строк и столбцов.
В Pascal матрица описывается так же, как и массив.
Реализация матрицы в Pascal
Randomize; For i := 1 To N Do For j := 1 To N Do Begin A[i,j] := Random(100); Write(A[i,j]); End;
Доступ к элементам матрицы осуществляется по номеру строки и номеру столбца. В программе это реализуется с помощью вложенного цикла.
Матрицу можно обрабатывать как по строкам, так и по столбцам.
Для матрицы справедливы те же алгоритмы, что и для одномерных массивов. Необходимо помнить только о том, что доступ к элементам осуществляется по двум индексам в цикле.
Источник: bigspawn.blogspot.com