send
Grupo de Telegram
play_arrow
Este sitio utiliza cookies propias y de terceros. Si continúa navegando consideramos que acepta el uso de cookies. OK Más Información.

[TPC-R] #1 Fibonacci

  • 15 Respuestas
  • 3111 Vistas

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado Once

  • *
  • Underc0der
  • Mensajes: 383
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil
    • El blog de Once
  • Twitter: @don_once
« en: Febrero 05, 2014, 12:15:07 am »

The Python Challenges
N°1 Fibonacci
Relámpago




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 Fibonacci

En 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 uno

Condición
El 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 (You are not allowed to view links. Register or Login y You are not allowed to view links. Register or Login) con el siguiente asunto: [TPC-R] #1 (Debido a la cantidad de códigos que nos llegan)

Happy coding

« Última modificación: Junio 24, 2016, 11:04:00 pm por Once »






You are not allowed to view links. Register or Login

Desconectado deni_celine

  • *
  • Underc0der
  • Mensajes: 36
  • Actividad:
    0%
  • Reputación 0
  • un susurro con la fuerza de mil gritos
    • Ver Perfil
« Respuesta #1 en: Febrero 05, 2014, 03:48:46 am »
suerte q justo tenía la función fibonacci en algún lado, código enviado!

Conectado 79137913

  • *
  • Co Admin
  • Mensajes: 614
  • Actividad:
    18.33%
  • Reputación 10
  • 4 Esquinas
    • Ver Perfil
    • Doors.Party
    • Email
  • Skype: fg_mdq@hotmail.com
« Respuesta #2 en: Febrero 05, 2014, 09:42:07 am »
HOLA!!!

Codigo enviado.

Código: Python
  1. for x in-2,2:print" 3 1 9R7u3l1e9z7"[::x]

GRACIAS POR LEER!!!
"Algunos creen que soy un bot, puede que tengan razon"
"Como no se puede igualar a Dios, ya he decidido que hacer, ¡SUPERARLO!"
"La peor de las ignorancias es no saber corregirlas"

*Shadow Scout Team*                                                   You are not allowed to view links. Register or Login

Desconectado Once

  • *
  • Underc0der
  • Mensajes: 383
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil
    • El blog de Once
  • Twitter: @don_once
« Respuesta #3 en: Febrero 06, 2014, 11:20:23 am »
Recibidos hasta ahora un par de codes!  No olviden que hoy cierra el reto.

Saludos!






You are not allowed to view links. Register or Login

Desconectado Once

  • *
  • Underc0der
  • Mensajes: 383
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil
    • El blog de Once
  • Twitter: @don_once
« Respuesta #4 en: Febrero 07, 2014, 02:29:58 am »
No cumplen las condiciones:

Usuario: Bladeyer
Caracteres: 198
Código: Python
  1. from math import *
  2. def fib(n):
  3.         if n <= 70:
  4.                 return floor((((1 + sqrt(5))/2)**n)/sqrt(5) + 0.5)
  5.         else:
  6.                 return fib(n-1) + fib(n-2)
  7.  
  8. def funcion():
  9.     print([fib(i) for i in range(101)])
  10. funcion()

Usuario: Sanko
Caracteres: 75
Código: Python
  1. print int((((1 + 5**0.5) / 2)**100 - (1-((1 + 5**0.5) / 2))**100) / 5**0.5)

Usuario: Juan
Lenguaje: Perl

Código: Perl
  1. # Juan
  2.  
  3. my $n0 = 0;
  4. my $n1 = 1;
  5.  
  6. You are not allowed to view links. Register or Login "$n0\n$n1\n";
  7.  
  8. for my $numero (0..100)
  9. {
  10.     my $resultado = $n0 + $n1;
  11.        
  12.         You are not allowed to view links. Register or Login "$resultado\n";
  13.        
  14.         $n0 = $n1;
  15.         $n1 = $resultado;
  16. }

Cumplen las condiciones

Usuario: deni_celine
Caracteres: 78

Código: Python
  1. 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

Código: Python
  1. def a():
  2.  b = [1,1]
  3.  for x in range(98): b.append(b[-1]+b[-2])
  4.  return b

Ganador
79137913
72 caracteres






You are not allowed to view links. Register or Login

Desconectado Sanko

  • *
  • Underc0der
  • Mensajes: 541
  • Actividad:
    0%
  • Reputación 0
  • ¿Puedes?
    • Ver Perfil
    • Underc0de
« Respuesta #5 en: Febrero 07, 2014, 07:03:40 am »
Esto me pasa por no leer bien el enunciado xd, en clase más de lo mismo.
Congrats
Sigueme en Twitter : @Sankosk
Estos nuevos staff no tienen puta idea XD

Desconectado deni_celine

  • *
  • Underc0der
  • Mensajes: 36
  • Actividad:
    0%
  • Reputación 0
  • un susurro con la fuerza de mil gritos
    • Ver Perfil
« Respuesta #6 en: Febrero 07, 2014, 08:41:57 am »
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
Código: Python
  1. def f():l=[1,1];exec"l.append(l[-1]+l[-2]);"*98;return l
« Última modificación: Febrero 07, 2014, 09:53:20 am por deni_celine »

Conectado 79137913

  • *
  • Co Admin
  • Mensajes: 614
  • Actividad:
    18.33%
  • Reputación 10
  • 4 Esquinas
    • Ver Perfil
    • Doors.Party
    • Email
  • Skype: fg_mdq@hotmail.com
« Respuesta #7 en: Febrero 07, 2014, 10:08:29 am »
HOLA!!!

Wiii Gane :D!!!!!

Código: You are not allowed to view links. Register or Login
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!!!
"Algunos creen que soy un bot, puede que tengan razon"
"Como no se puede igualar a Dios, ya he decidido que hacer, ¡SUPERARLO!"
"La peor de las ignorancias es no saber corregirlas"

*Shadow Scout Team*                                                   You are not allowed to view links. Register or Login

Desconectado Once

  • *
  • Underc0der
  • Mensajes: 383
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil
    • El blog de Once
  • Twitter: @don_once
« Respuesta #8 en: Febrero 07, 2014, 01:49:53 pm »
You are not allowed to view links. Register or Login
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
Código: Python
  1. 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:

Código: Python
  1. def f():l=[1,1];exec"l+=[l[-1]+l[-2]];"*98;return l

Saludos!






You are not allowed to view links. Register or Login

Desconectado deni_celine

  • *
  • Underc0der
  • Mensajes: 36
  • Actividad:
    0%
  • Reputación 0
  • un susurro con la fuerza de mil gritos
    • Ver Perfil
« Respuesta #9 en: Febrero 07, 2014, 02:09:37 pm »
excelente! tendre en cuenta  esa técnica tb. me gusta esta forma de aprender :D

Conectado 79137913

  • *
  • Co Admin
  • Mensajes: 614
  • Actividad:
    18.33%
  • Reputación 10
  • 4 Esquinas
    • Ver Perfil
    • Doors.Party
    • Email
  • Skype: fg_mdq@hotmail.com
« Respuesta #10 en: Febrero 07, 2014, 03:25:10 pm »
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!!!
"Algunos creen que soy un bot, puede que tengan razon"
"Como no se puede igualar a Dios, ya he decidido que hacer, ¡SUPERARLO!"
"La peor de las ignorancias es no saber corregirlas"

*Shadow Scout Team*                                                   You are not allowed to view links. Register or Login

Desconectado Once

  • *
  • Underc0der
  • Mensajes: 383
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil
    • El blog de Once
  • Twitter: @don_once
« Respuesta #11 en: Febrero 07, 2014, 04:16:37 pm »
You are not allowed to view links. Register or Login
excelente! tendre en cuenta  esa técnica tb. me gusta esta forma de aprender :D

You are not allowed to view links. Register or Login
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!






You are not allowed to view links. Register or Login

Desconectado overxfl0w13

  • *
  • Underc0der
  • Mensajes: 26
  • Actividad:
    0%
  • Reputación 0
  • Hola1
    • Ver Perfil
  • Skype: overxfl0w13
« Respuesta #12 en: Febrero 07, 2014, 08:48:19 pm »
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í:

Código: Python
  1. def fib_aux(x,y,n):
  2.         return x if n==0 else fib_aux(y,x+y,n-1)
  3. def fib(n):
  4.         return 1 if n<2 else fib_aux(1,1,n-1)
  5. print [fib(i) for i in range(0,100)]
  6.  

Un saludo :)

Conectado 79137913

  • *
  • Co Admin
  • Mensajes: 614
  • Actividad:
    18.33%
  • Reputación 10
  • 4 Esquinas
    • Ver Perfil
    • Doors.Party
    • Email
  • Skype: fg_mdq@hotmail.com
« Respuesta #13 en: Febrero 10, 2014, 09:59:54 am »
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!!!
"Algunos creen que soy un bot, puede que tengan razon"
"Como no se puede igualar a Dios, ya he decidido que hacer, ¡SUPERARLO!"
"La peor de las ignorancias es no saber corregirlas"

*Shadow Scout Team*                                                   You are not allowed to view links. Register or Login

Desconectado overxfl0w13

  • *
  • Underc0der
  • Mensajes: 26
  • Actividad:
    0%
  • Reputación 0
  • Hola1
    • Ver Perfil
  • Skype: overxfl0w13
« Respuesta #14 en: Febrero 10, 2014, 01:27:56 pm »
You are not allowed to view links. Register or Login
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:
Código: Python
  1. #!/usr/bin/env python
  2.  
  3. import time
  4.  
  5.  
  6. def fib_aux(x,y,n):
  7.         return x if n==0 else fib_aux(y,x+y,n-1)
  8. def fib(n):
  9.         return 1 if n<2 else fib_aux(1,1,n-1)
  10.  
  11. def a():
  12.     b = [1,1]
  13.     for x in range(700): b.append(b[-1]+b[-2])
  14.     return b
  15.    
  16. ttot = 0
  17. for i in range(0,1000):
  18.         it = time.time()
  19.         fib(700)
  20.         et = time.time()
  21.         ttot += et-it
  22. print ttot/1000
  23.  
  24. ttot = 0
  25. for i in range(0,1000):
  26.         it = time.time()
  27.         a()
  28.         et = time.time()
  29.         ttot += et-it
  30. print ttot/1000

Resultados:
                      · 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:
Código: Python
  1. import time
  2.  
  3.  
  4. def fib_aux(x,y,n):
  5.         return x if n==0 else fib_aux(y,x+y,n-1)
  6. def fib(n):
  7.         return 1 if n<2 else fib_aux(1,1,n-1)
  8.  
  9. def a():
  10.     b = [1,1]
  11.     for x in range(100): b.append(b[-1]+b[-2])
  12.     return b
  13.    
  14. ttot = 0
  15. for i in range(0,10000):
  16.         it = time.time()
  17.         t = [fib(n) for n in range(0,100)]
  18.         et = time.time()
  19.         ttot += et-it
  20. print ttot/10000
  21.  
  22. ttot = 0
  23. for i in range(0,10000):
  24.         it = time.time()
  25.         t = a()
  26.         et = time.time()
  27.         ttot += et-it
  28. print ttot/10000

Resultados:   
                      · 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
« Última modificación: Febrero 10, 2014, 01:38:08 pm por overxfl0w13 »

Conectado 79137913

  • *
  • Co Admin
  • Mensajes: 614
  • Actividad:
    18.33%
  • Reputación 10
  • 4 Esquinas
    • Ver Perfil
    • Doors.Party
    • Email
  • Skype: fg_mdq@hotmail.com
« Respuesta #15 en: Febrero 10, 2014, 03:26:35 pm »
HOLA!!!

Es cierto, se ve que solo querias mostrar una manera recursiva optimizada no un codigo mas eficiente que el otro.

GRACIAS POR LEER!!!
"Algunos creen que soy un bot, puede que tengan razon"
"Como no se puede igualar a Dios, ya he decidido que hacer, ¡SUPERARLO!"
"La peor de las ignorancias es no saber corregirlas"

*Shadow Scout Team*                                                   You are not allowed to view links. Register or Login

 

¿Te gustó el post? COMPARTILO!



[Código-Python] Sucesión Fibonacci - JaAViEr

Iniciado por JaAViEr

Respuestas: 0
Vistas: 898
Último mensaje Junio 03, 2011, 02:16:08 am
por JaAViEr