fork download
copy 
  1. //c headers
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <ctype.h>
  6. #include <math.h>
  7. #include <limits.h>
  8. //c++ headers
  9. #include <iostream>
  10. #include <sstream>
  11. #include <algorithm>
  12. #include <vector>
  13. #include <set>
  14. #include <queue>
  15. #include <map>
  16. #include <stack>
  17. using namespace std;
  18.  
  19. //#define DEBUG
  20.  
  21. /// STRUCTURE FOR FRACTION NUMBER
  22. /// it will store number as fraction and
  23. /// do operations as we do with fractions
  24. struct Fraction
  25. {
  26.     typedef long long Tp;
  27.  
  28.     ///variables
  29.     Tp num;
  30.     Tp denom;
  31.  
  32.     ///initialize
  33.     Fraction() : num(0), denom(1) { }
  34.     Fraction(const Tp& n) : num(n), denom(1) { }
  35.     Fraction(const Tp& n, const Tp& d)
  36.     {
  37.         num = n;
  38.         denom = d;
  39.         normalize();
  40.     }
  41.  
  42.     ///input and output
  43.     friend istream& operator >> (istream& in, Fraction& n)
  44.     {
  45.         n.denom = 1;
  46.         in >> n.num;
  47.         if(in.get() == '/')
  48.             in >> n.denom;
  49.         n.normalize();
  50.         return in;
  51.     }
  52.     friend ostream& operator << (ostream& out, const Fraction& n)
  53.     {
  54.         out << n.num;
  55.         if(n.num != 0 && n.denom > 1)
  56.             out << '/' << n.denom;
  57.         return out;
  58.     }
  59.  
  60.     ///logical operators
  61.     bool operator == (const Tp& rhs) const
  62.     {
  63.         return denom == 1 && num == rhs;
  64.     }
  65.  
  66.     bool operator != (const Tp& rhs) const
  67.     {
  68.         return !(*this == rhs);
  69.     }
  70.  
  71.     ///arithmetic operators with same type
  72.     Fraction operator + (const Fraction& b)
  73.     {
  74.         Fraction res;
  75.         Fraction& a = *this;
  76.         res.denom = a.denom * b.denom;
  77.         res.num =  a.num * b.denom + b.num * a.denom;
  78.         res.normalize();
  79.         return res;
  80.     }
  81.     Fraction operator - (const Fraction& b)
  82.     {
  83.         Fraction res;
  84.         Fraction& a = *this;
  85.         res.denom = a.denom * b.denom;
  86.         res.num =  a.num * b.denom - b.num * a.denom;
  87.         res.normalize();
  88.         return res;
  89.     }
  90.     Fraction operator * (const Fraction& b)
  91.     {
  92.         Fraction res;
  93.         Fraction& a = *this;
  94.         res.num = a.num * b.num;
  95.         res. denom = a.denom * b.denom;
  96.         res.normalize();
  97.         return res;
  98.     }
  99.     Fraction operator / (const Fraction& b)
  100.     {
  101. #ifdef DEBUG
  102.         if(b == 0)
  103.         {
  104.             cout << "DIVIDE BY ZERO!!" << endl;
  105.             exit(0);
  106.         }
  107. #endif // DEBUG
  108.  
  109.         Fraction res;
  110.         Fraction& a = *this;
  111.         res.num = a.num * b.denom;
  112.         res.denom = a.denom * b.num;
  113.         res.normalize();
  114.         return res;
  115.     }
  116.  
  117.     ///necessary functions
  118.     void normalize()
  119.     {
  120.  
  121. #ifdef DEBUG
  122.         if(denom == 0)
  123.         {
  124.             cout << "Denominator is zero!!" << endl;
  125.             exit(0);
  126.         }
  127. #endif // DEBUG
  128.  
  129.         if(num == 0) denom = 1;
  130.         if(denom == 0) denom = 1;
  131.  
  132.         if(denom < 0)
  133.         {
  134.             num = -num;
  135.             denom = -denom;
  136.         }
  137.  
  138.         int g = __gcd(abs(num), denom);
  139.         if(g > 0)
  140.         {
  141.             num /= g;
  142.             denom /= g;
  143.         }
  144.     }
  145. };
  146.  
  147.  
  148. ///
  149. /// MATRIX OPERATIONS
  150. ///
  151.  
  152. typedef vector<Fraction> VFD;
  153.  
  154. //scan the matrix
  155. void getmatrix(vector<VFD>& matrix, int row, int col)
  156. {
  157.     for(int i = 0; i < row; ++i)
  158.     {
  159.         matrix.push_back(VFD());
  160.         for(int j = 0; j < col; ++j)
  161.         {
  162.             matrix[i].push_back(Fraction());
  163.             cin >> matrix[i][j];
  164.         }
  165.     }
  166. }
  167.  
  168. #ifdef DEBUG
  169. void show(vector<VFD>& mat)
  170. {
  171.     cout << "\nMATRIX of order " << mat.size()
  172.          << " * " << mat[0].size() << endl;
  173.  
  174.     for(int i = 0; i < mat.size(); ++i)
  175.     {
  176.         for(int j = 0; j < mat[i].size(); ++j)
  177.             cout << mat[i][j] << "   ";
  178.         cout << endl;
  179.     }
  180.     cout << endl;
  181.  
  182. }
  183. #endif // DEBUG
  184.  
  185. //row reduced echelon form -> gaussian algo
  186. void reduce(vector<VFD>& mat, int row, int col)
  187. {
  188.     for(int i = 0; i < row; ++i)
  189.     {
  190.  
  191. #ifdef DEBUG
  192.         show(mat);
  193. #endif // DEBUG
  194.  
  195.         //make sure that the pivot is not zero
  196.         if(mat[i][i] == 0)
  197.         {
  198.             bool cont = true;
  199.  
  200.             //check down rows
  201.             for(int r = i + 1; cont && r < row; ++r)
  202.             {
  203.                 if(mat[r][i] != 0)
  204.                 {
  205.                     cont = false;
  206.                     swap(mat[i], mat[r]);
  207.                     break;
  208.                 }
  209.             }
  210.             //check upper rows
  211.             for(int r = i - 1; cont && r >= 0; --r)
  212.             {
  213.                 if(mat[r][r] == 0 && mat[r][i] != 0)
  214.                 {
  215.                     cont = false;
  216.                     swap(mat[i], mat[r]);
  217.                     break;
  218.                 }
  219.             }
  220.  
  221.             if(cont) continue;
  222.         }
  223.  
  224.         //check if pivot is 1
  225.         // if not divide the row by pivot
  226.         Fraction pivot = mat[i][i];
  227.         if(pivot != 1)
  228.         {
  229.             for(int j = 0; j < col; ++j)
  230.                 mat[i][j] = mat[i][j] / pivot;
  231.         }
  232.  
  233.         //for all row do operatoins
  234.         // to make the rest of pivot column zero
  235.         for(int j = 0; j < row; ++j)
  236.         {
  237.             if(i != j) //if not the pivot row..
  238.             {
  239.                 //multiply pivot row element with pivot column value
  240.                 //then substract the value from pivot row to
  241.                 //make all pivot coloumn zero
  242.                 pivot = mat[j][i];
  243.                 for(int k = 0; k < col; ++k)
  244.                     mat[j][k] = mat[j][k] - (mat[i][k] * pivot);
  245.             }
  246.         }
  247.     }
  248.  
  249. #ifdef DEBUG
  250.     show(mat);
  251. #endif // DEBUG
  252.  
  253. }
  254.  
  255. ///
  256. ///MAIN METHOD
  257. ///
  258.  
  259. int main()
  260. { 
  261.     bool putline = false;
  262.  
  263.     int mat_num;
  264.     int variable, equation;
  265.     while(cin >> mat_num && mat_num)
  266.     {
  267.         if(putline) putchar('\n');
  268.         printf("Solution for Matrix System # %d\n", mat_num);
  269.         putline = true;
  270.  
  271.         cin >> variable >> equation;
  272.  
  273.         //get matrix
  274.         int row = equation,
  275.             col = variable + 1;
  276.         vector<VFD> matrix;
  277.         getmatrix(matrix, row, col);
  278.  
  279.         //get the reduced matrix form
  280.         reduce(matrix, row, col);
  281.  
  282.         //determine the ranks of reduced form
  283.         int rkA = 0, rkAc = 0;
  284.         for(int i = 0, j; i < row; ++i)
  285.         {
  286.             bool rk = true;
  287.             for(j = 0; rk && j < col - 1; ++j)
  288.                 if(matrix[i][j] != 0) rk = false;
  289.             if(!rk) ++rkA;
  290.  
  291.             if(matrix[i][j] != 0) rk = false;
  292.             if(!rk) ++rkAc;
  293.         }
  294.  
  295.         //if rankof A is 0 or rank of A and AC doesn't match
  296.         // system is inconsistent or there is no solution
  297.         if(rkA != rkAc)
  298.         {
  299.             printf("No Solution.\n");
  300.             continue;
  301.         }
  302.  
  303.         //in consistent system if number of unknowns > rank of A
  304.         // then there are infite soluton
  305.         // in this case arbitrary constants = variable - rank
  306.         if(variable > rkA)
  307.         {
  308.             printf("Infinitely many solutions containing %d arbitrary constants.\n", variable - rkAc);
  309.             continue;
  310.         }
  311.  
  312.  
  313.         //there are finite solution
  314.         // print them all one by one
  315.         for(int i = 0; i < variable; ++i)
  316.         {
  317.             printf("x[%d] = ", i + 1);
  318.             cout << matrix[i][variable] << endl;
  319.         }
  320.  
  321.     }
  322.  
  323.     return 0;
  324. }
  325.  
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
1
4 3
0 1 1 1 3
0 0 1 1 2
0 0 0 1 1

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

3
4 4
0 1 1 1 3
0 0 0 0 0
0 0 0 1 1
0 1 1 2 9

4
4 4
1/-2 -2/-3 1/-2 6/9 8/12
67/-5 -5/9 0 0 1
0 0 0 1 1
1 0 1 1 7

5
4 8
1/-2 -2/-3 1/-2 6/9 8/12
1/-2 -2/-3 1/-2 6/9 8/12
67/-5 -5/9 0 0 1
67/-5 -5/9 0 0 1
0 0 0 1 1
0 0 0 1 1
1 0 1 1 7
1 0 1 1 7

6
4 5
1/-2 -2/-3 1/-2 6/9 8/12
67/-5 -5/9 0 0 1
0 0 0 1 1
1 0 1 1 7
1 0 1 1 8

5 
5 3 
1 3 3 2 1 5 
0 0 3 1 2 1 
0 0 0 0 0 0 

10 
2 4 
0 0 0 
0 0 0 
1 2 1 
2 2 2 

11 
3 3 
2 1 1 5 
4 -6 0 -2 
-2 7 2 9 

12 
3 3 
353 45 29 79 
45 29 3 5 
29 3 4 8 

13 
2 4 
1 2 1 
6/2 1 2 
4 3 1 
2 1 2 

14 
3 3 
0 0 3 10 
0 3 -3 3 
2 -1 2 7 

15 
2 3 
1 1 10 
1 1 20 
2 2 50 

18 
3 3 
2 2 2 2 
4 4 4 4 
16 16 16 16 

20 
3 3 
1 2 0 3 
3 4 4 7 
5 6 3 8 

22 
1 5 
1 10 
-1 -10 
2 20 
3 30 
5 50 

0
stdout
copy 
Solution for Matrix System # 1
Infinitely many solutions containing 1 arbitrary constants.

Solution for Matrix System # 2
No Solution.

Solution for Matrix System # 3
No Solution.

Solution for Matrix System # 4
x[1] = -35/134
x[2] = 9/2
x[3] = 839/134
x[4] = 1

Solution for Matrix System # 5
x[1] = -35/134
x[2] = 9/2
x[3] = 839/134
x[4] = 1

Solution for Matrix System # 6
No Solution.

Solution for Matrix System # 5
Infinitely many solutions containing 3 arbitrary constants.

Solution for Matrix System # 10
x[1] = 1
x[2] = 0

Solution for Matrix System # 11
x[1] = 1
x[2] = 1
x[3] = 2

Solution for Matrix System # 12
x[1] = 585/3278
x[2] = -631/3278
x[3] = 1394/1639

Solution for Matrix System # 13
No Solution.

Solution for Matrix System # 14
x[1] = 7/3
x[2] = 13/3
x[3] = 10/3

Solution for Matrix System # 15
No Solution.

Solution for Matrix System # 18
Infinitely many solutions containing 2 arbitrary constants.

Solution for Matrix System # 20
x[1] = -7/5
x[2] = 11/5
x[3] = 3/5

Solution for Matrix System # 22
x[1] = 10
https://ideone.com/9oLpyC
Fractional Number and Matrix Class implementation - NEED DEBUGGING
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!