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

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

ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано

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

Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів

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

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені  ІГОРЯ СІКОРСЬКОГО”                     ЗВІТ з лабораторної роботи №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:06-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!