Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розріджені матриці
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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;
}
Висновок: У цій лабораторної роботі ознайомилися з роботою з роздріженою матрицею. Розробили таким чином економний спосіб зберігання матриці. Виконали завдання згідно до індивідуального варіанту. Зроблено звіт до лабораторної роботи та надіслано викладачу.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора