Pagini recente » Cod sursa (job #124474) | Cod sursa (job #333489) | Cod sursa (job #815340) | Cod sursa (job #2694089) | Cod sursa (job #811050)
Cod sursa(job #811050)
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#define MLen 301
#define NLen 302
#define EPS 0.001
using namespace std;
double A[MLen][NLen];
double x[NLen];
int main()
{
freopen("gauss.in","r",stdin);
freopen("gauss.out","w",stdout);
int M,N;
cin>>M>>N; // M ecuatii, N necunoscute
++N; // in matricea A memorez pe coloana N vectorul de solutii B
for(int i=1;i<=M;++i)
for(int j=1;j<=N;++j)
cin>>A[i][j];
/* schimb forma lui A intr-una care ma ajuta sa calculez mai usor vectorul x
* iau num(i) = numarul de elem nule consecutive incepand cu coloana 1 de pe linia i
*
* A' (matricea A modificata) va avea urmatoarea proprietate:
* num(1) < num(2) < num(3) < .. < num(M)
*
* OBSERVATIE 0: Daca M(numar ecuatii) < N(numar necunoscute) nu inseamna ca nu am solutie.
* Pot exista variabile libere si N(devine numarul variabilelor fixe necunoscute) poate ajunge <= M.
*/
for(int R=1,C=1;R<=M&&C<N;) // R-row, C-column
{
// caut un element nenul pe coloana C
// daca acest element nu exista atunci x[C] este o variabila libera
if(A[R][C]==0) // daca A[R][C] = 0 caut o alta linie care are A[i][C] nenul, unde R < i <= M
{
int nR=0;
for(int i=R+1;i<=M;++i)
if(A[i][C])
{
nR=i;
break;
}
if(nR==0) // nu am gasit o linie cu elementul de pe coloana C nenul => x[C] este variabila libera
{
++C;
continue;
}
else
for(int j=C;j<=N;++j) // interschimb 2 linii
swap(A[R][j],A[nR][j]);
}
for(int j=C+1;j<=N;++j) A[R][j]/=A[R][C]; // vreau ca linia R sa aiba forma (0, 0, .. 0, 1, ...)
A[R][C]=1;
// reduc celelate linii a.i A[i][C] = 0, unde R < i <= M
// ma folosesc de linia R pe care o inmultesc cu A[i][C] si o scad din linia i
// A[R][C] = 1
for(int i=R+1;i<=M;++i)
if(A[i][R]!=0)
{
for(int j=C+1;j<=N;++j)
A[i][j]-=A[i][C]*A[R][j];
A[i][C]=0;
}
++R, ++C;
}
/* caut solutiile parcurgand matricea A' de jos in sus
*
* fie linia i care are forma (0, 0, .., 0, 1, d[j+1], d[j+2], .. ,d[N-1]), cu num(i) 0-uri in fata
* eu voi calcula x[j] = d[N] - suma(x[k] * d[k]), j < k < N
*
* cum num(i) < num(orice linie cu indicele > i) si j=num(i) + 1 atunci inseamna ca eu deja stiu x[k]
*
* OBSERVATIE 1: Daca am o linie de forma (0, 0, .., 0, z), z != 0 , atunci NU am solutie la sistem
* OBSERVATIE 2: Variabilele libere pot avea orice valoare (aici vor fi 71)
*/
for(int i=1;i<N;++i) x[i]=71;
for(int R=M;R>0;--R)
{
int C=1;
while(A[R][C]==0&&C<N) ++C;
if(C==N&&abs(A[R][N])>EPS) // vezi OBSERVATIA 1
{
cout<<"Imposibil\n";
return 0;
}
x[C]=A[R][N]; // calculez x[C]
for(int j=C+1;j<N;++j)
x[C]-=x[j]*A[R][j];
}
// afisare
for(int i=1;i<N;++i) printf("%.10lf ",x[i]);
cout<<'\n';
return 0;
}