Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- class Gauss {
- public static int gcd(int a, int b) {
- while (b != 0) {
- int tmp = a % b;
- a = b;
- b = tmp;
- }
- return a;
- }
- public static void main(String[] args) {
- Scanner s = new Scanner(System.in);
- int n = s.nextInt();
- int m = n;
- int[][] A_num_arr = new int[n][n];
- int[][] A_den_arr = new int[n][n];
- int[] b_num_arr = new int[n];
- int[] b_den_arr = new int[n];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- A_num_arr[i][j] = s.nextInt();
- A_den_arr[i][j] = 1;
- }
- b_num_arr[i] = s.nextInt();
- b_den_arr[i] = 1;
- }
- int N = n;
- for (int p = 0; p < N; p++) {
- int max = p;
- for (int i = p + 1; i < N; i++) {
- if (Math.abs((double) A_num_arr[i][p] / A_den_arr[i][p]) > Math.abs((double) A_num_arr[max][p] / A_den_arr[max][p])) {
- max = i;
- }
- }
- int[] temp1 = A_num_arr[p];
- A_num_arr[p] = A_num_arr[max];
- A_num_arr[max] = temp1;
- int[] temp2 = A_den_arr[p];
- A_den_arr[p] = A_den_arr[max];
- A_den_arr[max] = temp2;
- int t1 = b_num_arr[p];
- b_num_arr[p] = b_num_arr[max];
- b_num_arr[max] = t1;
- int t2 = b_den_arr[p];
- b_den_arr[p] = b_den_arr[max];
- b_den_arr[max] = t2;
- if (Math.abs((double) A_num_arr[p][p] / A_den_arr[p][p]) <= 1e-10) {
- System.out.println("No solution");
- return;
- }
- for (int i = p + 1; i < N; i++) {
- int r_num = A_num_arr[i][p] * A_den_arr[p][p];
- int r_den = A_den_arr[i][p] * A_num_arr[p][p];
- b_num_arr[i] = b_num_arr[i] * r_den * b_den_arr[p] - b_den_arr[i] * r_num * b_num_arr[p];
- b_den_arr[i] = b_den_arr[i] * r_den * b_den_arr[p];
- int gcd = gcd(b_num_arr[i], b_den_arr[i]);
- b_num_arr[i] = b_num_arr[i] / gcd;
- b_den_arr[i] = b_den_arr[i] / gcd;
- for (int j = p; j < N; j++) {
- A_num_arr[i][j] = A_num_arr[i][j] * r_den * A_den_arr[p][j] - A_den_arr[i][j] * r_num * A_num_arr[p][j];
- A_den_arr[i][j] = A_den_arr[i][j] * r_den * A_den_arr[p][j];
- gcd = gcd(A_num_arr[i][j], A_den_arr[i][j]);
- A_num_arr[i][j] = A_num_arr[i][j] / gcd;
- A_den_arr[i][j] = A_den_arr[i][j] / gcd;
- }
- }
- }
- int[] x_num = new int[N];
- int[] x_den = new int[N];
- for (int i = N - 1; i >= 0; i--) {
- int sum_num = 0;
- int sum_den = 1;
- for (int j = i + 1; j < N; j++) {
- sum_num = sum_num * A_den_arr[i][j] * x_den[j] + sum_den * A_num_arr[i][j] * x_num[j];
- sum_den = sum_den * A_den_arr[i][j] * x_den[j];
- int gcd = gcd(sum_num, sum_den);
- sum_num = sum_num / gcd;
- sum_den = sum_den / gcd;
- }
- x_num[i] = (b_num_arr[i] * sum_den - sum_num * b_den_arr[i]) * A_den_arr[i][i];
- x_den[i] = b_den_arr[i] * sum_den * A_num_arr[i][i];
- int gcd = gcd(x_num[i], x_den[i]);
- x_num[i] = x_num[i] / gcd;
- x_den[i] = x_den[i] / gcd;
- }
- for (int i = 0; i < N; i++) {
- if (x_den[i] < 0) {
- x_den[i] = x_den[i] * (-1);
- x_num[i] = x_num[i] * (-1);
- }
- System.out.println(x_num[i] + "/" + x_den[i]);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement