Solved

Multiplying Polynomials using recursion

Posted on 2002-05-02
11
650 Views
Last Modified: 2012-06-27
I am using the GNU Compiler.

I am trying to multiply 2 polynomials.

Using recursion and arrays. Polynom.cpp has already been completed by the instructor. We just need to finish main.cpp, specifically (void MultPoly (Polynomial p, Polynomial q, Polynomial& r).)

The following the block is what is giving me issues:

void MultPoly (Polynomial p, Polynomial q, Polynomial& r)
{
    int deg;
    float coEff;

    deg=p.GetDegree();
    coEff=p.GetCoefficient(deg);
    p.DeleteTerm(deg);
    MultPoly(p,q,r);
    coEff=coEff*r.GetCoefficient(deg);
    r.InsertTerm(coEff,deg);
}

The whole program compiles correctly, but I am not getting any result for multiplying polynomials when I input 2 of them. It doesn't seg fault, it just doesn't print anything.

All it needs to do is multiply 2 polynomials together, then print the result to the screen.

Thanks for the help!
0
Comment
Question by:jonisgone
  • 3
  • 3
  • 2
  • +3
11 Comments
 
LVL 6

Expert Comment

by:thienpnguyen
ID: 6987148
You use "recursive algorithm" but I don't see the algorithm's base case : when the algorithm stops to call itseft .

0
 
LVL 6

Expert Comment

by:thienpnguyen
ID: 6987154
Could you explain what DeleteInsert and InsertTerm( coEff, deg) does ?
0
 
LVL 5

Expert Comment

by:BlackDiamond
ID: 6987207
if (deg > 0){
   MultPoly(p,q,r);
}
0
Microsoft Certification Exam 74-409

Veeam® is happy to provide the Microsoft community with a study guide prepared by MVP and MCT, Orin Thomas. This guide will take you through each of the exam objectives, helping you to prepare for and pass the examination.

 
LVL 6

Expert Comment

by:thienpnguyen
ID: 6987217
Not only that bug, I think that the algorithm also has problem . But I don't know what DeleteItem and InsertItem, I can not point out exactly what problem is
0
 

Author Comment

by:jonisgone
ID: 6987292
DeleteTerm allows for the next term in the Polynomial p to be examined(that was input by the user at the beginning of the program).  

InsertTerm will be what is printed out to the screen at the end of the program.  It is not part of main.cpp but poly.cpp...it looks like this:

void Polynomial::InsertTerm (float coeff, int deg)

// Precondition:
//     A nonnegative degree deg and a coefficient coeff are assigned
// Postcondition:
//     The polynomial contains a term of degree deg whose coefficient
//     is coeff.  If the polynomial originally had a term of degree deg
//     then the coefficient of that term has been replaced.  If coeff
//     is zero the result is the same as DeleteTerm (deg).

{
    if ( fabs(coeff) < .000001 )
    {
      DeleteTerm (deg);
      return;
    }

    Term* currPtr;       // Moving pointer
    Term* prevPtr;       // Pointer to node before *currPtr

// Find previous insertion point

    prevPtr = NULL;
    currPtr = leadingTerm;
    while (currPtr != NULL && deg < currPtr->degree)
    {
        prevPtr = currPtr;
        currPtr = currPtr->link;
    }

// Replace coefficient, if appropriate.

    if (currPtr != NULL && deg == currPtr->degree)
    {
      currPtr->coefficient = coeff;
      return;
    }

// Set up node to be inserted

    Term* newTerm = new Term;
    newTerm->degree = deg;
    newTerm->coefficient = coeff;

// Insert new term

    newTerm->link = currPtr;
    if (prevPtr == NULL)
        leadingTerm = newTerm;
    else
        prevPtr->link = newTerm;
};

//******************************************************************

void Polynomial::DeleteTerm (int deg)

// Precondition:
//     an integer deg is assigned
// Postcondition:
//     The term of degree deg in the polynomial (if it existed) has been
//     removed

{
    Term* delPtr;     // Pointer to term to be deleted
    Term* currPtr;    // Loop control pointer

// Do nothing if the polynomial is zero

    if (leadingTerm == NULL)
        ;

// Check if term to be deleted is first term

    else if (deg == leadingTerm->degree)
    {
        delPtr = leadingTerm;
        leadingTerm = leadingTerm->link;
        delete delPtr;
    }

// Search for node in rest of list

    else
    {
        currPtr = leadingTerm;
        while (currPtr->link != NULL && currPtr->link->degree > deg)
            currPtr = currPtr->link;
        if (currPtr->link != NULL && currPtr->link->degree == deg)
        {
            delPtr = currPtr->link;
            currPtr->link = currPtr->link->link;
            delete delPtr;
        }
    }
};
0
 

Author Comment

by:jonisgone
ID: 6987312
DeleteTerm allows for the next term in the Polynomial p to be examined(that was input by the user at the beginning of the program).  

InsertTerm will be what is printed out to the screen at the end of the program.  It is not part of main.cpp but poly.cpp...it looks like this:

void Polynomial::InsertTerm (float coeff, int deg)

// Precondition:
//     A nonnegative degree deg and a coefficient coeff are assigned
// Postcondition:
//     The polynomial contains a term of degree deg whose coefficient
//     is coeff.  If the polynomial originally had a term of degree deg
//     then the coefficient of that term has been replaced.  If coeff
//     is zero the result is the same as DeleteTerm (deg).

{
    if ( fabs(coeff) < .000001 )
    {
      DeleteTerm (deg);
      return;
    }

    Term* currPtr;       // Moving pointer
    Term* prevPtr;       // Pointer to node before *currPtr

// Find previous insertion point

    prevPtr = NULL;
    currPtr = leadingTerm;
    while (currPtr != NULL && deg < currPtr->degree)
    {
        prevPtr = currPtr;
        currPtr = currPtr->link;
    }

// Replace coefficient, if appropriate.

    if (currPtr != NULL && deg == currPtr->degree)
    {
      currPtr->coefficient = coeff;
      return;
    }

// Set up node to be inserted

    Term* newTerm = new Term;
    newTerm->degree = deg;
    newTerm->coefficient = coeff;

// Insert new term

    newTerm->link = currPtr;
    if (prevPtr == NULL)
        leadingTerm = newTerm;
    else
        prevPtr->link = newTerm;
};

//******************************************************************

void Polynomial::DeleteTerm (int deg)

// Precondition:
//     an integer deg is assigned
// Postcondition:
//     The term of degree deg in the polynomial (if it existed) has been
//     removed

{
    Term* delPtr;     // Pointer to term to be deleted
    Term* currPtr;    // Loop control pointer

// Do nothing if the polynomial is zero

    if (leadingTerm == NULL)
        ;

// Check if term to be deleted is first term

    else if (deg == leadingTerm->degree)
    {
        delPtr = leadingTerm;
        leadingTerm = leadingTerm->link;
        delete delPtr;
    }

// Search for node in rest of list

    else
    {
        currPtr = leadingTerm;
        while (currPtr->link != NULL && currPtr->link->degree > deg)
            currPtr = currPtr->link;
        if (currPtr->link != NULL && currPtr->link->degree == deg)
        {
            delPtr = currPtr->link;
            currPtr->link = currPtr->link->link;
            delete delPtr;
        }
    }
};
0
 

Author Comment

by:jonisgone
ID: 6987466
I did a little more work on the function, and came up with this.  I am including AddPoly in hopes someone will understand more clearly what I am asking (keep getting seg fault for product of the Polys):

void MultPoly (Polynomial p, Polynomial q, Polynomial& r)
{
    int deg;
    float coEff;

    deg=p.GetDegree();
    coEff=p.GetCoefficient(deg);
    p.DeleteTerm(deg);
    MultPoly(p,q,r);
    EasyMult(coEff,deg,q);   //multiplies leading term by rest
    AddPoly(p,q,r);          //will addup p & q polys
    r.InsertTerm(coEff,deg);
}

// this next function is needed to multiply leading term by the rest of the polynomial.

void EasyMult (float a, int m, Polynomial p)
{
     int deg;
     float coEff;
     deg=m*p.GetDegree();
     coEff=a*p.GetCoefficient(deg);

}

If u want to talk to me right away, just IM me on AIM @ humboldtjon.  Thanks to whoever helps, i will give many points away for your generosity...
0
 
LVL 22

Expert Comment

by:ambience
ID: 6987875

deg=p.GetDegree();  // what if there is no term !!!

if(deg == -1) return;  // you are missing something like that

// or perhaps

if(p.termCount() == 0) return;

coEff=p.GetCoefficient(deg);

p.DeleteTerm(deg);  // so i think that decrements the degree

0
 
LVL 5

Accepted Solution

by:
BlackDiamond earned 200 total points
ID: 6989242
Jon,
Here is the solution to your problem.  You were close, but needed a non-destructive ADD function.  That got rid of the need to use the insert in the mult function (you just call mult and add recursively).

cheers, BD

void AddPoly (Polynomial p, Polynomial q, Polynomial& r)

// Precondition: p and q are polynomials.
//
// Postcondition: r is the sum of p and q.
//
// Uses recursion.

{
    int deg;
    float coEff;
    Polynomial p_copy, q_copy;
//  Make sure r is zeroed out.  This is useful for Mult.
    while (!r.IsZero()) {
     r.DeleteTerm(r.GetDegree());
    }
    if (p.IsZero())
     r.CopyFrom(q);
    else
    {
//  Make safe copies of p and q
     p_copy.CopyFrom(p);
     q_copy.CopyFrom(q);
     deg=p_copy.GetDegree();
     coEff=p_copy.GetCoefficient(deg);
     p_copy.DeleteTerm(deg);
     AddPoly(p_copy,q_copy,r);
     coEff=coEff+r.GetCoefficient(deg);
     r.InsertTerm(coEff,deg);
    }

}

void MultPoly (Polynomial p, Polynomial q, Polynomial& r)
{
    int deg;
    float coEff;
    Polynomial q_copy, multresult, addresult;
    if(! p.IsZero()) {

       deg=p.GetDegree();
       coEff=p.GetCoefficient(deg);
       p.DeleteTerm(deg);
       MultPoly(p,q,r);
       q_copy.CopyFrom(q);
       EasyMult(coEff,deg,q_copy,multresult);
       AddPoly(multresult,r,r);
    }
}

void EasyMult (float a, int m, Polynomial p, Polynomial &multresult)
{
     int deg;
     float coEff;
     if (! p.IsZero()) {
        deg=p.GetDegree();
        coEff=p.GetCoefficient(deg);
        p.DeleteTerm(deg);
        EasyMult(a, m, p, multresult);
        deg = deg + m;
        coEff = coEff * a;
        multresult.InsertTerm(coEff,deg);
     }
}

 
0
 
LVL 11

Expert Comment

by:griessh
ID: 7178484
Dear jonisgone

I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. You can always request to keep this question open. But remember, experts can only help you if you provide feedback to their questions.
Unless there is objection or further activity,  I will suggest to accept

     "BlackDiamond"

comment(s) as an answer.

If you think your question was not answered at all, you can explain here why you want to do this and post a request in Community support (please include this link) to refund your points. The link to the Community Support area is: http://www.experts-exchange.com/commspt/


PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
======
Werner
0
 
LVL 6

Expert Comment

by:Mindphaser
ID: 7199734
Force accepted

** Mindphaser - Community Support Moderator **
0

Featured Post

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
PDF library for Delphi 2 121
C++ to C# code conversion issue 4 106
sorting efficency of sorting algorithm 30 113
Add values of each row in an array 3 57
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question