首页 > 专题系列 > Java解POJ > POJ 1914 Cramer’s Rule [解题报告] Java
2013
11-10

POJ 1914 Cramer’s Rule [解题报告] Java

Cramer’s Rule

问题描述 :

Background

Consider a system of linear equations, here three equations of three variables x1, x2, x3. The general form looks something like this, with given numbers aij and bi:

a11x1 + a12x2 + a13x3 = b1

a21x1 + a22x2 + a23x3 = b2

a31x1 + a32x2 + a33x3 = b3


Or, using matrices and vectors:



According to Cramer’s rule, the solution can be given in terms of determinants, i.e.

xi =det(Ai)/det(A)


where Ai is the matrix obtained from A by replacing the i-th column with the vector b. For 3 * 3 determinants,you can use the following simple formula to calculate the determinant:



Obviously, Cramer’s rule only works for det(A) != 0. One can show that the system has a unique solution if and only if det(A) != 0. Otherwise, the system has either no solution or infinitely many solutions.

Please note that one would not use Cramer’s rule to solve a large system of linear equations, simply because calculating a single determinant is as time-consuming as solving the complete system by a more efficient algorithm.

Problem

Given a system of three linear equations in three variables, use Cramer’s rule to find the unique solution if it exists. More precisely, calculate the determinants of the Ai and of A and decide by looking at det(A) whether the system has a unique solution. If it does, calculate the solution according to Cramer’s rule.

输入:

The first line contains the number of scenarios.

For each scenario, you are given three lines corresponding to the three equations, with the coefficients of the matrix A and the coordinates of the vector b arranged as follows:

a11 a12 a13 b1

a21 a22 a23 b2

a31 a32 a33 b3


All numbers are integers in the range {−1000, . . . , 1000}. They are separated by single blanks.

输出:

For each scenario print three lines. In the first line, print the determinants of A1, A2, A3, and A, as integers and separated by single blanks. In the second line, print (depending on det(A)) either “No unique solution” or “Unique solution: “, followed by the values of x1, x2, x3 with three digits after the decimal point,again separated from each other by a single blank. For solutions xi with -0.0005 < xi < 0.0005 always print "0.000" instead of the "-0.000" that your print command might come up with. The third line is empty.

样例输入:

3
4 0 0 1
0 2 0 2
0 0 1 4
1 2 3 1
1 1 1 2
2 2 2 3
1 0 0 1
0 1 0 0
0 0 -1 0

样例输出:

2 8 32 8
Unique solution: 0.250 1.000 4.000

1 -2 1 0
No unique solution

-1 0 0 -1
Unique solution: 1.000 0.000 0.000

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
   int n=scanner.nextInt();
	BigInteger[][] a;
	BigInteger[] b;
	BigInteger aa,aa1,aa2,aa3;
	for (int i=0;i< n ;i++ ){
         a=new BigInteger[3][3];
	 b=new BigInteger[3];
	 for (int j=0;j< 3 ;j++ ){
	   for (int k=0;k< 3 ;k++ ){
	    a[j][k]=scanner.nextBigInteger();
	   }
	  b[j]=scanner.nextBigInteger();
	}
	aa=a[0][0].multiply(a[1][1].multiply(a[2][2]).add(a[1][2].multiply(a[2][1]).negate())).
          add((a[0][1].multiply(a[1][0].multiply(a[2][2]).
          add(a[1][2].multiply(a[2][0]).negate()))).negate()).
          add(a[0][2].multiply(a[1][0].multiply(a[2][1]).
          add(a[1][1].multiply(a[2][0]).negate())));

       aa1=b[0].multiply(a[1][1].multiply(a[2][2]).add(a[1][2].multiply(a[2][1]).negate())).
         add((a[0][1].multiply(b[1].multiply(a[2][2]).
         add(a[1][2].multiply(b[2]).negate()))).negate()).
         add(a[0][2].multiply(b[1].multiply(a[2][1]).
         add(a[1][1].multiply(b[2]).negate())));

      aa2=a[0][0].multiply(b[1].multiply(a[2][2]).add(a[1][2].multiply(b[2]).negate())).
         add((b[0].multiply(a[1][0].multiply(a[2][2]).
         add(a[1][2].multiply(a[2][0]).negate()))).negate()).
         add(a[0][2].multiply(a[1][0].multiply(b[2]).
         add(b[1].multiply(a[2][0]).negate())));

      aa3=a[0][0].multiply(a[1][1].multiply(b[2]).add(b[1].multiply(a[2][1]).negate())).
         add((a[0][1].multiply(a[1][0].multiply(b[2]).
         add(b[1].multiply(a[2][0]).negate()))).negate()).
         add(b[0].multiply(a[1][0].multiply(a[2][1]).
         add(a[1][1].multiply(a[2][0]).negate())));

	System.out.println(aa1+" "+aa2+" "+aa3+" "+aa);
	if (aa.equals(BigInteger.ZERO)){
		System.out.println("No unique solution");
	}
       else{
	DecimalFormat df=new DecimalFormat("0.000");
	BigDecimal x1=new BigDecimal(aa1.toString());
	BigDecimal x2=new BigDecimal(aa2.toString());
	BigDecimal x3=new BigDecimal(aa3.toString());
	BigDecimal x=new BigDecimal(aa.toString());
	BigDecimal xx1=x1.divide(x,6,BigDecimal.ROUND_HALF_UP);
	BigDecimal xx2=x2.divide(x,6,BigDecimal.ROUND_HALF_UP);
	BigDecimal xx3=x3.divide(x,6,BigDecimal.ROUND_HALF_UP);
   System.out.println("Unique solution: "+df.format(xx1)+" "+df.format(xx2)+" "+df.format(xx3));
	}
	System.out.println();
  }
}
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. [email protected]