НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №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]) { int tmp0 = matr[k - 1][0]; int tmp1 = matr[k - 1][1]; int tmp2 = matr[k - 1][2]; matr[k - 1][0] = matr[k][0]; matr[k - 1][1] = matr[k][1]; matr[k - 1][2] = matr[k][2]; matr[k][0] = tmp0; matr[k][1] = tmp1; matr[k][2] = tmp2; } } } //cортування по значенням для кожного стовпчика for (int i = 0; i < count-1; i++) { int j = i; if (matr[i][1] % 2 != 0) continue; while (matr[j][1] == matr[j + 1][1]) { j++; if (j + 1 == count) break; } for (int l = i;l <= j;++l){ for (int k=l+1;k<=j;++k){ if (matr[l][2]>matr[k][2]){ int tmp0 = matr[l][0]; int tmp1 = matr[l][1]; int tmp2 = matr[l][2]; matr[l][0] = matr[k][0]; matr[l][1] = matr[k][1]; matr[l][2] = matr[k][2]; matr[k][0] = tmp0; matr[k][1] = tmp1; matr[k][2] = tmp2; } } } int minus = 0; for (int k = j; k >= i; k--) { matr[k][0] = 9 - minus; minus++; } i = j; } int[][] arrAfterSort = new int[size][size]; System.out.println("\nРозріджена матриця у початковому вигляді після сортування:"); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { arrAfterSort[i][j] = 0; } } for (int i = 0; i < count; i++) { arrAfterSort[matr[i][0]][matr[i][1]] = matr[i][2]; } for(int i = 0; i < size;i++){ for(int j = 0;j < size;j++) System.out.print(arrAfterSort[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]); } } } Висновки. Під час виконання лабораторної роботи набуто знання і навички стосовно роботи з розрідженими матрицями. Створена програма сортує розріджену матрицю в скороченому вигляді.