Last active
November 2, 2017 19:00
-
-
Save aviskase/b3baf9e9db1a6f7f964c to your computer and use it in GitHub Desktop.
Домашка по первой неделе для ликбеза по дискретной математики. Решение СЛАУ методом Гаусса.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner; | |
import java.util.Arrays; | |
import java.util.ArrayList; | |
class Main { | |
public static void main(String[] args) { | |
Solver s = new Solver(); | |
s.solveGaussian(); | |
} | |
} | |
class Solver { | |
private double[][] T; | |
private double[] roots; | |
private void printT() { | |
for (double[] item : T) { | |
System.out.println(Arrays.toString(item)); | |
} | |
System.out.println(); | |
} | |
private void printRoots() { | |
String rootsString = ""; | |
for (double item : roots) { | |
rootsString += item + " "; | |
} | |
System.out.println(rootsString); | |
} | |
private boolean swapRow(int row) { | |
for (int i = row+1; i < T.length; i++) { | |
if (T[i][row] != 0) { | |
double[] tmpRow = T[row]; | |
T[row] = T[i]; | |
T[i] = tmpRow; | |
return true; | |
} | |
} | |
return false; | |
} | |
private int findNextX(int oldX, int row) { | |
for (int i = oldX; i < T[row].length; i++) { | |
if (T[row][i] != 0) { | |
return i; | |
} | |
} | |
return -1; | |
} | |
private boolean isZero(double a) { | |
final double EPSILON = 1E-14; | |
return (Math.abs(a) <= EPSILON); | |
} | |
private void parseInput() { | |
Scanner s = new Scanner(System.in); | |
int n = s.nextInt(); | |
int m = s.nextInt() + 1; | |
T = new double[n][m]; | |
roots = new double[m-1]; | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
T[i][j] = s.nextDouble(); | |
} | |
} | |
} | |
private void forwardPass() { | |
int x = 0; | |
for (int i = 0; i < T.length-1; i++, x++) { | |
if (T[i][x] == 0) { | |
boolean isSwapped = swapRow(i); | |
if (!isSwapped) { | |
x = findNextX(x, i); | |
} | |
} | |
for (int j = i+1; j < T.length; j++) { | |
double coef = -T[j][x] / T[i][x]; | |
for (int k = x; k < T[i].length; k++) { | |
T[j][k] += T[i][k] * coef; | |
} | |
} | |
cleanT(); | |
} | |
} | |
private boolean containsOnlyZeros(double[] arr) { | |
boolean answer = false; | |
for (double item : arr) { | |
if (!isZero(item)) { | |
return false; | |
} else { | |
answer = true; | |
} | |
} | |
return answer; | |
} | |
private void cleanT() { | |
ArrayList<double[]> newT = new ArrayList<double[]>(); | |
for (double[] item : T) { | |
if (!containsOnlyZeros(item)) { | |
newT.add(item); | |
} | |
} | |
T = newT.toArray(new double[newT.size()][T[0].length]); | |
} | |
private int checkRoots() { | |
// "YES" = 0, "INF" = 1, "NO" = -1 | |
for (double[] item : T) { | |
boolean condition = (!isZero(item[item.length-1])) && (containsOnlyZeros(Arrays.copyOfRange(item, 0, item.length-1))); | |
if (condition) { | |
return -1; | |
} | |
} | |
if (T.length < (T[0].length - 1)) { | |
return 1; | |
} | |
return 0; | |
} | |
private void backwardPass() { | |
for (int i = T.length-1; i >= 1; i--) { | |
for (int j = i-1; j >= 0; j--) { | |
double coef = -T[j][i] / T[i][i]; | |
for (int k = T[i].length-1; k >= 0; k--) { | |
T[j][k] += T[i][k] * coef; | |
} | |
} | |
} | |
for (int i = 0; i < T.length; i++) { | |
roots[i] = T[i][T[i].length-1] / T[i][i]; | |
} | |
} | |
public void solveGaussian() { | |
parseInput(); | |
forwardPass(); | |
cleanT(); | |
int check = checkRoots(); | |
if (check == -1) { | |
System.out.println("NO"); | |
} else if (check == 1) { | |
System.out.println("INF"); | |
} else { | |
System.out.println("YES"); | |
backwardPass(); | |
printRoots(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment