Розріджені матриці. Звіт до лабораторної роботи з Програмування складних алгоритмів. Робота № 100551

Розріджені матриці

Інформація про навчальний заклад

ВУЗ:

Національний технічний університет України Київський політехнічний інститут

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2023

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування складних алгоритмів

Завантажити

Частина тексту файла (без зображень, графіків і формул):

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №6 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Розріджені матриці» Варіант № 16 Дата « 19 » червня 2022 Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з розрідженими матрицями. Завдання до лабораторної роботи: Розробити спосіб економного зберігання пам’яті розріджених матриць. Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді. 16. Поставити на головну діагональ матриці мінімальний елемент стовпчик Теоретичні відомості: На практицi зустрiчаються масиви, якi через певнi причини можуть займати пам’ять не повнiстю, а частково. Це особливо актуально для масивiв великих розмiрiв, таких що для їхнього збереження в повному об’ємi може бути не достатньо пам’ятi комп’ютера. Розрiджений масив – це масив, бiльшiсть елементiв якого рiвнi мiж собою, так що зберiгати достатньо лише невелику кiлькiсть значень, вiдмiнних вiд основного (фонового) значення. Нема єдиного визначення, яка кiлькiсть ненульових елементiв має бути в матрицi, щоб вона була розрiдженою. При роботi iз розрiдженими масивами питання розташування їх в пам’ятi реалiзуються на логiчному рiвнi з врахуванням типу елементiв. Простим прикладом роботи iз розрiдженими масивами можуть бути електроннi таблицi: попри те, що робочий лист документу має розмiр 16384 × 1048576 елементiв (для Excel 2010) зайнятими є не бiльше 1 вiдсотка вiд потенцiйно доступних комiрок. Розрiзняють два типи розрiджених масивiв: • масиви, в яких розташування елементiв зi значеннями, вiдмiнними вiд фонового, можуть бути описанi математично; • масиви з випадковим розташуванням елементiв. До масивiв з математичним описом розташування елементiв вiдносяться масиви, в яких iснують функцiональнi закономiрностi в розташуваннi елементiв iз значеннями, вiдмiнними вiд фонового. Елементи, значення яких є фоновими, називають нульовими. Елементи, значення яких вiдмiннi вiд фонового називають ненульовими. Фонове значення не обов’язково рiвне нулю. Ненульовi значення зберiгаються, як правило, в одновимiрному масивi, а зв’язок мiж розташуванням у розрiдженому масивi i в новому, одновимiрному, описується математично за допомогою формули, що перетворює iндекси масиву в iндекси вектора. На практицi для роботи з розрiдженим масивом розробляються функцiї: • для перетворення iндексiв масиву в iндекс вектора; • для отримання значення елемента масиву з його упакованого представлення за iндексами; • для запису значення елемента масиву в її упаковане представлення за iндексами. До масивiв з випадковим розташуванням елементiв вiдносяться масиви, в яких не iснує закономiрностей у розташуваннi елементiв iз значеннями, вiдмiнними вiд фонового. Один з основних способiв збереження подiбних розрiджених матриць полягає у збереженнi ненульових елементiв в одновимiрному масивi iз iдентифiкацiєю кожного елемента масиву iндексами. Спосiб послiдовного розподiлу має також ту перевагу, що операцiї над матрицями можуть бути виконанi швидше, нiж це можливо при представленнi у виглядi послiдовного масиву, особливо якщо розмiр матрицi великий. Пам’ять, необхiдна для збереження розрiджених матриць, складається з двох частин: основної пам’ятi, у якiй розмiщуються числовi значення елементiв та додаткової пам’ятi, де зберiгаються iндекси та iнша iнформацiя, необхiдна для формування структури матриць i яка забезпечує доступ до числових значень їх елементiв. Способи зберiгання i використання даних, що зберiгаються в основнiй i додатковiй пам’ятi, досить рiзноманiтнi i визначаються, головним чином, обраним методом. Якщо елементами масиву є цiлi числi, то найпростiший пiдхiд полягає у створеннi двомiрного масиву розмiрностi n ∗ 3, де n - кiлькiсть ненульових елементiв вихiдної розрiдженої матрицi. Першi два елементи кожного рядка мiстять iндекси рядка та стовпця ненульового елементу, а третiй - значення самого елементу. Результат роботи програми: / Посилання на код: https://replit.com/join/zovaaipifk-tr-15khavkin #include <iostream> using namespace std; int GetSize(int** Arr, int Rows, int Cols){ if(!Arr || Rows <= 0 || Cols <= 0) return 0; int Size = 0; for (int i = 0; i < Rows; ++i){ for (int j = 0; j < Cols; ++j){ if(Arr[i][j] != 0) Size++; } } return Size; } int main(){ srand(time(nullptr)); const int Rows = 5; const int Cols = 5; int** FullMatrix = new int*[Rows]; cout << "Повна матриця: " << endl; for (int i = 0; i < Rows; ++i){ FullMatrix[i] = new int; for (int j = 0; j < Cols; ++j){ if(rand() % 2 == 0){//50% for zero FullMatrix[i][j] = rand() % 10; }else{ FullMatrix[i][j] = 0; } cout << FullMatrix[i][j] << " "; } cout << endl; } int Size = GetSize(FullMatrix, Rows, Cols); int** SparseMatrix = new int*[3]; for (int i = 0; i < 3; ++i){ SparseMatrix[i] = new int[Size]; } //Get SparseMatrix cout << endl << "Розріджена матриця: " << endl; cout << "| # | Ряд | Кол |Значення|" << endl; int k = 0; for (int i = 0; i < Rows; i++){ for (int j = 0; j < Cols; j++){ if (FullMatrix[i][j] == 0) continue; SparseMatrix[0][k] = i; SparseMatrix[1][k] = j; SparseMatrix[2][k] = FullMatrix[i][j]; k++; if(k < 10){ cout << "| "; }else{ cout << "| "; } cout << k << " | " << i << " | " << j << " | " << FullMatrix[i][j] << " |" << endl; } } int** TransferedMatrix = new int*[Rows]; for (int i = 0; i < Rows; ++i){ TransferedMatrix[i] = new int[Cols]; for (int j = 0; j < Cols; ++j){ TransferedMatrix[i][j] = 0; } } int min,tempm; //Зміна елементів for(int i=0;i<Size;i++){ TransferedMatrix[SparseMatrix[0][i]][SparseMatrix[1][i]]=SparseMatrix[2][i]; } for(int j=0; j<Cols;j++){ min=100; for (int i = 0; i < Size; ++i){ if(SparseMatrix[1][i]==j && min==100){ min = SparseMatrix[2][i]; tempm=i; }else if(SparseMatrix[1][i]==j && SparseMatrix[2][i]<min){ min=SparseMatrix[2][i]; tempm=i; } } TransferedMatrix[j][j]=min; } cout << endl << "Змінена матриця: " << endl; for (int i = 0; i < Rows; ++i){ for (int j = 0; j < Cols; ++j){ cout << TransferedMatrix[i][j] << " "; } cout << endl; } return 0; } Висновок: У цій лабораторної роботі ознайомилися з роботою з роздріженою матрицею. Розробили таким чином економний спосіб зберігання матриці. Виконали завдання згідно до індивідуального варіанту. Зроблено звіт до лабораторної роботи та надіслано викладачу.

Звіт до лабораторної роботи Програмування складних алгоритмів

28.07.2023 13:30

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись