Hay una pregunta muy conocido aquí que pregunta por un corto (menos caracteres) generador de secuencia de Fibonacci.

Me gustaría saber si alguien puede generar solo los primeros N elementos, de la secuencia de Fibonacci, en un espacio muy corto. Estoy tratando de hacerlo en Python, pero estoy interesado en cualquier respuesta corta, en cualquier idioma. La función F (N) genera los primeros N elementos de la secuencia, los devuelve como el retorno de la función o los imprime.

Curiosamente, parece que las respuestas de código de golf comienzan con 1 1 2, en lugar de 0 1 1 2. ¿Es una convención en código-golf o programación en general? (Wikipedia dice que la secuencia de Fibonacci comienza con cero).

Muestra de Python (primeros 5 elementos):

def f(i,j,n):
    if n>0:
        print i;
        f(j,i+j,n-1)
f(1,1,5)

C

No me molesté en contar, pero aquí hay un ejemplo divertido:

f(n){return n<4?1:f(--n)+f(--n);}
main(a,b){for(scanf("%d",&b);a++<=b;printf("%d ",f(a)));}

Prueba de que funciona.

Estoy bastante orgulloso de esto: me aburrí, así que reorganicé mi código (con algunas pequeñas adiciones) para que cada línea representara un valor en la secuencia de Fibonacci.

                         #                                // 1
                         f                                // 1
                         //                               // 2
                        (n)                               // 3
                       {/**/                              // 5
                      return n                            // 8
                    <2 ? 1:f(--n)                         // 13
                +f(--n); } main(a, b)                     // 21
          {a = 0, b = 0;scanf("%d",&b); for(              // 34
;a < b; a+=1) { int res = f(a); printf("%d ", res); } }   // 55

Prueba de que funciona.

Haskell (26)

Sorprendentemente, este es solo un personaje más largo que la solución J.

f = (`tomar`s)
s = 0: scanl (+) 1s

Me afeito algunos caracteres al:

1. Utilizando takecomo operador binario;
2. Usando en scanllugar del detallado zipWith.

Aquí hay una Python de una sola línea. Utiliza punto flotante, por lo que puede haber algunos npara los que ya no es preciso.

F=lambda n:' '.join('%d'%(((1+5**.5)/2)**i/5**.5+.5)for i in range(n))

F(n)devuelve una cadena que contiene los primeros nnúmeros de Fibonacci separados por espacios.

GolfScript, 16 caracteres

~0 1@{.2$+}*;;]`

Salida de ejemplo:

$ ruby golfscript.rb ~/Code/golf/fib.gs <<< "12"
[0 1 1 2 3 5 8 13 21 34 55 89]

Perl, 50 caracteres.

sub f{($a,$b,$c)=@_;$c--&&say($a)&&f($b,$a+$b,$c)}

Scala 71:

def f(c:Int,a:Int=0,b:Int=1):Unit={println(a);if(c>0)f(c-1,b,a+b)};f(9)

huellas dactilares

0
1
1
2
3
5
8
13
21
34

Perl, 29 28 bytes

perl -E'say$b+=$;=$b-$;for-pop..--$;' 8
1
1
2
3
5
8
13
21

Explicación

Esto se basa en la $b += $a = $b-$arecurrencia clásica que funciona de la siguiente manera:

• Al comienzo de cada ciclo $acontiene F(n-2)y $bcontieneF(n)
• Después $a = $b-$a $acontieneF(n-1)
• Después $b += $a $bcontieneF(n+1)

El problema aquí es la inicialización. La forma clásica es $b += $a = $b-$a || 1pero luego la secuencia continúa1 2 3 5 ...

Al extender la secuencia de Fibonacci a la izquierda:

... 5 -3 2 -1 1 0 1 1 2 3 5 ...

ves que el punto de partida adecuado es $a = -1y $b = 0. La inicialización de $ a se puede combinar con la configuración del bucle

Finalmente reemplace $apor $;para deshacerse del espacio antes delfor

Te puedo dar una solución Python de dos líneas. Esto los devolverá como una lista.

f = lambda n: 1 if n < 2 else f(n-1) + f(n-2)
g = lambda m: map(f, range(0,m))

print g(5)

Podría imprimirlos agregando otro mapa para hacerlos cadenas y luego agregando una unión, pero eso me parece innecesario.

Desafortunadamente no sé cómo poner una lambda recursiva map, así que estoy atrapado en dos líneas.

Python (78 caracteres)

He utilizado la fórmula de Binet para calcular los números de Fibonacci -

[(1 + sqrt (5)) ^ n- (1-sqrt (5) ^ n] / [(2 ^ n) sqrt (5)]

No es tan pequeño algunas de las otras respuestas aquí, pero chico, es rápido

n=input()
i=1
x=5**0.5
while i<=n:
    print ((1+x)**i-(1-x)**i)/((2**i)*x)
    i+=1

Esquema

Esto se optimiza utilizando la recursividad de cola:

(define (fib n)
  (let fib ([n n] [a 0] [b 1])
    (if (zero? n) (list a)
        (cons a (fib (- n 1) b (+ a b))))))

Haskell

fib n = take n f
f = 0:1:zipWith (+) f (tail f)

Prueba de que funciona .

J, 25 caracteres

Me doy cuenta de que las soluciones J probablemente no sean lo que buscas, pero aquí hay una de todos modos. :-)

0 1(],+/&(_2&{.))@[&0~2-~

Uso:

    0 1(],+/&(_2&{.))@[&0~2-~ 6
0 1 1 2 3 5
    0 1(],+/&(_2&{.))@[&0~2-~ 10
0 1 1 2 3 5 8 13 21 34

Cómo funciona:

Comenzando desde la derecha (porque los programas J se leen de derecha a izquierda),

2-~ 6El ~operador invierte el argumento al verbo, por lo que esto es lo mismo que6-2

Ignorando la sección entre paréntesis por el momento, 0 1(...)@[&0~ xtoma el verbo entre paréntesis y lo ejecuta xveces usando la lista 0 1como entrada; ~nuevamente invierte los argumentos aquí, dando x (...)@[&0 ] 0 1, lo que significa que puedo mantener la entrada al final de la función.

Dentro de los corchetes hay un tenedor ],+/&(_2&{.)que se compone de tres verbos ], ,y +/&(_2&{.).

Un tenedor toma tres verbos a b cy los usa así: (x a y) b (x c y)dónde xy yson los argumentos del tenedor. El ,es el verbo central en esta bifurcación y une los resultados de x ] yy x +/&(_2&{.) yjuntos.

]devuelve el argumento izquierdo sin modificaciones, por lo que se x ] yevalúa como x.

+/&(_2&{.)toma los dos últimos elementos de la lista dada (_2&{.), en este caso 0 1, y luego los agrega +/(los &s simplemente actúan como pegamento).

Una vez que el verbo ha funcionado una vez que el resultado se retroalimenta para la siguiente ejecución, genera la secuencia.

TI-Basic, 43 caracteres

:1→Y:0→X
:For(N,1,N
:Disp X
:Y→Z
:X+Y→Y
:Z→X
:End

Este código puede insertarse directamente en el programa principal o convertirse en un programa separado al que hace referencia el primero.

APL (33)

{⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}

Uso:

   {⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}7
0 1 1 2 3 5 8

Pitón (55)

a,b=0,1

for i in range(int(input())):a,b=b,a+b;print(b)

Powershell - 35 caracteres

Powershell acepta entradas de canalización , por lo que creo que n |in n | <mycode>no debería estar en contra de mi cuenta, sino que es solo una parte de iniciar una "función" en el lenguaje.

La primera solución supone que comenzamos en 0:

%{for($2=1;$_--){($2=($1+=$2)-$2)}}

La segunda solución supone que podemos comenzar en 1:

%{for($2=1;$_--){($1=($2+=$1)-$1)}}

Ejemplo de invocación: 5 | %{for($2=1;$_--){($1=($2+=$1)-$1)}}

Rendimientos:

1
1
2
3
5

Curiosamente, intentos de evitar la sobrecarga de la for()bucle resultaron en el mismo recuento de caracteres: %{$2=1;iex('($1=($2+=$1)-$1);'*$_)}.

Python, 43 caracteres

Aquí hay tres frases básicas fundamentalmente diferentes que no usan la fórmula de Binet.

f=lambda n:reduce(lambda(r,a,b),c:(r+[b],a+b,a),'.'*n,([],1,0))[0]
f=lambda n:map(lambda x:x.append(x[-1]+x[-2])or x,[[0,1]]*n)[0]
def f(n):a=0;b=1;exec'print a;a,b=b,a+b;'*n

Nunca he abusado reducetanto.

dc, 32 caracteres:

En realidad, esto siempre mostrará los dos primeros 1, por lo que la función solo funciona como se esperaba para N> = 2 .

?2-sn1df[dsa+plarln1-dsn0<q]dsqx

C, 75 caracteres:

No es tan genial como la respuesta aceptada, pero más corto y mucho más rápido:

main(n,t,j,i){j=0,i=scanf("%d",&n);while(n--)t=i,i=j,printf("%d\n",j+=t);}

CL, 64 caracteres:

Uno de mis marcadores más utilizados este semestre tiene un ejemplo interesante que es más corto que muchos de los otros aquí, y es solo una invocación directa de la loopmacro, ¡básicamente solo una declaración! Despojado de todo el espacio en blanco que pude:

(loop repeat n for x = 0 then y and y = 1 then(+ x y)collect y)

¡Bastante corto, agradable y legible! Para leer la entrada, n (incluidos los espacios en blanco circundantes) puede reemplazarse (read), agregando 3 caracteres.

FALSO, 28 bytes

0 1- 1 10[$][@@$@+$." "@1-]#

Python 2, 38 bytes

Una mejora en una solución publicada anteriormente:

a=b=1
exec'print a;a,b=b,a+b;'*input()

Esto usa execuna multiplicación de cuerdas para evitar bucles.

Python 3, 46 bytes

No tan eficiente en Python 3:

a=b=1
exec('print(a);a,b=b,a+b;'*int(input()))

C99, 58 caracteres

La siguiente función llena una matriz de enteros con los primeros nvalores de la secuencia de Fibonacci que comienzan con 0.

void f(int*a,int n){for(int p=0,q=1;n--;q+=*a++)*a=p,p=q;}

Pruebe el arnés, tomando ncomo argumento de línea de comando:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
     int n = (argc > 1) ? atoi(argv[1]) : 1;
     int a[n];
     f(a, n);
     for (int i = 0; i < n; ++i)
          printf("%d\n", a[i]);
}

CoffeeScript, 48

f=(n,i=1,j=1)->(console.log i;f n-1,j,i+j)if n>0

65 en js:

function f(n,i,j){if(n>0)console.log(i),f(n-1,(j=j||1),(i||1)+j)}

PHP, 87

function f($n,$a=array(0,1)){echo' '.$a[0];$n>0?f(--$n,array($a[1],array_sum($a))):'';}

Usos array_sumy función recursiva para generar series.

P.ej:

 $ php5 fibo.php 9
 0 1 1 2 3 5 8 13 21 34 

F #, 123

let f n = Seq.unfold(fun (i,j)->Some(i,(j,i+j)))(0,1)|>Seq.take n
f 5|>Seq.iter(fun x->printfn "%i" x)

Scala, 65 caracteres

(Seq(1,0)/:(3 to 9)){(s,_)=>s.take(2).sum+:s}.sorted map println

Esto imprime, por ejemplo, los primeros 9 números de Fibonacci. Para una versión más útil que tome la longitud de secuencia de la entrada de la consola, se requieren 70 caracteres:

(Seq(1,0)/:(3 to readInt)){(s,_)=>s.take(2).sum+:s}.sorted map println

Tenga cuidado con el uso de un Rango que limita esto a los valores Int.

Q 24

f:{{x,sum -2#x}/[x;0 1]}

Primeros n números de fibonacci

Lua, 85 bytes

Estoy aprendiendo Lua, así que me gustaría agregar este idioma al grupo.

function f(x)
    return (x<3) and 1 or f(x-1)+f(x-2)
end
for i=1,io.read() do
    print(f(i))
end

y todo tomó 85 caracteres, con el parámetro como argumento de línea de comando. Otro buen punto es que es fácil de leer.

FALSO, 20 caracteres

^1@[1-$][@2ø+$.\9,]#

La entrada debe estar en la pila antes de ejecutar esto.

Pyt , 3 bytes

ř⁻Ḟ

Pruébalo en línea!

ř crea una matriz [1, 2, 3, ..., x]
⁻ Disminuye cada elemento una vez (ya que Ḟ es 0 indexado)
Ḟ por cada elemento en x lo convierte en su equivalente de Fibonacci

código de máquina x86 - 379 bytes

La versión con encabezados ELF con 484 bytes:

00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 0300 0100 0000 c080 0408 3400 0000  ............4...
00000020: 0000 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
00000030: 0000 0000 0100 0000 0000 0000 0080 0408  ................
00000040: 0000 0000 e401 0000 0010 0000 0500 0000  ................
00000050: 0010 0000 0100 0000 0000 0000 0090 0408  ................
00000060: 0000 0000 0000 0000 0000 1000 0600 0000  ................
00000070: 0010 0000 0000 0000 0000 0000 0000 0000  ................
00000080: 51b9 0090 0408 8801 31c0 ba01 0000 00eb  Q.......1.......
00000090: 0351 89c1 31c0 89c3 43b0 04cd 8031 c099  .Q..1...C....1..
000000a0: 4259 c300 0000 0000 0000 0000 0000 0000  BY..............
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000c0: 31c0 9942 b903 9004 08c6 4101 0ac6 4102  1..B......A...A.
000000d0: 01c6 4103 013a 7103 0f84 ff00 0000 3a71  ..A..:q.......:q
000000e0: 0374 2680 4103 050f b641 036b c008 0041  .t&.A....A.k...A
000000f0: 048a 4104 e887 ffff ff80 6904 30c6 4103  ..A.......i.0.A.
00000100: 0183 e903 3a71 0375 da8a 4104 e86f ffff  ....:q.u..A..o..
00000110: ff3a 7106 0f84 ba00 0000 0fb6 4105 8841  .:q.........A..A
00000120: 060f b641 0788 4105 0fb6 4107 0041 06c6  ...A..A...A..A..
00000130: 4107 003a 7106 0f84 8800 0000 c641 0701  A..:q........A..
00000140: fe49 063a 7106 0f84 7800 0000 c641 0702  .I.:q...x....A..
00000150: fe49 063a 7106 0f84 6800 0000 c641 0703  .I.:q...h....A..
00000160: fe49 063a 7106 0f84 5800 0000 c641 0704  .I.:q...X....A..
00000170: fe49 063a 7106 744c c641 0705 fe49 063a  .I.:q.tL.A...I.:
00000180: 7106 7440 c641 0706 fe49 063a 7106 7434  [email protected].:q.t4
00000190: c641 0707 fe49 063a 7106 7428 c641 0708  .A...I.:q.t(.A..
000001a0: fe49 063a 7106 741c c641 0709 fe49 063a  .I.:q.t..A...I.:
000001b0: 7106 7410 fe41 08fe 4109 fe49 060f b641  q.t..A..A..I...A
000001c0: 0688 4107 c641 0601 83c1 033a 7106 0f85  ..A..A.....:q...
000001d0: 46ff ffff 3a71 030f 8501 ffff ffb3 0031  F...:q.........1
000001e0: c040 cd80                                .@..

Versión sin encabezado (esa es la que se debe calificar):

00000000: 67c6 4101 0a67 c641 0201 67c6 4103 0167  g.A..g.A..g.A..g
00000010: 3a71 030f 842a 0167 3a71 0374 2e67 8041  :q...*.g:q.t.g.A
00000020: 0305 6667 0fb6 4103 666b c008 6700 4104  ..fg..A.fk..g.A.
00000030: 678a 4104 e80d 0167 8069 0430 67c6 4103  g.A....g.i.0g.A.
00000040: 0166 83e9 0367 3a71 0375 d267 8a41 04e8  .f...g:q.u.g.A..
00000050: f200 673a 7106 0f84 df00 6667 0fb6 4105  ..g:q.....fg..A.
00000060: 6788 4106 6667 0fb6 4107 6788 4105 6667  g.A.fg..A.g.A.fg
00000070: 0fb6 4107 6700 4106 67c6 4107 0067 3a71  ..A.g.A.g.A..g:q
00000080: 060f 84a3 0067 c641 0701 67fe 4906 673a  .....g.A..g.I.g:
00000090: 7106 0f84 9200 67c6 4107 0267 fe49 0667  q.....g.A..g.I.g
000000a0: 3a71 060f 8481 0067 c641 0703 67fe 4906  :q.....g.A..g.I.
000000b0: 673a 7106 0f84 7000 67c6 4107 0467 fe49  g:q...p.g.A..g.I
000000c0: 0667 3a71 0674 6167 c641 0705 67fe 4906  .g:q.tag.A..g.I.
000000d0: 673a 7106 7452 67c6 4107 0667 fe49 0667  g:q.tRg.A..g.I.g
000000e0: 3a71 0674 4367 c641 0707 67fe 4906 673a  :q.tCg.A..g.I.g:
000000f0: 7106 7434 67c6 4107 0867 fe49 0667 3a71  q.t4g.A..g.I.g:q
00000100: 0674 2567 c641 0709 67fe 4906 673a 7106  .t%g.A..g.I.g:q.
00000110: 7416 67fe 4108 67fe 4109 67fe 4906 6667  t.g.A.g.A.g.I.fg
00000120: 0fb6 4106 6788 4107 67c6 4106 0166 83c1  ..A.g.A.g.A..f..
00000130: 0367 3a71 060f 8521 ff67 3a71 030f 85d6  .g:q...!.g:q....
00000140: fe00 0000 6651 66b9 7801 0000 6788 0166  ....fQf.x...g..f
00000150: 31c0 66ba 0100 0000 eb05 6651 6689 c166  1.f.......fQf..f
00000160: 31c0 6689 c366 43b0 04cd 8066 31c0 6699  1.f..fC....f1.f.
00000170: 6642 6659 c300 0000 0000 00              fBfY.......

∞$\mathrm{\infty }$$\infty$