Die Fibonacci-Folge ist eine Folge von Zahlen, wobei jede Zahl in der Folge die Summe der beiden vorhergehenden Zahlen ist. Die ersten beiden Zahlen in der Sequenz sind beide 1.

Hier sind die ersten Begriffe

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

Schreiben Sie den kürzesten Code, der entweder:

• Erzeugt die Fibonacci-Sequenz ohne Ende.

• Given nberechnet den ndritten Term der Sequenz. (Entweder 1 oder null indiziert)

Sie können Standardformate für Ein- und Ausgabe verwenden.

(Ich habe beide Optionen angegeben, falls eine in der von Ihnen gewählten Sprache einfacher ist als die andere.)

Für die Funktion, die eine annimmt n, muss ein angemessen großer Rückgabewert (mindestens die größte Fibonacci-Zahl, die der normalen Wortgröße Ihres Computers entspricht) unterstützt werden.

Bestenliste

/* 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 Zeichen:

Anonyme unendliche Fibonacci-Sequenzliste:

^2,*+*...*

Gleich wie:

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

Sie können es also einem Array zuweisen:

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

oder

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

Und erhalten Sie die ersten elf Werte (von 0 bis 10) mit:

say @short-fibs[^11];

oder mit:

say @fibs[^11];

Warten Sie, Sie können auch die ersten 50 Nummern aus der anonymen Liste selbst abrufen:

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

Das gibt zurück:

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

Und ein einfacher Benchmark:

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

Mit:

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

EOF

Brainfuck, 22 Schläge

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

Erzeugt die Fibonacci-Sequenz, die sich allmählich über das Speicherband bewegt.

Haskell, 17 15 14 Zeichen

f=1:scanl(+)1f

Probieren Sie es online!

C # 4, 58 Bytes

Stream (69; 65, wenn schwach geschrieben IEnumerable)

(Annahme einer usingRichtlinie für System.Collections.Generic.)

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

Einzelwert (58)

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

GolfScript, 12

Jetzt nur noch 12 Zeichen!

1.{[email protected]+.}do

> <> - 15 Zeichen

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

J, 10 Zeichen

Unter Verwendung der eingebauten Berechnung der Taylorreihenkoeffizienten kann es also zu geringfügigem Betrug kommen. Hab es hier gelernt .

   (%-.-*:)t.

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

Hexagonie ,18 14 12

Danke Martin für 6 Bytes!

1="/}.!+/M8;

Erweitert:

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

Probieren Sie es online aus

Alt, antworte. Dies wird beibehalten, da die Bilder und Erläuterungen für neue Hexagony-Benutzer hilfreich sein können.

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

Erweitert:

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

Dies gibt die Fibonacci-Sequenz aus, die durch Zeilenumbrüche getrennt ist.

Probieren Sie es online! Seien Sie vorsichtig, der Online-Interpreter mag keine unendlichen Ausgaben.

Erläuterung

Es gibt zwei "Unterprogramme" für dieses Programm, die jeweils von einer der beiden verwendeten IPs ausgeführt werden. Die erste Routine druckt Zeilenumbrüche und die zweite die Fibonacci-Berechnung und Ausgabe.

Das erste Unterprogramm beginnt in der ersten Zeile und bewegt sich die ganze Zeit von links nach rechts. Er gibt zuerst den Wert am Speicherzeiger aus (initialisiert auf Null) und erhöht dann den Wert am Speicherzeiger um 1. Nach dem No-Op springt die IP zur dritten Zeile, die zuerst in eine andere Speicherzelle wechselt und dann eine neue Zeile ausgibt. Da eine neue Zeile einen positiven Wert hat (ihr Wert ist 10), springt der Code immer zur nächsten fünften Zeile. Die fünfte Zeile gibt den Speicherzeiger auf unsere Fibonacci-Nummer zurück und wechselt dann zur anderen Subroutine. Wenn wir von dieser Subroutine zurückkehren, springt die IP nach der Ausführung eines No-Op in die dritte Zeile zurück.

Die zweite Unterroutine beginnt in der oberen rechten Ecke und bewegt sich nach Südosten. Nach einem No-Op werden wir auf die zweite Linie nach Westen geschickt. Diese Zeile gibt die aktuelle Fibonacci-Nummer aus, bevor der Speicherzeiger an die nächste Stelle bewegt wird. Dann springt die IP zur vierten Zeile, wo sie die nächste Fibonacci-Zahl unter Verwendung der vorherigen beiden berechnet. Dann gibt es die Kontrolle an die erste Subroutine zurück, aber wenn es die Kontrolle über das Programm wiedererlangt, fährt es fort, bis es auf einen Sprung trifft, wo es über den Spiegel springt, der ursprünglich verwendet wurde, um es nach Westen zu richten, während es zur zweiten Zeile zurückkehrt.

Vorläufige hübsche Bilder!

Die linke Seite des Bildes ist das Programm, die rechte Seite repräsentiert den Speicher. Das blaue Kästchen ist die erste IP, und beide IPs zeigen auf die nächste auszuführende Anweisung.

Hinweis: Bilder erscheinen möglicherweise nur für Personen mit ähnlich eingeschränkten Kenntnissen in Bildbearbeitungsprogrammen hübsch: PI fügt mindestens zwei weitere Iterationen hinzu, damit die Verwendung des *Operators klarer wird.

Anmerkung 2: Ich habe die Antwort von alephalpha erst gesehen , nachdem ich das meiste geschrieben hatte. Ich dachte, dass sie aufgrund der Trennung immer noch wertvoll ist, aber die tatsächlichen Fibonacci-Teile unserer Programme sind sehr ähnlich. Außerdem ist dies das kleinste Hexagony-Programm, bei dem mehr als eine IP-Adresse verwendet wurde

COW , 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 mit Rekursion ... hier kommt ein StackOverflow!

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

Gelee , 3 Bytes

+¡1

Probieren Sie es online!

Wie es funktioniert

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

^‡ ¡ Sieh dir die beiden Links links an. Da es nur einen gibt, muss es der Körper der Schleife sein. Daher wird eine Zahl von der Eingabe gelesen. Da es keine Befehlszeilenargumente gibt, wird diese Nummer aus STDIN gelesen.

Golfscript - Einzelnummer - 11.12.10

12 Zeichen für die Eingabe von stdin:

~0 1@{.@+}*;

11 Zeichen für die Eingabe bereits auf dem Stapel:

0 1@{.@+}*;

10 Zeichen zur weiteren Definition von 1 als 0. Fibonacci-Zahl:

1.@{.@+}*;

Rubin

29 27 25 24 Zeichen

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

Bearbeiten: machte es eine Endlosschleife. ;)

Mathematica, 9 Zeichen

Fibonacci

Wenn integrierte Funktionen nicht zulässig sind, ist hier eine explizite Lösung:

Mathematica, 33 32 31 Zeichen

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

DC (20 Byte)

Als Bonus ist es sogar verschleiert;)

zzr[dsb+lbrplax]dsax

EDIT: Ich kann darauf hinweisen, dass es alle Zahlen in der Fibonacci-Sequenz druckt , wenn Sie lange genug warten.

Vorspiel , 12 Bytes

Eine der wenigen Herausforderungen, bei denen Prelude tatsächlich ziemlich wettbewerbsfähig ist:

1(v!v)
  ^+^

Dies erfordert den Python-Interpreter, der Werte als Dezimalzahlen anstelle von Zeichen ausgibt.

Erläuterung

Im Prelude werden alle Zeilen parallel ausgeführt, wobei der Anweisungszeiger die Programmspalten durchläuft. Jede Zeile hat einen eigenen Stack, der auf Null initialisiert wird.

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.

Die Schleife wird für immer wiederholt, da der erste Stapel niemals einen 0darüber hat.

Beachten Sie, dass dies die Fibonacci-Sequenz von startet 0.

Sechseck , 6 Bytes

Nicht konkurrierend, weil die Sprache neuer ist als die Frage.

1.}=+!

Ungolfed:

  1 .
 } = +
  ! .

Es druckt die Fibonacci-Sequenz ohne Trennzeichen.

TI-BASIC, 11

Von dem legendären TI-BASIC-Golfer Kenneth Hammond ("Weregoose") von dieser Seite . Läuft in O (1) -Zeit und betrachtet 0 als den 0. Term der Fibonacci-Sequenz.

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

Benutzen:

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

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

Wie funktioniert das? Wenn Sie rechnen, stellt sich heraus, dass dies sinh‾¹(.5)gleich ist ln φ, sodass es sich um eine modifizierte Version der Binet-Formel handelt, die rundet, anstatt den (1/φ)^nKorrekturausdruck zu verwenden. Die round((auf 9 Dezimalstellen runden) wird benötigt, um Rundungsfehler zu vermeiden.

K - 12

Berechnet die nund n-1Fibonacci-Zahl.

{x(|+\)/0 1}

Nur die nthFibonacci-Zahl.

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

Julia, 18 Bytes

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

Java, 55

Ich kann hier nicht mit der Prägnanz der meisten Sprachen mithalten, aber ich kann eine wesentlich andere und möglicherweise viel schnellere (konstante Zeit) Methode zur Berechnung der n-ten Zahl anbieten:

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

nist die Eingabe (int oder long), beginnend mit n = 1. Anstelle der Subtraktion werden Binets Formel und Runden verwendet.

Rubin, 25 Zeichen

Die Antwort von st0le wurde gekürzt.

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

FAC: Functional APL, 4 Zeichen (!!)

Nicht meins, daher als Community-Wiki gepostet. FAC ist ein Dialekt der APL, den Hai-Chen Tu offenbar 1985 als Dissertation vorgeschlagen hatte. Später schrieb er zusammen mit Alan J. Perlis einen Artikel mit dem Titel " FAC: A Functional APL Language ". Dieser Dialekt von APL verwendet "Lazy Arrays" und erlaubt Arrays von unendlicher Länge. Es definiert einen Operator "iter" ( ⌼), um eine kompakte Definition einiger rekursiver Sequenzen zu ermöglichen.

Der monadische ("unäre") Fall von ⌼ist im Grunde Haskells iterateund wird definiert als (F⌼) A ≡ A, (F A), (F (F A)), …. Der dyadische ( „binary“) Fall definiert ist etwas analog für zwei Variablen: A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …. Warum ist das nützlich? Nun, wie sich herausstellt, ist dies genau die Art von Wiederholung, die die Fibonacci-Sequenz hat. In der Tat ist eines der Beispiele dafür

1+⌼1

Produzieren der vertrauten Sequenz 1 1 2 3 5 8 ….

Also, los geht's, wahrscheinlich die kürzestmögliche Fibonacci-Implementierung in einer nicht neuartigen Programmiersprache. : D

R, 40 Bytes

Ich habe keine R-Lösung gesehen, also:

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

05AB1E, 7 Bytes

Code:

1$<FDr+

Probieren Sie es online!

Dodos , 26 Bytes

	dot F
F
	F dip
	F dip dip

Probieren Sie es online!

Wie es funktioniert

Die Funktion F erledigt das ganze schwere Heben; es wird rekursiv wie folgt definiert.

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

Immer wenn n> 1 ist , haben wir | n - 1 | = n - 1 <n und || n - 1 | - 1 | = | n - 1 - 1 | = n - 2 <n , daher gibt die Funktion (F (n - 1), F (n - 2)) zurück .

Wenn n = 0 ist , dann ist | n - 1 | = 1> 0 ; wenn n = 1 , dann || n - 1 | - 1 | = | 0 - 1 | = 1 = 1 . In beiden Fällen ruft die versuchten rekursive F (1) eine erhöhen Auslieferung Ausnahme, so F (0) liefert 0 und F (1) zurück 1 .

Zum Beispiel ist F (3) = (F (1), F (2)) = (1, F (0), F (1)) = (1, 0, 1) .

Schließlich ist die Hauptfunktion definiert als

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

es addiert also alle Koordinaten des von F zurückgegebenen Vektors .

Zum Beispiel ist main (3) = sum (F (3)) = sum (1, 0, 1) = 2 .

GolfScript, 13 Zeichen

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

(Meine Antwort von einer früheren Stapelüberlauf-Frage .)

Desmos , 61 Bytes

Golf gespielt

Klicken Sie auf die add sliderSchaltfläche für n.

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

Die letzte Zeile ist die Ausgabe.

Ungolfed

Ist eine Funktion.

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

Cubix , 10 Bytes

Nicht konkurrierende Antwort, da die Sprache neuer ist als die Frage.

Cubix ist eine neue zweidimensionale Sprache von @ETHproductions, bei der der Code in einen Würfel mit passender Größe eingepackt wird.

;.o.ON/+!)

Probieren Sie es online aus

Dies wird auf die folgende Weise auf einen 2 × 2-Würfel gewickelt

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

• O gibt den Wert des TOS aus
• N Schieben Sie den Zeilenvorschub auf den Stapel
• / spiegeln Norden
• o gibt den Charakter des TOS aus
• ; Pop TOS
• / reflektiere nach Osten, nachdem du den Würfel umrundet hast
• + Addiere die oberen 2 Werte des Stapels
• ! Überspringe den nächsten Befehl, wenn TOS 0 ist
• ) Erhöhen Sie die TOS um 1. Dies startet die Sequenz im Wesentlichen.

Dies ist eine Endlosschleife, die die Sequenz mit einem Trennzeichen für Zeilenumbrüche druckt. Es wird die Tatsache ausgenutzt, dass die meisten Befehle die Werte nicht aus dem Stapel entfernen.
Wenn das Trennzeichen ignoriert wird, kann dies mit 5 Bytes erfolgen.O+!)

Brainfuck, 16,15, 14/13 Zeichen

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

Erzeugt die Fibonacci-Sequenz und druckt nichts aus. Auch ist kürzer als die oben.

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

Dieser hat 14 Zeichen, druckt jedoch ASCII-Zeichen mit den Werten der Fibonacci-Sequenz aus.