Advertisement
baadgeorge

Untitled

Jul 3rd, 2022
1,066
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <chrono>
  5.  
  6.  
  7. //структура для матрицы
  8. struct matrix {
  9.  
  10.     double** matr;
  11.     int size;
  12. };
  13.  
  14. //функция создания матрицы(выделение памяти и задание размера)
  15. matrix* CreateMatrix(int size) {
  16.  
  17.     matrix* main_matrix = new matrix;
  18.     main_matrix->size = size;
  19.     main_matrix->matr = new double* [size];
  20.     for (int i = 0; i < main_matrix->size; i++) {
  21.         main_matrix->matr[i] = new double[main_matrix->size];
  22.     }
  23.     return main_matrix;
  24. }
  25.  
  26. //функция удаления матрицы
  27. void DeleteMatrix(matrix* mtrx) {
  28.  
  29.     // очистка памяти
  30.     for (int j = 0; j < mtrx->size; j++) {
  31.         delete[] mtrx->matr[j];
  32.     }
  33.     delete mtrx->matr;
  34.     mtrx->size = 0;
  35. }
  36.  
  37. //функция поиска строки с максимальным элементом в i-м столбце
  38. int RowMax(matrix* mtrx, int StartCol) {
  39.  
  40.     double max = std::abs(mtrx->matr[StartCol][StartCol]);
  41.     int maxPos = StartCol;
  42.     for (int i = StartCol + 1; i < mtrx->size; i++) {
  43.         double tmp = std::abs(mtrx->matr[i][StartCol]);
  44.         if (tmp > max) {
  45.             max = tmp;
  46.             maxPos = i;
  47.         }
  48.     }
  49.     return maxPos;
  50. }
  51.  
  52. //функция приведения матрицы к треугольному виду путем элементарных преобразований
  53. int Triangulation(matrix* mtrx) {
  54.  
  55.     int SwapCount = 0;
  56.     double tmp;
  57.     for (int i = 0; i < mtrx->size; i++) {
  58.         int iMax = RowMax(mtrx, i);
  59.         if (i != iMax) {
  60.             std::swap(mtrx->matr[i], mtrx->matr[iMax]);
  61.             SwapCount++; //считаем число перестановок строк
  62.         }
  63.  
  64.  
  65.         for (int j = i + 1; j < mtrx->size; j++) {
  66.             double coeff = mtrx->matr[j][i] / mtrx->matr[i][i];
  67.             for (int k = i; k < mtrx->size; k++) {
  68.                 tmp = mtrx->matr[j][k] - mtrx->matr[i][k] * coeff;
  69.                 if (std::abs(tmp) < 1e-12) mtrx->matr[j][k] = 0.0;
  70.                 else mtrx->matr[j][k] = tmp;
  71.             }
  72.         }
  73.     }
  74.     return SwapCount;
  75.  
  76. }
  77.  
  78. //функция создания матрицы заданнного размера со случайными значениями
  79. matrix* RandomMatrix(int size) {
  80.  
  81.     std::srand(time(nullptr));
  82.     matrix* mtrx = CreateMatrix(size);
  83.     for (int i = 0; i < size; i++) {
  84.         for (int j = 0; j < size; j++) {
  85.             //debug
  86.             //mtrx->matr[i][j] = rand() % 10;
  87.  
  88.             //release
  89.             mtrx->matr[i][j] = double(rand() % 100)/1000;
  90.         }
  91.     }
  92.     return mtrx;
  93. }
  94.  
  95. //функция вывода матрицы на экран
  96. void OutputMatrix(matrix* mtrx) {
  97.  
  98.     for (int i = 0; i < mtrx->size; i++) {
  99.         for (int j = 0; j < mtrx->size; j++) {
  100.             std::cout << std::setw(13) << mtrx->matr[i][j] << " ";
  101.         }
  102.         std::cout << std::endl;
  103.     }
  104.     std::cout << std::endl;
  105.     return;
  106. }
  107.  
  108. //функция копирования матрицы
  109. matrix* CopyMatrix(matrix* matrix_SRC) {
  110.  
  111.     matrix* matrix_DST = CreateMatrix(matrix_SRC->size);
  112.     if (matrix_SRC->size != matrix_DST->size) {
  113.         std::cout << "Copy error!" << std::endl;
  114.         return NULL;
  115.     }
  116.     for (int i = 0; i < matrix_SRC->size; i++) {
  117.         for (int j = 0; j < matrix_SRC->size; j++) {
  118.             matrix_DST->matr[i][j] = matrix_SRC->matr[i][j];
  119.         }
  120.  
  121.     }
  122.     return matrix_DST;
  123. }
  124.  
  125. //функция вычисления оперделителя матрицы методом Гаусса
  126. double GaussDet(matrix* mtrx) {
  127.  
  128.     double det;
  129.     switch (mtrx->size) {
  130.     case 0:
  131.         det = 0;
  132.         break;
  133.     case 1:
  134.         det = mtrx->matr[0][0];
  135.         break;
  136.     case 2:
  137.         det = mtrx->matr[0][0] * mtrx->matr[1][1] - mtrx->matr[0][1] * mtrx->matr[1][0];
  138.         break;
  139.     default:
  140.         //создание копии исходной матрицы для приведения к треугольному виду
  141.         //и вычисления определителя
  142.         matrix* tr_matrix = CopyMatrix(mtrx);
  143.  
  144.         int SwapCount = Triangulation(tr_matrix);
  145.         det = 1;
  146.         if (SwapCount % 2 == 1)
  147.         {
  148.             det = -1;
  149.         }
  150.         for (int i = 0; i < tr_matrix->size; i++) {
  151.             det *= tr_matrix->matr[i][i];
  152.         }
  153.  
  154.         //debug
  155.         //std::cout << "Triangle matrix:" << std::endl;
  156.         //OutputMatrix(tr_matrix);
  157.  
  158.         DeleteMatrix(tr_matrix);
  159.     }
  160.     return det;
  161. }
  162.  
  163. //функция транспонирования матрицы
  164. matrix* TransposeMatrix(matrix* mtrx) {
  165.  
  166.     matrix* tr_matrix = CreateMatrix(mtrx->size);
  167.     for (int i = 0; i < tr_matrix->size; i++) {
  168.         for (int j = 0; j < tr_matrix->size; j++) {
  169.  
  170.             //std::swap(tr_matrix->matr[i][j], tr_matrix->matr[j][i]);
  171.             tr_matrix->matr[i][j] = mtrx->matr[j][i];
  172.  
  173.         }
  174.     }
  175.     //debug
  176.     //OutputMatrix(tr_matrix);
  177.     return tr_matrix;
  178. }
  179.  
  180. //функция вычисления алгебраического дополнения для элемента матрицы
  181. double Cofactor(matrix* mtrx, matrix* minor, int row, int col) {
  182.  
  183.     int minor_row, minor_col;
  184.     //int minor_size = min->size - 1;
  185.     int cofactor;
  186.     int sign = ((row + col) % 2) ? -1 : 1;
  187.  
  188.     for (int i = 0; i < mtrx->size; i++) {
  189.  
  190.         minor_row = i;
  191.         if (i > row) minor_row--;
  192.  
  193.         for (int j = 0; j < mtrx->size; j++) {
  194.             minor_col = j;
  195.             if (j > col) minor_col--;
  196.             if (i != row && j != col) {
  197.                 minor->matr[minor_row][minor_col] = mtrx->matr[i][j];
  198.             }
  199.             //OutputMatrix(matrix, size);
  200.         }
  201.     }
  202.     cofactor = sign * GaussDet(minor);
  203.  
  204.     // debug
  205.     /*std::cout << "\nsome minor" << std::endl;
  206.     OutputMatrix(minor);
  207.     std::cout << "det of minor = " << GaussDet(minor) << std::endl;*/
  208.  
  209.     return cofactor;
  210. }
  211.  
  212. //функция вычисления обратной матрицы
  213. matrix* InverseMatrix(matrix* mtrx, double det) {
  214.  
  215.     //временная матрица для миноров матрицы
  216.     matrix* tmp_minor = CreateMatrix(mtrx->size - 1);
  217.  
  218.     //результирующая матрица
  219.     matrix* res_matrix = CreateMatrix(mtrx->size);
  220.  
  221.     //транспонированная матрица
  222.     matrix* tr_matrix = TransposeMatrix(mtrx);
  223.  
  224.     //debug
  225.     /*std::cout << "Transposed matrix " << std::endl;
  226.     OutputMatrix(tr_matrix);*/
  227.  
  228.     double cofactor;
  229.  
  230.     //алгебраические дополнения для элементов матрицы
  231.     for (int i = 0; i < res_matrix->size; i++) {
  232.         for (int j = 0; j < res_matrix->size; j++) {
  233.  
  234.             cofactor = Cofactor(tr_matrix, tmp_minor, i, j);
  235.  
  236.             if (std::abs(cofactor) < 1e-12) res_matrix->matr[i][j] = 0.0;
  237.             else res_matrix->matr[i][j] = cofactor / det;
  238.         }
  239.     }
  240.  
  241.     //очистка памяти под миноры
  242.     DeleteMatrix(tmp_minor);
  243.     delete tmp_minor;
  244.  
  245.     //очистка памяти под транспонированную матрицу
  246.     DeleteMatrix(tr_matrix);
  247.     delete tr_matrix;
  248.  
  249.     return res_matrix;
  250. }
  251.  
  252.  
  253.  
  254. int main(int argc, char* argv[]) {
  255.  
  256.     /*if (argc < 1) {
  257.         std::cout << "Wrong size!" << std::endl;
  258.         return -1;
  259.     }
  260.  
  261.     int size = std::stoi(argv[1]);*/
  262.  
  263.     int size = 10;
  264.  
  265.     //исходная матрица
  266.     matrix* main_matrix = RandomMatrix(size);
  267.  
  268.     /*std::cout << "Main matrix " << std::endl;
  269.     OutputMatrix(main_matrix);*/
  270.     std::cout << "OnePointerMatrix with size " << size << std::endl;
  271.  
  272.     auto start = std::chrono::steady_clock::now();
  273.     double det = GaussDet(main_matrix);
  274.     //std::cout << "Determinant of main matrix: " << det << std::endl;
  275.     if (det == 0) {
  276.         std::cout << "Inverse matrix doesn't exist!";
  277.         return -1;
  278.     }
  279.  
  280.     //обратная матрица
  281.     matrix* inverse_matrix = InverseMatrix(main_matrix, det);
  282.  
  283.     auto end = std::chrono::steady_clock::now();
  284.  
  285.     std::chrono::duration<double> elapsed = end - start;
  286.     std::cout << "Executions time: " << elapsed.count() << " seconds" << std::endl;
  287.  
  288.     /*std::cout << "\nInversed matrix " << std::endl;
  289.     OutputMatrix(inverse_matrix);*/
  290.  
  291.     //очистка памяти под обратную матрицу
  292.     DeleteMatrix(inverse_matrix);
  293.     delete inverse_matrix;
  294.  
  295.     //очистка памяти под исходную матрицу
  296.     DeleteMatrix(main_matrix);
  297.     delete main_matrix;
  298.  
  299.     return 0;
  300. }
Advertisement
RAW Paste Data Copied
Advertisement