¿Cómo encontrar el número de la serie Fibonacci más cercano?

Mi siguiente paso es que si la entrada no está en la Serie Fibonacci, el progtwig tiene que dar una salida con un número que esté en la serie más cercana a la entrada. No sé cómo proceder, ¿alguien me puede ayudar?

def fibs(): a,b = 0,1 yield a yield b while True: a,b = b,a+b yield b n = int(input("please, enter a number: ")) for fib in fibs(): if n == fib: print("Yes! Your number is a Fibonacci number!") break if fib > n: print("No! Your number is not a Fibonacci number!") break 

Por qué este método funciona bien:

Esta es una forma que no requiere cálculos previos, por lo que es fantástica para el rendimiento y, por lo tanto, al verificar números muy grandes.


El progtwig:

 from math import * n = int(input("Enter a number:")) if sqrt(5*n**2+4)%1==0 or sqrt(5*n**2-4)%1==0: print("Your number is a Fibonacci number!") else: print("Your number is not a Fibonacci number.") c = 0 while 1: c += 1 if sqrt(5*(n+c)**2+4)%1==0 or sqrt(5*(n+c)**2-4)%1==0: print("%s is the closest Fibonacci number to your entry." % str(n+c)) break if sqrt(5*(nc)**2+4)%1==0 or sqrt(5*(nc)**2-4)%1==0: print("%s is the closest Fibonacci number to your entry." % str(nc)) break 

La explicación:

Si (5 * n ^ 2 + 4) o (5 * n ^ 2 – 4) es un cuadrado perfecto, entonces n es un número de Fibonacci.


Progtwig de entrada / salida

 Enter a number: 9999999999 Your number is not a Fibonacci number. 9999816735 is the closest Fibonacci number to your entry. Enter a number: 9999816735 Your number is a Fibonacci number! 

Esta es una forma sencilla de usar su generador que está bien para probar números pequeños.

 def fibs(): a,b = 0,1 yield a yield b while True: a,b = b,a+b yield b def nearest_fib(n): ''' If n is a Fibonacci number return True and n Otherwise, return False and the nearest Fibonacci number ''' for fib in fibs(): if fib == n: return True, n elif fib < n: prev = fib else: # Is n closest to prev or to fib? if n - prev < fib - n: return False, prev else: return False, fib # Test for i in range(35): print(i, nearest_fib(i)) 

salida

 0 (True, 0) 1 (True, 1) 2 (True, 2) 3 (True, 3) 4 (False, 5) 5 (True, 5) 6 (False, 5) 7 (False, 8) 8 (True, 8) 9 (False, 8) 10 (False, 8) 11 (False, 13) 12 (False, 13) 13 (True, 13) 14 (False, 13) 15 (False, 13) 16 (False, 13) 17 (False, 21) 18 (False, 21) 19 (False, 21) 20 (False, 21) 21 (True, 21) 22 (False, 21) 23 (False, 21) 24 (False, 21) 25 (False, 21) 26 (False, 21) 27 (False, 21) 28 (False, 34) 29 (False, 34) 30 (False, 34) 31 (False, 34) 32 (False, 34) 33 (False, 34) 34 (True, 34) 

Actualizar

Aquí hay un método más eficiente que utiliza la fórmula de Binet para aproximar primero y: F (y) = n. Luego utiliza un par de identidades relacionadas con la forma de la matriz (que puede calcular F (n) en tiempo O (log (n)) para encontrar recursivamente los números de Fibonacci más cercanos a n. La recursión es bastante rápida porque utiliza un caché para mantener los valores que ya se han calculado. Sin el caché, este algoritmo es aproximadamente la misma velocidad que la de Rockybilly.

 from math import log, sqrt def fast_fib(n, cache={0: 0, 1: 1}): if n in cache: return cache[n] m = (n + 1) // 2 a, b = fast_fib(m - 1), fast_fib(m) fib = a * a + b * b if n & 1 else (2 * a + b) * b cache[n] = fib return fib logroot5 = log(5) / 2 logphi = log((1 + 5 ** 0.5) / 2) def nearest_fib(n): if n == 0: return 0 # Approximate by inverting the large term of Binet's formula y = int((log(n) + logroot5) / logphi) lo = fast_fib(y) hi = fast_fib(y + 1) return lo if n - lo < hi - n else hi for i in range(35): print(i, nearest_fib(i)) 

salida

 0 0 1 1 2 2 3 3 4 5 5 5 6 5 7 8 8 8 9 8 10 8 11 13 12 13 13 13 14 13 15 13 16 13 17 21 18 21 19 21 20 21 21 21 22 21 23 21 24 21 25 21 26 21 27 21 28 34 29 34 30 34 31 34 32 34 33 34 34 34 

Tenga en cuenta que fast_fib usa un argumento mutable predeterminado para el caché, pero está bien aquí porque queremos que el caché recuerde su contenido anterior.

En mis pruebas de velocidad, un caché de argumentos mutable predeterminado es más rápido que cualquier otra forma de caché, pero tiene el inconveniente de que es imposible borrar el caché desde fuera de la función, y si agrega lógica a la función para el borrado de caché, esto afecta el rendimiento. para la mayoría de las llamadas cuando no desea borrar el caché.

Actualizar

En realidad, es posible borrar un caché de argumentos mutable predeterminado fuera de la función. Podemos acceder a los argumentos predeterminados de una función a través de su atributo .__default__ (o .func_defaults en versiones anteriores de Python 2; .__default__ funciona en Python 2.6, pero no en 2.5).

P.ej,

 d = fast_fib.__defaults__[0] d.clear() d.update({0: 0, 1: 1}) 

Aquí hay un código (que se ejecuta en Python 2 y Python 3) que realiza pruebas de tiempo en algunos de los algoritmos enviados para esta pregunta. Rockybilly es muy similar a mi primera versión, excepto que evita tener que guardar el valor anterior. También he hecho el generador de fibs del OP un poco más compacto.

El código de Douglas está bien para números pequeños, o cuando el argumento es, de hecho, un número de Fibonacci, pero se vuelve muy lento para números grandes que no son de Fibonacci debido a la lenta búsqueda de uno por uno. He podido optimizarlo un poco al evitar el recálculo de varias cantidades, pero eso no hace una gran diferencia en la velocidad de carrera.

En esta versión, mi función fast_fib() usa un caché global para que se pueda borrar entre pruebas para hacer que los tiempos sean más justos.

 #!/usr/bin/env python3 """ Find the nearest Fibonacci number to a given integer Test speeds of various algorithms See https://stackoverflow.com/questions/40682947/fibonacci-in-python Written by PM 2Ring 2016.11.19 Incorporating code by Rockybilly and Douglas """ from __future__ import print_function, division from math import log, sqrt from time import time def fibs(): a, b = 0, 1 while True: yield a a, b = b, a + b def nearest_fib_Rocky(n): ''' Find the nearest Fibonacci number to n ''' fibgen = fibs() for fib in fibgen: if fib == n: return n elif fib > n: next_fib = next(fibgen) return next_fib - fib if 2 * n < next_fib else fib def nearest_fib_Doug(n): a = 5 * n * n if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0: return n c = 1 while True: m = n + c a = 5 * m * m if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0: return m m = n - c a = 5 * m * m if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0: return m c += 1 cache={0: 0, 1: 1} def fast_fib(n): if n in cache: return cache[n] m = (n + 1) // 2 a, b = fast_fib(m - 1), fast_fib(m) fib = a * a + b * b if n & 1 else (2 * a + b) * b cache[n] = fib return fib logroot5 = log(5) / 2 logphi = log((1 + 5 ** 0.5) / 2) def nearest_fib_PM2R(n): if n == 0: return 0 # Approximate by inverting the large term of Binet's formula y = int((log(n) + logroot5) / logphi) lo = fast_fib(y) hi = fast_fib(y + 1) return lo if n - lo < hi - n else hi funcs = ( nearest_fib_PM2R, nearest_fib_Rocky, nearest_fib_Doug, ) # Verify that all the functions return the same result def verify(lo, hi): for n in range(lo, hi): a = [f(n) for f in funcs] head, tail = a[0], a[1:] if not all(head == u for u in tail): print('Error:', n, a) return False else: print('Ok') return True def time_test(lo, hi): print('lo =', lo, 'hi =', hi) for f in funcs: start = time() for n in range(lo, hi): f(n) t = time() - start print('{0:18}: {1}'.format(f.__name__, t)) print() verify(0, 1000) cache={0: 0, 1: 1} time_test(0, 1000) funcs = funcs[:-1] cache={0: 0, 1: 1} time_test(1000, 50000) 

salida típica

 Ok lo = 0 hi = 1000 nearest_fib_PM2R : 0.005465507507324219 nearest_fib_Rocky : 0.02432560920715332 nearest_fib_Doug : 0.45461463928222656 lo = 1000 hi = 50000 nearest_fib_PM2R : 0.26880311965942383 nearest_fib_Rocky : 1.266334056854248 

Estos tiempos se encuentran en una vieja máquina de 2 GHz de 32 bits que ejecuta Python 3.6 en Linux. Python 2.6 da tiempos similares.

FWIW, tanto el código de Rockybilly como el mío pueden manejar números muy grandes. Aquí está la salida de tiempo de time_test(10**1000, 10**1000 + 1000) :

 nearest_fib_PM2R : 0.011492252349853516 nearest_fib_Rocky : 7.556792497634888 

No es necesario mantener el fibonacci anterior si no le importa hacer una llamada de generador adicional.

Primero almacena el generador dentro de una variable.

 gen = fibs() n = int(input("please, enter a number: ")) for fib in gen: if n == fib: print("Yes! Your number is a Fibonacci number!") break if fib > n: print("No! Your number is not a Fibonacci number!") next_fib = next(gen) prev = next_fib - fib closest = prev if n - prev < fib - n else fib # Search for Python ternary operator # If you are a stranger to this line of code. print("The closest fibonacci number to your entry is %s" % closest) break 

Edición: Primero usé gen.next() para obtener el siguiente valor del rendimiento, sin embargo, olvidé que en Python 3, se le cambia el nombre como uso a gen.__next__() . Por favor, tenga cuidado de usarlo. next(gen) es el uso esperado para ambas versiones de Python.

Usted podría comprimir las fibs con sí mismo:

 n = int(input("please, enter a number: ")) for fib, next_fib in itertools.izip(fibs(), itertools.islice(fibs(), 1, None)): if n == fib: print("Yes! Your number is a Fibonacci number!") break if next_fib > n: closest = fib if n - fib < next_fib - n else next_fib print("The closest Fibonacci number is {}".format(closest)) break 

Podrías usar itertools.tee para optimizarlo un poco.