👨🏫 Resuelve Fibonacci con JavaScript: solución con recursividad y con bucles
Vložit
- čas přidán 13. 03. 2022
- Una de las preguntas más típicas en la universidad o pruebas técnicas de JavaScript es resolver la sucesión de números de Fibonacci! 👩🏫
Normalmente la gente usa la solución recursiva... pero lo cierto es que no es la mejor en cuanto optimización.
Siempre podrías usar la memoización de los resultados previos pero, la verdad, es que es mejor usar una solución iterativa. Además demuestra que entiendes el núcleo del algoritmo.
Eso sí, aunque la solución del bucle es mejor que la de recursividad... puedes usar la fórmula de Binet para calcularlo el número todavía más rápido. Aunque no creo que nadie espere que sepas esta solución de memoria:
El código sería:
function fibonacci(n) {
return Math.round((Math.pow(1.618033988749895, n) - Math.pow(-0.6180339887498949, n)) / 2.23606797749979);
}
La explicación: artofproblemsolving.com/wiki/...
▶ Disfruta de los directos en: / midudev - Věda a technologie
con recursión me cuesta hacerlo por la forma en la que hay que pensar.. pero con la iteración lo hice sin problemas...
lo hice de esta forma en javascrit:
function fibonacci(numero){
let contenedor = 0;
let contador = 0;
let a = 0;
let b = 1;
let c = 0;
while(contador < numero){
contenedor = c
c = a + b;
a = b;
b = c;
contador++;
};
return contenedor;
};
console.log(fibonacci(10));
uso las variables A y B como los numero iniciales (0,1) y la variable C para hacer la suma de esas variables, la variable contenedor será donde se guardara cada suma, y la variable contador lo uso para detener el siclo, dentro del bucle cada vez que se repita,, A tendra el valor de B y B tendra el valor de C de esta forma se cumple la funcion de sumar los numero anteriores.
Grax por el comentario. Me ayudó más a entender!
Midu seria interesante que explicaras lo del Big o, quizas buscando puedo encontrar pero nada que un god como tu lo explique porque se que entiendo de primera
me abriste la mente , del cuando como y porque se debe o no hacer un tipo de algoritmo. Grande midu.
Muy interesante midu, muchas gracias!
La segunda implementacion si bien tiene mejor complejidad temporal porque estas guardando todos los resultados precalculados. Tiene una alta complejidad espacial, estas guardando en memoria una gran cantidad de datos donde la mayoria ya no la vas a usar mas, solamente te importan los 2 ultimos elementos del array. Podrias simplemente usar 2 variables y guardar ahi lo que necesitas, pasas de complejidad espacial O(|n|) a O(1)
Claro. En este caso lo dejamos así porque a veces más que el resultado final, se pide la serie completa y ahí sí necesitas guardarlos.
Al final lo más fácil hubiera sido usar Binet para la complejidad más sencilla. Pero no es realista que la gente se lo sepa de memoria. :)
@@midulive tenes toda la razon, me habia olvidado completamente de la formula explicita.
Estoy aprendiendo Python sin investigar como se hace ni nada, solo enfocándome en que me diera el resultado sin pensar en la optimización ya que todavía no entiendo bien lo de recurcibidad siquiera, llegué a este resultado, no se si sea el más óptimo o no pero esto me salió:
fib = 0
prev_fib = 1
for i in range (1, 51):
Print(fib)
new_fib = fib + prev_fib
prev_fib = fib
fib = new_fib
Se puede hacer con recursividad usando memoization, pero creo que el space complexity se elevaría, aún así es una solución funcional pero creo que sigue siendo más rápido en performance con loops y de igual manera, aún un poco más rápido con while en lugar de un for y ni se diga si se usan variables temporales en vez de un array. ¡Saludos!
const fiboRec = (n, memo = {}) => {
if (n in memo) return memo[n];
if (n === 0) return 0;
if (n === 1) return 1;
memo[n] = fiboRec(n - 2, memo) + fiboRec(n - 1, memo);
return memo[n];
}
console.time('fiboRec');
console.log('fiboRec',fiboRec(1000));
console.timeEnd('fiboRec');
const fiboLoop = n => {
const fib = [0,1];
for(let i = 2; i {
const fib = [0,1];
let i = 2;
while (i {
let n_1 = 1;
let n_2 = 0;
let i = 2;
while (i
Por cierto, la recursividad no siempre es tan mala si se usa combinado con técnicas como "Dynamic Programming", por ejemplo, podrías tener el mismo time complexity the O(N), si agregas memoization, ya que no estarías volviendo a calcular las partes más pequeñas. Ejemplo:
```javascript
function fibonacciMemoization(n, memo = {}) {
if (memo[n]) {
return memo[n]
}
if (n
Te amo
Tienes servicio de acesorias o desarrollo web?
Pero como es que se ejecuta ,,no entiendo .,,..
Muchas Gracias!
en retries de cosas está bueno usar recursividad.
No entiendo por qué la recursividad la planteó de esa manera, yo la armé de la siguiente manera imprimiendo logs de forma creciente y funciona, siendo de orden N:
function fibonacci( n, h, i ){
if( i > n ){
return;
}
console.log( i );
return fibonacci( n, i, h + i );
}
que usas para probar codigo de js
runJS
Gyro Zeppeli controla muy bien el giro Fubonacci
como se llama el editor que stá usando??
Se llama runjs, y es un programa que instalas y puedes ejecutar código JavaScript usando algunos temas como Dracula, y puedes ver la ejecución ahí mismo. (Similar a QuokaJs)
Como hacer un algoritmo que muestre, los 50 primeros números primos de la serie Fibonacci.
Necesito ayuda
Pero si justamente este vídeo te da la solución!!!!
@@midulive Es que no se entendió, no se entiende como se ejecuta
@@dragonOfLemons No lo entendiste, que es diferente. La recursividad puede ser un tema complejo y requiere también que hagas un esfuerzo para estudiarlo.