#include "stdafx.h"
#include "math.h"
#include "iostream"
#include "iomanip"
#include "time.h"
using namespace std;

int SLAU(double **matrica_a, int n, double *massiv_b, double *x)                 //функция необходимых преобразовании
{
	int i, j, k, r;                                         //
	double c, M, max, s, **a, *b;                           //
	a = new double *[n];                                    //
	for (i = 0; i < n; i++)                                 //инициализация необходимых переменных и массивов
	{                                                       //
		a[i] = new double[n];                               //
	}                                                       //
	b = new double[n];
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			a[i][j] = matrica_a[i][j];
		}
	}
	for (i = 0; i < n; i++)
	{
		b[i] = massiv_b[i];
	}
	for (k = 0; k<n; k++)
	{
		max = fabs(a[k][k]);
		r = k;
		for (i = k + 1; i<n; i++)
		{
			if (fabs(a[i][k])>max)
			{
				max = fabs(a[i][k]);
				r = i;
			}
		}
		for (j = 0; j<n; j++)
		{
			c = a[k][j];
			a[k][j] = a[r][j];
			a[r][j] = c;
		}
		c = b[k];
		b[k] = b[r];
		b[r] = c;
		for (i = k + 1; i<n; i++)
		{
			for (M = a[i][k] / a[k][k], j = k; j < n; j++)
			{
				a[i][j] -= M*a[k][j];
			}
			b[i] -= M*b[k];
		}
	}
	if (a[n - 1][n - 1] == 0)
	{
		if (b[n - 1] == 0)
			return -1;
		else return -2;
	}
	else
	{
		for (i = n - 1; i >= 0; i--)
		{
			for (s = 0, j = i + 1; j < n; j++)
			{
				s += a[i][j] * x[j];
			}
			x[i] = (b[i] - s) / a[i][i];
		}
		return 0;
	}
	for (i = 0; i < n; i++)
	{
		delete[] a[i];
	}
	delete[] a;
	delete[] b;
}

int parralelSLAU(double **matrica_a, int n, double *massiv_b, double *x)                 //функция необходимых преобразовании
{
	int i, j, k, r;                                         //
	double c, M, max, s, **a, *b;                           //
	a = new double *[n];                                    //
	for (i = 0; i < n; i++)                                 //инициализация необходимых переменных и массивов
	{                                                       //
		a[i] = new double[n];                               //
	}                                                       //
	b = new double[n];
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			a[i][j] = matrica_a[i][j];
		}
	}
	for (i = 0; i < n; i++)
	{
		b[i] = massiv_b[i];
	}
	for (k = 0; k<n; k++)
	{
		max = fabs(a[k][k]);
		r = k;
		for (i = k + 1; i<n; i++)
		{
			if (fabs(a[i][k])>max)
			{
				max = fabs(a[i][k]);
				r = i;
			}
		}
		for (j = 0; j<n; j++)
		{
			c = a[k][j];
			a[k][j] = a[r][j];
			a[r][j] = c;
		}
		c = b[k];
		b[k] = b[r];
		b[r] = c;
		for (i = k + 1; i<n; i++)
		{
			for (M = a[i][k] / a[k][k], j = k; j < n; j++)
			{
				a[i][j] -= M*a[k][j];
			}
			b[i] -= M*b[k];
		}
	}
	if (a[n - 1][n - 1] == 0)
	{
		if (b[n - 1] == 0)
			return -1;
		else return -2;
	}
	else
	{
		for (i = n - 1; i >= 0; i--)
		{
			for (s = 0, j = i + 1; j < n; j++)
			{
				s += a[i][j] * x[j];
			}
			x[i] = (b[i] - s) / a[i][i];
		}
		return 0;
	}
	for (i = 0; i < n; i++)
	{
		delete[] a[i];
	}
	delete[] a;
	delete[] b;
}

int INVERSE(double **a, int n, double **y, int choise)                                 //функция нахождения обратной матрицы
{
	int i, j, res;
	double *b, *x;
	b = new double[n];
	x = new double[n];
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (j == i)
				b[j] = 1;
			else b[j] = 0;
		}
		if(choise == 0)
			res = SLAU(a, n, b, x);
		else res = parralelSLAU(a, n, b, x);
		if (res != 0)
			break;
		else
		{
			for (j = 0; j < n; j++)
			{
				y[j][i] = x[j];
			}
		}
	}
	delete[] x;
	delete[] b;
	if (res != 0)
		return -1;
	else return 0;
}

int main()
{
	setlocale(LC_ALL, "Rus");
	srand(time(NULL));
	int result, i, j, N;
	double **a, **b;
	cout << "N = ";
	cin >> N;                   //ввод размера
	a = new double *[N];
	for (i = 0; i < N; i++)
	{
		a[i] = new double[N];                 //инициализация пустого двумерного массива для исходной матрицы
	}
	b = new double *[N];
	for (i = 0; i < N; i++)
	{
		b[i] = new double[N];               //инициализация пустого двумерного массива для обратной матрицы
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if(i == j)
				a[i][j] = rand() % 10 + 1;
			else a[i][j] = rand() % 11;                         //генерация значении исходной матрицы
		}
	}
	cout << "Сгенерированная матрица" << endl;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cout << a[i][j] << " ";                         // вывод сгенерированной матрицы
		}
		cout << endl;
	}
	int k = 0;
	for (i = 0; i < N; i++)                                 //
	{                                                       // проверка на наличие нулей в главной диагонали
		if (a[i][i] == 0)                                   //
			k++;                                            //
	}
	if (k == 0)
	{
		clock_t startTime1 = clock();                                              //начало выполнения основной функции
		result = INVERSE(a, N, b, 0);          //нахождение обратной матрицы
		clock_t finishTime1 = clock();                                             //конец выполнения основной функции
		clock_t searchTime1 = (double)(finishTime1 - startTime1) / (double)CLOCKS_PER_SEC * 1000000.0;         //вычисление разницы от начала до конца выполнения функции

		b = new double *[N];
		for (i = 0; i < N; i++)
		{
			b[i] = new double[N];               //инициализация пустого двумерного массива для обратной матрицы
		}

		clock_t startTime2 = clock();                                             //начало выполнения основной функции
		result = INVERSE(a, N, b, 1);          //нахождение обратной матрицы
		clock_t finishTime2 = clock();                                             //конец выполнения основной функции
		clock_t searchTime2 = (double)(finishTime2 - startTime2) / (double)CLOCKS_PER_SEC * 1000000.0;         //вычисление разницы от начала до конца выполнения функции
		if (result == 0)
		{
			cout << "Обратная матрица" << endl;
			for (i = 0; i < N; cout << endl, i++)
			{
				for (j = 0; j < N; j++)
				{
					cout << setprecision(3) << b[i][j] << "\t";                  //вывод обратной матрицы
				}
			}
			cout << "Время работы последовательного кода в микросекундах - " << searchTime1 << endl;
			cout << "Время работы параллельного кода в микросекундах - " << searchTime2 << endl;
		}
		else cout << "Обратной матрицы не существует" << endl;
	}
	else cout << "Диагональ содержит нули!";
	for (i = 0; i < N; i++)
	{
		delete[] a[i];
	}
	delete[] a;
	for (i = 0; i < N; i++)
	{
		delete[] b[i];
	}
	delete[] b;

	system("pause");
	return 0;
}