import java.util.*;
import java.io.*;
import java.math.*;
class Fraction {
BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
Fraction() { }
Fraction(BigInteger a, BigInteger b)
{
BigInteger d = a.gcd(b);
a = a.divide(d); b = b.divide(d);
if (b.compareTo(BigInteger.ZERO) < 0) {
a = a.negate(); b = b.negate();
}
this.a = a; this.b = b;
}
@Override
public String toString()
{
BigInteger d = a.gcd(b);
a = a.divide(d);
b = b.divide(d);
if (b.compareTo(BigInteger.ONE) == 0)
return a.toString();
return a + "/" + b;
}
public Fraction add(Fraction p)
{
return new Fraction(a.multiply(p.b).add(b.multiply(p.a)), b.multiply(p.b));
}
public Fraction subtract(Fraction p)
{
return new Fraction(a.multiply(p.b).subtract(b.multiply(p.a)), b.multiply(p.b));
}
public Fraction muliply(Fraction p)
{
return new Fraction(a.multiply(p.a), b.multiply(p.b));
}
public Fraction divide(Fraction p)
{
return new Fraction(a.multiply(p.b), b.multiply(p.a));
}
public Fraction abs()
{
return new Fraction(a.abs(), b.abs());
}
public int compareTo(Fraction p)
{
return a.multiply(p.b).subtract(b.multiply(p.a)).signum();
}
}
class Matrix {
Fraction data[][];
}
public class Main {
// Gaussian elimination
public static Fraction[] gaussianElimination(Fraction A[][], int m) throws Exception
{
for (int i = 0; i < m; ++i)
{
// Find pivot in column i, starting in row i:
int maxi = i;
for (int k = i + 1; k < m; ++k)
if (A[k][i].abs().compareTo(A[maxi][i].abs()) > 0)
maxi = k;
if (A[maxi][i].a.compareTo(BigInteger.ZERO) == 0)
throw new Exception("no solution");
// swap rows i and maxi, but do not change the value of i
// Now A[i,i] will contain the old value of A[maxi,i].
if (i != maxi) {
Fraction tmp[] = A[i];
A[i] = A[maxi];
A[maxi] = tmp;
}
// divide each entry in row i by A[i,i]
// Now A[i,i] will have the value 1.
for (int k = m; k >= i; --k)
A[i][k] = A[i][k].divide(A[i][i]);
// subtract A[u,j] * row i from row u
// Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
for (int u = i + 1; u < m; ++u)
for (int k = m; k > i; --k)
A[u][k] = A[u][k].subtract(A[u][i].muliply(A[i][k]));
}
Fraction x[] = new Fraction[m];
x[m - 1] = A[m - 1][m].divide(A[m - 1][m - 1]);
for (int i = m - 2; i >= 0; --i)
{
x[i] = A[i][m];
for (int k = i + 1; k < m; ++k)
x[i] = x[i].subtract(x[k].muliply(A[i][k]));
x[i] = x[i].divide(A[i][i]);
}
return x;
}
public static void main(String args[])
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
Fraction a[][] = new Fraction[105][105];
Fraction x[] = new Fraction[105];
while (cin.hasNext())
{
int m = cin.nextInt();
for (int i = 0; i < m; ++i)
for (int j = 0; j <= m; ++j)
{
BigInteger tmp = cin.nextBigInteger();
a[i][j] = new Fraction(tmp, BigInteger.ONE);
}
try {
x = gaussianElimination(a, m);
for (int i = 0; i < m; ++i)
System.out.println(x[i]);
System.out.println();
} catch (Exception e) {
System.out.println("No solution.");
System.out.println();
}
}
}
}
分享到:
相关推荐
采用高斯消元方法消去未知数方程中的未知数,求解多远线性方程,界面简单实用
java 版本的高斯消元代码,新建工程,再把文件复制进去,运行就行了,修改A和b修改参数
计算方法之高斯消元算法的编程实现,是c语言实现
非常好用的高斯消元求解线性方程组方法,强烈推荐!!!!
先输入一个数n表示方程元数。 然后再输入一个 n*(n+1)的矩阵 具体见我的博客
运用高斯消元法求解线性方程组,尽量少采用了循环语句提交计算效率。
使用高斯消元法计算矩阵的逆,尤其适用于稀疏矩阵的逆的计算
高斯消元模版
矩阵中高斯消元程序(包括分别用MATLAB语言和c编写
NOIP ACM 高斯消元练习+数据题解
计算方法 列主元高斯消元,LU分解 代码 txt格式
高斯消元LU分解,详细请参考《算法导论》第七部分 算法问题选编中的第28章 矩阵运算。
数值方法中的数值方法的高斯消元算法实验源代码,值得大家下载!!
近日学到矩阵与行列式,发现解n元一次方程组居然可以化成如此简介的形式,于是便想到了将其程序化,通过简单的C语言编程实现输入n*(n+1)矩阵来解决n元一次...(完全自行思考、完全按照高斯消元原理写的,嫌烦还请别看)
Java单精度高斯消元
采用VC6.0编写的C++程序,全主元高斯消元法
文档内容为数值分析算法的C++实现。 算法包括:非线性方程求解、高斯消元发、高斯列主消元法、牛顿迭代法、割线法
用C/C++语言描述的高斯消元算法,方法简单易懂
基于MATLAB的LDPC码的性能仿真,包括H矩阵高斯消元变换方式、下三角形式和近似下三角形式三种
[精品]高斯消元_C语言代码