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