НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №6 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Розріджені матриці Варіант 7  Київ 20____ Мета: Навчитися працювати з розрідженими матрицями та з їх скороченим записом. Теоретична частина: Розріджена матриця — матриця, більша частина елементів якої є нулі. Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Для матриці порядку n елементів кількість ненульових елементів: є O(n). Таке визначення підходить хіба для теоретичного аналізу асимптотичних властивостей матричних алгоритмів. в кожному рядку не перевищує 10 в типовому випадку. Обмежено nα+1, де α <1. Представлення у структурах даних Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць. Зберігання ненульових елементів Одним з таких способів полягає в зберіганні ненульових елементів та їх координат. Цей спосіб є економний для пам'яті але для виконання дій з матрицями (додавання, множення) він є неефективний, оскільки кожного разу потрібно перебирати всі елементи для пошуку відповідного елемента. Зберігання ненульових елементів зв'язаних вказівниками У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями. Завдання до роботи: Розробити спосіб економного зберігання в пам’яті розріджених матриць. Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді. Провести сортування розрідженої матриці за вказаною схемою, будь-яким обраним методом. / Результати виконання лабораторної роботи: / / Створена програма сортує стовпчики матриці за збільшенням через один стовпчик(сортується тільки половина стовпчиків). Програмний код: public class LR6 { public static final int size = 10; public static void main(String[] args) { System.out.println("ЛР №6. Варіант 7"); System.out.println("Завдання: Розробити спосіб економного зберігання в пам’яті розріджених матриць."); int[][] arr = new int[size][size]; int count = 0; for(int i = 0;i < size;i++) { for (int j = 0; j < size; j++) { arr[i][j] = (int) (Math.random() * 50); if (arr[i][j] <= 10) { arr[i][j] = (int) (Math.random() * 9 + 1); count++; } else arr[i][j] = 0; } } int[][] matr = new int[count][3]; count = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if(arr[i][j]!=0){ matr[count][0] = i; matr[count][1] = j; matr[count][2] = arr[i][j]; count++; } } } System.out.println("Розріджена матриця у початковому вигляді:"); for(int i = 0; i < size;i++){ for(int j = 0;j < size;j++) System.out.print(arr[i][j] + " "); System.out.println(); } System.out.println("\nРозріджена матриця у скороченому вигляді:"); System.out.println("Рядок|Стовпчик|Значення"); for (int i = 0; i < matr.length; i++) { System.out.println(" " + matr[i][0] + " | " + matr[i][1] + " | " + matr[i][2]); } //cортування по стовпчику for (int i = 0; i < count-1; i++) { for (int k = count-1; k > i; k--) { if (matr[k - 1][1] > matr[k][1...