Cod sursa(job #770943)

Utilizator mi5humihai draghici mi5hu Data 24 iulie 2012 13:40:22
Problema Algoritmul lui Gauss Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <stdio.h>
#define NMAX 302

using namespace std;

float a[NMAX][NMAX+1];
int poz[NMAX];
int Line[NMAX];
float Rez[NMAX];

int n, m;

void read_() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m + 1; j++) {
            scanf("%f", &a[i][j]);
        }
    } 
}

bool get_sol() {
    for (int j = m; j>= 1; j--) {
        int i = Line[j];
        if (i != 0) {
            Rez[j] = a[i][m + 1] / a[i][j];
            for (int ii = 1; ii <= n; ii++) {
                a[ii][m + 1] -= (a[ii][j] * Rez[j]);
            }
        } else {
            if (a[i][m + 1] != 0) {
                return false;           
            }
            Rez[j] = 0;       
        }        
    }
    return true; 
}

bool check_() {
    if (n > m) {
        for (int i = m + 1; i <= n; i++) {
           if (a[i][m + 1] != 0) {
               return false;
           }
        }
        return true; 
    } 
    return true;
}

bool solve_() {
    int diagN = n < m ? n : m;
    for (int j = 1; j <= diagN; j++) {
        for (int i = 1; i <= n; i++) {
             if (poz[i] == 0 && a[i][j] != 0) { 
                 float  val = a[i][j];
                 for (int jj = j; jj <= m + 1; jj++) {                    
                     a[i][jj] /= val;
                 }                          
                 poz[i] = j;
                 Line[j] = i;        
                 for (int ii = 1; ii <= n; ii++) {
                     if (poz[ii] == 0 && a[ii][j] != 0) {
                         val = a[ii][j];
                         for (int jj = j; jj <= m + 1; jj++) {
                             a[ii][jj] -= (a[i][jj] *val);
                         }            
                     }
                 }
                 break;
             }
        }
    }          
    return (get_sol() && check_());
}

void print_(bool sol) {
    if (sol == false) {
        printf("Imposibil");        
    } else {
        for (int i = 1; i <= m; i++) {
            printf("%.10f ", Rez[i]);
        }
    }
}

int main() {
    freopen("gauss.in", "r", stdin);
    freopen("gauss.out", "w", stdout);
    
    read_();
    bool sol = solve_();
    print_(sol);
 
    return 0;
}