Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розріджені матриці
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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]); } } }
Висновки.
Під час виконання лабораторної роботи набуто знання і навички стосовно роботи з розрідженими матрицями. Створена програма сортує розріджену матрицю в скороченому вигляді.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора