La secuencia de Fibonacci es una secuencia de números, donde cada número de la secuencia es la suma de los dos números que la preceden. Los primeros dos números en la secuencia son ambos 1.

Aquí están los primeros términos

1 1 2 3 5 8 13 21 34 55 89 ...

Escriba el código más corto que:

• Genera la secuencia de Fibonacci sin fin.

• Dado ncalcula el ntérmino th de la secuencia. (1 o cero indexado)

Puede usar formas estándar de entrada y salida.

(Di ambas opciones en caso de que una sea más fácil de hacer en el idioma elegido que la otra).

Para la función que toma un n, debe admitirse un valor de retorno razonablemente grande (el número de Fibonacci más grande que se ajuste al tamaño de palabra normal de su computadora, como mínimo).

Tabla de clasificación

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}

body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

Perl 6, 10 caracteres:

Lista de secuencias de fibonacci infinita anónima:

^2,*+*...*

Igual que:

0, 1, -> $x, $y { $x + $y } ... Inf;

Entonces, puede asignarlo a una matriz:

my @short-fibs = ^2, * + * ... *;

o

my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;

Y obtenga los primeros once valores (de 0 a 10) con:

say @short-fibs[^11];

o con:

say @fibs[^11];

Espere, también puede obtener los primeros 50 números de la lista anónima:

say (^2,*+*...*)[^50]

Eso devuelve:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
63245986 102334155 165580141 267914296 433494437 701408733 1134903170 
1836311903 2971215073 4807526976 7778742049

Y algunos puntos de referencia simples:

real    0m0.966s
user    0m0.842s
sys     0m0.080s

Con:

$ time perl6 -e 'say (^2, *+* ... *)[^50]'

EOF

Brainfuck, 22 golpes

+>++[-<<[->+>+<<]>>>+]

Genera la secuencia de Fibonacci moviéndose gradualmente a través de la cinta de memoria.

Haskell, 17 15 14 caracteres

f=1:scanl(+)1f

Pruébalo en línea!

C # 4, 58 bytes

Stream (69; 65 si está tipeado débilmente IEnumerable)

(Asumiendo una usingdirectiva para System.Collections.Generic.)

IEnumerable<int>F(){int c=0,n=1;for(;;){yield return c;n+=c;c=n-c;}}

Valor único (58)

int F(uint n,int x=0,int y=1){return n<1?x:F(n-1,y,x+y);}

GolfScript, 12

¡Ahora, solo 12 caracteres!

1.{[email protected]+.}do

> <> - 15 caracteres

0:nao1v LF a+@:n:<o

J, 10 caracteres

Usar el cálculo incorporado de los coeficientes de la serie Taylor, por lo que quizás sea poco engañoso Lo aprendí aquí .

   (%-.-*:)t.

   (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075

Hexagony ,18 años 14 12

Gracias Martin por 6 bytes!

1="/}.!+/M8;

Expandido:

  1 = "
 / } . !
+ / M 8 ;
 . . . .
  . . .

Pruébalo en línea

Viejo, contesta. Esto se deja porque las imágenes y la explicación pueden ser útiles para los nuevos usuarios de Hexagony.

!).={!/"*10;$.[+{]

Expandido:

  ! ) .
 = { ! /
" * 1 0 ;
 $ . [ +
  { ] .

Esto imprime la secuencia de Fibonacci separada por nuevas líneas.

Pruébalo en línea! Sin embargo, tenga cuidado, al intérprete en línea no le gusta la salida infinita.

Explicación

Hay dos "subrutinas" para este programa, cada una de las cuales es ejecutada por una de las dos IP utilizadas. La primera rutina imprime nuevas líneas y la segunda realiza el cálculo y la salida de Fibonacci.

La primera subrutina comienza en la primera línea y se mueve de izquierda a derecha todo el tiempo. Primero imprime el valor en el puntero de memoria (inicializado a cero), y luego incrementa el valor en el puntero de memoria en 1. Después del no-op, el IP salta a la tercera línea que primero cambia a otra celda de memoria, luego imprime una nueva línea. Como una nueva línea tiene un valor positivo (su valor es 10), el código siempre saltará a la quinta línea, a continuación. La quinta línea devuelve el puntero de memoria a nuestro número de Fibonacci y luego cambia a la otra subrutina. Cuando regresemos de esta subrutina, la IP volverá a la tercera línea, después de ejecutar un no-op.

La segunda subrutina comienza en la esquina superior derecha y comienza a moverse hacia el sudeste. Después de un no-op, nos vemos obligados a viajar al oeste a lo largo de la segunda línea. Esta línea imprime el número actual de Fibonacci, antes de mover el puntero de memoria a la siguiente ubicación. Luego, el IP salta a la cuarta línea, donde calcula el siguiente número de Fibonacci usando los dos anteriores. Luego devuelve el control a la primera subrutina, pero cuando recupera el control del programa, continúa hasta que se encuentra con un salto, donde rebota sobre el espejo que originalmente se usó para apuntarlo al Oeste, ya que regresa a la segunda línea.

Imágenes bonitas preliminares!

El lado izquierdo de la imagen es el programa, el lado derecho representa la memoria. El cuadro azul es la primera IP, y ambas IP apuntan a la siguiente instrucción que se ejecutará.

Nota: Las imágenes solo pueden parecer bonitas para las personas que tienen una habilidad similar limitada con los programas de edición de imágenes: PI agregará al menos 2 iteraciones más para que el uso del *operador sea más claro.

Nota 2: solo vi la respuesta de alephalpha después de escribir la mayor parte de esto, pensé que todavía era valioso debido a la separación, pero las partes reales de Fibonacci de nuestros programas son muy similares. Además, este es el programa de Hexagony más pequeño que he visto haciendo uso de más de una IP, así que pensé que sería bueno mantenerlo de todos modos: P

VACA , 108

 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo

Python 2, 34 bytes

Python, usando la recursividad ... ¡aquí viene un StackOverflow!

def f(i,j):print i;f(j,i+j)
f(1,1)

Jalea , 3 bytes

+¡1

Pruébalo en línea!

Cómo funciona

+¡1    Niladic link. No implicit input.
       Since the link doesn't start with a nilad, the argument 0 is used.

  1    Yield 1.
+      Add the left and right argument.
 ¡     For reasons‡, read a number n from STDIN.
       Repeatedly call the dyadic link +, updating the right argument with
       the value of the left one, and the left one with the return value.

^‡ ¡ mira los dos enlaces a la izquierda. Como solo hay uno, tiene que ser el cuerpo del bucle. Por lo tanto, se lee un número desde la entrada. Como no hay argumentos de línea de comandos, ese número se lee desde STDIN.

Golfscript - número único - 12/12/10

12 caracteres para tomar la entrada de stdin:

~0 1@{.@+}*;

11 caracteres para la entrada ya en la pila:

0 1@{.@+}*;

10 caracteres para definir 1 como el número 0 de Fibonacci:

1.@{.@+}*;

Rubí

29 27 25 24 caracteres

p a=b=1;loop{b=a+a=p(b)}

Editar: lo convirtió en un bucle infinito. ;)

Mathematica, 9 caracteres

Fibonacci

Si las funciones integradas no están permitidas, aquí hay una solución explícita:

Mathematica, 33 32 31 caracteres

#&@@Nest[{+##,#}&@@#&,{0,1},#]&

DC (20 bytes)

Como beneficio adicional, incluso está ofuscado;)

zzr[dsb+lbrplax]dsax

EDITAR: Puedo señalar que imprime todos los números en la secuencia de Fibonacci, si espera lo suficiente.

Preludio , 12 bytes

Uno de los pocos desafíos donde Prelude es realmente bastante competitivo:

1(v!v)
  ^+^

Esto requiere el intérprete de Python que imprime los valores como números decimales en lugar de caracteres.

Explicación

En Prelude, todas las líneas se ejecutan en paralelo, con el puntero de instrucción atravesando las columnas del programa. Cada línea tiene su propia pila que se inicializa a cero.

1(v!v)
  ^+^
| Push a 1 onto the first stack.
 | Start a loop from here to the closing ).
  | Copy the top value from the first stack to the second and vice-versa.
   | Print the value on the first stack, add the top two numbers on the second stack.
    | Copy the top value from the first stack to the second and vice-versa.

El bucle se repite para siempre, porque la primera pila nunca tendrá un 0top.

Tenga en cuenta que esto inicia la secuencia de Fibonacci desde 0.

Hexagonía , 6 bytes.

No competir porque el lenguaje es más nuevo que la pregunta.

1.}=+!

Sin golf:

  1 .
 } = +
  ! .

Imprime la secuencia de Fibonacci sin ningún separador.

TI-BASIC, 11

Por el legendario golfista TI-BASIC Kenneth Hammond ("Weregoose"), desde este sitio . Se ejecuta en el tiempo O (1) y considera que 0 es el término 0 de la secuencia de Fibonacci.

int(round(√(.8)cosh(Anssinh‾¹(.5

Usar:

2:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     1

12:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     144

¿Como funciona esto? Si haces los cálculos, resulta que sinh‾¹(.5)es igual a ln φ, por lo que es una versión modificada de la fórmula de Binet que se redondea en lugar de usar el (1/φ)^ntérmino de corrección. El round((redondear a 9 decimales) es necesario para evitar errores de redondeo.

K - 12

Calcula el número de Fibonacci ny n-1.

{x(|+\)/0 1}

Solo el nthnúmero de Fibonacci.

{*x(|+\)/0 1}

Julia, 18 bytes

n->([1 1;1 0]^n)[]

Java, 55

No puedo competir con la concisión de la mayoría de los idiomas aquí, pero puedo ofrecer una forma sustancialmente diferente y posiblemente mucho más rápida (tiempo constante) para calcular el enésimo número:

Math.floor(Math.pow((Math.sqrt(5)+1)/2,n)/Math.sqrt(5))

nes la entrada (int o long), comenzando con n = 1. Utiliza la fórmula y las rondas de Binet en lugar de la resta.

Ruby, 25 caracteres

La respuesta de st0le se acortó.

p 1,a=b=1;loop{p b=a+a=b}

FAC: APL funcional, 4 caracteres (!!)

No es mío, por lo tanto publicado como wiki de la comunidad. FAC es un dialecto de APL que Hai-Chen Tu aparentemente sugirió como su disertación de doctorado en 1985. Más tarde escribió un artículo junto con Alan J. Perlis llamado " FAC: un lenguaje APL funcional ". Este dialecto de APL utiliza "matrices diferidas" y permite matrices de longitud infinita. Define un operador "iter" ( ⌼) para permitir la definición compacta de algunas secuencias recursivas.

El caso monádico ("unario") ⌼es básicamente el de Haskell iteratey se define como (F⌼) A ≡ A, (F A), (F (F A)), …. El caso ( "binario") diádica se define un tanto análoga por dos variables: A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …. ¿Por qué es útil esto? Bueno, resulta que este es precisamente el tipo de recurrencia que tiene la secuencia de Fibonacci. De hecho, uno de los ejemplos dados es

1+⌼1

produciendo la secuencia familiar 1 1 2 3 5 8 ….

Entonces, allí está, posiblemente la implementación de Fibonacci más corta posible en un lenguaje de programación no novedoso. :RE

R, 40 bytes

No he visto una solución R, así que:

f=function(n)ifelse(n<3,1,f(n-1)+f(n-2))

05AB1E, 7 bytes

Código:

1$<FDr+

Pruébalo en línea!

Dodos , 26 bytes

	dot F
F
	F dip
	F dip dip

Pruébalo en línea!

Cómo funciona

La función F hace todo el trabajo pesado; se define recursivamente de la siguiente manera.

F(n) = ( F(|n - 1|), F(||n - 1| - 1|) )

Siempre que n> 1 , tenemos | n - 1 | = N - 1 <n y || n - 1 | - 1 | = | n - 1 - 1 | = n - 2 <n , entonces la función retorna (F (n - 1), F (n - 2)) .

Si n = 0 , entonces | n - 1 | = 1> 0 ; si n = 1 , entonces || n - 1 | - 1 | = | 0 - 1 | = 1 = 1 . En ambos casos, los intentos de llamadas recursivas F (1) generan una excepción de Rendición , por lo que F (0) devuelve 0 y F (1) devuelve 1 .

Por ejemplo, F (3) = (F (1), F (2)) = (1, F (0), F (1)) = (1, 0, 1) .

Finalmente, la función principal se define como

main(n) = sum(F(n))

por lo que se suma todas las coordenadas del vector devuelto por F .

Por ejemplo, main (3) = sum (F (3)) = sum (1, 0, 1) = 2 .

GolfScript, 13 caracteres

2,~{..p@+.}do

(Mi respuesta de una pregunta anterior de Stack Overflow ).

Desmos , 61 bytes

Golfed

Haz clic en el add sliderbotón para n.

p=.5+.5\sqrt{5}
n=0
f=5^{-.5}\left(p^n-\left(-p\right)^{-n}\right)

La última línea es la salida.

Sin golf

Es una función.

\phi =\frac{1+\sqrt{5}}{2}
f_{ibonacci}\left(n\right)=\frac{\phi ^n-\left(-\phi \right)^{-n}}{\sqrt{5}}

Cubix , 10 bytes

Respuesta no competitiva porque el lenguaje es más nuevo que la pregunta.

Cubix es un nuevo lenguaje bidimensional de @ETHproductions donde el código está envuelto en un cubo del tamaño adecuado.

;.o.ON/+!)

Pruébalo en línea

Esto se envuelve en un cubo de 2 x 2 de la siguiente manera

    ; .
    o .
O N / + ! ) . .
. . . . . . . .
    . .
    . .

• O dar salida al valor de los TOS
• N empujar nueva línea en la pila
• / reflexionar hacia el norte
• o dar salida al carácter de los TOS
• ; pop TOS
• / reflexionar hacia el este después de dar la vuelta al cubo
• + agregar los 2 valores principales de la pila
• ! omita el siguiente comando si TOS es 0
• ) incremente el TOS en 1. Esto inicia la secuencia esencialmente.

Este es un bucle sin fin que imprime la secuencia con un separador de nueva línea. Aprovecha el hecho de que la mayoría de los comandos no muestran los valores de la pila.
Si se ignora el separador, esto se puede hacer con 5 bytes.O+!)

Brainfuck, 16,15, 14/13 caracteres

+[[->+>+<<]>]  

Genera la secuencia de Fibonacci y no imprime nada. Además, es más corto que el de arriba.

+[.[->+>+<<]>]   

Este tiene 14 caracteres pero imprime caracteres ASCII con los valores de la secuencia de Fibonacci.