Cod sursa(job #851214)

Utilizator Gady_paulGafton Paul Gady_paul Data 9 ianuarie 2013 18:18:25
Problema Algoritmul lui Gauss Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.95 kb
#include<iostream>
#include<fstream>
#include<vector>

#define epsilon 0.0000001

using namespace std;

void printMat(vector<vector<double> > a){
    for(unsigned int i=0; i<a.size(); i++){
        for(unsigned int j=0; j<a[i].size(); j++){
            cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
}

vector<vector<double> > read(){

    ifstream f("gauss.in");

    int n, m;

    f>>n>>m;

    vector<vector<double> > mat(n, vector<double> (++m));

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            f>>mat[i][j];
        }
    }

    return mat;
}

bool check(double a){

    if(a>0 && a-epsilon<=0)
        return true;
    else if(a<0 && a+epsilon>=0)
        return true;
    return false;

}

void swap(double &a, double &b){
    int d=a;
    a=b;
    b=d;
}

void swapLines(vector<vector<double> > &mat, int i, int j){
    for(unsigned int k=0; k<mat[0].size(); k++){
        swap(mat[i][k], mat[j][k]);
    }
}

void divideTwoLines(vector<vector<double> > &mat, int i, int j, int k){
    for(unsigned int q=0; q<mat[0].size(); q++){
        mat[j][q]-=mat[i][q]*k;
        if(check(mat[j][q]))
            mat[j][q]=0;
    }
}

void divideOnLine(vector<vector<double> > &mat, int i, int col, double k){
    for(unsigned int j=col; j<mat[0].size(); j++){
        mat[i][j]/=k;
    }
}

void diff(vector<vector<double> >&mat, int i, int j, double coef){
    for(unsigned int k=0; k<mat[0].size(); k++){
        mat[j][k]-=mat[i][k]*coef;
        if(check(mat[j][k]))
            mat[j][k]=0;
    }
}

int main(){

    vector<vector<double> > mat=read();

    int i=0; //lines
    int j=0; //columns

    while(i<mat[0].size() && j<mat.size()){

        int found=-1;

        for(unsigned int k=i; k<mat.size() && found==-1; k++){
            if(mat[k][j]!=0)
                found=k;
        }
        if(found==-1){
            j++;
        }else{
            if(found!=i)
                swapLines(mat, i, found);
            divideOnLine(mat, i, j, mat[i][j]);
            for(int k=mat.size()-1; k>i; k--){
                diff(mat, i, k, mat[k][j]);
            }
            i++;
            j++;
        }

    }

    vector<double> X(mat[0].size());

 //   printMat(mat);

    bool imposible=false;
    for(int i=X.size()-1; i>=0; i--){
        double res=mat[i][mat[i].size()-1];

        bool sol=false;
        for(int j=mat[i].size()-2; j>=i; j--){
            res-=mat[i][j]*X[j];
            if(mat[i][j]!=0)
                sol=true;
        }
//        if(!sol)
  //          cout<<"SD"<<i<<'\n';
        X[i]=res;
        if(!sol && mat[i][mat[i].size()-1]==0){
            X.erase(X.end()-1);
        }
        if(!sol && mat[i][mat[i].size()-1]!=0)
            imposible=true;
        if(!sol && mat[i][mat[i].size()-1]!=0)
            break;
    }


    freopen("gauss.out", "w", stdout);

    if(imposible){
        cout<<"Imposibil";
    }else{
        for(int i=0; i<X.size(); i++)
            cout<<X[i]<<' ';
    }   


    return 0;
}