挑战程序竞赛系列（43）：4.1矩阵 高斯消元
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434703
挑战程序竞赛系列（43）：4.1矩阵 高斯消元
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 2345: Central heating
知识点：高斯消元法，关于高斯消元法可以参考博文：
博文1：
http://www.cppblog.com/menjitianya/archive/2014/06/08/207226.html
博文2：
http://www.hankcs.com/program/algorithm/poj-2345-heating-central.html
我的理解：
它的核心在于消元，体现在迭代的过程当中，具体如下，依次遍历每一行，意味着消元消到了第i个变量，此时把后续行和第i个变量有关的全部消去，这样一来，第i+1行的所有变量数减一。
那么自然地，遍历到最后一行时，只剩一个变量，自然就出解了，接着把这个解慢慢往前回代，就能得到所有解。
此题思路：先将输入处理为01矩阵。题目用例中，如果第i个人管理第j个阀门，则记matrixj = 1，否则为0。然后目标是让所有闸门都开，也就是B向量都为1。
接着：把消元相减看成异或，乘法看成与运算，over。
代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201708/P2345.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 255;
int[][] matrix = new int[MAX_N][MAX_N];
void solve() {
while (more()){
int n = ni();
for (int i = 0; i < n; ++i){
int j = ni();
while (j != -1){
j--;
matrix[j][i] = 1;
matrix[j][n] = 1;
j = ni();
}
}
int[] ans = gauss(matrix, n);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < ans.length; ++i){
if (ans[i] == 1){
sb.append(" " + (i + 1));
}
}
out.println(sb.deleteCharAt(0).toString());
}
}
/*******************高斯消元法*********************/
public int[] gauss(int[][] matrix, int n){
int[] ans = new int[n];
for (int i = 0; i < n; ++i){
int row = i;
for (int j = i; j < n; ++j){
if (matrix[j][i] > matrix[row][i]){
row = j;
}
}
swap(matrix, i, row);
for (int j = i + 1; j < n; ++j){
if (matrix[j][i] == 1){
for (int k = i; k <= n; ++k){
matrix[j][k] ^= matrix[i][k];
}
}
}
}
for (int i = n - 1; i >= 0; --i){
ans[i] = matrix[i][n];
for (int j = i - 1; j >= 0; --j){
matrix[j][n] ^= (ans[i] & matrix[j][i]);
}
}
return ans;
}
public void swap(int[][] matrix, int i, int j){
int n = matrix[0].length;
for (int col = 0; col < n; ++col){
int tmp = matrix[i][col];
matrix[i][col] = matrix[j][col];
matrix[j][col] = tmp;
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}
POJ 3532: Resistance
心累，学完数学还要学物理么，这里就不再讲解电路的知识了，有兴趣的可以参考博文：
http://www.hankcs.com/program/algorithm/poj-3532-resistance.html
以及博文：
http://blog.csdn.net/u012139398/article/details/41345607
我重在实现高斯算法：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
String INPUT = "./data/judge/201708/P3532.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 100;
static final double EPS = 1E-8;
int N;
void solve() {
while (more()){
N = ni();
int M = ni();
double[][] matrix = new double[MAX_N][MAX_N];
for (int i = 0; i < M; ++i){
int x = ni();
int y = ni();
int r = ni();
--x;
--y;
double s = 1.0 / r;
matrix[x][x] += s;
matrix[y][y] += s;
matrix[x][y] -= s;
matrix[y][x] -= s;
}
N++;
matrix[0][N] = 1.0;
matrix[N - 2][N] = -1.0;
matrix[N - 1][N - 2] = 1.0;
out.printf("%.2f\n", gaussian(matrix));
}
}
public double gaussian(double[][] cal){
int n = N;
for (int i = 0; i < n; ++i){
int r;
for (r = i; r < n; ++r){
if (Math.abs(cal[r][i]) >= EPS){
break;
}
}
if (r == n) continue; // 无解直接跳过
swap(cal, i, r);
for (int j = i + 1; j <= n; ++j) cal[i][j] /= cal[i][i];
cal[i][i] = 1.0;
for (int j = 0; j < n; ++j){
if (i != j){
for (int k = i + 1; k <= n; ++k){
cal[j][k] -= (cal[j][i] * cal[i][k]);
}
cal[j][i] = 0.0;
}
}
}
return cal[0][N] / cal[0][0];
}
public void swap(double[][] matrix, int i, int j){
int n = matrix[0].length;
for (int col = 0; col < n; ++col){
double tmp = matrix[i][col];
matrix[i][col] = matrix[j][col];
matrix[j][col] = tmp;
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}需要注意的细节：进行归一化时，切记不要把当前变量给归一了，否则bug，所以有循环for从i+1开始，同理在消元时也从i+1开始。
POJ 3526: The Teacher’s Side of Math
此题的trick在于如何表达不同的αiβj\alpha^i\beta^j，很巧妙，因为在根号下，我们把式子转化为：
αimβjn
\alpha^{\frac{i}{m}}\beta^{\frac{j}{n}}
可以看出，i在(0,m)之间时，alpha一定为无理数，此题就是枚举出所有无理数之前的系数，让这些系数之和加起来等于0即可。
所以当i>m时，可以求出无理数之前的整数，比如：
αim=αi/m⋅αimodmm
\alpha^{\frac{i}{m}} = \alpha^{i / m}\cdot\alpha^{\frac{i\mod m}{m}}
i/m表示取下整哟，这样我们就可以把所有的α,β\alpha,\beta的无理数组合遍历出来，还恰好是：n*m + 1个方程。
你还可以参考：http://www.hankcs.com/program/algorithm/poj-3526-teacher-s-side-of-math-the.html
他的思路：
首先题目的隐含条件是，多项式最高次数一定为m*n。将(a1/m + b1/n)k二项展开后，除了最高次数项被题目限定为1之外，各项的系数和必须为0。以各项系数为变量，列出线性方程组，然后高斯消元求解即可。
JAVA代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201708/P3526.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final double EPS = 1E-8;
static final int MAX_N = 20 + 8;
int[][] matrix = new int[MAX_N][MAX_N];
int M, N, SIZE;
void solve() {
int[][] C = new int[MAX_N][MAX_N];
C[0][0] = 1;
for (int i = 1; i < MAX_N; ++i) {
C[i][0] = 1;
C[i][i] = 1;
for (int j = 1; j < i; ++j) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
while (true) {
int a = ni();
int m = ni();
int b = ni();
int n = ni();
M = m;
N = n;
if (a + m + b + n == 0)
break;
SIZE = n * m + 1;
double[][] matrix = new double[SIZE][SIZE + 1];
matrix[0][0] = matrix[0][SIZE] = 1;
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j <= i; ++j) {
matrix[to_index(j % m, (i - j) % n)][i < n * m ? i + 1 : 0] += C[i][j] * Math.pow((double) a, j / m)
* Math.pow((double) b, (i - j) / n);
}
}
gaussian(matrix);
StringBuilder sb = new StringBuilder();
sb.append("1");
for (int i = SIZE - 1; i >= 1; --i) {
sb.append(" " + (int)(round(ans[i])));
}
out.println(sb.toString());
}
}
double round(double x)
{
return x >= 0.0 ? Math.floor(x + 0.5) : Math.ceil(x - 0.5);
}
double[] ans;
public boolean gaussian(double[][] matrix) {
ans = new double[SIZE];
for (int i = 0; i < SIZE; ++i) {
int row = i;
for (int j = i; j < SIZE; ++j) {
if (Math.abs(matrix[j][i]) > Math.abs(matrix[row][i])) {
row = j;
}
}
swap(matrix, i, row);
if (Math.abs(matrix[i][i]) <= EPS)
return false;
for (int j = i + 1; j < SIZE + 1; ++j) matrix[i][j] /= matrix[i][i];
matrix[i][i] = 1;
for (int j = 0; j < SIZE; ++j) {
if (i != j) {
for (int k = i + 1; k < SIZE + 1; ++k) {
matrix[j][k] -= (matrix[j][i] * matrix[i][k]);
}
matrix[j][i] = 0.0;
}
}
}
for (int i = 0; i < SIZE; ++i) {
ans[i] = matrix[i][SIZE];
}
return true;
}
public void swap(double[][] matrix, int i, int j) {
int n = matrix[0].length;
for (int col = 0; col < n; ++col) {
double tmp = matrix[i][col];
matrix[i][col] = matrix[j][col];
matrix[j][col] = tmp;
}
}
public int to_index(int i, int j) {
return i * N + j + 1;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = !System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj) {
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more() {
return in.hasNext();
}
public int ni() {
return in.nextInt();
}
public long nl() {
return in.nextLong();
}
public double nd() {
return in.nextDouble();
}
public String ns() {
return in.nextString();
}
public char nc() {
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext() {
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}这模版有点叼啊，把把第一，只怪用JAVA写的太少了吧。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月31日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录