2012-10-16 21:45:08Morris
[線性代數][作業] Reduced row-echelon form
題 目：從檔案輸入Matrix並轉換成Row Echelon Form後，以檔案
輸出結果。
加分條件：成功完成”Reduced” Row Echelon Form的Matrix者，此次程式作業
成績 加 10分。
輸 入：檔名為input.txt的檔案，內容為任意大小的N×N Matrix值，第一行描述矩陣大小，其中宣告矩陣的大小不超過30×30。每個column之間以TAB分隔，每個row之間以斷行符號分隔。
輸 出：檔名為output.txt的檔案，內容為轉換成Row EchelonForm
的Matrix。每個column之間以空白符號分隔，每個row之間以斷行
符號分隔。
收件時間：10/18 24:00以前（未避免網路壅塞，請儘早上傳，不接受遲交）
評分說明：
1. 一個測試案例(下述案例)執行正確，給40分
2. 兩個測試案例(下述案例)執行正確，給60分
其他案例(未給)執行正確，給100分
3. 避免因浮點數運算造成的誤差，測試數據的計算過程中不會出現無限小數。
轉換過程中以分數計算並表示結果，助教將斟酌加分。
抄襲者雙方則以零分計算。
這裡提供幾筆測資
Sample Input:
3 3
1 2 3
4 5 6
7 8 9
5 5
1 3 0 -1 0
0 -2 4 -2 0
3 11 -4 -1 0
2 5 3 -4 0
1 2 3 4 7
3 3
2 8 4
2 5 1
4 10 -1
3 3
1 2 3
8 10 12
7 8 9
3 3
1 2 3
4 5 6
7 8 9
3 4
2 1 -1 8
-3 -1 2 -11
-2 1 2 -3
3 4
2 4 -2 2
4 9 -3 8
-2 -3 7 10
3 6
2 4 -2 1 0 0
4 9 -3 0 1 0
-2 -3 7 0 0 1
3 6
2 3 -2 1 0 0
1 -2 3 0 1 0
4 -1 4 0 0 1
3 4
1 0 2 6
-3 4 6 30
-1 -2 3 8
Sample output:
1 0 -1
0 1 2
0 0 0
1 0 0 0 -2
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
0 0 0 0 0
1 0 0
0 1 0
0 0 1
1 0 -1
0 1 2
0 0 0
1 0 -1
0 1 2
0 0 0
1 0 0 2
0 1 0 3
0 0 1 -1
1 0 0 -1
0 1 0 2
0 0 1 2
1 0 0 27/4 -11/4 3/4
0 1 0 -11/4 5/4 -1/4
0 0 1 3/4 -1/4 1/4
1 0 5/7 2/7 3/7 0
0 1 -8/7 1/7 -2/7 0
0 0 0 -1 -2 1
1 0 0 -10/11
0 1 0 18/11
0 0 1 38/11
C++
#include <iostream>
#include <fstream>
#define LL long long
using namespace std;
class Frac {
public:
LL a, b;
Frac() {
a = 0, b = 1;
}
Frac(int x, int y) {
a = x, b = y;
reduce();
}
Frac operator+(const Frac &y) {
LL ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) + y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator-(const Frac &y) {
LL ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) - y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator*(const Frac &y) {
LL tx, ty, tz, tw, g;
tx = this->a, ty = y.b;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.a;
g = gcd(tz, tw), tz /= g, tw /= g;
Frac z(tx*tw, ty*tz);
return z;
}
Frac operator/(const Frac &y) {
LL tx, ty, tz, tw, g;
tx = this->a, ty = y.a;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.b;
g = gcd(tz, tw), tz /= g, tw /= g;
Frac z(tx*tw, ty*tz);
return z;
}
private:
static LL gcd(LL x, LL y) {
if(!y) return x;
if(x < 0) x *= -1;
if(y < 0) y *= -1;
LL t;
while(x%y)
t = x, x = y, y = t%y;
return y;
}
void reduce() {
LL g = gcd(a, b);
a /= g, b /= g;
if(b < 0) a *= -1, b *= -1;
}
};
ostream& operator<<(ostream& out, const Frac&x) {
out << x.a;
if(x.b != 1)
out << '/' << x.b;
return out;
}
int main() {
ifstream fin("input.txt");
ofstream fout("output.txt");
int n, m, i, j, k, idx;
while(fin >> m >> n) {
Frac matrix[m][n];
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
fin >> matrix[i][j].a;
}
}
Frac tmp, one(1,1), tmp2;
for(i = 0, idx = 0; idx < m && i < n; i++) {
int ch = -1;
for(j = idx; j < m; j++)
if(matrix[j][i].a) {
ch = j;
break;
}
if(ch == -1) continue;
if(idx != ch)
for(j = 0; j < n; j++)
tmp = matrix[idx][j], matrix[idx][j] = matrix[ch][j], matrix[ch][j] = tmp;
tmp = one/matrix[idx][i];
for(j = 0; j < n; j++)
matrix[idx][j] = matrix[idx][j]*tmp;
for(j = 0; j < m; j++) {
if(idx == j) continue;
tmp = matrix[j][i]/matrix[idx][i];
if(tmp.a == 0) continue;
for(k = i; k < n; k++) {
matrix[j][k] = matrix[j][k] - tmp*matrix[idx][k];
}
}
idx++;
}
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
if(j) fout << ' ';
fout << matrix[i][j];
}
fout << endl;
}
fout << endl;
}
return 0;
}
接下來是 Java 格式
import java.util.Scanner;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import Frac.Frac;
public class GE {
public static void main(String[] args) {
Scanner fin = null;
PrintStream fout = null;
try {
fin = new Scanner(new FileInputStream("input.txt"));
fout = new PrintStream(new FileOutputStream("output.txt"));
} catch (Exception e) {
}
int n, m, i, j, k, aij, idx;
while (fin.hasNextInt()) {
m = fin.nextInt();
n = fin.nextInt();
Frac[][] matrix = new Frac[m][n];
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
aij = fin.nextInt();
matrix[i][j] = new Frac(aij, 1);
}
}
Frac tmp1, ONE;
ONE = new Frac(1, 1);
for(i = 0, idx = 0; idx < m && i < n; i++) {
int ch = -1;
for(j = idx; j < m; j++) {
if(matrix[j][i].a.compareTo(BigInteger.ZERO) != 0) {
ch = j;
break;
}
}
if(ch == -1) continue;
if(idx != ch) {
for(j = 0; j < n; j++) {
tmp1 = matrix[idx][j];
matrix[idx][j] = matrix[ch][j];
matrix[ch][j] = tmp1;
}
}
tmp1 = ONE.divide(matrix[idx][i]);
for(j = 0; j < n; j++)
matrix[idx][j] = matrix[idx][j].multiply(tmp1);
for(j = 0; j < m; j++) {
if(idx == j) continue;
tmp1 = matrix[j][i].divide(matrix[idx][i]);
for(k = i; k < n; k++) {
matrix[j][k] = matrix[j][k].substract(tmp1.multiply(matrix[idx][k]));
}
}
idx++;
}
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
if(j > 0) fout.print(' ');
fout.print(matrix[i][j]);
}
fout.println("");
}
}
}
}
package Frac;
import java.math.BigInteger;
public class Frac {
public BigInteger a, b;
public Frac() {
this(BigInteger.valueOf(0), BigInteger.valueOf(1));
}
public Frac(long x, long y) {
this(BigInteger.valueOf(x), BigInteger.valueOf(y));
}
public Frac(BigInteger ta, BigInteger tb) {
a = ta;
b = tb;
reduce();
}
public Frac add(Frac y) {
BigInteger ta, tb;
tb = b.divide(b.gcd(y.b)).multiply(y.b);
ta = a.multiply(tb.divide(b)).add(y.a.multiply(tb.divide(y.b)));
return new Frac(ta, tb);
}
public Frac substract(Frac y) {
BigInteger ta, tb;
tb = b.divide(b.gcd(y.b)).multiply(y.b);
ta = a.multiply(tb.divide(b)).subtract(y.a.multiply(tb.divide(y.b)));
return new Frac(ta, tb);
}
public Frac multiply(Frac y) {
BigInteger tx, ty, tz, tw, g;
tx = a;
ty = y.b;
g = tx.gcd(ty);
tx = tx.divide(g);
ty = ty.divide(g);
tz = b;
tw = y.a;
g = tz.gcd(tw);
tz = tz.divide(g);
tw = tw.divide(g);
return new Frac(tx.multiply(tw), ty.multiply(tz));
}
public Frac divide(Frac y) {
BigInteger tx, ty, tz, tw, g;
tx = a;
ty = y.a;
g = tx.gcd(ty);
tx = tx.divide(g);
ty = ty.divide(g);
tz = b;
tw = y.b;
g = tz.gcd(tw);
tz = tz.divide(g);
tw = tw.divide(g);
return new Frac(tx.multiply(tw), ty.multiply(tz));
}
public String toString() {
if (b.compareTo(BigInteger.ONE) == 0)
return a.toString();
return a.toString() + "/" + b;
}
private void reduce() {
BigInteger g = a.gcd(b);
a = a.divide(g);
b = b.divide(g);
if (b.compareTo(BigInteger.ZERO) < 0) {
a = a.negate();
b = b.negate();
}
}
}