Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.79 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. class Gauss {
  4. public static int gcd(int a, int b) {
  5. while (b != 0) {
  6. int tmp = a % b;
  7. a = b;
  8. b = tmp;
  9. }
  10. return a;
  11. }
  12.  
  13. public static void main(String[] args) {
  14. Scanner s = new Scanner(System.in);
  15. int n = s.nextInt();
  16. int m = n;
  17. int[][] A_num_arr = new int[n][n];
  18. int[][] A_den_arr = new int[n][n];
  19. int[] b_num_arr = new int[n];
  20. int[] b_den_arr = new int[n];
  21. for (int i = 0; i < n; i++) {
  22. for (int j = 0; j < m; j++) {
  23. A_num_arr[i][j] = s.nextInt();
  24. A_den_arr[i][j] = 1;
  25. }
  26. b_num_arr[i] = s.nextInt();
  27. b_den_arr[i] = 1;
  28. }
  29.  
  30. int N = n;
  31. for (int p = 0; p < N; p++) {
  32.  
  33. int max = p;
  34. for (int i = p + 1; i < N; i++) {
  35. 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])) {
  36. max = i;
  37. }
  38. }
  39. int[] temp1 = A_num_arr[p];
  40. A_num_arr[p] = A_num_arr[max];
  41. A_num_arr[max] = temp1;
  42. int[] temp2 = A_den_arr[p];
  43. A_den_arr[p] = A_den_arr[max];
  44. A_den_arr[max] = temp2;
  45. int t1 = b_num_arr[p];
  46. b_num_arr[p] = b_num_arr[max];
  47. b_num_arr[max] = t1;
  48. int t2 = b_den_arr[p];
  49. b_den_arr[p] = b_den_arr[max];
  50. b_den_arr[max] = t2;
  51.  
  52. if (Math.abs((double) A_num_arr[p][p] / A_den_arr[p][p]) <= 1e-10) {
  53. System.out.println("No solution");
  54. return;
  55. }
  56.  
  57. for (int i = p + 1; i < N; i++) {
  58. int r_num = A_num_arr[i][p] * A_den_arr[p][p];
  59. int r_den = A_den_arr[i][p] * A_num_arr[p][p];
  60. b_num_arr[i] = b_num_arr[i] * r_den * b_den_arr[p] - b_den_arr[i] * r_num * b_num_arr[p];
  61. b_den_arr[i] = b_den_arr[i] * r_den * b_den_arr[p];
  62. int gcd = gcd(b_num_arr[i], b_den_arr[i]);
  63. b_num_arr[i] = b_num_arr[i] / gcd;
  64. b_den_arr[i] = b_den_arr[i] / gcd;
  65. for (int j = p; j < N; j++) {
  66. 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];
  67. A_den_arr[i][j] = A_den_arr[i][j] * r_den * A_den_arr[p][j];
  68. gcd = gcd(A_num_arr[i][j], A_den_arr[i][j]);
  69. A_num_arr[i][j] = A_num_arr[i][j] / gcd;
  70. A_den_arr[i][j] = A_den_arr[i][j] / gcd;
  71. }
  72. }
  73. }
  74.  
  75. int[] x_num = new int[N];
  76. int[] x_den = new int[N];
  77. for (int i = N - 1; i >= 0; i--) {
  78. int sum_num = 0;
  79. int sum_den = 1;
  80. for (int j = i + 1; j < N; j++) {
  81. sum_num = sum_num * A_den_arr[i][j] * x_den[j] + sum_den * A_num_arr[i][j] * x_num[j];
  82. sum_den = sum_den * A_den_arr[i][j] * x_den[j];
  83. int gcd = gcd(sum_num, sum_den);
  84. sum_num = sum_num / gcd;
  85. sum_den = sum_den / gcd;
  86. }
  87. x_num[i] = (b_num_arr[i] * sum_den - sum_num * b_den_arr[i]) * A_den_arr[i][i];
  88. x_den[i] = b_den_arr[i] * sum_den * A_num_arr[i][i];
  89. int gcd = gcd(x_num[i], x_den[i]);
  90. x_num[i] = x_num[i] / gcd;
  91. x_den[i] = x_den[i] / gcd;
  92. }
  93.  
  94. for (int i = 0; i < N; i++) {
  95. if (x_den[i] < 0) {
  96. x_den[i] = x_den[i] * (-1);
  97. x_num[i] = x_num[i] * (-1);
  98. }
  99. System.out.println(x_num[i] + "/" + x_den[i]);
  100. }
  101. }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement