Entrevista de Fibonacci

El cálculo de la serie de Fibonacci es una tarea algorítmica clásica, porque a menudo se realiza en entrevistas cuando quieren verificar que el candidato, en principio, es al menos de alguna manera capaz en algoritmos. Supongamos que eres el mismo candidato. Se le asignó la tarea: en JavaScript, escriba una función fib(n) que devuelva el enésimo número de Fibonacci. Consideramos que el número cero de Fibonacci es cero. No se requiere validación del argumento. Que opciones tienes

1. Para ser más fácil, y la gente lo alcanzará.

La solución más simple es un ciclo banal.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

Un chiste Por supuesto, no necesita escribir así, a menos que, por supuesto, no sea entrevistado para el puesto de ofuscador a tiempo completo.

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

¿Te estás quedando sin cupones variables? cypok

Bien, bien, para una legibilidad aún mayor, escribamos esto:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

Esta es una opción clásica, simple y elegante. ¿Pero quizás quieres demostrar tu conocimiento de otros conceptos? Por ejemplo ...

2. Para entender la recursividad, debes entender la recursividad

Por ejemplo, sí, puede demostrar que puede hacer recursividad. Por ejemplo, así:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

Recuerda esta opción. Esto no vale la pena hacerlo. No debe ser Es imposible Nunca Esto es peor que patear cachorros, y es comparable a un pequeño holocausto.

Puedes preguntar por qué. En este caso, simplemente ejecute este código e intente calcular, por ejemplo, el número Fifty Fibonacci. Creo que sentirás un cierto retraso. Un chiste Creo que si ejecuta este código no en una supercomputadora, simplemente no esperará el resultado. A pesar de que el código simple y no recursivo de los ejemplos anteriores contará el quincuagésimo miembro de la secuencia de Fibonacci más rápido de lo que tiene tiempo para decir la palabra "cincuenta" o cualquier sílaba.

Expresado en el lenguaje aproximado de la notación O, dicha solución tiene una complejidad temporal de O (e ⁿ ). Es decir, el tiempo de ejecución de esta función crece exponencialmente al aumentar n. Es decir, cuando n aumenta en , el tiempo de ejecución aumenta en. En términos generales, si fib(45) tuvo que esperar una hora, luego fib(46) esperará dos horas, fib(47) - 4 horas, y así sucesivamente. Mastico con tanto detalle que cada lector, incluso un maquinista que primero intentó escribir guiones, pudo darse cuenta del horror de la situación.

Esto es correcto, pero demasiado grosero. Puede obtener una estimación más precisa del número de llamadas a la función ~ (1 + sqrt (5)) fib (n) y la hermosa observación "Para calcular el número de Fibonacci utilizando el método recursivo ingenuo, necesita 3,2 veces más llamadas a la función que el número de Fibonacci". Taus

Y obtenemos otro método para calcularlo. ¡Solo necesita ejecutar el método recursivo ingenuo, contar el número de llamadas a funciones y dividir por 3.2! Cerberuser

Si se le requiere que resuelva este problema de manera recursiva durante una entrevista, probablemente sea una trampa. Una recursión "correcta" que funcione en tiempo lineal podría verse, por ejemplo, así:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

Para resumir: a pesar del hecho de que los números de Fibonacci son un ejemplo clásico de recursión en un libro de texto, en realidad este no es el caso más conveniente para aplicar la recursividad. Pero puedes intentar mostrar algo más de conocimiento.

3. Función conmemorativa

Hay una forma mágica que convierte una solución monstruosamente ineficaz del último párrafo en una solución potencialmente muy rápida (aunque no sin problemas). Su nombre es memorización. Y si habla ruso, solo recordamos los resultados de llamadas anteriores en lugar de calcularlos nuevamente.

Básicamente, ni siquiera podemos cambiar nada dentro de esa solución, solo agregue una función de contenedor de memoize . Aquí, para mayor claridad, uso su versión simplificada para una función con un solo argumento.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Voila! Ahora la función fib tiene acceso al objeto de cache través del cierre. Si se llama con un argumento que no se ha encontrado previamente, el valor calculado se almacena en la cache . Con nuevas llamadas de función con el mismo argumento, el valor no tiene que ser recalculado, simplemente será tomado de la caché. El principal problema con la función de fib antigua "mala" era que los mismos valores se recalculaban varias veces. Por ejemplo, para calcular fib(45) fue necesario calcular f(44) una vez, dos veces f(43) , tres veces f(42) , cinco veces f(41) , y así sucesivamente.


Entonces, ahora los valores anteriores se calcularán una vez, y cuando se vuelvan a solicitar, solo se tomarán de la memoria caché. ¿Te imaginas cuánto más rápido podemos ahora calcular el cuadragésimo quinto número de Fibonacci? En serio, ¿a qué hora piensas?

De hecho, un poco más lento. Deliberadamente cometí un error clásico, a menudo cometido al memorizar funciones recursivas. Cuando fib(45) llama fib(45) "debajo del capó", se oldFib(45) , que llama a oldFib(44) y oldFib(43) por sus necesidades ... ¿Sientes la trampa? En lo sucesivo, ya hay llamadas a una función normal no memorizada. Por supuesto, cuando llamamos nuevamente a fib(45) , obtenemos instantáneamente el resultado del caché; sin embargo, la primera llamada no se aceleró en absoluto. Para solucionar esto, aún debe obtener oldFib debajo de la parte inferior de la llave:

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Genial Ahora la primera llamada a fib(45) funcionará a una velocidad comparable a la versión con un bucle. Y los desafíos adicionales generalmente funcionarán en tiempo constante ... ¡Vaya! De nuevo engañado. Obtener el valor de la propiedad de un objeto por clave es una operación rápida, pero aún así O (1) es solo en promedio, en el peor de los casos, puede degradarse a O (n). Para hacerlo muy bueno, en nuestro caso podemos cambiar el tipo de cache de un objeto a una matriz.

Por supuesto, uno no debe olvidar que la memorización requiere memoria. Y mientras reducimos la complejidad del tiempo, la complejidad de la memoria crece de O (1) a O (n).

¿De qué otra manera podemos presumir? Por ejemplo, demostrando su profundo conocimiento de las matemáticas.

4. Sr. Binet

Existe una ciencia especial y maravillosa sobre cómo transformar las relaciones de recurrencia en fórmulas explícitas. Aquí no entraremos en detalles. Solo diremos que para los números de Fibonacci, usando argumentos bastante simples, podemos derivar la siguiente fórmula, conocida como la fórmula de Binet:

$$

$$F_n = \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n - \ left (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {\ sqrt5} $$$

Sin embargo, es un lenguaje bastante matemático, lo escribimos en JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

Conduzcamos con los primeros números. Genial, todo parece funcionar. Aquí es 13, aquí es 21, aquí es 34, aquí es ... 54.9999999999999999?

Sí, por supuesto, ese resultado es lógico. La fórmula de Binet es matemáticamente precisa, pero la computadora funciona con fracciones de precisión finita, y se puede acumular un error durante las operaciones con ellos, lo que sucedió en este caso. Sin embargo, podemos arreglarlo. Sabiendo que lo restado en el numerador siempre será de magnitud pequeña, podemos simplificar la fórmula al siguiente estado:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

Aquí los corchetes extraños sin terminar significan el número entero más cercano, es decir, redondear. Reescribe nuestro código:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

Sí, eso está mucho mejor. Podemos ver 55 y 89, e incluso mi número favorito de Fibonacci es 144 (que me encanta porque es igual a doce al cuadrado). Todo estará bien hasta el número 76. Que debería ser igual a 3416454622906707, y nuestra función calculará 3416454622906706. Debido a que el problema de la precisión limitada de los números fraccionarios no ha desaparecido, simplemente lo empujamos más profundo y esperamos que no surja. Como muestra este ejemplo, esperaban en vano.

De hecho, podemos hacer algo más para guardar este método. Pero más sobre eso a continuación. Mientras tanto, bromas a un lado. Hablemos del método duro, duro y brutal.

5. Sigue al conejo blanco.

Dicen que si tiene un problema y se le ocurrió la idea de que puede resolverlo con expresiones regulares, ahora tiene dos problemas. Las matrices son expresiones regulares por el contrario. Muchos problemas, si se reformulan en el lenguaje de las matrices, se resuelven simplemente por sí mismos.

En cuanto a los números de Fibonacci, para ellos en lenguaje de matriz puede escribir esta identidad obvia:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ begin {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

Es decir, si tomamos un par de números consecutivos de Fibonacci y los multiplicamos por una matriz tan directa, obtenemos el siguiente par. Y la conclusión lógica se deduce de esto: si tomamos un par de cero y primeros números de Fibonacci, es decir, cero y uno, y los multiplicamos por esta matriz a una enésima potencia, obtenemos un par de n y en más el primer Fibonacci. Es decir, hablando humanamente:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n \ begin {pmatrix} 0 \\ 1 \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

Puede simplificar esto un poco más abandonando los vectores. De hecho, todos los valores necesarios están contenidos en la matriz misma:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_ {n} \\ F_ {n} & F_ {n + 1 } \ end {pmatrix}$$

Genial, ¿no es así? Queda por entender, para qué armonía del culo, si no es un filarmónico. Quiero decir, ¿por qué son tales dificultades de la nada? Y la respuesta es simple: exponenciación rápida.

¿Cuántas multiplicaciones elementales se necesitan para calcular, por ejemplo, 2 ¹⁰ ? Una persona normal dirá nueve. Dos veces dos - cuatro. Dos veces cuatro u ocho. Dos veces ocho son dieciseis. Y así sucesivamente. Una persona astuta dirá que cuatro.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

El programador dirá. que recuerda este número de memoria, y que nada necesita ser multiplicado. Sin embargo, discutimos los problemas de la memoria anterior.

Por lo tanto, una exponenciación rápida también es aplicable a las matrices y, por lo tanto, nos permite reducir la complejidad de tiempo asintótica de nuestra función de O (n) a O (log n). Y esto es muy bueno, a menos que, por supuesto, esta complejidad sea realmente tan importante para nosotros. Escribamos el código:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

Entonces obtuvimos el algoritmo más rápido en el Salvaje Oeste. Y, a diferencia de la mayoría de los anteriores, se puede demostrar de manera no irónica en una entrevista. Y en algunos lugares con capacidad matemática se esperará de usted.

PS

Prometí un comentario sobre cómo guardar un método basado en la fórmula de Binet. La respuesta está en este artículo mío. Allí, para las necesidades de la economía nacional, escribí una clase especial, la raíz de cinco números racionales, que, sin pérdida de precisión, puede almacenar los resultados de operaciones aritméticas en enteros y una raíz de cinco. Puede tomar esta clase, complementarla con el método de redondeo y usarla para buscar números de Fibonacci usando la fórmula de Binet. Y luego inyectar óxido nitroso mediante la aplicación de exponenciación rápida.

Y lo que es más interesante: si observa cuidadosamente qué números se obtendrán en el proceso, qué operaciones se realizarán, quedará claro que este método es la misma multiplicación de matrices, solo que bajo una fachada diferente. La única diferencia es si almacenamos números en matrices bidimensionales o en los campos de un objeto de una clase especial.

Eso es todo Si cree que me he perdido algunas otras formas interesantes de encontrar números que nadie necesita, asegúrese de escribir sobre eso en los comentarios.

También existe un método como la duplicación rápida . Funciona como la multiplicación de matrices en O (log), pero con una constante menor en asintóticos (y en la práctica). Brevemente, se usan dos fórmulas allí, confiando en que uno puede retroceder rápidamente a índices dos veces más bajos de forma recursiva:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

La implementación, por cierto, es bastante compacta.

Comparación de la velocidad de los diferentes métodos.

just_maksim