La séquence de Fibonacci est une séquence de nombres, où chaque nombre de la séquence est la somme des deux nombres qui le précèdent. Les deux premiers chiffres de la séquence sont tous deux 1.

Voici les premiers termes

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

Écrivez le code le plus court qui soit:

• Génère la séquence de Fibonacci sans fin.

• Given ncalcule le nthème de la séquence. (1 ou zéro indexé)

Vous pouvez utiliser des formes standard d’entrée et de sortie.

(J'ai donné les deux options au cas où l'une est plus facile à faire que l'autre dans la langue de votre choix.)

Pour la fonction prenant un n, une valeur de retour raisonnablement grande (le plus grand nombre de Fibonacci qui correspond au moins à la taille de mot normale de votre ordinateur) doit être prise en charge.

Classement

/* 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 caractères:

Liste de séquence infinie anonyme de fibonacci:

^2,*+*...*

Pareil que:

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

Donc, vous pouvez l'assigner à un tableau:

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

ou

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

Et obtenez les onze premières valeurs (de 0 à 10) avec:

say @short-fibs[^11];

ou avec:

say @fibs[^11];

Attendez, vous pouvez aussi obtenir les 50 premiers numéros de la liste anonyme:

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

Cela retourne:

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

Et quelques repères simples:

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

Avec:

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

EOF

Brainfuck, 22 coups

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

Génère la séquence de Fibonacci se déplaçant progressivement sur la bande mémoire.

Haskell, 17 15 14 caractères

f=1:scanl(+)1f

Essayez-le en ligne!

C # 4, 58 octets

Stream (69; 65 si faiblement typé IEnumerable)

(En supposant une usingdirective pour System.Collections.Generic.)

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

Valeur unique (58)

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

GolfScript, 12

Maintenant, juste 12 caractères!

1.{[email protected]+.}do

> <> - 15 caractères

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

J, 10 caractères

En utilisant le calcul intégré des coefficients de la série de Taylor alors peut-être un peu tricheur. Appris ici .

   (%-.-*:)t.

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

Hexagone ,18 14 12

Merci Martin pour 6 octets!

1="/}.!+/M8;

Étendu:

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

Essayez-le en ligne

Vieux, réponds. Ceci est laissé car les images et l'explication pourraient être utiles aux nouveaux utilisateurs d'Hexagony.

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

Étendu:

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

Ceci affiche la séquence de Fibonacci séparée par des nouvelles lignes.

Essayez-le en ligne! Attention cependant, l'interprète en ligne n'aime pas vraiment les sorties infinies.

Explication

Il y a deux "sous-routines" à ce programme, chacune étant exécutée par l'un des deux IP utilisés. La première routine imprime les nouvelles lignes et la seconde effectue le calcul et la sortie de Fibonacci.

Le premier sous-programme commence sur la première ligne et se déplace de gauche à droite tout le temps. Il imprime d'abord la valeur au niveau du pointeur de la mémoire (initialisé à zéro), puis incrémente la valeur au niveau du pointeur de la mémoire 1. Après l’interdiction d’opération, l’IP passe à la troisième ligne qui bascule d’abord dans une autre cellule mémoire, puis imprime une nouvelle ligne. Puisqu'une nouvelle ligne a une valeur positive (sa valeur est 10), le code passera toujours à la cinquième ligne, la suivante. La cinquième ligne renvoie le pointeur de la mémoire sur notre numéro Fibonacci, puis passe à l’autre sous-programme. Lorsque nous reviendrons de ce sous-programme, l’adresse IP reviendra à la troisième ligne, après avoir exécuté un no-op.

Le deuxième sous-programme commence dans le coin supérieur droit et commence à se déplacer vers le sud-est. Après un no-op, nous sommes obligés de voyager vers l'ouest le long de la deuxième ligne. Cette ligne imprime le numéro de Fibonacci actuel avant de déplacer le pointeur de la mémoire vers le prochain emplacement. Ensuite, l’IP saute à la quatrième ligne, où il calcule le numéro Fibonacci suivant en utilisant les deux précédents. Il redonne ensuite le contrôle au premier sous-programme, mais lorsqu'il reprend le contrôle du programme, il continue jusqu'à ce qu'il rencontre un saut, où il rebondit sur le miroir qui était utilisé à l'origine pour le diriger vers l'ouest, puis qu'il retourne à la deuxième ligne.

Jolies images préliminaires!

Le côté gauche de l'image est le programme, le côté droit représente la mémoire. La boîte bleue est la première adresse IP et les deux adresses IP pointent vers l'instruction suivante à exécuter.

Remarque: les images peuvent sembler attrayantes aux personnes ayant des compétences limitées similaires avec les programmes d'édition d'images: PI ajoutera au moins 2 itérations supplémentaires afin que l'utilisation de l' *opérateur devienne plus claire.

Note 2: Je n’ai vu la réponse d’Alephalpha qu’après avoir écrit la majeure partie de ceci: j’ai pensé que c’était toujours utile en raison de la séparation, mais les parties Fibonacci de nos programmes sont très similaires. En outre, il s’agit du plus petit programme Hexagony que j’ai vu utiliser plus d’une adresse IP; j’ai donc pensé qu’il serait peut-être bon de le garder de toute façon: P

VACHE , 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 octets

Python, en utilisant la récursivité ... voici un StackOverflow!

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

Gelée , 3 octets

+¡1

Essayez-le en ligne!

Comment ça fonctionne

+¡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.

^‡ ¡ jette un œil aux deux liens à gauche. Puisqu'il n'y en a qu'un, ce doit être le corps de la boucle. Par conséquent, un nombre est lu à partir de l'entrée. Comme il n'y a pas d'argument de ligne de commande, ce nombre est lu à partir de STDIN.

Golfscript - numéro unique - 12/11/10

12 caractères pour prendre l'entrée de stdin:

~0 1@{.@+}*;

11 caractères pour l'entrée déjà sur la pile:

0 1@{.@+}*;

10 caractères pour définir plus en détail 1 comme numéro de Fibonacci:

1.@{.@+}*;

Rubis

29 27 25 24 Chars

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

Edit: fait une boucle infinie. ;)

Mathematica, 9 caractères

Fibonacci

Si les fonctions intégrées ne sont pas autorisées, voici une solution explicite:

Mathematica, 33 32 31 caractères

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

DC (20 octets)

En prime, il est même obscurci;)

zzr[dsb+lbrplax]dsax

EDIT: Je peux préciser qu’il affiche tous les nombres de la séquence fibonacci, si vous attendez assez longtemps.

Prélude , 12 octets

Un des rares défis où Prelude est en fait assez compétitif:

1(v!v)
  ^+^

Cela nécessite un interpréteur Python qui imprime les valeurs sous forme de nombres décimaux au lieu de caractères.

Explication

Dans Prelude, toutes les lignes sont exécutées en parallèle, le pointeur d'instruction traversant les colonnes du programme. Chaque ligne a sa propre pile qui est initialisée à zéro.

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.

La boucle se répète à l'infini, car la première pile n'aura jamais 0de dessus.

Notez que cela commence la séquence de Fibonacci à partir de 0.

Hexagonie , 6 octets

Non compétitif car la langue est plus récente que la question.

1.}=+!

Ungolfed:

  1 .
 } = +
  ! .

Il imprime la séquence de Fibonacci sans séparateur.

TI-BASIC, 11

Par le légendaire golfeur Kenneth Hammond ("Weregoose") de TI-BASIC, de ce site . S'exécute dans le temps O (1) et considère 0 comme le 0ème terme de la séquence de Fibonacci.

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

Utiliser:

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

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

Comment cela marche-t-il? Si vous faites le calcul, il s'avère que sinh‾¹(.5)c'est égal à ln φ, alors c'est une version modifiée de la formule de Binet qui arrondit au lieu d'utiliser le (1/φ)^nterme de correction. La valeur round((arrondir à 9 décimales) est nécessaire pour éviter les erreurs d’arrondi.

K - 12

Calcule le nombre net n-1Fibonacci.

{x(|+\)/0 1}

Juste le nthnuméro de Fibonacci.

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

Julia, 18 octets

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

Java, 55

Je ne peux pas rivaliser avec la concision de la plupart des langues ici, mais je peux offrir un moyen sensiblement différent et peut-être beaucoup plus rapide (temps constant) de calculer le n-ème nombre:

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

nest l'entrée (int ou long), en commençant par n = 1. Il utilise la formule et les arrondis de Binet au lieu de la soustraction.

Ruby, 25 caractères

la réponse de st0le raccourcie.

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

FAC: APL fonctionnel, 4 caractères (!!)

Pas le mien, donc posté comme wiki de communauté. FAC est un dialecte de l'APL que Hai-Chen Tu a apparemment suggéré comme thèse de doctorat en 1985. Il a ensuite écrit un article avec Alan J. Perlis intitulé " FAC: un langage fonctionnel de l'APL ". Ce dialecte de APL utilise des "tableaux paresseux" et permet des tableaux de longueur infinie. Il définit un opérateur "iter" ( ⌼) pour permettre une définition compacte de certaines séquences récursives.

Le cas monadique ("unaire") de ⌼est fondamentalement celui de Haskell iterate, et est défini comme (F⌼) A ≡ A, (F A), (F (F A)), …. Le cas dyadique ( « binaire ») est défini un peu analogue pour deux variables: A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …. Pourquoi est-ce utile? Eh bien, il s’avère que c’est précisément le type de récurrence de la séquence de Fibonacci. En fait, l’un des exemples cités est:

1+⌼1

produire la séquence familière 1 1 2 3 5 8 ….

Donc, voilà, probablement la mise en oeuvre de Fibonacci la plus courte possible dans un langage de programmation sans nouveauté. :RÉ

R, 40 octets

N'ayant pas vu de solution R, alors:

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

05AB1E, 7 octets

Code:

1$<FDr+

Essayez-le en ligne!

Dodos , 26 octets

	dot F
F
	F dip
	F dip dip

Essayez-le en ligne!

Comment ça fonctionne

La fonction F fait tout le gros du travail; il est défini récursivement comme suit.

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

Chaque fois que n> 1 , on a | n - 1 | = n - 1 <n et || n - 1 | - 1 | = | n - 1 - 1 | = n - 2 <n , la fonction retourne donc (F (n - 1), F (n - 2)) .

Si n = 0 , alors | n - 1 | = 1> 0 ; si n = 1 , alors || n - 1 | - 1 | = | 0 - 1 | = 1 = 1 . Dans les deux cas, la tentative d'appels récursifs F (1) déclenche une exception Surrender , donc F (0) renvoie 0 et F (1) renvoie 1 .

Par exemple, F (3) = (F (1), F (2)) = (1, F (0), F (1)) = (1, 0, 1) .

Enfin, la fonction principale est définie comme

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

il ajoute toutes les coordonnées du vecteur retourné par F .

Par exemple, main (3) = somme (F (3)) = somme (1, 0, 1) = 2 .

GolfScript, 13 caractères

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

(Ma réponse à une précédente question sur le dépassement de capacité .)

Desmos , 61 octets

Golfé

Cliquez sur le add sliderbouton pour n.

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

La dernière ligne est la sortie.

Ungolfed

Est une fonction.

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

Cubix , 10 octets

Réponse non concurrente car la langue est plus récente que la question.

Cubix est un nouveau langage bidimensionnel de @ETHproductions dans lequel le code est encapsulé dans un cube de la taille voulue.

;.o.ON/+!)

Essayez-le en ligne

Cela enveloppe un cube 2 x 2 de la manière suivante

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

• O afficher la valeur du TOS
• N pousser la nouvelle ligne sur la pile
• / refléter le nord
• o affiche le caractère du TOS
• ; pop TOS
• / refléter l'est après avoir contourné le cube
• + ajouter les 2 premières valeurs de la pile
• ! ignorer la commande suivante si le TOS est 0
• ) incrémente le TOS de 1. Ceci lance la séquence essentiellement.

Il s'agit d'une boucle sans fin qui imprime la séquence avec un séparateur de nouvelle ligne. Il tire parti du fait que la plupart des commandes ne suppriment pas les valeurs de la pile.
Si le séparateur est ignoré, cela peut être fait avec 5 octets.O+!)

Brainfuck, 16,15, 14/13 caractères

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

Génère la séquence de Fibonacci et n’imprime rien. En outre, est plus courte que celle ci-dessus.

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

Celui-ci a 14 caractères mais affiche les caractères ASCII avec les valeurs de la séquence de Fibonacci.