Тема 12. Алгоритми роботи з багатомірними масивами

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

У чому особливість оголошення багатомірного масиву? Як у типі вказати розмірність масиву? Це робиться досить просто, за рахунок використання ком. От як виглядає оголошення багатомірного масиву в загальному випадку:

Число ком, збільшене на одиницю, і задає розмірність масиву. Що стосується об'явників, те все, що сказано для одномірних масивів, справедливо й для багатомірних. Можна лише відзначити, що хоча явна ініціалізація з використанням багатомірних константних масивів можлива, але застосовується рідко через громіздкість такої структури. Простіше ініціалізацію реалізувати програмно, але іноді вона все-таки застосовується. От приклад:

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

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

a[1, 1]: = 0; елементу масиву a з індексом 1.1 привласнюється значення 0;

a[1, 0]: = a[1, 0]*2; елемент масиву a з індексом 1, 0 подвоюється.

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

Рис 12.1. Двовимірний масив.

Розглянемо приклад двовимірного масиву. Загальне ім’я масиву А. кількість елементів стовбця і рядків по 5. Якщо кількість рядків і стовпців співпадають – такі масиви називаються симетричними. Якщо ні - несиметричними. Перший індекс елемента масиву визначає номер рядка, другий номер стовпця.

Серед класичних алгоритмів розглянемо наступні:

· алгоритм вводу масиву;

· алгоритм виводу масиву;

· алгоритм пошуку мінімального та максимального елементу;

· алгоритм формування нового масиву за даними критеріями;

та інші.

Для симетричних масивів розрізняють поняття головної діагоналі. Це елементи у яких індекси рядка і стовпця співпадають:

та побічної діагоналі

Серед класичних алгоритмів роботи з симетричними масивами розглянемо наступні:

· алгоритм пошуку максимального елементу головної та другорядної діагоналі;

· алгоритм находження суми елементів, які знаходяться під головною діагоналлю;

· алгоритм находження суми елементів між головною і побічною діагоналлю;

та інші.

Розглянемо класичну задачу пошуку максимального елементу двомірного масиву цілих чисел і виділимо основні блоки програми:

Лістинг 12.1.

{

int i = 0, j = 0; // об’явлення змінних

Console.Write(" N=");

int n = Int32.Parse(Console.ReadLine()); // введення кількості рядків

Console.Write(" М=");

int m = Int32.Parse(Console.ReadLine()); // введення кількості стовпців

int[, ] mas = new int[n, m]; // оголошеня масиву

// Блок заповнення двовимірного масиву цілими числами введеними з клавіатури

for (i = 0; i < n; i++) // початок циклу роботи з рядками

{

for (j = 0; j < n; j++) // початок циклу роботи зі стовпцями

{

Console.Write(" [" + (i) + ", " + (j) + " ]="); // вивід позиції елементу, що вводиться

mas[i, j] = int.Parse(Console.ReadLine()); // введення елементу

}

}

// Блок пошуку максимального елементу масиву

int max = mas[0, 0], i1 = 0, j1 = 0;

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

{

if (max < mas[i, j]) { max = mas[i, j]; i1 = i; j1 = j; }

}

}

// Вивід результатів роботи програми

Console.WriteLine(" Найбільше число " + max+ " знаходиться в " + (i1+1) + " -му рядку." + (j1+1)+ " стовпцю");

// Вивід мосиву

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

Console.Write(mas[i, j] + " ");

Console.WriteLine();

}

Console.ReadKey();

}

}

}

Як бачимо, в представленому алгоритмі можна виділити два стандартних блоки: ввід масиву, пошук максимального елементу, вивід масиву.

Приклад заповнення масиву випадковими числами:

Лістинг 12.2.

for (i = 0; i < n; i++) // початок циклу роботи з рядками

{

for (j = 0; j < n; j++) // початок циклу роботи зі стовпцями

{

mas[i, j] = r.Next(100);

} }

Приклад заповнення масиву розрахунком функції:

for (i = 0; i < n; i++) // початок циклу роботи з рядками

{

for (j = 0; j < n; j++) // початок циклу роботи зі стовпцями

{

mas[i, j] = Math.Cos(i)+ Math.Sin(j);

}

}

Розглянемо приклад роботи алгоритму з симетричними масивами.

В симетричному масиві знайти суму чисел, які знаходяться нижче головної діагоналі.

Якщо головна діагональ має однакові індекси то нам потрібно знайти суму елементів, які на рисунку жовті.

Лістинг 12.3.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication8

{

class Program

{

static void Main(string[] args)

{

int n = int.Parse(Console.ReadLine());

int[, ] mas = new int[n+2, n+2];

int i, j, sum=0;

Random r = new Random();

for (i = 1; i < = n + 1; i++)

for (j = 1; j < = n + 1; j++)

mas[i, j] = r.Next(100);

// блок підрахунку суми

for (i = 2; i < = n + 1; i++)

for (j = 1; j < = i; j++)

{

sum = sum + mas[i, j];

}

Console.WriteLine(sum);

}

}

}

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

for (i = 1; i < = n; i++)

for (j = 1; j < = n-i; j++)

{

sum = sum + mas[i, j];

}

Console.WriteLine(sum);

Ці задачі не складні. Основна дія знаходження суми(sum = sum + mas[i, j];). А циклами необхідно задати ті значення змінних і, j, які нам вибирають необхідні елементи з масиву.

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

Три матриці - Matr, Matr й Matr - мають довільні розміри, що з'ясовують у діалозі з користувачем, і використання для їхнього опису динамічних масивів представляється зовсім природним. Метод CreateTwoDimAr заповнює випадковими числами елементи матриці, переданої йому як аргумент, метод PrintAr2 виводить матрицю на печать.

Метод MultMatr виконує множення прямокутних матриць. Це класичне завдання з набору завдань, розв'язуваних на першому курсі. От текст цього методу:

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

Зверніть увагу, як виглядають результати консольного виводу на даному етапі роботи (рис. 12.2).

Рис. 12.2 Множення матриць