Програмування операцій з квадратними масивами(матрицями) Pascal

Програмування  операцій з квадратними  масивами(матрицями)

Як було зазначено вище, одновимірні масиви застосовуються для зберігання послідовностей. Проте для багатьох структур даних зображення у вигляді послідовності є неприйнятним. Наприклад, результати матчів футбольного чемпіонату найзручніше подавати у вигляді квадратної таблиці. Для зберігання таких структур даних застосовують багатовимірні масиви, серед яких найбільш широко використовуються двовимірні масиви (матриці). У даному розділі розглядаються базові операції над елементами двовимірних масивів, а також техніка програмного розв'язування деяких матричних задач лінійної алгебри.

Базові операції обробки двовимірних масивів

Наведемо спочатку перелік базових операцій над матрицями та їх елементами. До таких операцій належать:

• введення та виведення матриць;
• створення нової матриці за заданим алгоритмом;
• пошук елементів матриці за певним критерієм;
• визначення, чи задовольняє матриця або окремі її елементи певній властивості;
• виконання певних операцій над компонентами матриць (переставлення рядків і стовпців, множення матриць тощо).

Оголошення багатовимірних масивів. Доступ до елементів

Розглянемо прямокутну таблицю з m х n однотипних елементів, що містить m рядків та n стовпців. У математиці таку таблицю називають матрицею, а дані, що їх містить матриця, - елементами. У програмуванні матричні структури називаються двовимірними масивами.

Наведемо синтаксис оголошення змінної матричного типу в мові Pascal:

<ім'я матриці>:аrrау[<нижній індекс рядка>..<верхній індекс рядка>,<нижній індекс стовпця>..<верхній індекс стовпця>] of <тип елементів>;

У цьому оголошенні array, of — зарезервовані слова, <тип елементів> - будь-який тип, крім файлового, <нижній індекс рядка> і <верхній індекс рядка>— константи, що визначають межі діапазону допустимих значень індексу рядка, а <нижній індекс стовпця> та <верхній індекс стовпця> — константи, що визначають межі діапазону допустимих значень індексу стовпця. Масиви, що мають більш ніж два виміри, оголошуються в аналогічний спосіб.

Зазначимо, що, як і будь-який тип даних користувача, тип двовимірного масиву можна оголосити також в розділі type окремо від оголошення змінної матричного типу.

Наведемо приклади оголошень багатовимірних масивів. Нагадаємо, що обсяг сегмента пам'яті, де будуть зберігатися дані Pascal-програми, становить 64 Кбайт, і тому під час визначення розміру масиву необхідно враховувати можливість переповнення пам'яті.

const k=10; m=20; n=5;
type TMatrix=array[1..k,1..m] of integer;
var a:TMatrix;
  b:array[1..n,1..n] of real;
  c:array[1..4,1..3] of char;
  d:array[byte,1..2] of integer;
  mat:array[1..3,5..10,2..4] of integer;

Доступ до елементів матриці здійснюється операцією індексування [ ] за двома індексами, які визначають номер рядка та номер стовпця елемента. Синтаксис операції індексування є таким:

<ім'я масиву>[<номер рядка>,<номер стовпця>]

Зазначимо, що доступ до елементів масивів, які мають більш ніж два виміри, здійснюється також із застосуванням операції індексування. Але її операндами є більш ніж два індекси. Тепер дамо приклади індексування елементів оголошених вище масивів.

с[4,3]:='С';
mat[2,6,3]:=a[k,m]+d[0,2];

Перейдемо до розгляду форм зображення багатовимірних масивів. Як вже зазначалось, природною формою зображення двовимірного масиву вважається таблиця. Для прикладу на рис. 7.16 зображено масив, що може бути оголошений як
а:аrrау[1..4,1..4] of integer.

Рис. 7.16. Двовимірний масив розмірністю 4x4

Природне зображення багатовимірного масиву має суттєво відрізнятися від його зображення в оперативній пам'яті, адже оперативна пам'ять має лінійну структуру. За яким же принципом елементи матриці розташовуються в пам'яті комп'ютера? Спочатку у послідовних комірках записуються всі елементи першого рядка, потім у подальших послідовних комірках записуються елементи другого рядка і т. д., поки не буде вичерпано всі елементи. Розмір оперативної пам'яті визначається при оголошенні багатовимірного масиву і не змінюється під час роботи з ним.

На рис. 7.18 подано зображення в оперативній пам'яті двовимірного масиву
а:аrrау[1..4,1..4] of integer.

Рис. 7.18. Зображення матриці в оперативній пам'яті

Тепер розглянемо типові алгоритмічні схеми обробки елементів матриці з метою подальшого застосування цих схем до розв'язання матричних задач. Зробимо загальне зауваження: однотипну обробку всіх елементів деякої матриці найлегше здійснити шляхом її обходу за рядками або стовпцями. Тобто спочатку обробляються всі елементи першого рядка (стовпця), потім — всі елементи другого рядка (стовпця) і т. д. Найпростішим методом реалізації такого обходу є використання вкладених циклів for. Отже, перейдемо до розв'язання базових матричних задач.
Введення матриці є достатньо очевидною операцією:

var
  a:array[1..5,1..5] of integer;
  i,j:integer;
begin
  for i:=1 to 5 do
    for j:=1 to 5 do
      readln(a[i,j]);
end.

Стосовно виведення матриці слід зауважити, що у вікні результатів програми елементи матриці мають подаватись у вигляді таблиці. Тому переводити курсор на новий рядок слід лише після виведення всіх елементів поточного рядка:

var
  a:array[1..5,1..5] of integer;
  i,j:integer;
begin
  for i:=1 to 5 do
    begin
      for j:=1 to 5 do
        write(a[i,j],' ');
      writeln;
    end;
end.

Аналогічну структуру має код, що ініціалізує всі елементи матриці деякими значеннями:

var
  a:array[1..5,1..5] of integer;
  i,j:integer;
begin
  for i:=1 to 5 do
     for j:=1 to 5 do
       a[i,j]:=10;
end.

Одна з типових задач — пошук максимального або мінімального елемента матриці. Розв'язання цієї задачі нічим принципово не відрізняється від розв'язання аналогічної задачі для одновимірних масивів. У програмі ех7_13 здійснюється пошук значення та індексів максимального елемента матриці, яка ініціалізується випадковими числами. Максимальний елемент запам'ятовується у змінній max, індекс рядка, в якому розташований цей елемент, — у змінній іmах, а індекс стовпця — у змінній jmax.

---

Приклад 7.14

Program EX7_13;
var a:array[1..5, 1..5] of integer;
  i,j,imax,jmax:integer;
  max:integer;
begin
  randomize;
  for i:=1 to 5 do
    for j:=1 to 5 do
      a[i,j]:=random(20);
      max:=a[1,1];
  for i:=1 to 5 do    for j:=1 to 5 do      if max<a[i,j] then        begin
          max:=a[i,j];
          imax:=i;
          jmax:=j;
        end;
end.

---

Потреба у перестановці або обміні значеннями між двома елементами багатовимірного масиву виникає, насамперед, у задачах упорядкування. У деяких задачах переставляють рядки або стовпці.

Перестановку рядків або стовпців можна виконати лише шляхом послідовних перестановок відповідних елементів. Наведемо фрагмент коду, що демонструє перестановку першого та п'ятого стовпців матриці. Нагадаємо, що для обміну значеннями між двома елементами слід використовувати допоміжну змінну.

var a:array[1..5, 1..5] of integer;
  i,tmp:integer;
begin
  for i:=1 to 5 do    begin
      tmp:=a[i,1];
      a[i,1]:=a[i,5];
      a[i,5]:=tmp;
    end;
end.

Розглянемо такі операції, як вставка та видалення даних у багатовимірних масивах. Вставка та видалення окремих елементів матриці є, загалом, некоректними операціями, оскільки вони призводять до невизначеності щодо поведінки інших елементів: незрозуміло, слід зсувати елементи стовпця чи рядка, в яких відбувається вставка або видалення, чи здійснювати якийсь інший зсув. Тому найчастіше під час перетворення матриць операцію вставки або видалення поширюють на цілий рядок або стовпець. Але нагадаємо, що у будь-яких масивах будь-якої вимірності кількість елементів, яка була вказана під час оголошення, змінюватись не може. Тому вставка рядка або стовпця можлива тільки в межах оголошеної кількості рядків або стовпців. Видалення заданого рядка матриці демонструє програма ех7_14.

---

Приклад 7.15

Program EX7_14;
var a:array[1..5,1..5] of integer;
  i,j,k,n,m:integer;
begin
  writeln('enter number comb and column');
  readln(n,m);
  randomize;
  for i:=1 to n do
    for j:=1 to m do
      a[i,j]:=random(20);
  writeln('enter number comb for delete');
  readln(k);
  for i:=k to n-1 do    for j:=1 to m do
      a[i,j]:=a[i+1,j];
  n:=n-1;
end.

Цикл видалення k-го рядка працює так: на місце k-го рядка записують рядок k + 1, на місце (k + 1)-гo рядка - рядок k + 2 і т. д., доки не буде вичерпано всі рядки. Оскільки обсяг пам'яті, що виділена під масив, під час його обробки не змінюється, то при видаленні будь-якого елемента масиву останній елемент буде дублюватися. Тому по завершенні циклу видалення слід зменшити на одиницю задану раніше кількість рядків.

Program MATRIX; {Найменування програми}

Uses CRT;

var i1, i2, i3: integer; {Лічильник рядків}

j1, j2, j3: integer; {Лічильник стовпців}

operation: integer; {Варіант розвитку програми}

det: real; {Визначник} k: integer; {Робоча змінна}

{Масиви (матриці), що використовуються в програмі}

MAS1, {Матриця А} MAS2, {Матриця В} MAS3: array [1 .. 10,1 .. 10] of real; {Матриця С}

BEGIN {Початок програми}

WriteLn ('Що Ви бажаєте робити з матрицями?');

{Вибір користувачем варіанту розвитку програми}

WriteLn ('Якщо Ви бажаєте знайти визначник матриці, натисніть 1');

WriteLn ('Якщо Ви бажаєте знайти зворотну матрицю, натисніть 2');

WriteLn ('Якщо Ви бажаєте транспонувати матрицю, натисніть 3');

WriteLn ('Якщо Ви бажаєте скласти матриці, натисніть 4');

WriteLn ('Якщо Ви бажаєте відняти матриці, натисніть 5');

WriteLn ('Якщо Ви бажаєте перемножити матриці, натисніть 6');

ReadLn (operation); {Занесення обраного варіанту в пам'ять}

WriteLn ('Введіть кількість рядків матриці, не більше 10');

ReadLn (m1);

WriteLn ('Введіть кількість стовпців початкової матриці, не більше 10');

ReadLn (n1);

If ((1> n1) or (n1> 10) or (1> m1) or (m1> 10)) {Умови помилки}

then begin  WriteLn ('ПОМИЛКА !!!');  end

else begin  WriteLn ('Введіть початкову матрицю'); {Введення вихідної матриці}

for i1: = 1 to m1 do

for j1: = 1 to n1 do Read (MAS1 [i1, j1]);  end;

for i1: = 1 to m1 do {Відповідь вихідної матриці}  begin

for j1: = 1 to n1 do  Write (MAS1 [i1, j1]);  WriteLn;  end;

Case operation of {Оператор вибору «operation»}

1: begin {Визначник}

if (m1 <> n1) then writeLn ('ПОМИЛКА !!!') {Умова помилки}  else

begin {Формула визначника}

det: = (MAS1 [1,1] * MAS1 [2,2] * MAS1 [3,3]+ MAS1 [2,1] * MAS1 [3,2] * MAS1 [1,3] + MAS1 [1,2] * MAS1 [2,3] * MAS1 [3,1])- (MAS1 [3,1] * MAS1 [2,2] * MAS1 [1,3]+ MAS1 [3,2] * MAS1 [2,3] * MAS1 [1,1]+ MAS1 [2,1] * MAS1 [1,2] * MAS1 [3,3]);

WriteLn ('Визначник матриці розміром 3х3, det =', det); {Висновок визначника}  end;  end;

2: begin {обернена матриця}

if (m1 <> n1) then WriteLn ('ПОМИЛКА !!!') {Умова помилки}  else begin  {Визначник}

det: = (MAS1 [1,1] * MAS1 [2,2] * MAS1 [3,3] + MAS1 [2,1] * MAS1 [3,2] * MAS1 [1,3]+ MAS1 [1,2] * MAS1 [2,3] * MAS1 [3,1])- (MAS1 [3,1] * MAS1 [2,2] * MAS1 [1,3]+ MAS1 [3,2] * MAS1 [2,3] * MAS1 [1,1]+ MAS1 [2,1] * MAS1 [1,2] * MAS1 [3,3]);

if det = 0 then WriteLn ('ПОМИЛКА !!!') {Умова помилки} else begin {Союзна матриця}

for i1: = 1 to m1 do

for j1: = 1 to n1 do MAS2 [i1, j1]: = MAS1 [j1, i1]; {Підсумкова формула}

for i1: = 1 to m1 do

for j1: = 1 to n1 do MAS3 [i1, j1]: = (1/det) * MAS2 [i1, j1];

WriteLn; WriteLn ('обернена матриця:');

for i1: = 1 to m1 do begin {Відповідь оберненої матриці}

for j1: = 1 to n1 do

Write (MAS3 [i1, j1]);   WriteLn;  end;    end;    end;  end;

3: begin {Транспонування матриці}

for i1: = 1 to m1 do

for j1: = 1 to n1 do MAS2 [i1, j1]: = MAS1 [j1, i1]; {Формула}

WriteLn ('Транспонована матриця:');

for i1: = 1 to m1 do begin {Відповідь транспонованої матриці}

for j1: = 1 to n1 do

Write (MAS2 [i1, j1]);  WriteLn;  end;  end;

4,5: begin {Додавання / віднімання матриць} {Введення другої матриці}

WriteLn ('Введіть кількість рядків другої матриці');  ReadLn (m2);

Writeln ('Введіть кількість стовпців другого матриці');  ReadLn (n2);

If (n2 <> n1) or (m2 <> m1)  then WriteLn ('OSHIBKA !!!') {Умова помилки}  else begin

WriteLn ('Введіть другу матрицю');

for i1: = 1 to m1 do

for j1: = 1 to n1 do

Read (MAS2 [i1, j1]);  end;

for i1: = 1 to m1 do {Вигляд другої матриці}  begin

for j1: = 1 to n1 do  Write (MAS2 [i1, j1]);  WriteLn; end;

if operation = 4 then k: = 1;

if operation = 5 then k: = -1;

for i1: = 1 to m1 do

for j1: = 1 to n1 do

MAS3 [i1, j1]: = MAS1 [i1, j1] + k * MAS2 [i1, j1]; {Підсумкова формула}

writeln ('Сума / різниця:');

for i1: = 1 to m1 do begin

for j1: = 1 to n1 do Write (MAS3 [i1, j1]);  WriteLn; end;    end;

6: begin {Множення матриць}  {Введення другого матриці}

WriteLn ('Введіть кількість рядків другий матриці');  ReadLn (m2);

Writeln ('Введіть кількість стовпців другого матриці');  ReadLn (n2);

If ((1> = m2) or (m2> = 10) or (1> = n2) or (n2> = 10) {Умова помилки}

or (n2 <> m1)) then WriteLn ('ПОМИЛКА !!!')  else begin

WriteLn ('Введіть другу матрицю');

for i2: = 1 to m2 do

for j2: = 1 to n2 do Read (MAS2 [i2, j2]);  end;

for i2: = 1 to m2 do begin {Вигляд другої матриці}

for j2: = 1 to n2 do  Write (MAS2 [i2, j2]);   WriteLn;  end;

m3: = m1; n3: = n2;

for i3: = 1 to m3 do

for j3: = 1 to n3 do begin   MAS3 [i3, j3]: = 0;

for i2: = 1 to m2 do   {Підсумкова формула}

MAS3 [i3, j3]: = MAS3 [i3, j3] + MAS1 [i3, i2] * MAS2 [i2, j3];

end;

begin {Вигляд добутку матриць}

writeln;

writeln ('Добуток двох матриць:');

for i3: = 1 to m1 do begin

for j3: = 1 to n2 do Write (MAS3 [i3, j3]);

WriteLn;

end; end;  end;  end; {End Case}

END. {Кінець програми}

http://vvpc.com.ua/tests_informatiks/inform/osnovy_program/7/2.htm