Jump to content




Recent Status Updates

  • Photo
      30 Sep
    rhossis

    laptop hard disk seated beneath motherboard but with no access panel. 7 hours to replace :(

    Show comments (3)
  • Photo
      19 Sep
    Chall

    I love it when you go to write a help thread, then while writing, you reach an enlightenment, and figure it out yourself.

    Show comments (3)
View All Updates

Developed by Kemal Taskin
Photo
- - - - -

Solving systems of equations (C++)

nested loop equation

  • Please log in to reply
No replies to this topic

#1 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 01 February 2010 - 02:11 PM

I recently went through a math class (Advanced Alg. IV) that required me
to solve a system of equations in several different ways such as Cramer's rule, and inverse matrices. We also learned how to solve a system of equations using Row Reduced Echelon Form (RREF) matrices. While learning this process, it occurred to me that there was a distinct and simple pattern to solving the matrix. It also occurred to me that this pattern could easily be duplicated in a program written to solve the system. Thus, I created this program that solves systems of equations through the RREF method.

I used C++ to write this solver (just to let you know).

For those of you who don't know, RREF says that when we take a system of equations, we first create an augmented matrix to represent the system.

[[ 4  1  3 -2
   2 1/2 7  4
   6 3/4 2 -7]]

This would represent a system of equations with 3 variables. What we end up with after a series of operations on the matrix might look something like this:

[[ 1 0 0  -3
   0 1 0   1
   0 0 1 -1/2]]

Where x=-3, y=1, and z=-1/2. The program that I have created performs the correct operations on a given matrix to find the solutions to the system of equations represented therein. More on RREF can be found here (wish I had visited this site before making the program).

Instead of going with a double data type to represent numbers in the matrix, I opted for a fraction data type as fractions are much easier to work with and overcome the problem of double imprecision. I used the fraction class provided by Brian Overland in his book "C++ Without Fear" as a base and added functionality as I went along.

Here is the header file:
/ Class automatically generated by Dev-C++ New Class wizard

#ifndef FRACTION_H
#define FRACTION_H

#include <iostream>
#include <string>

class Fraction
{
    private: 
        int num, den;
        void normalize();
        int gcf(int a, int b);
        int lcm(int a, int b);
        
	public:
		Fraction() {set(0, 1);}
		Fraction(int n, int d) {set(n, d);}
		Fraction(int n) {set(n, 1);}
		Fraction (const Fraction &src);
		Fraction (std::string);
		
		void set(int n, int d) {num = n; den = d; normalize();}
		
		int getNum() const {return num;}
		int getDen() const {return den;}
		Fraction add(const Fraction &other);
		Fraction mult(const Fraction &other);
		Fraction operator+(const Fraction &other) {return add(other);}
		Fraction operator*(const Fraction &other) {return mult(other);}
		int operator==(const Fraction &other);
		friend std::ostream &operator<<(std::ostream &os, Fraction &fr);
};

#endif

And here is the body of the class:
// Class automatically generated by Dev-C++ New Class wizard

#include "fraction.h"
#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>

Fraction::Fraction(Fraction const &src)
{
     num = src.num;
     den = src.den;
}

Fraction::Fraction(std::string fractString)
{
     int divPos = fractString.find("/");
     char numString[80] = ""; //Quick patch, make the array big enough (hopefully)
     char denString[80] = "";
     
     strcpy(numString, fractString.substr(0, divPos).c_str());
     num = atoi(numString);
     
     if (divPos == -1)
     {
        den = 1;
     }
        
     else
     {
        strcpy(denString, fractString.substr(divPos + 1).c_str());
        den = atoi(denString);
     }
}

void Fraction::normalize()
{
     if (den == 0 || num == 0)
     {
          num = 0;
          den = 1;
     }
     
     if (den < 0)
     {
          num *= -1;
          den *= -1;
     }
     
     int n = gcf(num, den);
     num = num/n;
     den = den/n;
}

int Fraction::gcf(int a, int b) 
{
    if (a % b == 0)
       return abs(b);
    else
       return gcf(b, a % b);
}

int Fraction::lcm(int a, int b)
{
    return (a / gcf(a, b)) * b;
}

Fraction Fraction::add(const Fraction &other)
{
    Fraction fract;
    int lcd = lcm(den, other.den);
    int quot1 = lcd/den;
    int quot2 = lcd/other.den;
    fract.set(num * quot1 + other.num * quot2, lcd);
    fract.normalize();
    return fract;
}

Fraction Fraction::mult(const Fraction &other)
{
    Fraction fract;
    fract.set(num * other.num, den * other.den);
    return fract;
}

int Fraction::operator==(const Fraction &other)
{
    return (num == other.num && den == other.den);
}

std::ostream &operator<<(std::ostream &os, Fraction &fr)
{
    os << fr.num << "/" << fr.den;
    return os;
}

The last part is the main class. I initially wanted to use dynamic memory allocation to create my matrix, but then realized that it would be inapropriate considering the complex data types I was dealing with. I opted to use vectors which can be expanded and deflated at will. The steps in the program go something like this:

*find out the dimensions of the matrix.
*take in all the data as strings and convert to fractions.
*enter the solving loop.
*solve each column of the matrix except for the last one which contains the solutions and display each step as solving occurs.
*show the final solution to the matrix and exit.

So, here is the source code to the main function:
#include <iostream>
#include <string>
#include <vector>
#include "fraction.h"

using namespace std;

void showMatrix(int, int, vector<vector<Fraction> >);

int main(void)
{
    int rows, cols;
    string inputBuffer = "";
    vector<vector<Fraction> > mat;
    vector<Fraction> buffer;
    Fraction negitiveFrac(-1/1);
    Fraction multNumber2;
    
    int currentRow = 0, currentCol = 0;
    
    cout << "Enter the number of rowsXcolumns in the matrix: ";
    cin >> rows;
    cin >> cols;
    
    for(int i = 0; i < rows; i++)
    {
        vector<Fraction> row;
        mat.push_back(row);
        for(int j = 0; j < cols; j++)
        {
            cout << "Enter row " << i + 1 << ", column " << j + 1 << " : ";
            cin >> inputBuffer;
            Fraction fracBuffer(inputBuffer);
            mat[i].push_back(fracBuffer);
        }
        cout << endl;
    }
    
    while(currentRow < rows && currentCol < cols)
    {    
        Fraction multNumber1(mat[currentRow][currentCol].getDen(), mat[currentRow][currentCol].getNum());
        
        for(int i = 0; i < cols; i++)
            mat[currentRow][i] = mat[currentRow][i] * multNumber1;
        
        showMatrix(rows, cols, mat);
        
        for(int i = 0; i < rows; i++)
        {   
            if (currentRow == i)
                continue;
            else
            {
                multNumber2 = negitiveFrac * mat[i][currentCol];
                for(int j = 0; j < cols; j++)
                    buffer.push_back(mat[currentRow][j]);
            }
            
            for(int j = 0; j < cols; j++)
                mat[i][j] = mat[i][j] + (buffer[j] * multNumber2);
            
            showMatrix(rows, cols, mat);
        }
        
        currentRow += 1;
        currentCol += 1;
        buffer.clear();
    }
    
    cout << "Final solution of the system of equations provided: " << endl;
    showMatrix(rows, cols, mat);
    cout << endl;
    system("pause");
}

void showMatrix(int rows, int cols, vector<vector<Fraction> > mat)
{
    cout << "[[";
    for(int i = 0; i < rows; i++)
    {
        if (i != 0) cout << "  ";
        for(int j = 0; j < cols; j++)
            cout << " " << mat[i][j] << " ";
        if (i != rows - 1)cout << "\n";
    }
    cout << "]]" << endl << endl;
}      

This program is kind of slopped together, and doesn't include input validation or fancy output formatting. It shows some cool concepts though, like how to overcome double imprecision as well as vectors and nested loops (alot of nested loops :)). The classes could probably be modified to allow any size matrix to be entered (until the computers memory fills up that is), but right now there is a limit because of the character buffer in the fraction class. I have attached the source code, which should compile in Dev-C++ but may have errors in another compiler. Let me know what you think!

Attached Files

  • Attached File  rref.zip   161.83KB   338 downloads

  • 0





Also tagged with one or more of these keywords: nested loop, equation