Sign in to follow this  
Nomad010

[java] Problem With Algorithm

Recommended Posts

I have been working on a polynomial system in Java. I don't where it'll go, but it'll be useful to further projects. So this is how I planned it. You have a Monomial class which has a coefficient and a power of x, though more will be included eg: a differentiate function. Then you have a Polynomial class which has a vector which stores Monomial objects, herein the problem lies. When a Polynomial is made, I would like it to sort in descending powers of 'x', remove powers with coefficients of zero, and add coefficients of like powers. This last part does not work. I have redone the method 4 times and each time I get wrong results. Either this is an algorithmic problem or a problem in my head. The problems are in the "void sort()" method. The current method is very hard to follow because I got so frustrated while trying to make the method that I just stopped making neat, logical code and resort to messy code that has 1% chance of being written correctly. Monomial.java
class Monomial
{
 private long power = 0;
 private long coefficient = 0;
 
 public Monomial(long Power, long Coefficient)
 {
  power = Power;
  coefficient = Coefficient;
 }
 
 public String toString()
 {
  return "(" + coefficient + "x^" + power + ")"; 
 }
 
 public long getPower()
 {
  return power;
 }
 
 public void setPower(long newPower)
 {
  power = newPower;
 }
 
 public long getCoeff()
 {
  return coefficient;
 }
 
 public void setCoeff(long newCoefficient)
 {
  coefficient = newCoefficient;
 }
}


Polynomial.java
import java.util.*;

class Polynomial
{
 Vector monomials = new Vector();
 
 public Polynomial(Monomial terms[])
 {
  for(int i = 0; i < java.lang.reflect.Array.getLength(terms);i++)
   monomials.addElement(terms[i]);
  
  sort();
 }
 
 public void sort()
 {  
  int difLength = 0;
  
  for(int i = 0; i < monomials.size(); i++)
  {
   boolean hasOccured = false;
   Monomial testObject = (Monomial) monomials.elementAt(i);
   
   for(int j = 0; j < i; j++)
   {
    Monomial currentObject = (Monomial) monomials.elementAt(j);
    if(currentObject.getPower() == testObject.getPower())
     hasOccured = true;
   }
   
   if(!hasOccured)
    difLength++;
  }
  
  if(difLength != monomials.size())
  {
   for(int i = 0; i < monomials.size(); i++)
   {
    Monomial testObject = (Monomial) monomials.elementAt(i);
    for(int j = 0; j < monomials.size(); j++)
    {
     Monomial currentObject = (Monomial) monomials.elementAt(j);
     if(currentObject.getPower() == testObject.getPower() /*&& (currentObject.equals(testObject))*/)
     {
      testObject.setCoeff(testObject.getCoeff() + currentObject.getCoeff());
      monomials.removeElementAt(j);
      j=0;
     }
    }
   }
   
   Monomial[] sortArray = new Monomial[difLength];
   
   for(int i = 0; 0 < monomials.size();i++)
   {
    long highestPower = ((Monomial) monomials.elementAt(0)).getPower();
    int num = 0; 
    for(int j = 0; j < monomials.size();j++)
    {
     Monomial currentObject = (Monomial) monomials.elementAt(j);
     highestPower = (highestPower > currentObject.getPower())? highestPower : currentObject.getPower();
     num = (highestPower > currentObject.getPower())? num : j;
    }
    
    sortArray[i] = (Monomial) monomials.elementAt(num);
    monomials.removeElementAt(num);
   }
   
   for(int i = 0; i < difLength; i++)
    monomials.addElement(sortArray[i]);
  }
  else
  {
   Monomial sortArray[] = new Monomial[monomials.size()];
   
   for(int i = 0; i < monomials.size(); i++)
   {
    sortArray[i] = (Monomial) monomials.elementAt(i);
    monomials.removeElementAt(i);
   }
   
   for(int i = 0; i < monomials.size(); i++)
   {
    long highestPower = ((Monomial) monomials.elementAt(0)).getPower();
    int num = 0;
     
    for(int j = 0; j < monomials.size(); j++)
    {
     Monomial currentObject = (Monomial) monomials.elementAt(j);
     highestPower = (highestPower > currentObject.getPower()) && !(monomials.contains(currentObject))? highestPower : currentObject.getPower();
     num = (highestPower > currentObject.getPower())  && !(monomials.contains(currentObject))? num : j;
    }
    
    sortArray[i] = (Monomial) monomials.elementAt(num);
    monomials.removeElementAt(num);
   }
  }
 }
 
 public String toString()
 {
  String s = "";
  
  for(int i = 0; i < monomials.size();i++)
   s = s + monomials.elementAt(i).toString();
   
  return s;
 }
}


TestPolynomial.java
class TestPolynomial
{
 public static void main(String args[])
 {
  Monomial[] m = new Monomial[5];
  
  for(int i = 0; i < 5; i++)
  {
   long Power = (long) Math.round(Math.random() * 10);
   long Coeff = (long) Math.round(Math.random() * 10);
    
   m[i] = new Monomial(Power, Coeff);
  }
  
  Polynomial p = new Polynomial(m);
  
  for(int i = 0; i < 5; i++)
   System.out.println(m[i]);
   
  System.out.println(); 
  System.out.println(p.toString());
 }
}


Thank you.

Share this post


Link to post
Share on other sites
First of all, you should use ArrayList instead of Vector, unless you require synchronization.

You implement both the sorting and the "if power is equal, add coefficients" method in "sort". This should be done sepperately.

For the sorting, "Monomical" should implement "Comparable" and then you should use the "java.util.Arrays.sort()" method to do this for you.

The other immediate thing I can see is:
in the "sort" method:


if(difLength != monomials.size())
{
for(int i = 0; i < monomials.size(); i++)
{
Monomial testObject = (Monomial) monomials.elementAt(i);
for(int j = 0; j < monomials.size(); j++)
{
Monomial currentObject = (Monomial) monomials.elementAt(j);
if(currentObject.getPower() == testObject.getPower() /*&& (currentObject.equals(testObject))*/)
{
testObject.setCoeff(testObject.getCoeff() + currentObject.getCoeff());
monomials.removeElementAt(j);
j=0;
}
}
}



The two "for" loops both iterate through the whole size of "monomials". Thereby, every Monomial gets compared to itself, the powers of itself are added and then the object is removed.

That's all I can help you with at the moment. Sorry for not providing any coded solutions... I'm drunk. :\

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this