Cod sursa(job #1040003)

Utilizator sziliMandici Szilard szili Data 23 noiembrie 2013 20:47:51
Problema Algoritmul lui Gauss Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 3.22 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 301
#define MAX_M 310

using namespace std;

int n,m;
double coeff[MAX_N][MAX_M];

double variables[MAX_N];
int p[MAX_M];
int isSuccessful = 1;

int obtainNonNullIndex(int i, int j){
    for (int r=i; r<n; r++){
        if (coeff[r][j] != 0.0){
            return r;
        }
    }

    return -1;
}

void swapEquations(int eq1, int eq2){
    double swapp;

    for (int j = 0; j<m+1; j++){
        swapp = coeff[eq1][j];
        coeff[eq1][j] = coeff[eq2][j];
        coeff[eq2][j] = swapp;
    }
}


void divideEquationBy(int eq, double divisor){

    for (int i=0; i<m+1; i++){
        coeff[eq][i]  = coeff[eq][i]/divisor;
    }
}

int consistentRemainingEquations(int i){
    for (int r=i; r<n; r++){
        if (coeff[r][m] != 0.0){
            return 0;
        }
    }

    return 1;
}

int main()
{
    freopen("gauss.in", "r", stdin);
    freopen("gauss.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int number;
    for (int i=0; i<n; i++){
        for (int j=0; j<(m+1); j++){
            scanf("%d", &number);
            coeff[i][j] = (double)number;
        }
    }

    int j=0;
    int i=0;

    for (i=0; i<n && j<m; i++){
        int nonNullIndex = obtainNonNullIndex(i, j);

        if (nonNullIndex != -1){
            if (nonNullIndex != i){
                swapEquations(i, nonNullIndex);
            }

            divideEquationBy(i, coeff[i][j]);
            //now coeff[i][j] should be 1

            int r = i+1;

            while (r<n){
                if (coeff[r][j] != 0.0){
                    //we should eliminate coeff[r][j] a.i. we should make it 0
                    double multFactor = coeff[r][j] / (-1.0);

                    for (int ss=j; ss<m+1; ss++){
                        coeff[r][ss] = coeff[r][ss] + coeff[i][ss]*multFactor;
                    }
                }

                r++;
            }

        }

        j++;
    }

    // cases: 1) we have more equations than variables (m > n)
    //          ==-> need to check if the remaining equations are "0" (the sistem is compatible)

    //        2) more variables than equations. In this case suppose that the remaining variables are 0.

    if (m > n) {
        if (!consistentRemainingEquations(i)){
            printf("Imposibil");
            isSuccessful = 0;
        }
    }

    j--;
    i--;
    if (isSuccessful){
        while (i >= 0){
            // actually i == j

            if (coeff[i][j] == 0.0){
                if (coeff[i][m] != 0.0){
                    printf("Imposibil");
                    isSuccessful = 0;
                    break;
                }
            } else {
                int r = j;
                double partial = 0.0;
                while (r<m){
                    r++;
                    partial += coeff[i][r]*variables[r];
                }

                variables[j] =coeff[i][m] - partial;
            }

            i--;
            j--;
        }
    }


    if (isSuccessful){
        for (int i=0; i<m; i++){
            printf("%lf ", variables[i]);
        }
    }

    return 0;
}