НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №6 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Розріджені матриці» Варіант 13 Київ 2022 Мета: Метою лабораторної роботи є ознайомитися з основами роботи з представленням у пам’яті розріджених матриць, зберіганням та обробкою такого вигляду матриць. Теоретичні відомості Розріджена матриця — матриця, більша частина елементів якої є нулі. Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Величезні розріджені матриці часто виникають, наприклад, при чисельному розв’язуванні диференціальних рівнянь у частинних похідних. Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць. Одним з таких способів полягає в зберіганні ненульових елементів та їх координат. Цей спосіб є економний для пам'яті але для виконання дій з матрицями (додавання, множення) він є неефективний, оскільки кожного разу потрібно перебирати всі елементи для пошуку відповідного елемента. У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями. Для матриці порядку n елементів кількість ненульових елементів / Завдання до лабороторної роботи: Розробити спосіб економного зберігання в пам’яті розріджених матриць Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді / Рисунок 1. Завдання 13 варіанту. Результат роботи / / / / Висновки: розроблено програму, що виконує створення такої матриці, в якої більшість елементів є нулями, тобто таку матрицю можна назвати розрідженою. Для економного представлення такої матриці у пам’яті побудовано клас SparseMatrix, який представляє розріджену матрицю як масив підкласів, полями яких є координати ненульового елменту та його значення. Оброблено розріджену матрицю за особистим завданням. Програмний код class Lr6 { public static void main(String[] args) { System.out.println("Матриця ДО обробки у розгорнутому вигляді:"); var matrix = createDefaultMatrix(10); displayDefaultMatrix(matrix); System.out.println("Матриця ДО обробки у стисненому вигляді:"); SparseMatrix sparseMatrix = new SparseMatrix(matrix); sparseMatrix.display(); System.out.println("Матриця ПІСЛЯ обробки у розгорнутому вигляді:"); sparseMatrix.task(); displayDefaultMatrix(sparseMatrix.getDefaultMatrix()); System.out.println("Матриця ПІСЛЯ обробки у стисненому вигляді:"); sparseMatrix.display(); } static int[][] createDefaultMatrix(int n) { int[][] arr = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { double rand = Math.random(); if (rand >= 0.7 && rand <= 0.9) arr[i][j] = (int)(Math.random() * 9.0) + 1; } } return arr; } static void displayDefaultMatrix(int[][] arr) { for (int i = 0; i < arr.length; i++) { System.out.println(Arrays.toString(arr[i])); } } } class SparseMatrix { SparseMatrixElement[] matrix; int columns; int rows; SparseMatrix(int[][] defaultMatrix) { List<SparseMatrixElement> list = new ArrayList<SparseMatrixElement>(); for (int i = 0; i < defaultMatrix.length; i++) for (int j = 0; j < defaultMatrix[i].length; j++) { if (defaultMatrix[i][j] != 0) { list.add(new SparseMatrixElement(new Point(i, j), defaultMatrix[i][j])); } } matrix = new SparseMatrixElement[list.size()]; list.toArray(matrix); rows = defaultMatrix.length; columns = defaultMatrix[0].length; } void display() { for (int i = 0; i< matrix.length; i++) System.out.println("<"+matrix[i].position.x+", "+matrix[i].position.y+"> = "+matrix[i].value); } void task() { for (int i = 0; i < rows; i++) { for (int j = 0; j <= columns - 5; j+=5) { replace(new Point(i,j), new Point(i,j+4)); replace(new Point(i,j+1), new Point(i,j+3)); } } } void replace(Point pos1, Point pos2) { SparseMatrixElement el1 = find(pos1); SparseMatrixElement el2 = find(pos2); if (el1 == null && el2 == null) return; if (el1 != null && el2 != null) { el1.position = pos2; el2.position = pos1; return; } if (el1 != null) { el1.position = pos2; return; } if (el2 != null) { el2.position = pos1; return; } } SparseMatrixElement find(Point pos) { for (int i = 0; i < matrix.length; i++) if (matrix[i].position.x == pos.x && matrix[i].position.y == pos.y) return matrix[i]; return null; } int[][] getDefaultMatrix() { int[][] arr = new int[rows][columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { SparseMatrixElement current = find(new Point(i, j)); if (current == null) arr[i][j] = 0; else arr[i][j] = current.value; } } return arr; } private class SparseMatrixElement { Point position; int value; SparseMatrixElement(Point point, int val) { position = point; value = val; } } }