Mi problema anterior (que ahora está resuelto) fue:

Como entrada, tengo una lista de números enteros no negativos que se supone que son los coeficientes de un polinomio. Pero también quiero evaluar el polinomio para un cierto número x.

Por ejemplo:
Si tenemos L=[2,3,1] como entrada y x=42 obtenemos 2x^2+3x+1=3655 Lo que quiero es, por ejemplo:

>>>p=polynomial([2,3,1])
>>>p(O)
1 
>>>p(42)
>>>3655

El código es

def polynomial(coef):
 def poly(x):
    result = 0
    x_n = 1  
    for a in reversed(coef):
        result += a * x_n
        x_n *= x 
    return result
 return poly

Lo que quería hacer ahora es encontrar el inverso, eso significa que la entrada es un polinomio monótono y el número entero positivo y y quiero encontrar un número entero x tal que p (x) = y, y x debería ser solo en [1,10 ** 10], por ejemplo:

>>>p=polynomial([2,3,1])
>>>p(O)
1 
>>>p(42)
>>>3655
>>>invert(3655,p)
42

Esto es lo que tengo hasta ahora, pero lo que obtengo es un error de tiempo de ejecución:

def polynomial(coef):
 def poly(x):
    result = 0
    xn = 1  
    for c in reversed(coef):
        result += c * xn
        xn *= x 
    return result
 return poly


def invert(y,p):

test=10**10

if p(2)>p(1):
    if p(test)>y:
        test=test//2 +(test%2)
        return invert(y,p)
    elif p(test)<y:
        test=test+(test//2)
        return invert(y,p)
    else:
        return test

if p(2)<p(1):
    if p(test)<y:
        test=test//2 +(test%2)
        return invert(y,p)
    elif p(test)>y:
        test=test+(test//2)
        return invert(y,p)
    else:
        return test

El error que ocurre es

  ...
  File "poly.py", line 17, in invert
   return invert(y,p)
  File "poly.py", line 14, in invert
  if p(2)>p(1):
   File "poly.py", line 5, in poly
   for c in reversed(coef):
   RuntimeError: maximum recursion depth exceeded while calling a    Python object

¿Qué estoy haciendo mal?

0
Tesla 12 ene. 2017 a las 11:40

3 respuestas

La mejor respuesta

Escribí el código ahora mismo, limitando todo al conocimiento / habilidad que solo tengo hasta ahora, y funciona:

def polynomial(coef):
 def poly(x):
    result = 0
    x_n = 1  
    for a in reversed(coef):
        result += a * x_n
        x_n *= x 
    return result
 return poly

def invert(y,p):

 x=10**10

 while p(x)!=y:
    if p(x)>y:
        w=x
        x=x//2
    elif p(x)<y:
        x=(x+w)//2
    return x
0
Tesla 12 ene. 2017 a las 18:34

Su función invert se repite para siempre porque nunca modifica los argumentos que pasa a la próxima llamada. Modificas test, pero eso no te sirve de nada, ya que la llamada interna tendrá su propia copia de test.

Hay algunas formas de solucionar el problema. Puede pasar test como argumento para la función invert, con su valor inicial como valor predeterminado que se usará la primera vez:

def invert(y, p, test=10**10):
    # ...

    # later, when you recurse:
    test = test // 2      # or whatever
    return invert(y, p, test)    # pass on the modified test value

Otro enfoque (probablemente mejor) sería abandonar la recursividad y utilizar un bucle en su lugar. Un bucle while parece que sería apropiado aquí:

def invert(y, p):
    test = 10**10

    sign = (-1)**(p(2) < p(1))

    while True:
        if p(test) > y:
            test -= sign * (test // 2)
        elif p(test) < y:
            test += sign * (test // 2)
        else:
            return test    # this is the only case that returns

Dejé el algoritmo general igual que lo que hace su código original (solo simplificado un poco). Es posible que ese algoritmo no sea correcto si su polinomio no está aumentando o disminuyendo estrictamente. Realmente deberías calcular la derivada del polinomio en test para determinar en qué dirección ajustar, pero te lo dejaré a ti para que lo descubras.

3
Blckknght 12 ene. 2017 a las 20:56

Me tomé la libertad de corregir la sangría del código que publicaste. Verifique que el siguiente código sea realmente el que tiene, con respecto a las sangrías El siguiente código devuelve el resultado deseado.

def polynomial(coef):
    def poly(x):
        result = 0
        x_n = 1  
        for a in reversed(coef):
            result += a * x_n
            x_n *= x 
        return result
     return poly

def invert(y,p,test): # updated

    # test=10**10 # This was the problem

    # You reset 'test' for every recursive call
    # which means you will stand still without
    # any progress until the max num of allowed
    # recursive calls are reached.

    if p(2)>p(1):
        if p(test)>y:
            test=test//2 +(test%2)
            return invert(y,p,test) # updated
        elif p(test)<y:
            test=test+(test//2)
            return invert(y,p,test) # updated
        else:
            return test

    if p(2)<p(1):
        if p(test)<y:
            test=test//2 +(test%2)
            return invert(y,p,test) # updated
        elif p(test)>y:
            test=test+(test//2)
            return invert(y,p,test) # updated
        else:
            return test

p = polynomial([2,3,1])
t = 10**10
print(invert(3655,p,t))
1
magnus 12 ene. 2017 a las 09:29