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