НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №6 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Розріджені матриці» Варіант № 20 Дата «19» червня 2022 Завдання до лабораторної роботи: Розробити спосіб економного зберігання в пам’яті розріджених матриць. Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді. Завдання для варіанту 20: Провести обмін елементів матриці за вказаною схемою, любим обраним методом / Теоретична частина Розріджена матриця — матриця, більша частина елементів якої є нулі. Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Для матриці порядку n елементів кількість ненульових елементів: є O(n). Таке визначення підходить хіба для теоретичного аналізу асимптотичних властивостей матричних алгоритмів. в кожному рядку не перевищує 10 в типовому випадку. обмежено nα+1, де α <1. Представлення у структурах даних Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць. Зберігання ненульових елементів Одним з таких способів полягає в зберіганні ненульових елементів та їх координат. Цей спосіб є економний для пам'яті але для виконання дій з матрицями (додавання, множення) він є неефективний, оскільки кожного разу потрібно перебирати всі елементи для пошуку відповідного елемента. Зберігання ненульових елементів зв'язаних вказівниками У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями. Результат роботи // // Висновок: У ході виконання даної лабораторної роботи було отримано практичні навички роботи з розрідженими матрицями, розроблено спосіб економного зберігання в пам’яті розріджених матриць, виконано завдання згідно варіанта над стисненою матрицею. Код програми: package com.company; import java.awt.*; import java.util.ArrayList; public class LR_6 { public static void main(String[] args) { System.out.println("ЛР №6. Варіант 20"); System.out.println("Завдання: Розробити спосіб економного зберігання в пам’яті розріджених матриць."); int size = 10; //Створюємо звичаний двовимірний масив, у якому більшість елементів генеруються нулями int[][] array = new int[size][size]; for (int i= 0; i< size;i++) for (int j = 0;j <size;j ++) array[i][j] = Math.random() < 0.35 ? (int)(Math.random() * 10) : 0; Matrix matrix = new Matrix(array); System.out.println("Початкова матриця у звичайному вигляді"); matrix.displayLikeArray(); System.out.println("Та ж початкова матриця у стисненому вигляді"); matrix.display(); System.out.println("Індивідуальне завдання над стисненою матрицею: "); System.out.println("Провести обмін елементів матриці за вказаною схемою (ДИВИТИСЯ СХЕМУ ВАРІАНТУ В ЗВІТІ)"); matrix.task1(); System.out.println("Результат у звичайному вигляді масиву:"); matrix.displayLikeArray(); System.out.println("Результат у вигляді стисненої матриці:"); matrix.display(); } } class Matrix { ArrayList<ElementInfo> elements; int height, width; Matrix(int[][] array) { elements = new ArrayList<>(); height = array.length; width = array[0].length; for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) if (array[i][j] != 0) elements.add(new ElementInfo(i, j, array[i][j])); } void display() { for (int i = 0; i< elements.size(); i++) System.out.println("рядок = "+elements.get(i).row + " | стовпичк = "+elements.get(i).column + " | значення = " + elements.get(i).value); } void displayLikeArray() { for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { ElementInfo current = find(i, j); if (current == null) System.out.printf("0 "); else System.out.printf(current.value + " "); } System.out.println(); } } ElementInfo find(int row, int column) { for (int i = 0; i < elements.size(); i++) if (elements.get(i).row == row && elements.get(i).column == column) return elements.get(i); return null; } void task1() { for (int i = 0; i< elements.size(); i++) elements.get(i).row = (height - 1) - elements.get(i).row; } class ElementInfo { int row, column, value; ElementInfo(int row, int column, int value) { this.row = row; this.column = column; this.value = value; } } }