10

我想知道如何将多项式解析为函数并返回导数。我将使用什么数据结构或方法来解析多项式？最好不使用任何库，因为这个问题可能会在技术面试中弹出。

polynomial-> of nth degree

def derivative(polynomial):
    return derivative

Example:

f(x)  = 2x^2+3x+1
f'(x) = 4x+3

我不想要一个解决方案，这不是家庭作业，而是我将从哪里开始的提示。

4

8 回答 8

17

单个变量中的多项式可以简单地表示为包含系数的数组。因此，例如 1 + 5x 3 - 29x 5可以表示为[1, 0, 0, 5, 0, -29]。以这种形式表示，导数很容易计算。

假设poly是上面的python列表。然后

deriv_poly = [poly[i] * i for i in range(1, len(poly))]

对于稀疏多项式，其他表示相对容易，例如对列表(coefficient, exponent)或将指数映射到系数的字典。

解析表达式比较复杂，但是使用各种解析框架应该很容易，因为语法比较简单。

于 2012-06-22T12:16:04.273 回答
5

我现在想出了这个。你想要的是这样的：

  1. 解析多项式：您需要有一个预定义的模式。输入越“不受信任”或“狂野”，您就必须更好地解析它。你可以使用正则表达式。

  2. 列出方程（coeff, power_of_x）的基本组成部分。

  3. 做数学（导数公式）

  4. 以输入的方式返回一个方程。

这给了你：

import re

def read(eq):
    terms = eq.split('+')
    equation = [re.split('x\^?', t) for t in terms]
    eq_map = []
    for e in equation:
        try:
            coeff = int(e[0])
        except ValueError:
            coeff = 1
        try:
            power = int(e[1])
        except ValueError:
            power = 1
        except IndexError:
            power = 0
        eq_map.append((coeff, power))
    return eq_map

def write(eq_map):
    def str_power(p):
        if p == 0:
            return ''
        elif p == 1:
            return 'x'
        else:
            return 'x^%d' % (p,)

    def str_coeff(c):
        return '' if c == 1 else str(c)
    str_terms = [(str_coeff(c) + str_power(p)) for c, p in eq_map]
    return "+".join(str_terms)

def derivative(eq):
    eq_map = read(eq)
    der_map = [(p*c, p-1) for c, p in eq_map[:-1]]
    return write(der_map)

def run(eq):
    print eq, '->', derivative(eq)

run("2x^2+3x+1")
run("x^3+2x^2+1")

这是非常基本的。例如：2*x^3不会因为“*”而工作。当然，在很多情况下它不起作用，但这是基本思想。

于 2012-06-22T12:08:39.143 回答
5

根据我的经验，矩阵在表示多项式时通常非常有用

于 2012-06-22T11:35:26.510 回答
3

好吧，我相信起点是定义表达式的基本组成部分。

当您查看一个函数并想要这样处理它时，它基本上是一种语法，它可能会有点复杂，具体取决于您想要允许多少细节。

你的语法有 EXPRESSION 的形式。

EXPRESSION 可以是：TERM（您的函数基本上类似于 nx^y）或 TERM OPERATOR EXPRESSION

如果您可以解析这样的函数，您只需要定义处理 TERM 的规则，然后递归地对表达式的其余部分应用相同的方法。

您的多项式将始终具有 nx^y 的形式，对于 y 为 0 或 1 或 n 为 1 且被省略的情况进行了一些简化。

这就是我在不使用任何额外库的情况下处理它的方式。如果您愿意，我可以尝试进一步解释我的观点。

顺便说一句，我知道我的回答并没有完全解决 Python 或要使用的数据结构，但它是解决此类问题的一种可能方法。

于 2012-06-22T11:40:39.377 回答
2

我的解决方案使用迭代，其中第 i 个元素是 x^i 的系数，因此对于p(x) = 3*x^5 + 2*x^3 + x^2 + 5，输入将是[5, 0, 1, 2, 0, 3]. 导数是p'(x) = 15*x^4 + 6*x^2 + 2*x，所以预期的结果应该是[0, 2, 6, 0, 15]。

>>> import itertools, operator
>>> coeff = [5, 0, 1, 2, 0, 3]
>>> print list(itertools.imap(operator.mul, itertools.islice(coeff, 1, None), itertools.count(1)))
[0, 2, 6, 0, 15]

更新：我想在这里使用迭代器和所有东西非常棘手，但我的解决方案结果是 GregS 的两倍多。有人可以解释一下这种缓慢是从哪里来的吗？

>>> print timeit.repeat("poly(coeff)", "poly = lambda coeff: [coeff[i] * i for i in range(1, len(coeff))]; coeff = [1, 0, 0, 5, 0, -29]")
[1.7786244418210748, 1.7956598059847046, 1.7500179643792024]
>>> print timeit.repeat("poly(coeff)", "import operator, itertools; poly = lambda coeff: list(itertools.imap(operator.mul, itertools.islice(coeff, 1, None), itertools.count(1))); coeff = [1, 0, 0, 5, 0, -29]")
[4.01759841913463, 4.152715700867423, 5.195021813889031]
于 2012-06-22T12:29:21.970 回答
1

不是一个漂亮或具体的解决方案，但您可以改进它:) 使用字典来存储系数及其幂，以幂为键。

import re
def polynomial(data):
    coeffs = {}
    splits = map(str.strip, re.split(r"([+ \-])",data))
    sign = 1
    for p in splits:
        if p in "+-":
            sign = 1 if p == '+' else -1
            continue
        s = re.split('[^0-9]+', p)
        coeff = int(s[0])
        if len(s) == 1:
            pow = 0
        elif s[1] == '':
            pow = 1
        else:
            pow = int(s[1])
        coeffs[pow] = sign * coeff
    return coeffs

def derive(poly):
    return dict([(p-1, p*c) for p,c in poly.items() if p != 0])

def print_poly(poly, var = 'x'):
    print(''.join(['{0}{1}{2}^{3}'.format('+-'[c<0],c,var,p) for p,c in sorted(poly.items(), reverse = True)]))
于 2012-06-22T12:07:13.400 回答
1

如果多项式方程以列表形式给出。例如：p=[9,4,12,2] 返回值将是 [27, 8, 12]

     def derivative(p):
        derv=[]
        for i in range(len(p)-1):
            derv.append((len(p)-i-1)*p[i])
        return derv
于 2017-12-20T06:29:12.563 回答
0

第 7 行和第 8 行将提取列表中的系数和指数，而不考虑符号。第 13 和 14 行从列表中删除空字符串。这并不完美，但更简单：

import pdb;                                                                                                                                                                                                                                                                 
import re;                                                                      


poly = input("Input the polynomial you want to find its derivative : ")         

coefficients = re.split("x\^[+-]?[0-9]+",poly)                                  
exponents = re.split("[+-]?[0-9]+x\^",poly)                                     

print(coefficients)                                                            
print(exponents)                                                               

coefficients = [ i for i in coefficients if i !='']                             
exponents = [i for i in exponents if i !='']                                    

print(coefficients)                                                            
print(exponents)                                                               

derivative=""                                                                   
for i in range(len(coefficients)):                                              
    print(coefficients[i])                                                      
    print(exponents[i])                                                         
    coefficient = int(coefficients[i])*int(exponents[i])                        
    exponent = int(exponents[i]) - 1                                            
    if exponent == 0:                                                           
        derivative +=  str(coefficient)                                         
    else:                                                                       
        derivative +=  str(coefficient) + "x^" + str(exponent)                  

print("The original value is {0}".format(poly))                                 
print("The derivative is {0}".format(derivative))
于 2016-01-23T08:29:42.270 回答