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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

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

Рік:

2023

Тип роботи:

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

Предмет:

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

Завантажити

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

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №6 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Розріджені матриці» Варіант 18 Мета: Метою лабораторної роботи є ознайомитися з основами роботи з розрідженими матрицями. Теоретична частина На практиц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й - значення самого елементу. Завдання до лабораторної роботи: 1 Розробити спосіб економного зберігання в пам’яті розріджених матриць. 2 Виконати індивідуальне завдання над стисненою матрицею. 3 Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді. 18. Обнулити мінімальні елементи кожного рядка масиву. Результат роботи / / Висновок: Було написано програму, що перетворює розріджену матрицю в скорочену, для заощадження пам’яті. Потім у скороченій матриці видаляється найменший елемент кожного ряду, після чого вона знов перетворюється в розріджену матрицю. Програмний код https://replit.com/join/wpzkegxxly-okseniait #include <stdio.h> #define size 10 #define BLU "\e[0;34m" #define WHT "\e[0;37m" void fillm(int arr[size][size]){ srand(time(NULL)); int random; for(int i = 0;i < size;i++){ for(int j = 0;j < size;j++){ random = rand() % 50; if(random >= 10){ arr[i][j] = 0; } else{ arr[i][j] = random; } } } } void printm(int arr[size][size]){ for(int i = 0;i < size;i++){ for(int j = 0;j < size;j++){ if(arr[i][j]!=0){ printf(BLU"%d "WHT, arr[i][j]); } else{ printf("%d ", arr[i][j]); } } printf("\n"); } } int countnozero(int arr[size][size]){ int count = 0; for(int i = 0; i < size;i++){ for(int j = 0;j < size;j++){ if(arr[i][j] != 0){ count++; } } } return count; } void fillsm(int nozero, int shrinkedarr[nozero][3], int arr[size][size]){ int a = 0; for(int i = 0;i < size;i++){ for(int j = 0;j < size;j++){ if(arr[i][j] != 0){ shrinkedarr[a][0] = arr[i][j]; shrinkedarr[a][1] = i; shrinkedarr[a][2] = j; a++; } } } } void createmfsm(int nozero, int shrinkedarr[nozero][3], int arr[size][size]){ for(int i = 0;i < size;i++){ for(int j = 0;j < size;j++){ arr[i][j] = 0; } } for(int i = 0;i < nozero;i++){ arr[shrinkedarr[i][1]][shrinkedarr[i][2]] = shrinkedarr[i][0]; } } void printsm(int nozero, int shrinkedarr[nozero][3]){ for(int i = 0;i < nozero;i++){ if(shrinkedarr[i][0]!=0){ printf("%d [%d] [%d] \n", shrinkedarr[i][0], shrinkedarr[i][1], shrinkedarr[i][2]); } } } void minToZero(int nozero, int shrinkedarr[nozero][3]){ int min, kMin; min=20; for(int k=0; k<50; k++){ if(shrinkedarr[k][0]<min){ min=shrinkedarr[k][0]; kMin=k; } if(shrinkedarr[k+1][1]>shrinkedarr[k][1]){ shrinkedarr[kMin][0]=0; min=20; } } } int main(){ int arr[size][size]; fillm(arr); printf("Початкова матриця:\n"); printm(arr); int nozero = countnozero(arr); int shrinkedarr[nozero][3]; fillsm(nozero, shrinkedarr, arr); printf("\nСтиснена матриця:\n"); printsm(nozero, shrinkedarr); minToZero(nozero, shrinkedarr); createmfsm(nozero, shrinkedarr, arr); printf("\nМатриця без мінімальних значень рядів:\n"); printm(arr); printf("\nСкорочена матриця без мінімальних значень рядів:\n"); printsm(nozero, shrinkedarr); return 0; }

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

29.06.2023 21:45

Коментарі

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

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

поділитись