Can someone give me some ideas on how to solve this problem?

[mscheaf]

Hi, I am new here. I am taking a class for my senior year for my BS. Our last project is to create a Polynomial calculator in CLISP. I am having trouble with one aspect of it.

Polynomials are represented as lists of lists ex: 7x^2 - 3x + 4 would be '((7 X 2) (-3 X 1) (4 X 0))

So I need to make a function that adds two polynomials

ex:

(add-poly '((6 X 7) (3 X 1) (4 X 0)) '((2 X 2) (-3 X 1) (3 X 0)))

would give me: ((6 X 7) (2 X 2) (7 X 0))

I am not sure how to start on this. I have tried a few things but nothing seems to work. Any advice?

[qbg]

Okay, so you are given the structure the data is given to you. Your two main options here are use it as is, or convert it to another form for your use, and then convert back.

Either way, it may be useful to break down the problem of adding two polynomials by defining a function, say add-term-to-poly, and then use it in writing add-poly; if you define such a function, add-poly can be as simple as (for example):

Code: Select all

(defun add-poly (poly1 poly2)
  (dolist (term poly1)
    (setf ploy2 (add-term-to-poly term poly2)))
  poly2)


You can of course write it in another style if you want.

If you don't convert to another data structure, add-poly should be easily doable in O(m*n) time (with m and n being the lengths of the two polynomials).

As a hint, take a look at FIND and its :KEY argument. Alternatively, you could do add-term-to-poly in a recursive manner (which would work assuming the polynomial is not too long).

[Paul Donnelly]

I am not sure how to start on this. I have tried a few things but nothing seems to work. Any advice?

Do you mean you have to use the CLISP implementation of Common Lisp, or did you mean to write "CL"?

I would start by defining a few functions, such as ADD-TERMS to add terms with like exponents and POW> and POW= to compare the exponents in two terms. Once I had those, it would be simple to iterate over the two, adding like terms where appropriate and combining the two polynomials otherwise. Since the input is certain to be short, you could even write it as a non-tail-recursive function.

Another approach would be to fill in the zero terms to make both the same length, making the actual addition loop less complicated. Or you could write a function that takes a single term and fits it into another polynomial in the appropriate place, then fit the second polynomials terms into the first one by one. Any of the above would work, so pick the one you think is the best algorithm. Just break down your approach into small chunks that you know how to do.