Table of Contents
- Gaussian Elimination Solving System of Linear Equations
-
- Code
- Gaussian Elimination Solving XOR Linear Equations
-
- main idea
- Code
Gaussian elimination to solve linear equations
Description of topic:
Enter a containing
no
no
n equations
no
no
System of linear equations in n unknowns.
The coefficients in the system of equations are real numbers.
Solve this system of equations.
The figure below shows a
m
m
m equations
no
no
Example of a system of linear equations in n unknowns:
{
a
11
x
1
+
a
12
x
2
+
?
+
a
1
no
x
no
=
b
1
a
twenty one
x
1
+
a
twenty two
x
2
+
?
+
a
2
no
x
no
=
b
2
?
a
m
1
x
1
+
a
m
2
x
2
+
?
+
a
m
no
x
no
=
b
m
\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \ a_{21}x_1 + a_{22}x_2 + \cdots + a_ {2n}x_n = b_2 \ \vdots \ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases}
?
Enter format:
The first row contains integers
no
no
n.
next
no
no
n lines, each containing
no
+
1
n + 1
n + 1 real numbers representing the
no
no
n coefficients and a constant to the right of the equal sign.
Output format:
If there is a unique solution to the given system of linear equations, the output total
no
no
n rows, where the
i
i
Line i outputs the first
i
i
The solution of i unknowns, the result is rounded to two decimal places.
Outputs Infinite group solutions if there are infinite solutions to the given linear equation system.
If the given system of linear equations has no solution, output No solution.
Data range:
1
≤
no
≤
100
1≤n≤100
1≤n≤100, all input coefficients and constants are kept to two decimal places, and the absolute value does not exceed 100.
Sample input:
3 1.00 2.00 -1.00 -6.00 2.00 1.00 -3.00 -9.00 -1.00 -1.00 2.00 7.00
Sample output:
1.00 -2.00 3.00
Code Implementation
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int N = 110;
const double eps = 1e-8;
double a[N][N];
int n;
int gauss()
{<!-- -->
int row = 0;
for (int col = 0; col < n; col ++ )
{<!-- -->
int t = row;
for (int i = row + 1; i < n; + + i) // Find the row with the largest absolute value in the current column
if (fabs(a[t][col]) - fabs(a[i][col]) < eps) t = i;
if (fabs(a[t][col]) < eps) continue; // all elements in the current column are 0, then directly enter the next cycle
for (int i = n; i >= col; --i)
{<!-- -->
a[t][i] /= a[t][col]; // Simplify the first row with the largest absolute value to 1
swap(a[t][i], a[row][i]); // swap this row to the top
}
for (int i = row + 1; i < n; + + i) // Use the current row to eliminate the elements at the corresponding column positions of all the rows below to 0
{<!-- -->
if (fabs(a[i][col]) < eps) continue;
for (int j = n; j >= col; --j) a[i][j] -= a[i][col] * a[row][j];
}
row + + ;
}
// Determine the uniqueness of the solution
if (row < n) // rank of coefficient matrix < n
{<!-- -->
// Determine whether the rank of the coefficient matrix is the same as that of the augmented matrix
for (int i = row; i < n; + + i)
if (fabs(a[i][n]) > eps) return 0;
return 2;
}
for (int i = n - 1; i >= 0; --i)
{<!-- -->
for (int j = i + 1; j < n; + + j)
a[i][n] -= a[i][j] * a[j][n]; // This step is clever
}
return 1;
}
int main()
{<!-- -->
cin >> n;
for (int i = 0; i < n; + + i)
{<!-- -->
for (int j = 0; j <= n; + + j)
cin >> a[i][j];
}
int flag = gauss();
if (flag == 0)
cout << "No solution" << endl;
else if (flag == 1)
for (int i = 0; i < n; + + i) cout << a[i][n] << endl;
else
cout << "Infinite group solutions" << endl;
return 0;
}
Gaussian elimination to solve XOR linear equations
XOR operation is also known as addition without carry
Description of topic:
Enter a containing
no
no
n equations
no
no
XOR system of linear equations in n unknowns.
The coefficients and constants in the equation system are
0
0
0 or
1
1
1, the value of each unknown is also
0
0
0 or
1
1
1.
Solve this system of equations.
An example XOR system of linear equations is as follows:
M[1][1]x[1] ^ M[1][2]x[2] ^ ... ^ M[1][n]x[n] = B[1] M[2][1]x[1] ^ M[2][2]x[2] ^ ... ^ M[2][n]x[n] = B[2] … M[n][1]x[1] ^ M[n][2]x[2] ^ ... ^ M[n][n]x[n] = B[n]
Where ^ means exclusive or (XOR),
m
[
i
]
[
j
]
M[i][j]
M[i][j] represents the first
i
i
i formula
x
[
j
]
x[j]
coefficient of x[j],
B
[
i
]
B[i]
B[i] is the first
i
i
The constants on the right-hand side of the i equations take values
0
0
0 or
1
1
1.
Enter format:
The first row contains integers
no
no
n.
next
no
no
n lines, each containing
no
+
1
n + 1
n + 1 integers
0
0
0 or
1
1
1, representing an equation of
no
no
n coefficients and a constant to the right of the equal sign.
Output format:
If there is a unique solution to the given system of linear equations, the output total
no
no
n rows, where the
i
i
Line i outputs the first
i
i
The solution for the i unknowns.
Outputs Multiple sets of solutions if multiple sets of solutions exist for the given linear system.
If the given system of linear equations has no solution, output No solution.
Data range:
1
≤
no
≤
100
1≤n≤100
1≤n≤100
Sample input:
3 1 1 0 1 0 1 1 0 1 0 0 1
Sample output:
1 0 0
Core idea
XOR-addition without carry
The XOR between the equation and the equation must be performed together to ensure that the left and right sides of the equation are still equal.
a
a
a ^
b
b
b ^
c
c
c =
x
x
x
d
d
d ^
f
f
f =
the y
the y
the y
but
a
a
a ^
b
b
b ^
d
d
d ^
c
c
c ^
f
f
f =
x
x
x ^
the y
the y
the y
^ in bit operations can correspond to both addition and subtraction, and & amp; can correspond to multiplication.
Code Implementation
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N];
int n;
int gauss()
{<!-- -->
int row = 0;
for (int col = 0; col < n; + + col)
{<!-- -->
int t = row;
for (int i = row; i < n; + + i)
if (a[i][col])
{<!-- -->
t = i;
break;
}
if (!a[t][col]) continue;
for (int i = col; i <= n; + + i) swap(a[t][i], a[row][i]);
for (int i = row + 1; i < n; + + i)
{<!-- -->
if (!a[i][col]) continue;
for (int j = n; j >= col; --j)
a[i][j] ^= a[i][col] & amp; a[row][j]; // written as a[i][j] ^= a[i][col] * a[row ][j]; also available
}
row + + ;
}
if (row < n)
{<!-- -->
for (int i = row; i < n; + + i)
if (a[i][n]) return 0;
return 2;
}
for (int i = n - 1; i >= 0; --i)
{<!-- -->
for (int j = i + 1; j < n; + + j)
a[i][n] ^= a[i][j] & a[j][n];
}
return 1;
}
int main()
{<!-- -->
cin >> n;
for (int i = 0; i < n; + + i)
for (int j = 0; j <= n; + + j) cin >> a[i][j];
int t = gauss();
if (t == 0) cout << "No solution" << endl;
else if (t == 1)
for (int i = 0; i < n; + + i) cout << a[i][n] << endl;
else cout << "Multiple sets of solutions" << endl;
return 0;
}