Fişierul intrare/ieşire:	gauss.in, gauss.out	Sursă	Arhiva Educationala
Autor	Arhiva Educationala	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	0.2 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Algoritmul lui Gauss

Se da un sistem de N ecuatii liniare cu M necunoscute. Notam necunoscutele cu x_i, 1 ≤ i ≤ M. Sa se determine, daca acest lucru este posibil, un set de valori ale necunoscutelor pentru care fiecare ecuatie este adevarata. Sistemul va fi dat sub forma unei matrici A cu N linii si M+1 coloane. Pe linia i a acestei matrici se va afla descrierea ecuatiei cu numarul i din sistem, astfel: A_i,1 * x₁ + A_i,2 * x₂ + ... + A_i,M * x_M = A_i,M+1.

Date de intrare

Pe prima linie a fişierului de intrare gauss.in se vor afla numerele N si M cu semnificatia din enunt. Pe urmatoarele N linii se vor afla cate M+1 intregi, descriind matricea A.

Date de ieşire

În fişierul de ieşire gauss.out se vor afisa M numere reale, cu precizia de 4 zecimale, reprezentand valorile sirului x, in cazul in care sistemul are solutie. In caz contrar, se va afisa mesajul "Imposibil".

Restricţii

• 1 ≤ N, M ≤ 100
• -100 ≤ A_i,j ≤ 100
• Solutia va fi considerata corecta daca, pentru fiecare i, 1 ≤ i ≤ N, rezultatul expresiei A_i,1 * x₁ + A_i,2 * x₂ + ... + A_i,M * x_M difera prin maxim 0.001 de A_i,M+1.

Exemplu

Explicatie

• 2 * 2 + 1 * 3 + (-1) * (-1) = 4 + 3 + 1 = 8
• (-3) * 2 + (-1) * 3 + 2 * (-1) = -6 - 3 - 2 = -11
• (-2) * 2 + 1 * 3 + 2 * (-1) = -4 + 3 - 2 = -3

Indicatii de rezolvare

Eliminarea Gaussiana este cel mai folosit algoritm pentru rezolvarea sistemelor de ecuatii liniare. Metoda reduce succesiv ecuatiile, lasand matricea initiala sub o forma din care vom putea afla usor valorile necunoscutelor. Astfel, notand cu p_i pozitia celui mai din stanga coeficient nenul de pe linia i, algoritmul garanteaza obtinerea urmatoarului sir de relatii: p₁ < p₂ < ... < p_N (1). Aceste pozitii vor fi chiar indicii necunoscutelor fixe, cele care pot lua o singura valoare pentru ca sistemul sa aiba in continuare solutie. Celelalte necunoscute, ale caror indici nu se regasesc printre aceste pozitii, pot lua orice valoare si se numesc variabile libere. Pentru a usura calculele, vom considera in continuare ca acestea iau valoarea 0.

In continuare vom descrie algoritmul propriu-zis. Pornim cu un indice pentru linii, sa-l notam i, si un indice pentru coloane, j, initializate initial cu 1. Cautam pe coloana j, o linie x, i ≤ x astfel incat A_x,j ≠ 0. Daca aceasta linie nu exista, inseamna ca necunoscuta cu indicele j este variabila libera, iar noi incrementam indicele j. Altfel, interschimbam liniile i si x si impartim toata ecuatia de pe linia i la A_i,j. In continuare vom scadea ecuatia i din toate ecuatiile u, i < u, astfel incat toti coeficientii A_u,j sa devina 0. Acest lucru este necesar pentru respectarea conditiei (1), avand in vedere ca nu putem avea x ≠ i cu $p_x = p_i.

Cum se trimit solutii?