НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №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-15[ім’я автора приховано] #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; } Висновок: У цій лабораторної роботі ознайомилися з роботою з роздріженою матрицею. Розробили таким чином економний спосіб зберігання матриці. Виконали завдання згідно до індивідуального варіанту. Зроблено звіт до лабораторної роботи та надіслано викладачу.