-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.cpp
359 lines (299 loc) · 8.64 KB
/
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
#include <bits/stdc++.h>
using namespace std;
/**
* @brief Greatest Common Divisor. The library one for this is only available on C++ 17.
*
*/
int _gcd_(int oprA, int oprB){
return oprB>0?_gcd_(oprB,oprA%oprB):oprA;
}
/**
* @brief Struct for Fractions, which includes the absolute values of numerator and denominator, as well as a boolean sign.
*
*/
typedef struct frac{
int nume;
int deno;
bool sign;
/**
* @brief Set the fraction so that its value equals the given integer.
*/
void init(int val){
nume=abs(val);
deno=1;
sign=(val>0);
}
/**
* @brief Set the fraction so that it equals to x/y.
*/
void init(int x, int y){
nume=abs(x);
deno=abs(y);
sign=true;
if(x<0){sign=!sign;}
if(y<0){sign=!sign;}
round();
}
/**
* @brief Round the fraction to the most simple form.
*/
void round(){
if(isZero()){deno=1; sign=true; return;}
if(nume<0){nume=-nume; sign=!sign;}
if(deno<0){deno=-deno; sign=!sign;}
int tmpgcd=_gcd_(nume,deno);
nume/=tmpgcd;
deno/=tmpgcd;
}
bool isZero(){
return nume==0;
}
/**
* @brief Return the fraction's value as a double.
*/
double toDeci(){
return (double)nume/(double)deno*(sign?(1):(-1));
}
};
frac** mat;
int _row_=0,_col_=0;
/**
* @brief Return the inverted fraction (1/opr).
*/
frac frcinv(frac opr){
frac nfrc;
nfrc.init(opr.deno,opr.nume);
nfrc.sign=opr.sign;
nfrc.round();
return nfrc;
}
/**
* @brief Return the reverted fraction (-opr).
*/
frac frcrev(frac opr){
frac nfrc;
nfrc.init(opr.nume,opr.deno);
nfrc.sign=!opr.sign;
nfrc.round();
return nfrc;
}
/**
* @brief Return the sum of two fractions (oprA+oprB).
*/
frac frcadd(frac oprA, frac oprB){
int comDeno=oprA.deno*oprB.deno;
int anume=oprA.nume*(comDeno/oprA.deno)*(oprA.sign?1:(-1));
int bnume=oprB.nume*(comDeno/oprB.deno)*(oprB.sign?1:(-1));
frac nfrc;
nfrc.init(anume+bnume,comDeno);
nfrc.round();
return nfrc;
}
/**
* @brief Return the difference of the two fractions (oprA-oprB).
*/
frac frcmin(frac oprA, frac oprB){
return frcadd(oprA,frcrev(oprB));
}
/**
* @brief Return the product of the two fractions (oprA*oprB).
*/
frac frcmul(frac oprA, frac oprB){
frac nfrc;
nfrc.init(oprA.nume*oprB.nume,oprA.deno*oprB.deno);
nfrc.sign=(oprA.sign==oprB.sign);
nfrc.round();
return nfrc;
}
/**
* @brief Return the quotient of the two fractions (oprA/oprB).
* @note This is only allowed when toDeci(oprB)!=0.0d; .
*/
frac frcdiv(frac oprA, frac oprB){
return frcmul(oprA,frcinv(oprB));
}
/**
* @brief Look for the first non-zero entry in the matrix of a designated column after a starting index. The left-most column is considered column 0.
* @return The row number of the first non-zero entry found: If a non-zero entry is found; (-1) if no such entry is found. The upper-most row is considered row 0.
*/
int cscan(int colNum, int startInd){
int curRow=startInd;
while(curRow<_row_){
if(!mat[curRow][colNum].isZero()){
return curRow;
} curRow++;
}
return -1;
}
void _printMat_(){
printf("----------\n");
for(int i=0;i<_row_;++i){
inloop: for(int j=0;j<_col_;++j){
if(mat[i][j].deno==1){
printf("%c%d ",mat[i][j].sign?'+':'-',mat[i][j].nume);
} else{
printf("%c%d/%d ",mat[i][j].sign?'+':'-',mat[i][j].nume,mat[i][j].deno);
}
}
printf("\n");
}
printf("----------\n\n\n");
}
/**
* @brief Look for the first non-zero entry in the matrix of a designated row after a starting index. The upper-most column is considered row 0.
* @return The column number of the first non-zero entry found: If a non-zero entry is found; (-1) if no such entry is found. The left-most column is considered column 0.
*/
int rscan(int rowNum, int startInd){
int curCol=startInd;
while(curCol<_col_){
if(!mat[rowNum][curCol].isZero()){
return curCol;
} curCol++;
}
return -1;
}
void _replace_(int refRow, int tarRow){
if(refRow==tarRow){return;}
int refst=rscan(refRow,0);
if(mat[tarRow][refst].isZero()){
return;
}
int curCol=refst;
frac rratio=frcdiv(mat[tarRow][refst],mat[refRow][refst]);
while(curCol<_col_){
mat[tarRow][curCol]=frcmin(mat[tarRow][curCol],frcmul(mat[refRow][curCol],rratio));
curCol++;
}
printf("-----");
printf("(R%d)%c(%d/%d)*(R%d) yields:\n",tarRow,rratio.sign?'-':'+',rratio.nume,rratio.deno,refRow);
_printMat_();
}
void _swap_(int rowA, int rowB){
if(rowA==rowB){return;}
int curCol=0;
frac tmpFrc;
while(curCol<_col_){
tmpFrc=mat[rowA][curCol];
mat[rowA][curCol]=mat[rowB][curCol];
mat[rowB][curCol]=tmpFrc;
++curCol;
}
printf("-----");
printf("Exchange row (R%d) and row (R%d) yields:\n",rowA,rowB);
_printMat_();
}
void _scale_(int tarRow){
int stCol=rscan(tarRow,0);
frac comRat=mat[tarRow][rscan(tarRow,0)];
int curCol=stCol;
while(curCol<_col_){
mat[tarRow][curCol]=frcdiv(mat[tarRow][curCol],comRat);
curCol++;
}
frac tmpRat=frcinv(comRat);
printf("-----");
printf("(R%d)*(%c%d/%d) yields:\n",tarRow,tmpRat.sign?'+':'-',tmpRat.nume,tmpRat.deno);
_printMat_();
}
void doForwardElim(int beginRow, int beginCol){
printf("Iterating from (%d,%d)\n",beginRow,beginCol);
// Return if the elimination process is trivial. a.k.a if it begins at the last row or to the right of the last column.
if(beginRow==_row_ || beginCol==_col_){return;}
// If no pivot entry is found on the current column, move on to the next column.
if(cscan(beginCol,beginRow)==-1){doForwardElim(beginRow,beginCol+1); return;}
// Find the first row from the top with non-zero entry (pivot entry) on the begin-column column as the "base-row".
// Swap the base-row with the zeroth row so that the base-row is on the top.
_swap_(beginRow,cscan(beginCol,beginRow));
// Scale the base-row so that it is uniform.
_scale_(beginRow);
int curRow=beginRow;
while(curRow<_row_){
_replace_(beginRow,curRow);
curRow++;
}
doForwardElim(beginRow+1,beginCol+1);
}
void doBackwardElim(){
printf("Reverse Elimination:\n");
int pivCol=0;
for(int curRow=_row_-1;curRow>=0;curRow--){
pivCol=rscan(curRow,0);
if(pivCol==-1){continue;}
for(int i=curRow-1;i>=0;i--){
if(!mat[i][pivCol].isZero()){
_replace_(curRow,i);
}
}
}
}
void _iniMat_(){
mat=new frac*[_row_];
for(int i=0;i<_row_;++i){
mat[i]=new frac[_col_];
}
int rtmp=0;
for(int i=0;i<_row_;++i){
for(int j=0;j<_col_;++j){
cin>>rtmp;
mat[i][j].init(rtmp);
}
}
}
void _iniFrcMat_(){
mat=new frac*[_row_];
for(int i=0;i<_row_;++i){
mat[i]=new frac[_col_];
}
int numetmp=0;
int denotmp=0;
char aflag=' ';
for(int i=0;i<_row_;++i){
for(int j=0;j<_col_;++j){
scanf("%c%d/%d",&aflag,&numetmp,&denotmp);
mat[i][j].init(numetmp*(aflag=='+'?(1):(-1)),denotmp);
}
}
}
void _freeMat_(){
for(int i=0;i<_row_;++i){
delete [] mat[i];
}
delete [] mat;
}
void _printSol_(){
int curRow=0;
while(curRow<_row_){
for(int i=0;i<_col_-1;++i){
if(mat[curRow][i].isZero()){
continue;
}
printf("%c",mat[curRow][i].sign?'+':'-');
if(!(mat[curRow][i].nume==mat[curRow][i].deno)){
printf("%d",mat[curRow][i].nume);
}
if(mat[curRow][i].deno!=1){
printf("/%d",mat[curRow][i].deno);
}
printf("x{%d}",i);
}
++curRow;
}
}
void _printFrc_(frac opr){
printf("%c%d/%d\n",opr.sign?'+':'-',opr.nume,opr.deno);
}
void _printMeta_(frac opr){
printf("(%d,%d,%c)",opr.nume,opr.deno,opr.sign?'T':'F');
}
void make(){
_iniMat_();
doForwardElim(0,0);
doBackwardElim();
_printMat_();
}
int main(){
cin>>_row_>>_col_;
make();
_freeMat_();
return 0;
}