Hướng dẫn polynomial multiplication in python - phép nhân đa thức trong python

Trong hướng dẫn này, chúng ta sẽ học cách nhân hai đa thức trong Python.

Phép nhân đa thức

Hãy cùng xem xét hai đa thức P, Q. trong đó p là 2+3x^1+4x^3 và q là 1+2x^1+4x^2+5x^3.Sản phẩm của đa thức p và q là 2+7x^1+14x^2+26x^3+23x^4+16x^5+20x^6.

Sản phẩm của hai đa thức là sự nhân của mỗi thuật ngữ của đa thức đầu tiên với mỗi thuật ngữ trong đa thức thứ hai.Chẳng hạn, hãy để Lốc chiều dài của đa thức P, Q lần lượt là M, N.

Cách tiếp cận

1) Đầu tiên tạo ra một mảng kết quả của kích thước M+N-1 lưu trữ kết quả.

2) Thứ hai, khởi tạo tất cả các giá trị trong kết quả [] thành 0.

3) Nhân mọi phần tử trong đa thức p với mọi phần tử trong kết quả đa thức Q [i+j] = result [i+j]+p [i]*q [j]
result[i+j] = result[i+j]+P[i]*Q[j]

4) Trả về kết quả

def polynomial_multiplication(P, Q):
    m = len(P)
    n = len(Q)
    result = [0]*(m+n-1)
    for i in range(m):
        for j in range(n):
            result[i+j] += P[i]*Q[j]

    return result

# function that print polynomial
def polynomial(poly):
    n = len(poly)
    for i in range(n): 
        print(poly[i], end = "")
        if (i != 0): 
            print("x^", i, end = "") 
        if (i != n - 1): 
            print(" + ", end = "")

# polynomial in array representation
P = [2, 3, 0, 4]
print("First polynomial is:")
polynomial(P)
print('\n')
Q = [1, 2, 4, 5]
print("Second polynomial is: ")
polynomial(Q)
print('\n')
result = (polynomial_multiplication(P, Q))
print("Product of polynomials is: ")
polynomial(result)

Đầu ra

First polynomial is:
2 + 3x^ 1 + 0x^ 2 + 4x^ 3

Second polynomial is: 
1 + 2x^ 1 + 4x^ 2 + 5x^ 3

Product of polynomials is: 
2 + 7x^ 1 + 14x^ 2 + 26x^ 3 + 23x^ 4 + 16x^ 5 + 20x^ 6

Ngoài ra, đọc

  • Cách tìm rễ của đa thức trong Python

s1 = [1,5,2]
s2 = [6,1,4,3]
res = [0]*(len(s1)+len(s2)-1)
for o1,i1 in enumerate(s1):
    for o2,i2 in enumerate(s2):
        res[o1+o2] += i1*i2

Chỉnh sửa: Để vinh danh @Katrielalex: In honor of @katrielalex:

import collections
import itertools

class Polynomial(object):
    def __init__(self, *args):
        """
        Create a polynomial in one of three ways:

        p = Polynomial(poly)           # copy constructor
        p = Polynomial([1,2,3 ...])    # from sequence
        p = Polynomial(1, 2, 3 ...)    # from scalars
        """
        super(Polynomial,self).__init__()
        if len(args)==1:
            val = args[0]
            if isinstance(val, Polynomial):                # copy constructor
                self.coeffs = val.coeffs[:]
            elif isinstance(val, collections.Iterable):    # from sequence
                self.coeffs = list(val)
            else:                                          # from single scalar
                self.coeffs = [val+0]
        else:                                              # multiple scalars
            self.coeffs = [i+0 for i in args]
        self.trim()

    def __add__(self, val):
        "Return self+val"
        if isinstance(val, Polynomial):                    # add Polynomial
            res = [a+b for a,b in itertools.izip_longest(self.coeffs, val.coeffs, fillvalue=0)]
        else:                                              # add scalar
            if self.coeffs:
                res = self.coeffs[:]
                res[0] += val
            else:
                res = val
        return self.__class__(res)

    def __call__(self, val):
        "Evaluate at X==val"
        res = 0
        pwr = 1
        for co in self.coeffs:
            res += co*pwr
            pwr *= val
        return res

    def __eq__(self, val):
        "Test self==val"
        if isinstance(val, Polynomial):
            return self.coeffs == val.coeffs
        else:
            return len(self.coeffs)==1 and self.coeffs[0]==val

    def __mul__(self, val):
        "Return self*val"
        if isinstance(val, Polynomial):
            _s = self.coeffs
            _v = val.coeffs
            res = [0]*(len(_s)+len(_v)-1)
            for selfpow,selfco in enumerate(_s):
                for valpow,valco in enumerate(_v):
                    res[selfpow+valpow] += selfco*valco
        else:
            res = [co*val for co in self.coeffs]
        return self.__class__(res)

    def __neg__(self):
        "Return -self"
        return self.__class__([-co for co in self.coeffs])

    def __pow__(self, y, z=None):
        raise NotImplemented()

    def _radd__(self, val):
        "Return val+self"
        return self+val

    def __repr__(self):
        return "{0}({1})".format(self.__class__.__name__, self.coeffs)

    def __rmul__(self, val):
        "Return val*self"
        return self*val

    def __rsub__(self, val):
        "Return val-self"
        return -self + val

    def __str__(self):
        "Return string formatted as aX^3 + bX^2 + c^X + d"
        res = []
        for po,co in enumerate(self.coeffs):
            if co:
                if po==0:
                    po = ''
                elif po==1:
                    po = 'X'
                else:
                    po = 'X^'+str(po)
                res.append(str(co)+po)
        if res:
            res.reverse()
            return ' + '.join(res)
        else:
            return "0"

    def __sub__(self, val):
        "Return self-val"
        return self.__add__(-val)

    def trim(self):
        "Remove trailing 0-coefficients"
        _co = self.coeffs
        if _co:
            offs = len(_co)-1
            if _co[offs]==0:
                offs -= 1
                while offs >= 0 and _co[offs]==0:
                    offs -= 1
                del _co[offs+1:]