69113

Багатовимірні масиви. Оголошення багатовимірних масивів. Доступ до елементів. Базові операції їх обробки двовимірних масивів. Двовимірні масиви в задачах

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-30

96.5 KB

6 чел.

Лекція 22. Тема: Багатовимірні масиви. Оголошення багатовимірних масивів.

                             Доступ до елементів.Базові операції їх обробки двовимірних масивів.

                             Двовимірні  масиви в задачах.

План:

1. Багатовимірні масиви

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

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

4. Двовимірні масиви в задачах лінійної алгебри

1. Багатовимірні масиви

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

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

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

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

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

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

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

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

const k=10; m=20; n=5;

type Tmatrix=array[1..k,1..m] of integer;   {200 елементів}

var   a:TMatrix;

       b:array[1..n,1..n] of real;                     {25 елементів}

       с:array[1..4,1..3] of char;                    {12 елементів}

       d:array[byte, 1..2] of integer;              {512 елементів}

       mat:array[1..3,5..10,2..4] of integer;   {54 елементи, тривимірний масив}

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

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

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

c[4,3]:’C’;

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

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

              

 Напрям зміни другого індексу

             

                       1           2           3             4

[1,1]

[1,2]

[1,3]

[1,4]

[2,1]

[2,2]

[2,3]

[2,4]

[3,1]

[3,2]

[3,3]

[3,4]

[4,1]

[4,2]

[4,3]

[4,4]

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

Приклад зображення тривимірного масиву наведено на рис 7.17.

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

Такий засіб зображення матриці в оперативній пам’яті дає можливість індексувати не тільки її елементи, але і цілі рядки. Наприклад, у випадку використання масиву a:array[1..4,1..4] of integer в результаті операції a[1]:=a[3] значення всіх елементів третього рядка будуть присвоєні відповінним елементам першого рядка. Водночас індексувати цілі стовпці матриці неможливо, що також пояснюється принципом збереження елементів матриці в оперативній пам’яті.

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

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

введення та виведення матриць;

створеня нової матриці за заданим алгоритмом;

пошук елементів матриці за певним критерієм;

визначення, чи задовольняє матриця або окремі її елементи певній властивості;

виконання певних операцій над компонентами матриць (переставлення рядків і стовпців, множення матриць тощо).

Тепер розглянемо типові алгоритмічні схеми обробки елементів матриці з метою  подальшого застосування цих схем до розв'язання матричних задач. Зробимо загальне зауваження: однотипну обробку всіх елементів деякої матриці найлегше здійснити шляхом її обходу за рядками або стовпдями. Тобто спочатку обробляються всі елементи першого рядка (стовпця), потім - всі елементи другого рядка (стовпня) і т. д. Найпростішим методом реалізації такого обходу є використання вкладених циклів 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              {внутрішній цикл по стовпцях}

  read (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;                    {альтернативи:a[i,j]:=random(20);

                                                                   a[i,j]:=i*j; тощо}

end.

Одна з типових задач — пошук максимального або мінімального елемента матриці. Розв'язання цієї задачі нічим принципово не ввдрізняється від розв'язання аналогічної задачі для одновимірних масивів. У програмі ех7_13 здійснюється пошук значення та індексів максимального елемента матриці, яка ініціазуеться випадковими числами. Максималъний елемент запам’ятовується у змінній max, індекс рядка, в якому розташований цей елемент, - у змінній imax, а індекс стовпця -  у змінній 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(‘введіть кількість рядків та стовпців <=5’);

      readln(n,m);

      randomized;

      for i:=1 to n do

        for j:=1 to m do

          a[i,j]:=random(20);           {генерувати матрицю}

     writeln(‘введіть номер рядка для видалення’);

     readln(k);

     for i:=k to n-1 do                   {видалити k-й рядок}

      for j:=1 to m do

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

     n:=n-1;                                   {зменшити кількість рядків}

end.

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

4. Двовимірні масиви в задачах лінійної алгебри

У розділі 7.3.2 були розглянуті алгоритми обробки матриць. Наведено декілька прикладів їх застосування з метою розв'язання задач лінійної алгебри. А саме побудуємо програмне розв'язання двох хрестоматійних задач: множення матриць та обчислення визначника квадратної матриці.

Множення матриць

Насамперед нагадаємо, що операція множення матриць А х В визначена тільки тоді, коли кількість стовпців матриці А дорівнює кількості рядків матриці В. Отже, добутком матриці А та матриці В називається матриця С, елемент якої cij дорівнює скалярному добутку i-го вектор-рядка матриці А та j-го вектор-стовпця матриці  В. Це означення можна записати у вигляді рівності С = АВ, де

cij=aTi*bj=  i=1..m,  j=1..l,  k=1..n.

Множення двох матриць можна зобразити такою схемою:

Тут А - (т х n)-матриця; В - (п х l)-матриця; аiT - i-й вектор-рядок матриці А; bj - j-й вектор стовпецъ матриці В.

Приклад 7.16

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

program ex7_15;                          {множення матриць}

type Matrix=array[1..10,1..10] of real;

var i,j:integer;                                {індекси елементів}

     A,B:Matrix;                              {вхідні матриці}

     С:Matrix;                                 {матриця результату множення}

     row1,row2:integer;                  {кількість рядків вхідних матриць}

     col1,col2:integer;                    {кількість стовців вхідних матриць}

{=================процедура введення матриці============}

procedure input (var Mas:Matrix;var line, kol:integer);

{Mas – матриця яку вводять; line,kol – кількість рядків і стовпців}

begin

 repead

    write(‘input numbers of rows >=1’);

    readln(line);

    write(‘input numbers of columns >=1’);

    readln(kol);

    if (line<1) or (kol<1) then

                                    writeln(‘it ’ ’s few, input more’);

    until (line>=1) and (kol>=1); {перевірка коректності даних}

    writeln(‘input matrix:’);

    for i:=1 to line do

    for j:=1 to kol do

         read(Mas[i,j]);

end;

{================процедура введення матриці=============}

procedure output (Mas:Matrix;line,kol:integer);

{Mas – матриця; line,kol – кількість рядків і стовпців}

begin

  for i:=1 to line do

  begin

    for j:=1 to kol do

      write(Mas[i,j]:6:2,’ ‘);              {виведення елемента}

    writeln;                                    {перевести курсор на новий рядок}

 end;

end;

{==================множення матриць===================}

procedure mult;

 var k:integer;    {індекс елемента скалярного добутку векторів}

 begin

   if col1<>row2 then   {перевірка відповідності матриць}

     writeln(‘multiplication is imposible – matrix are unconformable’)

   else

     begin

     for i:=1 to row1 do    {вибрати і-й вектор-рядок}

      for j:=1 to col2 do    {вибрати j–й вектор-стовпець}

      begin

      C[i,j]:=0;

       for k:=1 to col1 do

          C[i,j]:=C[i,j]+A[i,k]*B[k,j];   {скалярне множення векторів}

      end;

   end;

end;                                             {end of mult}

begin

  writeln(‘input metrix A: ’);

  input(A,row1,col1);                   {ввести матрицю А}

  writeln(‘input matrix B: ’);

  input(B,row2,col2);                   {ввести матрицю В}

  writeln(‘matrix A: ’);

  output(A,row1,col1);                 {вивести матрицю А}

  writeln(‘matrix B: ’);

  output(B,row2,col2);                 {вивести матрицю В}

  mult;                                         {перемножити А та В}

  writeln(‘result of multiplication: ’);

  output(C,row1,col2);                 {вивести матрицю С}

  readln;

end.

Обчислення визначника квадратної матриці

Поняття визначника застосовне лише до квадратних матриць. Матриця називається квадратною, якщо кількість її рядків дорівнює кількості стовпців. Означення поняття визначника квадратної матриці можна знайти у будь-якому підручнику з лінійної алгебри (наприклад, [6]). Обчислення визначника за його означенням є неефективним, і на практиці цей метод не використовуєтъся. Нижче буде наведено програмну реалізацію набагато ефективнішого методу, що грунтується на зведенні матриці до трикутного вигляду. Перш ніж розглядати цей метод, дамо означення декількох базових понять.

Нагадаємо, що квадратна матриця мае дві діагоналі. Діагональ, яка проходить від лівого верхнього кута матриці до її правого нижнього кута, називається головною. Елементи матриці, що маютъ рівні індекси рядків і стовпців, розташовані на головній діатоналі і називаються діагональними. Інша діагональ проходить із правого верхнього кута матриці до її лівого нижнього кута. Така діагональ називається побічною. Індекси елементів побічної дгагоналі відповвдають такій функційній залежності: j=n-i+1, де i — номер рядка, j - номер стовпця, а n -розмірність матриці. Матриця називається верхньо трикутною, якщо значення всіх її елементів, що розташовані під головною діагоналлю, дорівнюютъ нулю. Визначник трикутної матриці дорівнює добутку всіх її діагоналъних елементів. Розглянемо алгоритм зведення матриці до трикутного вигляду.

На першому кроці алгоритму отримують нулъові значення всіх елементів першого стовпця матриці, починаючи з другого елемента. Для цього визначаються коефіціенти виключення за формулою ki=-ai1/a11  i до елементів і-го рядка додаються відповідні елементи першого рядка, помножені на ki. На другому кроці алгоритму аналогічним чином отримують нульові значення всіх елементів другого стовпця матриці, починаючи з його третього елемента. Коефіцінти виключення внзначатимуться як ki=-ai2/a22. На ці коефіцінти множитимуться елементи другогого рядка, і отримані результати додаватимуться до елементів інших рядків. Процес триватиме п- 1 кроків. Отже, значення елементів трикутної матриці визначаються за формулою

aij’=aij-

Тут елемент akk - опорний елемент; i,j,k - індекси рядків і стовпців (і= 1, 2, ..., n, j=1, 2, ..., n; k = 1, 2, ..., n); п – вимірність матриці.

Отже, на кожній ітерації алгоритму опорними є діагоналъні елементи. Це дільники, тому їх значення не повинні дорівнювати нулю. Якщо r-й опорний елемент дорівнює нулю, то r-й і будь-який інший рядок, в r-му стовпці якого міститься ненульовий елемент, треба поміняти місцями. Внаслідок такої перестановки рядків визначник змінює знак. Всі інші дії алгоритму не зміюють значення визначника.

Приклад 7.17

Запишемо програму обчислення визначника квадратної матриці за поданим вище алгоритмом. Процедури inpute та output виконують введення та виведення матриці, процедура triangular(k:integer) призначена для отримання нулів під головною діагоналлю в k-му стовпці, процедура change міняє місцями рядки, а процедура determinant обчислює визначник.

program ex7_16;                  {обчислити визначник матриці}

var det:real;                          {значення визначника матриці}

      n:integer;                       {вимірність матриці}

      a:array[1..5,1..5] of real;{елементи матриці}

      sign:integer;                   {ознака зміни знака визначника}

{================введення елементів матриці==================}

procedure input;

var i,j:integer;                                      {параметри циклів}

begin

   writeln(‘input size of martix’);

    readln(n);    {введення кількості рядків і стовпців матриці}

    writeln(‘input components of matrix’);

    for i:=1 to n do

      for j:=1 to n do

      begin

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

        readln (a[i,j]);

   end;

end;

{==============виведення значень елементів матриці===========}

procedure outpute;

var i,j:integer;              {параметри циклів}

begin

 for i:1 to n do

   begin

    for j:=1 to n do

     write(a[i,j]:5:2, ‘ ‘);

   writeln;

  end;

end;

{==============обчислення трикутної матриці==============}

procedure triangular(k:integer);

                                               {k – номер рядка, що обчислюється}

var l,j:integer;                          {параметри циклів}

     koef:real;                           {коефіцієнтвиключенняелемента}

begin

  for l:=k+1 to n do                 {вибрати наступний рядок}

    begin

     koef:=a[l,k]/a[k,k];            {обчислити коефіцієнтвиключення”}

     for j:=1 to n do                   {обчислити елементи у вибраному рядку}

       a[l,j]:=a[l,j]-a[k,j]*koef;

   end;

end;

{================перестановка рядків====================}

procedure change(ii:integer);

{ii – номер рядка, що міняється місцями з будь-яким іншим рядком}

var j,k:integer;                {параметри циклів}

       tmp: real;                {тимчасова зміна для переставлення елементів}

begin

 sign:=1;           {ініціалізація ознаки зміни зніка визначника}

for j:=1 to n-ii do    {пошук рядка з ненульовим опорним елементом}

   if a[ii+j,ii]<>0 then   {якщо шуканий елемент не нульовий}

    begin

      for k:=1 to n do   {рядки переставляються}

       begin

        tmp:=a[ii,k];

        a[ii,k]:=a[ii+j,k];

        a[ii+j,k]:=tmp;

      end;

      sign:=-sign;   {ознака зміни знака визначника}

  end;

end;

{=================обчислити визначник=================}

procedure determinant;

var i:integer;

begin

  for i:=1 to n-1 do

   begin

    if a[i,i]=0 then    {якщо опорний елемент дорівнює нулю}

            change(i);         {переставити рядки місцями}

          triangular(i);   {обчислити стовпець трикутної матриці}

  end;

   det:=1;

   for i:=1 to n do    {перемножити диагональні елементи}

     det:=det*a[i,i];

   if sign<0 then det:=-det;   {змінити знак визначника}

end;

{===================головна програма===================}

begin

  writeln(‘determinant of matrix’);

  input;              {ввести матрицю}

  writeln(‘initial matrix’);

  output;      {ввести початкову матрицю}

  determinant;     {обчислити визначник}

  writeln(‘triangular matrix’);

  output;     {вивести трикутну матрицю}

  writeln(‘det=’,det:5:2);   {вивести значення визначника}

  readln;

end;

Контрольні питання

1. Багатовимірні масиви

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

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

4. Двовимірні масиви в задачах лінійної алгебри


 

А также другие работы, которые могут Вас заинтересовать

64222. Формирование общения в играх животных 33.5 KB
  Такие игры встречаются только у животных которым свойственны развитые формы группового поведения. У детёнышей нехищных животных совместная игра состоит из общеподвижных игр совместных прыжков игрового бегства и так далее Игровая борьба если она встречается у данных видов...
64223. Познавательная функция игровой активности животных 29 KB
  В последнем случае имеет место активное воздействие на объект игры особенно деструктивного порядка позволяющее изучить внутреннее строение объекта а не только его внешние признаки. Важно что в ходе игры животное относится практически к каждому незнакомому предмету как к потенциально значимому и пытается найти ему применение.
64224. Общая характеристика эволюции психики 29.5 KB
  Исходя из этого следует что движение являлось решающим фактором эволюции психики. Леонтьев рассматривая эволюцию психики анализировал наиболее глубокие и качественные изменения которые претерпела психика в процессе эволюции животного мира.
64225. Элементарная сенсорная психика. Низший уровень психического развития. Характеристика сенсомоторной активности простейших 30 KB
  На низшем уровне психического развития находится довольно большая группа животных. Движения простейших отличаются большим разнообразием. Локомоция простейших осуществляется в виде кинезов элементарных инстинктивных движений.
64226. Общая характеристика психической активности простейших 27.5 KB
  Наряду с этим у простейших встречаются и элементы допсихического отражения простая раздражимость характерная для растений. У простейших встречаются разнообразные формы передвижения в водной среде но только на самом примитивном уровне инстинктивного поведения кинезов.
64227. Высший уровень развития элементарной сенсорной психики. Нервная система как фактор усложнения психической деятельности животных 26 KB
  Усложнение структуры организма обусловило возникновение нервной системы которая осуществляет координацию деятельности этих многоклеточных образований.
64228. Органы чувств и сенсорные способности низших многоклеточных беспозвоночных 28 KB
  Предполагается что первичные органы чувств вообще обладали лишь общей присущей всей живой материи чувствительностью но в повышенной степени. Согласно приведённой гипотезе все органы чувств многоклеточных животных развились из наименее дифференцированных осязательных рецепторов.
64229. Общая характеристика моторной активности низших многоклеточных беспозвоночных 25.5 KB
  Большинство же червей ползают и роются в придонном иле проглатывая его вместе с органическими остатками или собирают с поверхности дна мелких животных и мёртвые организмы. У кольчатых червей впервые в эволюции животного мира появляются настоящие парные конечности...
64230. Таксисы у низших беспозвоночных 26 KB
  Кюн выделил следующие категории высших таксисов которые в полной мере развиты лишь у высших животных: тропотаксисы телотаксисы менотаксисы и мнемотаксисы. Низшим беспозвоночным свойственны в разной степени только первые три формы высших таксисов. Особенно значимы эти два вида таксисов для хищников.