En la escuela, a Pablito le han enseñado a obtener una sucesión infinita de números que le ha maravillado llamada La serie de Fibonacci. Fibonacci fue un matemático Italiano que diseño esta serie para resolver el problema de la cría de los conejos:
Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también
La serie tiene la siguiente secuencia:
1,1, 2, 3, 5, 8, 13, 21,… donde el número siguiente es la suma de los dos anteriores a este.
La maestra de Pablito se cree muy lista y les ha dejado resolver esta serie para los siguientes numeros:
2 = 1.0
5 = 5.0
14 = 377.0
25 =
150 =
512 =
809 =
1474 =
Prometiendo que aquel que logre resolverlas lo exentará del examen final y pasará sin ningún problema. La maestra lo hizo pensando que ningún alumno los resolvería pero no contaba con que a Pablito lo ayudarías tu.
Pablito ha diseñado un programa que obtiene el resultado.
[python]
def fibonacci(n):
if n<2:
return n
else:
return (fibonacci(n-1) + fibonacci(n-2))
[/python]
Ayuda a Pablito con su programa.
Actualización 26-Dic-08:
Pista: Modifica o cambia completamente el programa de Pablito ya que éste resulta muy tardado.
19 Comments
Eso parece fácil… deja que mi compu acabe de procesarlo y de digo la respuesta. O ¿sera mejor optimizarlo?… O a lápiz y papel y calcu.
@Nick, si, la verdad es que esta muy sencillo. Espero las respuestas. Saludos.
Será:
F(25)=75024
F(150)=9969216677189352939733964029952
F(512)=4489384531331071533787821747492071276103636659097649104586779801722170234
5688961142661903754343645509058560
F(809)=5266425683405200788102952169968216436871242891143227329047703583524008467
9673267513914983209197482115537660718985859196498266909149696843166503483078674
10688669225320448
F(1474)=499225460547801463531985795313521535332128401090294669940981421976173033
59523104269471455390562835412104406019654730583800904132982935807202575490044075
13263120328485489050580887743083761849357751270345392837939087473082990665206754
5822236147772760444400628059249610784412153766674534014113720760876471943168
@Nick Excelente, reto concluido. nos podrías mostrar tu programa o el método que utilizaste para obtenerlos?
Wow, eres rápido. Yo apenas estaba comprobándolo. Hice los cálculos en Java y los estaba comprobando con Python. Deja lo pongo presentable, documento, etc. y lo coloco. También estoy trabajando en el código para el reto anterior.
Debo decir “Benditos lenguajes con tipos de datos dinámicos”
jaja, es que me di una vuelta para chekar algo y bum, vi tu comentario. Muy bien, pondré un ranking para los retos.
La versión python:
[python]
import math
PHI = ( 1 + math.sqrt(5) ) / 2
def F(n):
return math.floor( math.pow(PHI, n) / math.sqrt(5) + 1/2 )
print F(25)
print F(150)
print F(512)
print F(809)
print F(1474)
[/python]
La version Java: B:1 [Serie Fibonacci]
¿Nos vas a mostrar tu código?
Si, porsupuesto, antes de publicar cada reto lo resuelvo.
Mi función fibonacci::
[python]
def Fibonacci(n):
return math.floor(1/math.sqrt(5)*math.pow((1+math.sqrt(5))/2,n)) – \
(1/math.sqrt(5)*math.pow((1-math.sqrt(5))/2,n))
[/python]
Felicitaciones @Nick, vas en primer lugar. Saludos.
Me habia perdido un rato por las vacaciones pero creo que es incorrecto el factorial de 25 el verdadero valor es de 75025 si no me equivoco y creo que se la complicaron un poco miren aca esta un codigo mas simple no se que tan eficiente sea del suyo pero creo que es un poquito mas rapido:
double a = 1, b = 0;
for (int i = 0; i<13; i++ )
{
a = a + b;
b = a + b;
}
el numero factorial sobre dos si quiero el del 25 le doy 25/ 2 es 12.5 y le pongo 13 en el ciclo, espero lo chequen a ver que les parece
@Mayolo, muy cierto, el problema de la matemática inductiva como dices es eso, el margen de error que fue muy pronunciado en el 25. xD
@Mayolo ¿Cómo? ¿Factorial? Bueno, pero si esta incorrecto. ¿Nos podrías explicar cual es la lógica detrás de tu código?
@lesthack ¿matemática inductiva? ¿margen de error? Hasta donde se el valor exacto de ‘x’ valor de la serie depende de que tan exacto se tome el valor de PHI. Más aun de que tan exacto se tome la raíz cuadrada de 5.
Eso quiere decir que los demás números también están mal. Y de hecho ya encontré el problema.
En los programas que presenté como solución, tanto en Python como en Java, uso la misma formula:
math.floor( math.pow(PHI, n) / math.sqrt(5) + 1/2 ). El problema es que, por alguna razón que no entiendo, nunca se suma el 1/2. O mejor dicho siempre suma cero; en Python la división 1/2 siempre da cero. Se aceptan explicaciones.[python]
print 1/2
[/python]
En java ocurre lo mismo:
[java]
System.out.println(1/2);
[java]
Cambiando simplemente el 1/2 por 0.5, todo funciona adecuadamente. De forma tal que el código queda:
math.floor( math.pow(PHI, n) / math.sqrt(5) + 0.5 ).Me respondo a mi mismo. Cuando se divide un entero por un entero da como resultado un entero. int = int / int. Lo mismo aplica para los double y float. Cuando se divide y los operandos son de diferente tipo el resultado toma el tipo de dato mas preciso. double = int /double. double = double / int. Regla general, por eso pasa lo mismo en Python y Java. Cosas de primero que aveces de olvidan.
Bueno optimizamos un poco la función, ahora ya no dividimos 1.0/2.0 ponemos directamente el resultado 
.
Otro error, dije que todos los demás números también estaban mal. Pero no todos los números habrían estado mal. Los números erróneos serían aquellos en los que el resultado de la operación (en su parte decimal)
java.lang.Math.floor( java.lang.Math.pow(PHI, n) / java.lang.Math.sqrt(5)estuviera entre (0.5, 1).saludos.
@Nick, la formular generadora de fibonacci que utilizamos fue obtenida por matemática inductiva por Édouard Lucas y debido al número “irracional” en tu programa llamas PHI la hace inexacta con un margen de error ligero.
Mayolo quiso decir Fibonacci en lugar de Factorial.
Y creo que el error de perdida de decimales también lo cometí yo.
Mayolo ha optado por un ciclo que perfectamente corre en tiempo polinomial reduciendo costos casi a O(n²). Empero, la formula que utilizamos tanto yo como tu Nick es mucho mas rápida.
Tiempo de ejecución total programa Nick, Lesthack: 0.013 s
Tiempo de ejecución total programa Mayolo: 0.103 s
La diferencia es pronunciada pero mínima.
Saludos.
@nick, el número irracional PHI también es llamado número áureo, número dorado, etc. Y vaya que me he sorprendido por lo enigmático que es.
Wow, Eso no lo sabía. Gracias Éduard Lucas. En la Wikipedia dicen que también invento el juego de las torres de Hanoi.
Estoy de acuerdo contigo, φ es muy enigmático. Esta en los girasoles, en el cuerpo humano, en nautilus (el animal, no el explorador de archivos) en tantas cosas, impresionante. Me sorprende que no lo conocieras.
Hmmm un detalle, las formulas que usan nuestros programas son diferentes.
Bueno por una décima de segundo no nos vamos a pelear.
@Nick, realmente son la misma, solo que tu formula esta mas reducida.
me temo que las respuestas no están del todo bien:
F(2) = 1
F(5) = 5
F(14) = 377
F(25) = 75025
F(150) = 9969216677189303386214405760200
F(512) = 44893845313309942978077298160660626646181883623886239791269694466661322268805744081870933775586567858979269
F(809) = 5266425683405057731495444092244174522861452105372257554189984579279362348691671275244047446224217175749585504549914494508130592637252870325717753776846061280936139129709
F(1474) = 49922546054777678351476448799364830626232385068022029277057092361751561817010796843439538243029637830326254743746116222205267068669327220182524725743309601567683954648939588216389546331215646259721293035324606932351713659799709631336569978107771336999740177766103904377182436396828235163092944218106306285607
44893845313309942978077298160660626646181883623886239791269694466661322268805744081870933775586567858979269L
fibo[809] = 5266425683405057731495444092244174522861452105372257554189984579279362348691671275244047446224217175749585504549914494508130592637252870325717753776846061280936139129709L
fibo[1474] = 49922546054777678351476448799364830626232385068022029277057092361751561817010796843439538243029637830326254743746116222205267068669327220182524725743309601567683954648939588216389546331215646259721293035324606932351713659799709631336569978107771336999740177766103904377182436396828235163092944218106306285607L
Lo que pasa es que para calcular los números de Fibonacci con la fórmula de Binet necesitas calcular ? a una cantidad inmensa de decimales, lo que elimina la ventaja de tener una fórmula aparentemente O(1) (recordemos, además que la multiplicación sobre números grandes no es O(1), sino aproximadamente O((logn)³), donde n es el número a multiplicar). Pueden verificar sus respuestas contra la OEIS en la siguiente liga: http://www.research.att.com/~njas/sequences/b000045.txt
Código en python
[code]
#!/usr/bin/python
fibonacci = [0,1]
for i in xrange(1473):
fibonacci.append(fibonacci[-1] + fibonacci[-2])
for i in (2,5,14,25,150,512,809,1474):
print "F(%d) = %s" % (i, fibonacci[i])
[/code]
lhchavez:~/code$ time python fibonacci.py
real 0m0.025s
user 0m0.020s
sys 0m0.004s
me temo que las respuestas no están del todo bien:
F(2) = 1
F(5) = 5
F(14) = 377
F(25) = 75025
F(150) = 9969216677189303386214405760200
F(512) = 4489384531330994297807729816066062664618188362388623979
1269694466661322268805744081870933775586567858979269
F(809) = 5266425683405057731495444092244174522861452105372257554
18998457927936234869167127524404744622421717574958550454991449
4508130592637252870325717753776846061280936139129709
F(1474) = 499225460547776783514764487993648306262323850680220292
77057092361751561817010796843439538243029637830326254743746116
22220526706866932722018252472574330960156768395464893958821638
95463312156462597212930353246069323517136597997096313365699781
07771336999740177766103904377182436396828235163092944218106306
285607
Código en python
[code]
#!/usr/bin/python
fibonacci = [0,1]
for i in xrange(1473): fibonacci.append(fibonacci[-1] + fibonacci[-2])
for i in (2,5,14,25,150,512,809,1474): print “F(%d) = %s” % (i, fibonacci[i])
[/code]
lhchavez:~/code$ time python fibonacci.py
real 0m0.025s
user 0m0.020s
sys 0m0.004s
Lo que pasa es que para calcular los números de Fibonacci con la fórmula de Binet necesitas calcular PHI a una cantidad inmensa de decimales, lo que elimina la ventaja de tener una fórmula aparentemente O(1) (recordemos, además que la multiplicación sobre números grandes no es O(1), sino aproximadamente O((logn)³), donde n es el número a multiplicar). Esto se puede hacer con ayuda de Java.math.BigDecimal, pero es mucho más sencillo hacerlo como dijo @Mayolo, pero con BigIntegers
Pueden verificar sus respuestas (menores a 500) contra la OEIS en la siguiente liga: http://www.research.att.com/~njas/sequences/b000045.txt
P.D. vivan los lenguajes con BigInteger integrado
@lhchavez me gusta como utilizas el xrange para iterar. En efecto, y gracias por aclarar los errores que hemos cometido, en particular, simplemente obtuve los siguientes resultados.
F(25) = 75025
F(150) = 9.96921667719e+30
F(512) = 4.48938453133e+106
F(809) = 5.26642568341e+168
F(1474) = 4.99225460548e+307
Y por lo tanto no me pude percatar de las diferencias.
Saludos.