Работа с двумерными массивами( матицы)

Пример 5.13 Сформировать единичную матрицу е размером n на n.

Единичной называется квадратная матрица, на главной диагонали которой элементы равны единице, а все остальные элементы равны нулю. е_ij = 1, если i = j, иначе е_ij = 0.

Алгоритм решения этой задачи включает в себя: ввод размера матрицы n; формирование матрицы; вывод результата расчета на экран дисплея.

program matr1;

uses crt;

const size =10;

var i,j,n: integer;

e: array [1..size,1..size] of integer;

Begin

write('Введите размер матрицы');

readln(n);

for i:= 1 to n do

for j:= 1 to n do

if i = j then e[i,j]:= 1

else e[i,j]:= 0;

clrscr;

gotoxy(3,3);

write(' Единичная матрица размером ', n, ' на ',n);

for i:= 1 to n do

for j:= 1 to n do

Begin

gotoxy(3*i,5 + j);

write(e[i,j])

End

End.

Индексы i и j определяют но­мер строки и столбца, на пересече­нии которых находится каждый эле­мент матрицы, и кроме этого опре­деляют положение курсора на экра­не в процедуре gotoxy(3*i,5+j).

Пример 5.14 Написать програм­му сложения двух матриц. Две матрицы можно сложить, если они имеют одинаковый размер. В результате получается матрица тако­го же размера, каждый элемент которой равен сумме соответствующих элементов исходных матриц: с_ij = а_ij + b_ij. Алго­ритм решения задачи содержит следующие этапы: ввод исходной матрицы а; ввод исходной матрицы b; расчет элементов матрицы с и вывод результата на экран дисплея.

program clgmatr;

uses crt;

const line = 20; column = 30;

type t = array[1..column] of real;

Var

i,j,n,m: integer;

a,b,c: array [1..line] of t;

Begin

clrscr;

write('Число строк матрицы (менее 21)'); readln(n);

write('Число столбцов матрицы (менее 31)'); readln(m);

clrscr; {Ввод матрицы а}

for i:=1 to n do

for j:=1 to m do

Begin

write('a[',i,',',j,']');

readln(a[i,j])

end;

clrscr; {Ввод матрицы b}

for i:=1 to n do

for j:=1 to m do

Begin

write('b[',i,',',j,']');

readln(b[i,j])

end;

clrscr; {Расчет и вывод матрицы с}

for i:=1 to n do

Begin

for j:=1 to m do

Begin

c[i,j]:= a[i,j] + b[i,j];

write(c[i,j]:6:2);

end;

Writeln

end;

Repeat until keypressed

End.

В программе определен новый тип данных - массивовый, состоящий из 30 элементов вещественного типа.

Для того, чтобы каждая строка матрицы с выводилась на экране с новой строки, в цикл по i включен пустой оператор вывода writeln.

Функция keypressed из модуля crt дает значение true, если в буфере input не осталось несчитанных символов, и false в противном случае. Цикл repeat until keypressed включен в программу для задержки изображения на экране вывода. Цикл repeat... until будет работать до тех пор, пока не будет нажата какая-либо клавиша.

Пример 5.15 Написать программу умножения двух матриц. Перемножить две матрицы можно лишь в том случае, если число столбцов первой матрицы равно числу строк второй матрицы. Если первый сомножитель, матрица а, имеет размер m на p, второй сомножитель, матрица в, имеет размер р на n, то в результате расчета получится матрица с размером m на n, каждый

_р

элемент которой с_ij: =Sa_ik*b_kj.

^k=1

program umnmatr;{Умножение матриц}

Сonst

m = 4; р = 3; n = 5;

Var

i: 1..m;

j: 1..n;

i: 1..P;

a: array [1..m,1..p] of real;

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

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

begin {Ввод матрицы а}

for i:= 1 to m do

for k:= 1 to p do

Begin

write('a[',i,',',k,']');

readln(a[i,k])

end;

for k:= 1 to p do { Ввод матрицы b}

for j:= 1 to n do

Begin

write('b[',k,',',j,']');

readln(b[k,j])

end;

for i:= 1 to m do { Умножение}

Begin

for j:= 1 to n do

Begin

c[i,j]:= 0;

for k:= 1 to p do

c[i,j]:=c[i,j] + a[i,k] * b[k,j];

end;

end;

writeln('Результат'); {Вывод матрицы}

for i:= 1 to m do

Begin

for j:= 1 to n do write(c[i,j]:8:2);

Writeln

end;

End.

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

Сортировка – это расположение чисел в порядке возрастания или убывания.

Сортировка методом "пузырька"

Пусть дано n чисел, которые необходимо расположить (для определенности) в порядке возрастания. При упорядочении выполняются следующие операции:

1) числа сравниваются попарно: первое со вторым; второе с третьим; i -тое – с (i +1) - тым;

2) если меньшее стоит в паре на втором месте (числа в паре не упорядочены по возрастанию), то сравниваемые числа меняются местами.

За один такой просмотр массива минимальное число "вытолкнется", по крайней мере, на одно место вверх (вперед), а максимальное – переместится в самый конец (вниз), т.е. минимальное число как легкий пузырек воздуха в жидкости постепенно "всплывает" в начало последовательности. Отсюда – название метода. За n- 1 просмотр произойдет полное упорядочение массива при любом исходном расположении чисел в нем. Рассмотрим работу метода на примере, приведенном на рис. 5.5.

 

								Исходный массив
								Перестановки в первом просмотре
								После первого просмотра
						31
								Перестановки во втором просмотре
								После второго просмотра
					26	31
								Перестановки в третьем просмотре
								После третьего просмотра
				19	26	31
								Перестановки в четвертом просмотре
								После четвертого просмотра
			13	19	26	31
В пятом просмотре перестановок нет. Сортировка окончена.
								Отсортированный массив

Рисунок 5.5 - Иллюстрация метода сортировки "пузырьком"

Program Sort;

Const

Nmax = 100;

Var

X: Array [1..Nmax] Of Real;

A: Real;

n, k, i: Integer;

Begin

Writeln('Введите количество чисел');

Readln(n);

Writeln('Введите массив чисел');

For i:= 1 To n Do

Read (X[i]);

For k:= 1 To n-1 Do{ Сортировка }

For i:= 1 To n-1 Do

If X[i] > X[i+1] Then

Begin

A:=X[i];

X[i]:=X[i+1];

X[i+1]:=A

End;

Writeln('Отсортированный массив чисел:');

For i:=1 To n Do

Write (X[i]);

End.

Глубину просмотра можно уменьшать, основываясь на том, что большие числа "опускаются" вниз (в конец последовательности) и затем не переставляются:

For k:= 1 To n-1 Do

For i:= 1 To n-k Do

If X[i] > X[i+1] Then

........

Сокращение количества просмотров улучшает временные характеристики метода. Из алгоритма можно понять, что если на одном из просмотров не было перестановок, то их не будет и потом – данные уже отсортированы, процесс сортировки следует закончить. Такой подход дает значительную экономию времени при работе с большими "почти отсортироваными" массивами. Примером такого массива может быть упорядоченный по алфавиту список сотрудников фирмы, на которую время от времени принимают новых работников.

Приведем алгоритм для этого метода.

В этом алгоритме используется переменная "Перестановка_есть", которой сначала присваивается значение "истина", а как только в одном из просмотров не будет перестановок – ей присвоится значение "ложь". Это позволит прервать выполнение цикла "Пока".

Program SortUsk;

Const

Nmax = 100;

Var

X: Array [1..Nmax] Of Real;

A: Real;

P: Boolean;

L, K, I, N: Integer;

Begin

Writeln('Введите количество чисел');

Readln(n);

Writeln('Введите массив чисел');

For i:= 1 To n Do

Read(X[i]);

P:= True; {Перестановка есть}

K:= 1; {Номер просмотра}

While P Do

Begin

L:=0; {Кол. перестановок}

For i:= 1 To n-k Do

If X[i] > X[i+1] Then

Begin

A:= X[i];

X[i]:=X[i+1];

X[i+1]:=A;

L:=L+1

End;

If L=0 Then

P:=False;

k:=k+1;

End;

Writeln('Отсортированный массив чисел');

For i:= 1 To n Do

Write(X[i]);

End.

Сортировка выбором

Пусть дан одномерный неупорядоченный массив, содержащий целые числа М={m_i}, i=1,n; n - число элементов. Необходимо упорядочить элементы этого массива по возрастанию их значений.

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

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

Пример 5.16 Программа сортировки выбором

Uses crt;

Var

M:array[1..1000] of integer;

n, i, j, Min, i_min:integer;

Begin

Clrscr;

Write(' Введите длину массива n = ');

Readln(n);

{ Вместо ввода с клавиатуры заполним массив случайными числами из диапазона от 0 до 500}

For i:=1 to n do M[i]:=Random(500);

For i:=1 to n-1 do

Begin

{принимаем за минимум i-й элемент}

Min:=M[i]; i_min:=i;

For j:=i+1 to n do

If M[j]<Min then

Begin

{найдено меньшее число - запоминаем его и его адрес}

Min:=M[j]; i_min:=j;

End;

{Обмен}

M[i_min]:=M[i];

M[i]:=Min;

End;

Writeln(' Упорядоченный массив');

For i:=1 to n do write(M[i],' ');

readkey;

End.

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

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

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

Пример 5.17 Программа обменной сортировки

Uses crt;

Var M:array[1..1000] of integer;

i,Z,n:integer; Key:byte;

Begin Clrscr;

{Ввод n и формирование массива М как в предыдущей программе}

Repeat

Key:=0;

For i:=1 to n-1 do

If M[i] > M[i+1] then

Begin

Z:=M[i];

M[i]:=M[i+1];

M[i+1]:=Z;

Key:=1;

end;

Until Key=0;

Writeln(' Упорядоченный массив');

For i:=1 to n do write(M[i],' '); readkey;

End.

Сортировка слиянием

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

Поскольку мы пока не знакомы с работой с файлами в ТР, рассмотрим алгоритм сортировки слиянием на примере слияния двух предварительно упорядоченных массивов Х и Y в один массив Z. Данные в массивах расположены в порядке возрастания их значений.

Обзначим через переменные dx, dy - длину (размер) массивов X, Y соответственно. Переменные ix, iy - счетчики (адреса) тех же массивов. Переменная iz - счетчик числа элементов нового массива Z.

Пример 5.18 Программа сортировки слиянием

Uses crt;

Var { Описание массивов и переменных}

X, Y: array[1..1000] of integer;

Z: array[1..2000] of integer;

dx,dy,ix,iy,iz,i:integer;

Begin Clrscr; { Ввод данных}

Write(' Введите длину массива Х '); readln(dx);

Writeln(' Введите упорядоченный по возрастанию массив Х');

For i:=1 to dx do read(X[i]); readln;

Write(' Введите длину массива Y '); readln(dy);

Writeln(' Введите упорядоченный по возрастанию массив Y');

For i:=1 to dy do read(Y[i]); readln;

ix:=1; iy:=1; iz:=0;

While (ix<=dx) and (iy<=dy) do

if X[ix]<Y[iy] then

begin {Перезапись значения из массива Х в массив Z}

inc(iz); Z[iz]:=X[ix]; inc(ix);

End

Else

begin {Перзапись значения из массива Y в массив Z}

inc(iz); Z[iz]:=Y[iy]; inc(iy);

end;

{ Один из массивов полностью переписан }

if ix>dx then { Переписан массив Х, дописываем все оставшееся из Y}

for i:=iy to dy do

Begin

inc(iz); Z[iz]:=Y[i];

End

else { Переписан массив Y, дописываем все оставшееся из X }

for i:=ix to dx do

Begin

inc(iz); Z[iz]:=X[i];

end;

{ Вывод результата слияния на экран}

writeln(' Полученный массив Z');

for i:=1 to iz do write(Z[i],' '); readln;

End.

Строковые типы

Данные строкового типа - это последовательность символов переменной длины. Такой тип еще называют типом string. Он во многом похож на одномерный массив символов, однако, в отличие от последнего, количество символов в строке-переменной может меняться от 0 до N, где N -максимальное количество символов в строке.

Описание строкового типа состоит из ключевого слова string, после которого в квадратных скобках указано максимальное количество символов строк» данного типа. Это количество может выражаться с помощью целой константы или имени целой константы. Если максимальный размер строки не указав, то он автоматически принимается равным 255 - максимально возможная длина строки. (Существуют еще ASCIIZ-строки, длина которых может достигать 65536 символов, но для работы с такими строками нужна особая директива компилятору). Длина переменной такого типа может динамически изменяться между 1 и значением константы. Символы в строке следует воспринимать как пронумерованные в интервале от 1 до значения константы.

П ример:

tyре

cities = string [20];

names = string [12].

Переменные типа cities - строкового типа, то есть строки символов, состоящие максимально из 20 символов. Переменные типа names максимально могут состоять из 12 символов. Переменные можно объявить следующим образом:

var

ci: array [1..20] of char;

na: array [1..12] of char.

В этом случае говорят, что ci и nа - символьные вектора. Символьные вектора можно рассматривать как строковые переменные, представляющие последовательности постоянной длины. Благодаря такой интерпретации имена cимвольных векторов и имена их элементов могут использоваться в строковых выражениях там, где могут использоваться имена строковых переменных.

Каждая величина строкового типа занимает в памяти на один байт больше, чем максимальное количество символов в строке данного типа. В дополни­тельном байте хранится информация о текущей длине строки. Если n - текущая длина строки, то в компоненте 0 помещается номер n последнего символа относительно начала строки.

Тип данных string предназначен для обработки строк. С данными типа string связан целый набор операций. Строки могут выводиться на экран монитора посредством стандартных процедур Write и Writeln и вводиться с помощью стандартных процедур Read и Readln. Следующая программа демонстрирует считывание строки.

program string_test;

var s: string[10];

Begin

writeln('Задайте несколько символов');

readln (s);

writeln(s,' длина:', ord(s[0]):5);

End.

В этом примере при вводе можно записать сколько угодно символов, но с помощью readln(s) можно считать максимум 10 символов, так как по описанию переменная s может содержать максимум 10 символов. Прочие символы игнорируются. Считываемых символов может быть и меньше 10.

Операции над строками

Строки можно присваивать, сливать и сравнивать.

Присваивание последовательности символов строковым переменным осуществляется с помощью оператора присваивания. С правой стороны оператора присваивания может находиться произвольное строковое выражение, а с левой имя строковой переменной.

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

str_1:= 'Это строка!'.

Присваиваемое значение строки, так же как и отдельный символ типа char, заключается в апострофы. Если апострофы опущены, то компилятор рассматривает приведенный фрагмент текста как числовую величину или как идентификатор.

Второй подход обеспечивает доступ к отдельным символам строки по номеру их позиции:

str_1 [1] = 'Э'; str_1 [2]:='т'; sfr_1 [3]:= 'о'; str_1 [4]:=' ';

Str_1 [5] = 'с'; str_1 [6]:= 'т'; str_1 [7]:= 'p'; str_1 [7]:= 'о';

str_1 [8] = 'к';str_1 [9]:= 'a'; str_1 [10]:= '!'

Переменная str_1 приобретает то же самое значение, что и при первом подходе. Для доступа к отдельному символу в строке необходимо указать имя строки и в квадратных скобках номер позиции элемента (символа) в строке. При этом по отношению к отдельному символу строки возможны все те же операции, что и к переменной типа char. Необходимо напомнить, что, кроме классической записи символьной переменной в одинарных кавычках, Турбо Паскаль вводит еще две формы. Одна из них - представление символа его кодом ASCII с помощью специального префикса #, вторая, для управляющих символов, - значок " и буква алфавита с тем же номером (см. главу 1). При необходимости включения в строку управляющих кодов можно пользоваться "клавиатурными" обозначениями. В этом случае значение состоит как бы из склеенных кусков:

^G‘Пocлe сигнала нажмите '^J’ клавишу пробела '

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

Пример.

type

name = string [7]

var

fname, Iname: name;

begin

fname:= 'Наталья';

Iname:= 'Кучинская';

write (fname,' ',Iname)

end.

В результате выполнения программы будет выведено: Наталья Кучинск, так как максимальная длина строки 7. Согласно описанию

var a: string [5]; b: string [10];

можно присвоить значение b:= а, хотя типы переменных различны. При присвоении а:= b, в "а" запишутся только первые 5 символов строки "b".

Объединение двух строк в одну может быть осуществлено с помощью оператора конкатенации. Этот оператор записывается с помощью знака + (плюс). Объединенная строка представляет собой строку, состоящую из всех символов первой строки и следующих за ними всех символов второй строки. Например:

Выражение Результат

'adam' + 'eva' 'adameva'

'5' + '.' + '4' '5.4'

‘Это' + ' ' + 'строка' + '!' 'Это строка!'

Произвольные пары строк могут сравниваться с помощью операторов отношений. Две строки сравниваются посимвольно слева направо. При обнаружении первого несовпадающего символа принимается решение в соответствии с таблицей кодов ASCII. Отношение 'balkon' > 'balken' дает результат true, так как символ 'о' стоит в таблице кодов после символа 'е'. Отношение 'Pascal' = 'pascal' дает результат false, так как у прописной буквы код больше, чем у заглавной. Символ '+' стоит в таблице кодов перед символом '-', поэтому сравнение '+' < '-' дает в результате true.

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