设计一个基于列表的两个一元多项式的基本运算

可以使用 Python 编写一个基于列表的一元多项式类，然后在类中实现基本运算。

class Polynomial:
    def __init__(self, coeffs):
        self.coeffs = coeffs
        
    def __add__(self, other):
        result = []
        i, j = 0, 0
        while i < len(self.coeffs) and j < len(other.coeffs):
            if self.coeffs[i][1] == other.coeffs[j][1]:
                result.append((self.coeffs[i][0] + other.coeffs[j][0], self.coeffs[i][1]))
                i += 1
                j += 1
            elif self.coeffs[i][1] < other.coeffs[j][1]:
                result.append(self.coeffs[i])
                i += 1
            else:
                result.append(other.coeffs[j])
                j += 1
        while i < len(self.coeffs):
            result.append(self.coeffs[i])
            i += 1
        while j < len(other.coeffs):
            result.append(other.coeffs[j])
            j += 1
        return Polynomial(result)
    
    def __sub__(self, other):
        result = []
        i, j = 0, 0
        while i < len(self.coeffs) and j < len(other.coeffs):
            if self.coeffs[i][1] == other.coeffs[j][1]:
                result.append((self.coeffs[i][0] - other.coeffs[j][0], self.coeffs[i][1]))
                i += 1
                j += 1
            elif self.coeffs[i][1] < other.coeffs[j][1]:
                result.append(self.coeffs[i])
                i += 1
            else:
                result.append((-other.coeffs[j][0], other.coeffs[j][1]))
                j += 1
        while i < len(self.coeffs):
            result.append(self.coeffs[i])
            i += 1
        while j < len(other.coeffs):
            result.append((-other.coeffs[j][0], other.coeffs[j][1]))
            j += 1
        return Polynomial(result)
    
    def __mul__(self, other):
        result = []
        for i in range(len(self.coeffs)):
            for j in range(len(other.coeffs)):
                coeff = self.coeffs[i][0] * other.coeffs[j][0]
                power = self.coeffs[i][1] + other.coeffs[j][1]
                result.append((coeff, power))
        result.sort(key=lambda x: x[1])
        new_result = []
        for i in range(len(result)):
            if i < len(result) - 1 and result[i][1] == result[i+1][1]:
                new_result.append((result[i][0] + result[i+1][0], result[i][1]))
                i += 1
            else:
                new_result.append(result[i])
        return Polynomial(new_result)
    
    def __str__(self):
        result = []
        for coeff, power in self.coeffs:
            if power == 0:
                result.append(str(coeff))
            elif power == 1:
                result.append(f"{coeff}x")
            else:
                result.append(f"{coeff}x^{power}")
        return " + ".join(result)

上述代码实现了一元多项式的加法、减法、乘法和字符串表示。其中，多项式的系数和次数都以元组的形式存储在列表中。

例如，假设有以下两个一元多项式：

$A(x) = 2x^3 - 3x^2 + 5x + 1$

$B(x) = 4x^2 - 1$

则可以通过以下代码创建并进行基本运算：

A = Polynomial([(2, 3), (-3, 2), (5, 1), (1, 0)])
B = Polynomial([(4, 2), (-1, 0)])
print(A + B) # 输出：2x^3 + x^2 + 5x
print(A - B) # 输出：2x^3 - 7x^2 + 5x + 1
print(A * B) # 输出：8x^5 - 11x^4 + 17x^3 - 7x^2 + 4x