我该如何创建处理多项式的函数？

Question

我有一些关于多项式的问题，花了大约四个小时，但我就是搞不定。我是Python和编程的新手，我已经试着在纸上解决它，但我还是不知道。

1. 编写并测试一个Python函数negate(p)，用于否定由其系数列表p表示的多项式，并返回一个新的多项式（表示为列表）。换句话说，编写一个使一列数字变为负数的函数。

2. 编写一个Python函数eval_polynomial(p, x)，返回由其系数列表p表示的多项式P的值P(x)。例如，eval_polynomial([1, 0, 3], 2)应该返回1*2^2 + 0*2 + 3 = 7。使用一个while循环。

3. 编写并测试一个函数multiply_by_one_term(p, a, k)，将给定的多项式p（表示为系数列表）乘以ax^k，并将乘积作为新列表返回。

如果有人能帮助我，我会非常感激。

- confusedstudent

---

打开Python shell并尝试这些例子：http://docs.python.org/2/tutorial/datastructures.html#list-comprehensions - Anycorn

情况2：在Python中，返回的值最好表示为“1 * 2 ** 2 + 0 * 2 ** 1 + 3 * 2 ** 0”。 - Antti Haapala -- Слава Україні

继@Anycorn的评论之后，使用ipython或ipython笔记本。 - Shashank Agarwal

Answer 1

我建议使用numpy.poly1d和numpy.polymul，其中系数为a0*x2 + a1*x + a2。

例如，要表示3*x**2 + 2*x + 1:

p1 = numpy.poly1d([3,2,1])

通过生成的 poly1d 对象，您可以使用 *、/ 等运算符进行操作：

print(p1*p1)
#   4      3      2
#9 x + 12 x + 10 x + 4 x + 1

假设 p 按顺序包含系数: a0 + a1*x + a2*x**2 + ...，如果您想构建自己的函数：

def eval_polynomial(p,x):
    return sum((a*x**i for i,a in enumerate(p)))

def multiply_by_one_term(p, a, k):
    return [0]*k + [a*i for i in p]

注意

我的评估函数使用指数运算，可以采用Horner法则避免，如另一个回答中所述，该方法在Numpy的polyval函数中提供。

- Saullo G. P. Castro

---

我还没有足够的声望，但我会给你点赞。我实际上理解了你解决方案背后的逻辑。 - confusedstudent

@confusedstudent 很棒，你理解了这个逻辑。 - Saullo G. P. Castro

这个解决方案在方法上很清晰，但明显效率低下。请考虑使用霍纳规则来避免在每次迭代中调用指数函数。我想我应该把它发布为一个答案。 - fearless_fool

Answer 2

请使用霍纳法！

对于多项式，您应该考虑使用霍纳法。其主要特点是计算N阶多项式只需要N次乘法和N次加法，不需要指数运算：

def eval_polynomial(P, x):
    '''
    Compute polynomial P(x) where P is a vector of coefficients, highest
    order coefficient at P[0].  Uses Horner's Method.
    '''
    result = 0
    for coeff in P:
        result = x * result + coeff
    return result

>>> eval_poly([1, 0, 3], 2)
7

您可以手动完成，也可以按链接查看其工作原理。

- fearless_fool

---

很好的解决方案来评估多项式，不过可以使用Numpy的polyval。 - Saullo G. P. Castro

NumPy很棒，但是OP要编写一个函数。而且有很多情况下，您可能希望在不引入所有NumPy的情况下评估多项式。 - fearless_fool