Disculpen por "arruinarles" este divertido desafío, pero me encontré teniendo que ingeniármelas para entender los códigos que posteaban. Me resultó interesantísimo cuando entendí (al menos en parte) qué es lo que hacían. Decidí entonces facilitarles la tarea a los demás navegantes y explicar una solución, para que no tengan que romperse la cabeza (o que sí lo hagan, pero que no se frustren si no lo entienden).
El código que me quedó calcula bien y rápidamente
fibo(1000)
.
ADVERTENCIA: si quieres resolver el desafío completamente por tu cuenta, no sigas leyendo mi comentario.
Gracias a la comunidad de
ForosDelWeb en general por las magníficas ideas aportadas.
Si no sabes qué es la
Serie de Fibonacci, primero dedícate a averiguar
qué es y luego sigue leyendo el post.
Explicación: la
serie de Fibonacci, traducida literalmente de la matemática a la computación resulta una función recursiva como la siguiente:
Código Javascript
:
Ver originalfunction fibonacci(n)
{
if(n==0)
{
return 0;
}
if(n<=2)
{
return 1;
}
return fibonacci(n-1)+fibonacci(n-2);
}
El problema con esa solución es que la computadora hace mucho más proceso que el necesario. Y eso no es sólo porque evaluar recursivamente una función requiera más procesamiento que dentro de un bucle, sino porque sencillamente se calcula de más:
Cada vez que se requiere calcular un
fibonacci(n) con
n>2, deben calcularse dos números de
fibonacci y así
recursivamente; pero se calculan muchas veces los mismos números. Veamos un ejemplo:
fibonacci(6):
- Debe calcular
fibonacci(5) y
fibonacci(4).
fibonacci(5):
- Debe calcular
fibonacci(4) y
fibonacci(3).
fibonacci(4):
- Debe calcular
fibonacci(3) y
fibonacci(2).
fibonacci(3):
- Debe calcular
fibonacci(2) y
fibonacci(1).
fibonacci(2) y
fibonacci(1):
- Es 1 (f(0)=0, f(1)=1, f(2)=1)
¿Me siguieron? Para calcular el
fibonacci(6) hay que calcular una vez el
fibonacci(5), 2 veces el
fibonacci(4), 3 veces el
fibonacci(3), 5 veces el
fibonacci(2) y 3 veces el
fibonacci(1) ¡14 cálculos! (más la suma final: ¡15!). Si no me creen háganse una prueba de escritorio con lápiz y papel... les quedará un lindo arbolito.
Obviamente el
fibonacci(k) siendo
k constante siempre será el mismo, por lo cual calcularlo más de una vez es innecesario. Y lo peor es que la situación empera drásticamente al tener que calcular
fibonacci(1000). Hay algunas soluciones computacionales a esto, como
memoization.
Pero el problema se evita pensando el cálculo desde otra perspectiva: sólo se necesitan dos variables (más una auxiliar) para calcular cualquier número de
fibonacci, siendo que estas variables contienen una el
fibonacci(n-1) y la otra el
fibonacci(n-2), pero sin necesidad de llamar a la función recursivamente para calcularlos, sino calculándolos a partir de
fibonacci(1) y
fibonacci(2) y guardando siempre los resultados parciales en estas mismas variables (esta idea la tomé de la solución de
Caricatos
en
este post):
Código Javascript
:
Ver originalfunction fiboN(n)
{
var f1=1;
var f2=1;
var aux;
for(var i=n; i>2; i--)
{
aux=f1;
f1+=f2;
f2=aux;
}
return f1;
}
Esta solución es sensiblemente más veloz (muchísimo más veloz de hecho, sólo calcula n-2 veces para
fibonacci(n)) que la anterior. Pero tiene un problema:
Javascript (así como la gran mayoría de lenguajes de programación, una buena excepción es
Python) no tiene cálculos aritméticos exactos cuando se trata de números muy grandes (o muy pequeños), sino que usan para almacenarlos en memoria una notación exponencial, que si bien es muy eficiente, es inexacta. Por eso, cuando se intentan calcular
fibonacci's grandes, los números empiezan a dar resultados erróneos. La solución que encontré a esto es almacenar los números como cadenas de caracteres. Para ello es necesario definir una suma de cadenas de caracteres como si de números se tratara (el algoritmo que uno utiliza cuando suma "a mano", con arrastre y todo), de modo que la computadora nunca tenga que manejar números grandes (de hecho, nunca mayores a 20). Entonces sí, el código final (muuuuuuuy similar al de
Nahuel2k10
):
Código Javascript
:
Ver originalfunction fibo(n)
{
var f1='1';
var f2='1';
var aux;
for(var i=n; i>2; i--)
{
aux=f1;
f1=sumar(f1,f2);
f2=aux;
}
return f1;
}
function sumar(a,b)
{
// Siempre a es mayor o igual que b %
var arrastre=false;
var ret='';
var suma;
var dif=a.length-b.length;
for(var i=a.length-1; i>=0; i--)
{
suma=arrastre?1:0;
suma+=parseInt(a.charAt(i))+parseInt(((i-dif)>=0)?b.charAt(i-dif):'0');
if(suma>=10)
{
arrastre=true;
suma=suma%10;
}
else
{
arrastre=false;
}
ret=suma+ret;
}
if(arrastre)
{
ret='1'+ret;
}
return ret;
}
¡Suerte!
...
¡Je, je!)... lo del ipad es otra broma, aunque en el futuro no se descartan premios en estos concursos... (tiren papelitos, muchachos) 
,
Este tema le ha gustado a 4 personas