It is currently Thu Jul 20, 2017 11:32 am

All times are UTC - 5 hours




 Page 1 of 1 [ 5 posts ] 
Author Message
 Post subject: Having A little trouble with recursion.
PostPosted: Wed Oct 17, 2012 3:54 pm 

Joined: Sat Aug 16, 2008 7:58 am
Posts: 447
I am working on a function that is comparing each term object in a vector to see if they are (alike) not being == that is for example 3x^2 + 4x^2 are alike terms. I am trying to find all like terms and add them so when I am doing going through the function each term that is left is different from the next and so on. Recursion would be a great way to do this since we do not know how many terms this polynomial will have. The trouble I am having is figuring out how to make the base case to break out of the recursion. This is the function I have so far. I use a function to sort them from greatest exponent to lest exponent. I will have to eventually change that function once I set up the highest order to the term if that term contains more than one variable for example: 3x^3*y^2 then this term would have an order of 5, but for now I am testing only using a single variable x in my terms.

// ------------------------------------------------------------------------- //
// combineLikeTerms()
//
template <class T>
void Polynomial<T>::combineLikeTerms() {
   
   // First We Order Our Terms.
   setPolynomialByDegreeOfExponent();   

   Term<T> t; // Temp Variable
   std::vector<Term<T>> vTempTerms; // Temp storage
   std::vector<Term<T>>::iterator it = _vTerms.begin();
   std::vector<Term<T>>::iterator it2 = (_vTerms.begin()+1);

   while ( it2 != _vTerms.end() ) {
      for ( int i = 0; i < (int)_vTerms.size()-1; i++ ) {
         if ( (*it).termsAreAlike( *it2 ) ) {
            t = *it + *it2; // Add The Like Terms
            vTempTerms.push_back( t ); // Push To Our Temp
            it += 2;  // Advance Two Locations
            it2 += 2; //     ""
         } else {
            t = *it; // Set Only First It To Our Temp
            vTempTerms.push_back( t );  // Push To Our Temp
            it++;  // Advance Only One Location For Each
            it2++;
         }
      }
   }

   // Set our Member Equal To Our Temp
   _vTerms = vTempTerms;

   // Reset Our Iterators
   it = _vTerms.begin();
   it2 = (_vTerms.begin()+1);

   combineLikeTerms();
   
} // combineLikeTerms


Any help would be awesome!!!


Offline
 Profile  
 
 Post subject: Re: Having A little trouble with recursion.
PostPosted: Wed Oct 17, 2012 7:56 pm 

Joined: Sat Aug 16, 2008 7:58 am
Posts: 447
I almost forget to mention, the base case to break out of the recursion would be when there are no more like terms.


Offline
 Profile  
 
 Post subject: Re: Having A little trouble with recursion.
PostPosted: Thu Oct 18, 2012 4:33 pm 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1102
Location: Ontario Canada
I don't know why you need to use recursion at all. Why not just use an std::map to store your values as you iterate through the container that holds your polynomial?


Offline
 Profile  
 
 Post subject: Re: Having A little trouble with recursion.
PostPosted: Thu Oct 18, 2012 5:08 pm 

Joined: Sat Aug 16, 2008 7:58 am
Posts: 447
Never thought about it that way. The reason I was thinking of recursion is for example, 3x^3 - 2x^3 + x^3 + 2x^2 + 5
and since the vector is already sorted... on the first run through the function 3x^3 - 2x^3 are the elements the function is checking to see if they are alike and it returns true, then we add these two to a temp vector since we already used them we will increment our itFirst and itSecond by 2 provided itSecond != vector.end()-1. Now that we advanced the pointers itFirst and itSecond are now looking at x^3 and 2x^2 respectively using the same function test but this time the function returns false, since itFirst failed we are taking itFirst and putting into our temp vector and we then increment out iterators both by 1 this time. Now, itFirst and itSecond are looking at 2x^2 + 5 and again this fails and since itSecond == vector.end()-1 we don't increment we just push both on the temp vector if the test fails, otherwise we add them together and push just result into the vector. After we are done the resulting temp vector would look like this. 5x^3 - 2x^3 + 2x^2 + 5 we still have like terms this is were I was thinking of using recursion, until the base case is met which is when there are no two terms that are alike. This was the idea I had in mind. This would sit well for any size vector container. The way it is implemented it is already set up to accept any number of variables to a term... Ex: 3x^2y^3z or mnq^2r^2st^3 ... etc.


Offline
 Profile  
 
 Post subject: Re: Having A little trouble with recursion.
PostPosted: Tue Oct 23, 2012 10:53 am 

Joined: Sat Aug 16, 2008 7:58 am
Posts: 447
After some work, I did not need to use recursion at all, and I didn't even have to use a map either. I have successfully created 3 class templates One class is Coefficient<T> wich is internally stored as std::complex<T> it will track if the number coef is a real value or complex value, and does a little error checking. The next class is the Term<T> which contains a Coefficient<T> object and 2 std::vector<>s one that holds a chars and one that holds an unsigned int. char for Variables in term and unsigned int for exponents. For a polynomial to be a polynomial the exponent has to be positve integers.... can not have x^-1 or x^(1/2) which does not evaulate to a polynomial. This class depends on the size of these two internal vectors be the same. For example, if we have a Term<T> t... that is 3m^3n^2 for each variable we have to have a valid matching exponent even if the exponent is 1 or 0 because the Polynomial<T> depends on it for combining terms and for constructing a std::string for easy printing. the makePolyString function will reduce any understood values. If the coefficient is = 1, it will only display the variable^exponent. if the exponent is 1 it will display only the coefficent*exponent. if the exponent is 0 it will only display the coefficient and if the coefficient is 0 it will not display that term and finally if the coefficient is -1 it will display - coefficient*exponent. These three sets of classes can allow you to create any valid polynomial. I read a few posts where some experienced programmers said that this was one of the hardest things to do is to represent the summation of all polynomials in a program, once I got the hang of implementing templates nicely and learned a little more into the std with using complex and stringstreams it was challenging but not all that hard, it only took me maybe a good month to debug and get clean code running with correct results. It may not be 100% bug free now and a little more error checking could be done, and even going back and revising some of the methods to run more efficient, so that most of the containers can run at most at O(n) or even better O(log N). Want to stay away from quadratic runtime as much as possible. However with a resonable polynomial I don't think we would have to worry about that with std::vector. Unless someone really wants to create a Polynomial with a few million terms, were each term have a few hundred or more variables and exponents attatched to it lol. This work was worth the great effort!!!


Offline
 Profile  
 
Display posts from previous:  Sort by  
 Page 1 of 1 [ 5 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Jump to:  

cron