The Python Challenges
N°1 Fibonacci
Relámpago
(http://rtdibermatica.com/wp-content/uploads/2011/10/Fibonacci-en-Naturaleza.jpg)
Los retos relámpago son retos que no necesariamente siguen la temática de los retos principales. Tampoco se evaluan los códigos bajo los mismos criterios.
El código ganador es el primero que cumpla con TODAS las condiciones establecidas.
Las condiciones de todos los retos relámpago (a menos que se indique lo contrario en un reto específico) son las siguientes:
- Cumplir todas y cada una de las condiciones establecidas para el reto.
- Sólo se acepta un código por participante (el primero que se envíe).
- Los usuarios descalificados del reto principal de la semana, no se tiene en cuenta en la puntuación de los retos relámpago de esa misma semana.
- Bajo ninguna circunstancia se publican los códigos en el hilo del reto.
- Si hay límite de tiempo para el reto, o si finaliza el tiempo del reto principal y ningún código cumple con todas las condiciones se cierra el reto sin ganadores.
Sucesión FibonacciEn este reto el objetivo es codear una función que regrese una lista con los primeros cien números de la serie Fibonacci comenzando desde el unoCondiciónEl código ganador será el más corto que cumpla con el objetivo.
El plazo máximo de entrega es para el Jueves 6 de Febrero.Los códigos deben ser enviados por mp a los moderadores (Once (http://underc0de.org/foro/profile/Once) y WhiZ (http://underc0de.org/foro/profile/WhiZ/)) con el siguiente asunto: [TPC-R] #1 (Debido a la cantidad de códigos que nos llegan)
Happy coding
suerte q justo tenía la función fibonacci en algún lado, código enviado!
HOLA!!!
Codigo enviado.
for x in-2,2:print" 3 1 9R7u3l1e9z7"[::x]
GRACIAS POR LEER!!!
Recibidos hasta ahora un par de codes! No olviden que hoy cierra el reto.
Saludos!
No cumplen las condiciones:
Usuario: Bladeyer
Caracteres: 198
from math import *
def fib(n):
if n <= 70:
return floor((((1 + sqrt(5))/2)**n)/sqrt(5) + 0.5)
else:
return fib(n-1) + fib(n-2)
def funcion():
print([fib(i) for i in range(101)])
funcion() Usuario: Sanko
Caracteres: 75
print int((((1 + 5**0.5) / 2)**100 - (1-((1 + 5**0.5) / 2))**100) / 5**0.5)Usuario: Juan
Lenguaje: Perl
# Juan
my $n0 = 0;
my $n1 = 1;
print "$n0\n$n1\n";
for my $numero (0..100)
{
my $resultado = $n0 + $n1;
print "$resultado\n";
$n0 = $n1;
$n1 = $resultado;
}Cumplen las condiciones
Usuario: deni_celine
Caracteres: 78
def f():g=lambda n:1if(n<2)else(g(n-1)+g(n-2));return[g(i)for i in range(100)]Usuario: 79137913
Caracteres: 72
def a():
b = [1,1]
for x in range(98): b.append(b[-1]+b[-2])
return bGanador
79137913
72 caracteres
Esto me pasa por no leer bien el enunciado xd, en clase más de lo mismo.
Congrats
6 caracteres noo :'( jajja congratulations al que ganó
edito: estaba mirando el código de 79137913 y es mucho mas eficiente q el mio y_y, le hice una humilde modificación para haceerlo mas inentendible xD . Salu2
def f():l=[1,1];exec"l.append(l[-1]+l[-2]);"*98;return l
HOLA!!!
Wiii Gane :D!!!!!
def f():l=[1,1];exec"l.append(l[-1]+l[-2]);"*98;return l
Buen codigo deni_celine!!!
Ya me guardo esa tecnica de exec"funcion"*nro
GRACIAS POR LEER!!!
No tienes permitido ver los links.
Registrarse o Entrar a mi cuenta
6 caracteres noo :'( jajja congratulations al que ganó
edito: estaba mirando el código de 79137913 y es mucho mas eficiente q el mio y_y, le hice una humilde modificación para haceerlo mas inentendible xD . Salu2
def f():l=[1,1];exec"l.append(l[-1]+l[-2]);"*98;return l
Muy bueno bro, muy ingeniosa la forma en que usas la multiplicación de strings Pero aún se pueden ahorrar un par de caracteres si en lugar de usar .append() se usa la concatenación de listas:
def f():l=[1,1];exec"l+=[l[-1]+l[-2]];"*98;return lSaludos!
excelente! tendre en cuenta esa técnica tb. me gusta esta forma de aprender :D
HOLA!!!
Que bueno!
Yo encontre el algoritmo.
deni nos enseño esa tecnica de excec"func"*n
y 11Sep nos enseño como agregar items a listas sin append.
GRACIAS POR LEER!!!
No tienes permitido ver los links.
Registrarse o Entrar a mi cuenta
excelente! tendre en cuenta esa técnica tb. me gusta esta forma de aprender :D
No tienes permitido ver los links.
Registrarse o Entrar a mi cuenta
HOLA!!!
Que bueno!
Yo encontre el algoritmo.
deni nos enseño esa tecnica de excec"func"*n
y 11Sep nos enseño como agregar items a listas sin append.
GRACIAS POR LEER!!!
Claro, la idea de los retos más que competir es encontrar diferentes formas de solucionar el mismo problema y encontrar nuevas formas para sacar el mayor provecho al lenguaje. Una forma más dinámica de aprender.
Saludos!
Enhorabuena 7913... a ver si se anima más gente a participar que en este reto han habido pocos códigos o eso parece :D.
La solución iterativa es la forma lógica de abordar el problema, tal como lo haría a mano cualquier persona, pero hay otras soluciones muy buenas también.
El código de deni_celine es el típico que usan para aproximar a los nobeles a la recursión, pero no es la solución recursiva más eficiente, es bastante lento como habréis comprobado :P. Normalmente en los lenguajes compilados el compilador lleva a cabo una tarea de reordenamiento y mejora en la eficiencia del código y lo que suelen hacer algunos compiladores cuando se topan con el algoritmo recursivo de fibonacci es utilizar un acumulador para "plantear" el problema mediante recursión de cola, está claro que el intérprete de python no nos proporciona esto, pero el código del reto por ejemplo sería algo así:
def fib_aux(x,y,n):
return x if n==0 else fib_aux(y,x+y,n-1)
def fib(n):
return 1 if n<2 else fib_aux(1,1,n-1)
print [fib(i) for i in range(0,100)]
Un saludo :)
HOLA!!!
Gracias Overflow...
Estoy en desacuerdo con que ese algoritmo es mas veloz que el mio.
Si prestas atencion tu codigo hara aproximadamente 100 call Jump a su funcion, 100 comprobaciones if y ademas sumas.
El mio solo tiene 1 call jump 98 iteraciones menos sumas y sin comprobaciones if.
GRACIAS POR LEER!!!
No tienes permitido ver los links.
Registrarse o Entrar a mi cuenta
HOLA!!!
Gracias Overflow...
Estoy en desacuerdo con que ese algoritmo es mas veloz que el mio.
Si prestas atencion tu codigo hara aproximadamente 100 call Jump a su funcion, 100 comprobaciones if y ademas sumas.
El mio solo tiene 1 call jump 98 iteraciones menos sumas y sin comprobaciones if.
GRACIAS POR LEER!!!
No dije en ningún momento que fuera más eficiente que el tuyo, es una mejor solución recursiva que la propuesta por deni_celine. Fijate que la solución iterativa es mejor que la solución de la recursión de cola para este reto por el hecho de que hay que llamar n veces a la función para calcular el fib de los n primeros números, mientras que en la tuya no. Sin embargo observa el benchmark para calcular únicamente el fibonacci de un número, probémoslo con un número alto a ver:
#!/usr/bin/env python
import time
def fib_aux(x,y,n):
return x if n==0 else fib_aux(y,x+y,n-1)
def fib(n):
return 1 if n<2 else fib_aux(1,1,n-1)
def a():
b = [1,1]
for x in range(700): b.append(b[-1]+b[-2])
return b
ttot = 0
for i in range(0,1000):
it = time.time()
fib(700)
et = time.time()
ttot += et-it
print ttot/1000
ttot = 0
for i in range(0,1000):
it = time.time()
a()
et = time.time()
ttot += et-it
print ttot/1000Resultados:
· Recursivo : 0.000249599981308s
· Iterativo : 0.000144299983978s
Nada mal para ser una solución recursiva dentro de los límites que nos pone la recursión ¿no? (Prueba a hacer el fib de 2000 en el iterativo y en el recursivo verás una gran limitación). Pero si lo probamos para este reto, se ve que la recursiva pierde por mucho mira:
import time
def fib_aux(x,y,n):
return x if n==0 else fib_aux(y,x+y,n-1)
def fib(n):
return 1 if n<2 else fib_aux(1,1,n-1)
def a():
b = [1,1]
for x in range(100): b.append(b[-1]+b[-2])
return b
ttot = 0
for i in range(0,10000):
it = time.time()
t = [fib(n) for n in range(0,100)]
et = time.time()
ttot += et-it
print ttot/10000
ttot = 0
for i in range(0,10000):
it = time.time()
t = a()
et = time.time()
ttot += et-it
print ttot/10000Resultados:
· Recursivo: 0.0012103000164s
· Iterativo : 1.91999912262e-05s
63 veces más rápido el iterativo para este reto. Puedes observar como el coste temporal de tu algoritmo es lineal O(n) mientras que el recursivo en este reto está forzado a ser cuadrático O(n^2) por lo que cuando aumenta la talla (la cantidad de números cuyo fibonacci queremos saber) la diferencia entre los costes se vuelve bastante notable. Como éstas, hay muchas más peculiaridades en los comportamientos de ambos algoritmos y está interesante leer códigos de retos para observarlos.
Un saludo :D
HOLA!!!
Es cierto, se ve que solo querias mostrar una manera recursiva optimizada no un codigo mas eficiente que el otro.
GRACIAS POR LEER!!!