Sekwencja Fibonacciego to ciąg liczb, gdzie każda liczba w ciągu jest sumą dwóch liczb poprzednich ją. Dwie pierwsze liczby w sekwencji to 1.

Oto kilka pierwszych warunków

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

Napisz najkrótszy kod, który:

• Generuje sekwencję Fibonacciego bez końca.

• Biorąc pod uwagę noblicza nth termin sekwencji. (Zindeksowany 1 lub zero)

Możesz użyć standardowych form wejścia i wyjścia.

(Podałem obie opcje na wypadek, gdyby jedna była łatwiejsza do wykonania w wybranym języku niż drugi).

W przypadku funkcji, która przyjmuje n, musi być obsługiwana stosunkowo duża wartość zwracana (największa liczba Fibonacciego, która odpowiada co najmniej normalnemu rozmiarowi słowa w komputerze).

Tabela liderów

/* 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 znaków:

Anonimowa nieskończona lista sekwencji Fibonacciego:

^2,*+*...*

Taki sam jak:

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

Możesz więc przypisać go do tablicy:

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

lub

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

I uzyskaj pierwsze jedenaście wartości (od 0 do 10) za pomocą:

say @short-fibs[^11];

lub z:

say @fibs[^11];

Poczekaj, z pierwszych anonimowych list możesz też pobrać pierwsze 50 liczb:

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

To zwraca:

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

I kilka prostych testów:

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

Z:

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

EOF

Brainfuck, 22 uderzeń

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

Generuje sekwencję Fibonacciego stopniowo przesuwającą się po taśmie pamięci.

Haskell, 17 15 14 znaków

f=1:scanl(+)1f

Wypróbuj online!

C # 4, 58 bajtów

Strumień (69; 65, jeśli słabo wpisany IEnumerable)

(Zakładając usingdyrektywę dla System.Collections.Generic.)

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

Jedna wartość (58)

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

GolfScript, 12

Teraz tylko 12 znaków!

1.{[email protected]+.}do

> <> - 15 znaków

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

J, 10 znaków

Korzystanie z wbudowanego obliczania współczynników serii Taylora, więc może trochę oszukiwać. Nauczyłem się tutaj .

   (%-.-*:)t.

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

Sześciokąt ,18 14 12

Dzięki Martin za 6 bajtów!

1="/}.!+/M8;

Rozszerzony:

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

Wypróbuj online

Stary, odpowiedz. Pozostaje, ponieważ obrazy i objaśnienia mogą być pomocne dla nowych użytkowników Hexagony.

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

Rozszerzony:

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

Spowoduje to wydrukowanie sekwencji Fibonacciego oddzielonej znakami nowej linii.

Wypróbuj online! Uważaj jednak, tłumacz online tak naprawdę nie lubi nieskończonej wydajności.

Wyjaśnienie

Istnieją dwa „podprogramy” tego programu, z których każdy jest obsługiwany przez jeden z dwóch używanych adresów IP. Pierwsza procedura drukuje znaki nowej linii, a druga wykonuje obliczenia i wyniki Fibonacciego.

Pierwszy podprogram rozpoczyna się w pierwszym wierszu i przez cały czas przesuwa się od lewej do prawej. Najpierw drukuje wartość wskaźnika pamięci (inicjowana na zero), a następnie zwiększa wartość wskaźnika pamięci o 1. Po braku operacji adres IP przeskakuje do trzeciej linii, która najpierw przełącza się na inną komórkę pamięci, a następnie drukuje nową linię. Ponieważ nowa linia ma wartość dodatnią (jej wartość wynosi 10), kod zawsze przeskakuje do piątej linii, następnie. Piąta linia zwraca wskaźnik pamięci do naszego numeru Fibonacciego, a następnie przełącza się na inny podprogram. Kiedy wrócimy z tego podprogramu, adres IP przeskoczy z powrotem do trzeciej linii po wykonaniu braku operacji.

Drugi podprogram rozpoczyna się w prawym górnym rogu i rozpoczyna ruch na południowy wschód. Po przerwie wracamy do drugiej linii na zachód. Ta linia wypisuje aktualny numer Fibonacciego, przed przeniesieniem wskaźnika pamięci do następnej lokalizacji. Następnie IP przeskakuje do czwartej linii, gdzie oblicza następną liczbę Fibonacciego za pomocą poprzednich dwóch. Następnie przekazuje kontrolę z powrotem do pierwszego podprogramu, ale gdy odzyskuje kontrolę nad programem, kontynuuje działanie, aż napotka skok, w którym odbija się od lustra, które pierwotnie służyło do wskazywania go na zachód, gdy wraca do drugiej linii.

Wstępne ładne zdjęcia!

Lewa strona obrazu to program, prawa strona reprezentuje pamięć. Niebieska ramka to pierwszy adres IP, a oba adresy IP wskazują następną instrukcję do wykonania.

Uwaga: Zdjęcia mogą wyglądać ładnie tylko dla osób o podobnie ograniczonych umiejętnościach w programach do edycji obrazów: PI doda co najmniej 2 kolejne iteracje, aby korzystanie z *operatora stało się bardziej przejrzyste.

Uwaga 2: Zobaczyłem odpowiedź alephalpha dopiero po napisaniu większości tego, pomyślałem, że wciąż była cenna z powodu separacji, ale rzeczywiste części Fibonacciego naszych programów są bardzo podobne. Ponadto jest to najmniejszy program Hexagony, który widziałem przy użyciu więcej niż jednego adresu IP, więc pomyślałem, że warto go zachować: P

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 bajty

Python, używając rekurencji ... oto nadchodzi StackOverflow!

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

Galaretka , 3 bajty

+¡1

Wypróbuj online!

Jak to działa

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

^‡ ¡ zagląda do dwóch linków po lewej stronie. Ponieważ jest tylko jeden, musi być ciałem pętli. Dlatego liczba jest odczytywana z wejścia. Ponieważ nie ma argumentów wiersza polecenia, liczba ta jest odczytywana ze STDIN.

Golfscript - pojedynczy numer - 12/11/10

12 znaków do pobierania danych wejściowych ze standardowego wejścia:

~0 1@{.@+}*;

11 znaków dla danych wejściowych już na stosie:

0 1@{.@+}*;

10 znaków dla dalszego zdefiniowania 1 jako 0. liczby Fibonacciego:

1.@{.@+}*;

Rubin

29 27 25 24 znaków

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

Edycja: uczyniła go nieskończoną pętlą. ;)

Mathematica, 9 znaków

Fibonacci

Jeśli wbudowane funkcje nie są dozwolone, oto wyraźne rozwiązanie:

Mathematica, 33 32 31 znaków

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

DC (20 bajtów)

Jako bonus jest nawet zaciemniony;)

zzr[dsb+lbrplax]dsax

EDYCJA: Mogę zaznaczyć, że wypisuje wszystkie liczby w sekwencji Fibonacciego, jeśli zaczekasz wystarczająco długo.

Preludium , 12 bajtów

Jedno z niewielu wyzwań, w których Preludium jest dość konkurencyjne:

1(v!v)
  ^+^

Wymaga to interpretera Pythona, który drukuje wartości jako liczby dziesiętne zamiast znaków.

Wyjaśnienie

W Preludium wszystkie wiersze są wykonywane równolegle, a kolumny instrukcji przechodzą przez program. Każda linia ma własny stos, który jest inicjowany na zero.

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.

Pętla powtarza się na zawsze, ponieważ pierwszy stos nigdy nie będzie miał 0na wierzchu.

Zauważ, że zaczyna się sekwencja Fibonacciego od 0.

Sześciokąt , 6 bajtów

Nie konkuruje, ponieważ język jest nowszy niż pytanie.

1.}=+!

Nie golfowany:

  1 .
 } = +
  ! .

Drukuje sekwencję Fibonacciego bez żadnego separatora.

TI-BASIC, 11

Legendarny golfista TI-BASIC Kenneth Hammond („Weregoose”) z tej strony . Działa w czasie O (1) i uważa, że ​​0 jest 0 terminem sekwencji Fibonacciego.

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

Używać:

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

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

Jak to działa? Jeśli wykonasz matematykę, okaże się, że sinh‾¹(.5)jest ona równa ln φ, więc jest to zmodyfikowana wersja formuły Bineta, która zaokrągla w dół zamiast używać (1/φ)^nterminu korygującego. round(Konieczna jest (okrągły do 9 miejsc po przecinku), aby uniknąć błędów zaokrągleń.

K - 12

Oblicza ni n-1liczby Fibonacciego.

{x(|+\)/0 1}

Tylko nthliczba Fibonacciego.

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

Julia, 18 bajtów

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

Java, 55

Nie mogę tutaj konkurować ze zwięzłością większości języków, ale mogę zaoferować znacznie inny i być może znacznie szybszy (stały czas) sposób obliczenia n-tej liczby:

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

nto wejście (int lub long), zaczynające się od n = 1. Używa formuły Bineta i zaokrągla zamiast odejmowania.

Ruby, 25 znaków

Odpowiedź st0le skrócona.

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

FAC: funkcjonalne APL, 4 znaki (!!)

Nie moja, dlatego opublikowana jako wiki społeczności. FAC jest dialektem APL, który Hai-Chen Tu najwyraźniej zasugerował jako swoją pracę doktorską w 1985 roku. Później wraz z Alanem J. Perlisem napisał artykuł zatytułowany „ FAC: A Functional APL Language ”. Ten dialekt APL używa „leniwych tablic” i pozwala na tablice o nieskończonej długości. Definiuje operator „iter” ( ⌼), aby umożliwić kompaktową definicję niektórych sekwencji rekurencyjnych.

Przypadek monadyczny („unarny”) ⌼jest w zasadzie przypadkiem Haskella iteratei jest zdefiniowany jako (F⌼) A ≡ A, (F A), (F (F A)), …. Dwójkowym ( „binarny”) sprawa jest nieco zdefiniowane analogicznie do dwóch zmiennych A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …. Dlaczego to jest przydatne? Jak się okazuje, jest to dokładnie taki rodzaj nawrotu, jaki ma sekwencja Fibonacciego. W rzeczywistości jednym z podanych przykładów jest

1+⌼1

tworząc znaną sekwencję 1 1 2 3 5 8 ….

A więc proszę bardzo krótka możliwa implementacja Fibonacciego w nieinnowacyjnym języku programowania. :RE

R, 40 bajtów

Nie widziałem rozwiązania R, więc:

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

05AB1E, 7 bajtów

Kod:

1$<FDr+

Wypróbuj online!

Dodos , 26 bajtów

	dot F
F
	F dip
	F dip dip

Wypróbuj online!

Jak to działa

Funkcja F wykonuje wszystkie ciężkie podnoszenie; zdefiniowano go rekurencyjnie w następujący sposób.

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

Ilekroć n> 1 , mamy | n - 1 | = n - 1 <n oraz || n - 1 | - 1 | = | n - 1 - 1 | = n - 2 <n , więc funkcja zwraca (F (n - 1), F (n - 2)) .

Jeśli n = 0 , to | n - 1 | = 1> 0 ; jeśli n = 1 , to || n - 1 | - 1 | = | 0 - 1 | = 1 = 1 . W obu przypadkach, próba połączenia rekurencyjne F (1) podnieść Surrender wyjątek, więc F (0) zwraca 0 i F (1) zwraca 1 .

Na przykład F (3) = (F (1), F (2)) = (1, F (0), F (1)) = (1, 0, 1) .

Wreszcie, główna funkcja jest zdefiniowana jako

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

więc sumuje wszystkie współrzędne wektora zwrócone przez F. .

Na przykład main (3) = suma (F (3)) = suma (1, 0, 1) = 2 .

GolfScript, 13 znaków

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

(Moja odpowiedź z poprzedniego pytania dotyczącego przepełnienia stosu ).

Desmos , 61 bajtów

Grał w golfa

Kliknij add sliderprzycisk dla n.

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

Ostatni wiersz to wynik.

Nie golfił

Jest funkcją.

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

Cubix , 10 bajtów

Odpowiedź niekonkurencyjna, ponieważ język jest nowszy niż pytanie.

Cubix to nowy, dwuwymiarowy język autorstwa @ETHproductions, w którym kod jest zawijany na kostkę o odpowiednim rozmiarze.

;.o.ON/+!)

Wypróbuj online

Zawija się to na kostkę 2 x 2 w następujący sposób

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

• O wyprowadza wartość TOS
• N pchnij nową linię na stos
• / odzwierciedlają północ
• o wypisuje znak TOS
• ; pop TOS
• / odbij się na wschód po obejściu sześcianu
• + dodaj 2 górne wartości stosu
• ! pomiń następne polecenie, jeśli TOS wynosi 0
• ) zwiększ TOS o 1. To zasadniczo rozpoczyna sekwencję.

Jest to nieskończona pętla, która drukuje sekwencję z separatorem nowej linii. Wykorzystuje to, że większość poleceń nie wyrzuca wartości ze stosu.
Jeśli separator zostanie zignorowany, można to zrobić za pomocą 5 bajtów.O+!)

Brainfuck, 16,15, 14/13 znaków

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

Generuje sekwencję Fibonacciego i niczego nie drukuje. Jest także krótszy niż powyższy.

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

Ten ma 14 znaków, ale drukuje znaki ASCII z wartościami sekwencji Fibonacciego.