Problem 1.3: General Semiring Operations (100pts)

Problem

In this problem, you will implement abstract functions that can operate on any subclass of the Semiring base class. Instead of repeating similar code for each subclass, you will leverage the power of abstraction in object-oriented programming (OOP) to write generic methods that work for all semiring objects.

First, ensure you have completed the implementations of the Matrix, Polynomial, and Integer classes from Problems 1.1 and 1.2. Then, implement the following methods in the Semiring base class:

• The method ntimes(self, n) in the Semiring class

  def ntimes(self, n):
  """Returns self added to itself n times.
  >>> base = Integer(3)
  >>> base.ntimes(4)
  12
  >>> p = Polynomial([1, 1])  # Represents x + 1
  >>> p.ntimes(3)
  3x + 3
  """
  assert n >= 0, "n must be a non-negative integer."
  """YOUR CODE HERE"""
  

• The method power(self, n) in the Semiring class

  def power(self, n):
    """Returns self raised to the power of n using repeated multiplication.
    >>> base = Integer(2)
    >>> base.power(3)
    8
    >>> p = Polynomial([1, 1])  # Represents x + 1
    >>> p.power(3)
    x^3 + 3x^2 + 3x + 1
    """
    assert n >= 0, "Exponent must be a positive integer."
    """YOUR CODE HERE"""
  

Based on the above methods, further, you need to implement the subst_poly(self, x) method that replaces the variable in a polynomial with another semiring object x.

在本问题中，您将实现可以对 Semiring 基类的任何子类进行操作的抽象函数。 您将利用面向对象编程 (OOP) 中抽象的力量来编写适用于所有半环对象的通用方法，而不是为每个子类重复相似的代码。

首先，请确保您已完成问题 1.1 和 1.2 中 Matrix、Polynomial 和 Integer 类的实现。然后，在 Semiring 基类中实现以下方法：

• Semiring 类中的 ntimes(self, n) 方法

  def ntimes(self, n):
  """返回 self 自身相加 n 次的结果。
  >>> base = Integer(3)
  >>> base.ntimes(4)
  12
  >>> p = Polynomial([1, 1])  # 表示 x + 1
  >>> p.ntimes(3)
  3x + 3
  """
  assert n >= 0, "n 必须是非负整数。"
  """YOUR CODE HERE"""
  

• Semiring 类中的 power(self, n) 方法

  def power(self, n):
    """使用重复乘法返回 self 的 n 次幂。
    >>> base = Integer(2)
    >>> base.power(3)
    8
    >>> p = Polynomial([1, 1])  # 表示 x + 1
    >>> p.power(3)
    x^3 + 3x^2 + 3x + 1
    """
    assert n >= 0, "指数必须是非负整数。"
    """YOUR CODE HERE"""
  

基于上述方法，您还需要实现 subst_poly(self, x) 方法，该方法将多项式中的变量替换为另一个半环对象 x。

def subst_poly(poly, x):
    """Substitutes the Semiring x into the polynomial poly and returns the result.
    For matrices, constant terms are multiplied by the identity matrix.
    >>> poly = Polynomial([1, -2, 3])  # Represents 3x^2 - 2x + 1
    >>> n = Integer(3)
    >>> p = Polynomial([0, 0, 1])  # x^2
    >>> m = Matrix([[1, 2, 3], [2, 1, 1], [2, 3, 3]])
    >>> subst_poly(poly, n)
    22
    >>> subst_poly(poly, m)
    [[32, 35, 36],
     [14, 23, 28],
     [38, 42, 49]]
    >>> subst_poly(poly, p)
    3x^4 - 2x^2 + 1
    """
    """YOUR CODE HERE"""

Hints

Hint:

When handling the coefficients in the polynomial, remember that they can be negative.

• 在处理多项式中的系数时，请记住它们可以是负数。