Skip to content

Problem 1.2: Polynomial and Integer (100pts)

Problem

Implement the Polynomial class and its subclass Integer inheriting the Semiring base class.

实现继承了 Semiring 基类的 Polynomial 类及其子类 Integer。

Polynomial

The Polynomial class represents univariate polynomials of integer coefficients, that is, polynomials in one variable (e.g., \( x \)). We use a list of coefficients to represent a polynomial, where the \( i \)-th element of the list is the coefficient for \( x^i \). For example, the list [2, 0, -1, 3] represents the polynomial $$ (2) + (0 \cdot x) + ((-1) \cdot x^2) + (3 \cdot x^3) = 3x^3 - x^2 + 2 $$ Specifically, [0] represents the zero polynomial, and [5] represents the constant polynomial \(5\).

The definition of addition and multiplication for polynomials is as follows:

  • Addition: The sum of two polynomials is obtained by adding their corresponding coefficients. That is, if \( P(x) \) and \( Q(x) \) are two polynomials, then their sum \( R(x) = P(x) + Q(x) \) is defined by adding the coefficients of the same degree.

For example, if \( P(x) = 5x^5 - 2x^2 + 12 \) and \( Q(x) = 3x^4 + x^2 + 7 \), then their sum is $$ R(x) = 5x^5 + 3x^4 + (-2 + 1)x^2 + (12 + 7) = 5x^5 + 3x^4 - x^2 + 19 $$

Accordingly, the zero element (additive identity) is the zero polynomial, and the additive inverse (negation) of a polynomial is obtained by negating each of its coefficients. * Multiplication: The product of two polynomials is obtained by multiplying each term of the first polynomial with each term of the second polynomial and combining like terms. That is, if \( P(x) \) and \( Q(x) \) are two polynomials, then their product \( R(x) = P(x) \times Q(x) \) is defined by $$ R(x) = \sum_{i=0}^{m} \sum_{j=0}^{n} P_i \cdot Q_j \cdot x^{i+j} $$ where \( P_i \) and \( Q_j \) are the coefficients of \( x^i \) and \( x^j \) in \( P(x) \) and \( Q(x) \), respectively, and \( m \) and \( n \) are the degrees of \( P(x) \) and \( Q(x) \).

For example, if \( P(x) = x + 1 \) and \( Q(x) = x^2 + x + 1 \), then their product is $$ R(x) = (x + 1)(x^2 + x + 1) = x^3 + 2x^2 + 2x + 1 $$

Accordingly, the one element (multiplicative identity) is the constant polynomial \(1\).

Here is the skeleton of the Polynomial class you need to implement:

Polynomial 类表示具有整数系数的单变量多项式，即一个变量（例如 \( x \)）的多项式。 我们使用系数列表来表示多项式，其中列表的第 \( i \) 个元素是 \( x^i \) 的系数。 例如，列表 [2, 0, -1, 3] 表示多项式 $$ (2) + (0 \cdot x) + ((-1) \cdot x^2) + (3 \cdot x^3) = 3x^3 - x^2 + 2 $$ 具体来说，[0] 表示零多项式，[5] 表示常数多项式 \(5\)。

多项式的加法和乘法的定义如下：

  • 加法：两个多项式的和是通过将它们对应的系数相加得到的。 也就是说，如果 \( P(x) \) 和 \( Q(x) \) 是两个多项式，那么它们的和 \( R(x) = P(x) + Q(x) \) 定义为将相同次数的系数相加。

例如，如果 \( P(x) = 5x^5 - 2x^2 + 12 \) 和 \( Q(x) = 3x^4 + x^2 + 7 \)，那么它们的和是 $$ R(x) = 5x^5 + 3x^4 + (-2 + 1)x^2 + (12 + 7) = 5x^5 + 3x^4 - x^2 + 19 $$

因此，零元（加法单位元）是零多项式，一个多项式的加法逆元（负元）是通过将其每个系数取负得到的。 * 乘法：两个多项式的乘积是通过将第一个多项式的每一项与第二个多项式的每一项相乘并合并同类项得到的。 也就是说，如果 \( P(x) \) 和 \( Q(x) \) 是两个多项式，那么它们的乘积 \( R(x) = P(x) \times Q(x) \) 定义为 $$ R(x) = \sum_{i=0}^{m} \sum_{j=0}^{n} P_i \cdot Q_j \cdot x^{i+j} $$ 其中 \( P_i \) 和 \( Q_j \) 分别是 \( P(x) \) 和 \( Q(x) \) 中 \( x^i \) 和 \( x^j \) 的系数，\( m \) 和 \( n \) 是 \( P(x) \) 和 \( Q(x) \) 的次数。

例如，如果 \( P(x) = x + 1 \) 和 \( Q(x) = x^2 + x + 1 \)，那么它们的乘积是 $$ R(x) = (x + 1)(x^2 + x + 1) = x^3 + 2x^2 + 2x + 1 $$

因此，幺元（乘法单位元）是常数多项式 \(1\)。

下面是您需要实现的 Polynomial 类的骨架：

class Polynomial(Semiring):
    """A class representing polynomials."""

    def __init__(self, coefficients):
        """Initializes a Polynomial with the given list of coefficients.
        The coefficient at index i corresponds to the term with degree i.
        >>> p = Polynomial([1, 2, 3])  # Represents 3x^2 + 2x + 1
        >>> p.coefficients
        [1, 2, 3]
        """
        self.coefficients = coefficients

    def add(self, other):
        """Returns a new Polynomial representing the sum of self and other.
        >>> p1 = Polynomial([1, 2])      # 2x + 1
        >>> p2 = Polynomial([3, 4, 5])   # 5x^2 + 4x + 3
        >>> p1.add(p2)
        5x^2 + 6x + 4
        """
        """YOUR CODE HERE"""

    def mult(self, other):
        """Returns a new Polynomial representing the product of self and other.
        >>> p1 = Polynomial([1, 2])      # 2x + 1
        >>> p2 = Polynomial([3, 4])      # 4x + 3
        >>> p1.mult(p2)
        8x^2 + 10x + 3
        """
        """YOUR CODE HERE"""

    def negative(self):
        """Returns a new Polynomial representing the additive inverse of self.
        >>> p = Polynomial([1, -2, 3])  # 3x^2 - 2x + 1
        >>> p.negative()
        -3x^2 + 2x - 1
        """
        """YOUR CODE HERE"""

    def zero(self):
        """Returns the zero polynomial."""
        """YOUR CODE HERE"""

    def one(self):
        """Returns the identity polynomial."""
        """YOUR CODE HERE"""

    def __repr__(self):
        """Returns the string representation of the polynomial.
        You are not supposed to understand this code now.
        >>> p = Polynomial([1, 0, 3])  # Represents 1 + 0x + 3x^2
        >>> repr(p)
        '3x^2 + 1'
        """
        terms = []
        for power, coeff in enumerate(self.coefficients):
            if coeff != 0:
                if power == 0:
                    terms.append(f'{coeff}')
                    continue
                elif power == 1:
                    base = 'x'
                else:
                    base = f'x^{power}'

                if coeff == 1:
                    terms.append(base)
                else:
                    terms.append(f'{coeff}{base}')
        return " + ".join(reversed(terms)).replace(" + -", " - ") if terms else "0"

Integer

The Integer class is a special case of Polynomial representing a single integer (a zero-degree polynomial).

Here is the skeleton of the Integer class you need to implement:

Integer 类是 Polynomial 的一个特殊情况，表示一个单个整数（一个零次多项式）。

下面是您需要实现的 Integer 类的骨架：

class Integer(Polynomial):
    """A class representing a single integer as a polynomial."""

    def __init__(self, value):
        """Initializes a Integer with the given value.
        >>> Integer(5)
        5
        """
        """YOUR CODE HERE"""

    def zero(self):
        """Returns the additive identity integer (0)."""
        return Integer(0)

    def one(self):
        """Returns the multiplicative identity integer (1)."""
        return Integer(1)

Hints

Hint:

You may need to call the initializer of its superclass to set up the coefficients properly. Use super().__init__() to call the parent class constructor.

  • 您可能需要调用其超类的初始化方法来正确设置系数。

  • 使用 super().__init__() 来调用父类的构造函数。