Twoje zadanie:

Napisz program lub funkcję, aby sprawdzić, czy wprowadzona liczba jest liczbą Fibonacciego . Liczba Fibonacciego to liczba zawarta w sekwencji Fibonacciego.

Sekwencja Fibonacciego jest zdefiniowana jako: F(n) = F(n - 1) + F(n - 2)

Z nasionami F(0) = 0i F(1) = 1.

Wejście:

Nieujemna liczba całkowita od 0 do 1 000 000 000, która może, ale nie musi być liczbą Fibonacciego.

Wynik:

Wartość true / falsy wskazująca, czy dane wejściowe są liczbą Fibonacciego.

Przykłady:

0-->truthy
1-->truthy
2-->truthy
12-->falsy

Punktacja:

To jest golf golfowy , wygrywa najmniej bajtów.

Neim , 2 bajty

f𝕚

Wyjaśnienie:

f       Push an infinite fibonacci list
 𝕚      Is the input in that list?

Działa tak samo jak moja odpowiedź To Hip to Square , ale używa innej nieskończonej listy: fdla Fibonacciego.

Spróbuj!

JavaScript (ES6), 34 bajty

f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

Rekurencyjnie generuje sekwencję Fibonacciego, aż znajdzie element większy lub równy wejściowi, a następnie zwraca element == wejście.

Siatkówka , 23 bajty

^$|^(^1|(?>\2?)(\1))*1$

Wypróbuj online!

Wejście w jednostkowej, wyjściowej 0lub 1.

Wyjaśnienie

Sekwencja Fibonacciego jest dobrym kandydatem do rozwiązania z referencjami do przodu, tj. „Referencją wsteczną”, która odnosi się albo do otaczającej grupy, albo do grupy, która pojawia się później w wyrażeniu regularnym (w tym przypadku faktycznie używamy obu z nich). Przy dopasowywaniu takich liczb, musimy znaleźć wyrażenie rekurencyjne dla różnicy między elementami sekwencji. Np. Aby dopasować liczby trójkątne, zwykle dopasowujemy poprzedni segment plus jeden. Aby dopasować liczby kwadratowe (których różnicami są liczby nieparzyste), dopasowujemy poprzedni segment plus dwa.

Ponieważ liczby Fibonacciego uzyskujemy przez dodanie elementu ostatniego do ostatniego, różnice między nimi są również tylko liczbami Fibonacciego. Musimy więc dopasować każdy segment jako sumę dwóch poprzednich. Rdzeń wyrażenia regularnego jest następujący:

(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

Teraz kończy się dodając numery Fibonacciego zaczynając od 1 , czyli 1, 1, 2, 3, 5, ... . Ci dodać do 1, 2, 4, 7, 12, ... . To znaczy, że są one o jeden mniejsze niż liczby Fibonacciego, więc dodajemy 1na końcu. Jedynym przypadkiem, którego to nie obejmuje, jest zero, więc ^$na początku mamy alternatywę.

Regex (smak ECMAScript), 392 358 328 224 206 165 bajtów

Techniki, które muszą wejść w grę, aby dopasować liczby Fibonacciego do wyrażenia regularnego ECMAScript (jednostronnie), są dalekie od tego, jak najlepiej to zrobić w większości innych smaków wyrażeń regularnych. Brak odwołań do przodu / zagnieżdżonych wstecz lub rekurencji oznacza, że ​​nie można bezpośrednio policzyć ani zachować bieżącej sumy czegokolwiek. Brak wyglądu sprawia, że ​​często jest to wyzwanie, nawet mając wystarczająco dużo miejsca do pracy.

Do wielu problemów należy podchodzić z zupełnie innej perspektywy i wydają się nierozwiązywalne aż do pojawienia się jakiegoś kluczowego wglądu. Zmusza cię to do rzucenia znacznie szerszej sieci w celu znalezienia, które matematyczne właściwości liczb, z którymi pracujesz, mogą być wykorzystane do rozwiązania konkretnego problemu.

W marcu 2014 r. Stało się tak w przypadku liczb Fibonacciego. Patrząc na stronę Wikipedii, początkowo nie mogłem znaleźć sposobu, chociaż jedna konkretna właściwość wydawała się kusząco blisko. Następnie matematyk teukon nakreślił metodę, która wyraźnie dała do zrozumienia, że ​​można to zrobić, używając tej właściwości razem z inną. Nie chciał skonstruować wyrażenia regularnego. Jego reakcja, kiedy poszedłem naprzód i to zrobiłem:

Jesteś szalony! ... Myślałem, że możesz to zrobić.

Podobnie jak w przypadku moich innych jednoargumentowych wyrażeń regularnych ECMAScript, ostrzeżę : Gorąco zalecam naukę rozwiązywania pojedynczych problemów matematycznych w wyrażeniach regularnych ECMAScript. To była dla mnie fascynująca podróż i nie chcę zepsuć jej nikomu, kto mógłby potencjalnie chcieć spróbować samemu, szczególnie tym, którzy interesują się teorią liczb. Zobacz ten post, aby uzyskać listę zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.

Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła Ci się magia wyrażeń regularnych . Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript, jak opisano w linku powyżej.

Wyzwanie, z którym początkowo się zmierzyłem: dodatnia liczba całkowita x jest liczbą Fibonacciego tylko wtedy, gdy 5x ² + 4 i / lub 5x ² - 4 to idealny kwadrat. Ale nie ma miejsca na obliczenie tego w wyrażeniu regularnym. Jedyne miejsce, w którym musimy pracować, to sam numer. Nie mamy nawet dość miejsca, aby pomnożyć przez 5 lub wziąć kwadrat, nie mówiąc już o obu.

pomysł teukona na to, jak go rozwiązać ( pierwotnie opublikowany tutaj ):

Wyrażenie regularne jest prezentowane z ciągiem postaci ^x*$, niech z będzie jego długością. Sprawdź, czy z jest jedną z pierwszych kilku liczb Fibonacciego ręcznie (do 21 powinno wystarczyć). Jeżeli nie jest:

1. Przeczytaj kilka liczb, a <b, tak aby b nie było większe niż 2a.
   
2. Wykorzystaj prognozy na przyszłość, aby zbudować ² , ab i b ² .
   
3. Upewnij się, że 5a ² + 4 lub 5a ² - 4 to idealny kwadrat (więc dla niektórych n musi być F _n-1 ).
   
4. Upewnij się, że albo 5b ² + 4, albo 5b ² + 4 to idealny kwadrat (więc b musi być F _n ).
   
5. Sprawdź, czy z = F _{2n + 3} lub z = F _{2n + 4} , używając wcześniej zbudowanego ² , ab i b ² oraz tożsamości:
   
   • F _2n-1 = F _n ² + F _n-1 ²
     
   • F _2n = (2F _n-1 + _Fn ) F _n
     

W skrócie: te tożsamości pozwalają nam zmniejszyć problem sprawdzania, czy dana liczba to Fibonacciego, do sprawdzania, czy para znacznie mniejszych liczb to Fibonacciego. Mała algebra pokaże, że dla wystarczająco dużej n (n = 3 powinno wystarczyć), F _{2n + 3} > F _n + 5F _n ² + 4, więc zawsze powinno być wystarczająco dużo miejsca.

A oto makieta algorytmu w C, który napisałem jako test przed zaimplementowaniem go w regexie.

Więc bez zbędnych ceregieli, oto regex:

^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$

Wypróbuj online!

I ładnie wydrukowana, skomentowana wersja:

^(
  (?=
    (x*)                   # \2+1 = potential number for which 5*(\2+1)^2 ± 4
                           # is a perfect square; this is true iff \2+1 is a Fibonacci
                           # number. Outside the surrounding lookahead block, \2+1 is
                           # guaranteed to be the largest number for which this is true
                           # such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
    .*
    (?=                    # tail = (\2+1) * (\2+1) * 5 + 4
      x{4}
      (                    # \3 = (\2+1) * 5
        x{5}
        (\2{5})            # \4 = \2 * 5
      )
      (?=\3*$)
      \4+$
    )
    (|x{4})                # \5 = parity - determined by whether the index of Fibonacci
                           #               number \2+1 is odd or even
    (?=xx (x*)(\6 x?))     # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
                           #      divided by 2
                           # \7 = the other half, including remainder
    \5
    # require that the current tail is a perfect square
    (x(x*))                # \8 = potential square root, which will be the square root
                           #      outside the surrounding lookahead; \9 = \8-1
    (?=(\8*)\9+$)          # \10 = must be zero for \8 to be a valid square root
    (?=\8*$\10)
    \8*
    (?=(x\2\9+$))          # \11 = result of multiplying \8 * (\2+1), where \8 is larger
    (x*)\12                # \12 = \11 / 2; the remainder will always be the same as it
                           #       is in \7, because \8 is odd iff \2+1 is odd
  )
  \7\11
  (
    \6\11
  |
    \12
  )
|
  x{0,3}|x{5}|x{8}|x{21}   # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

Algorytm mnożenia nie jest wyjaśniony w tych komentarzach, ale jest krótko wyjaśniony w akapicie mojego obfitego numeru wyrażenia regularnego .

Utrzymywałem sześć różnych wersji wyrażenia Fibonacciego: cztery, które zapadają od najkrótszej do największej prędkości i używają algorytmu wyjaśnionego powyżej, oraz dwie inne, które używają innego, znacznie szybszego, ale o wiele dłuższego algorytmu, który, jak się przekonałem, może faktycznie powrócić indeks Fibonacciego jako dopasowanie (objaśnienie tego algorytmu jest poza zakresem tego postu, ale wyjaśniono to w oryginalnej dyskusji Gist ). Nie sądzę, bym zachował tak wiele bardzo podobnych wersji wyrażenia regularnego, ponieważ w tym czasie przeprowadzałem wszystkie testy w PCRE i Perlu, ale mój silnik wyrażeń regularnych jest wystarczająco szybki, aby obawy o szybkość nie były już tak ważne (a jeśli konkretny konstrukt powoduje wąskie gardło, mogę dodać dla niego optymalizację) - choć prawdopodobnie ponownie utrzymałbym jedną najszybszą wersję i jedną najkrótszą wersję, jeśli różnica w prędkości były wystarczająco duże.

Wersja „zwraca indeks Fibonacciego minus 1 jako dopasowanie” (niezbyt mocno golfa):

Wypróbuj online!

Wszystkie wersje są na github z pełną historią zatwierdzeń optymalizacji golfa:

regex do dopasowania liczb Fibonacciego - krótkie, prędkość 0.txt (najkrótszą ale najwolniejszy jeden, jak w tym poście)
regex do dopasowania liczb Fibonacciego - krótkie, prędkość 1.txt
regex do dopasowania liczb Fibonacciego - krótki, prędkość 2.txt
regex dopasowania liczby Fibonacciego - krótki, prędkość 3.txt
regex do dopasowania liczb Fibonacciego - fastest.txt
regex do dopasowania liczb Fibonacciego - powrót index.txt

Python 3 , 48 bajtów

lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

Wypróbuj online!

Python 2, 48 44 bajtów

f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

Wypróbuj online

_{Podziękowania dla Jonathana Allana za uratowanie 4 bajtów}

05AB1E , 8 7 bajtów

>ÅF¹å¹m

Wyjaśnienie:

>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

Wypróbuj online!

-1 dzięki Jonathanowi Allanowi za obejście problemu 0-nie-a-fibonacciego.

Perl 6 , 23 bajtów

{$_∈(0,1,*+*...*>$_)}

Poważnie , 3 bajty

,fu

Wypróbuj online!

Zwraca indeks +1 na liście liczb Fibonacciego, jeśli jest prawdziwy, w przeciwnym razie zwraca fałsz.

Wyjaśnienie:

,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)

Galaretka ,  8 7  6 bajtów

-r‘ÆḞċ

Wypróbuj online!

W jaki sposób?

-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

Uwagi:

• przyrost, ‘potrzebna jest więc to działa na 2 i 3 , ponieważ są to 3 ^rd i 4 ^th Liczby Fibonacciego - ponad 3 wszystkie liczby Fibonacciego są większe niż ich indeksu.
• -jest potrzebna (a nie tylko ‘R), tak to działa na 0 od 0 to 0 ^th liczba Fibonacciego;

ZX81 BASIC 180 151 100 ~ 94 tokenizowanych bajtów BASIC

Dzięki Moggy na forach SinclairZXWorld, jest to o wiele fajniejsze rozwiązanie, które oszczędza więcej bajtów.

 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

To da 1, jeśli wprowadzono liczbę Fibonacciego, lub zero, jeśli nie. Chociaż oszczędza to bajty, jest znacznie wolniejsze niż stare rozwiązania poniżej. Aby uzyskać szybkość (ale więcej BASIC bajtów) usuń VALopakowania wokół literalnych liczb ciągu. Oto stare (er) rozwiązania z kilkoma objaśnieniami:

 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

Powyższe poprawki oszczędzają dalsze BASIC bajty do zagęszczenia IFinstrukcji w jeden PRINTwiersz 12; inne bajty zostały zapisane przy użyciu VALsłowa kluczowego i przy użyciu GOTO CODE "£", który w zestawie znaków ZX81 ma wartość 12. Ciągi zapisują więcej bajtów nad liczbami, ponieważ wszystkie wartości liczbowe są przechowywane jako liczby zmiennoprzecinkowe, dlatego zajmują więcej miejsca na stosie VAR.

C #, 109 bajtów

bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

Zdecydowanie można to poprawić, ale nie miałem czasu.

> <> , 21 19 + 3 = 24 22 bajtów

i1\{=n;
?!\:@+:{:}(

Dane wejściowe powinny znajdować się na stosie podczas uruchamiania programu, więc +3 bajty dla -vflagi.

Wypróbuj online!

Działa to poprzez generowanie liczb Fibonacciego, aż będą większe lub równe liczbie wejściowej, a następnie sprawdzanie, czy ostatnio wygenerowana liczba jest równa z danymi wejściowymi. Wyprowadza, 1jeśli była to liczba Fibonacciego, w 0przeciwnym razie.

Aby upewnić się, że 0jest obsługiwany poprawnie, ziarno jest -1 1- pierwsza wygenerowana liczba będzie 0raczej niż 1.

Dzięki @cole za wskazanie, którego imożna użyć do wypchnięcia -1na stos, gdy STDIN jest pusty. Bardzo mądry!

Poprzednia wersja:

01-1\{=n;
}(?!\:@+:{:

Mathematica, 37 bajtów

!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

-4 bajty z @ngenisis

MATL (16 bajtów)

2^5*4-t8+hX^tk=s

Wypróbuj online!

Nie jest to najbardziej golfowe rozwiązanie, ale chciałem zastosować bezpośrednią metodę sprawdzenia, czy „5 * x ^ 2 +/- 4” to idealny kwadrat .

Wyjaśnienie:

2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

Uwaga:

W przypadku „0” zwraca „2”, ponieważ zarówno 4, jak i -4 są idealnymi kwadratami, tak samo jak 1, co daje „1 1”. Rozważ każde niezerowe wyjście jako „prawdę”, a 0 jako „fałsz”.

Pari / GP , 32 bajty

n->!prod(x=0,n+1,fibonacci(x)-n)

Wypróbuj online!

PHP , 44 bajty

for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

Wypróbuj online!

PHP , 58 bajtów

for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

Wypróbuj online!

Java, 72 69 68 63 59 55 50 49 bajtów

n->{int a=0,b=1;for(;a<n;a=b-a)b+=a;return a==n;}

Sprawdź to sam!

Alternatywa (wciąż 49 bajtów)

n->{int a=0,b=1;for(;a<n;b=a+(a=b));return a==n;}

Niezbyt oryginalny: jest to prosta i podstawowa wersja iteracyjna.

Działa to dla liczb do 1 836 311,903 (47-ta liczba Fibonacciego) włącznie. Ponadto wynik jest niezdefiniowany (w tym potencjalna nieskończona pętla).

Podziękowania dla Kevina Cruijssena i Davida Conrada za pomoc w grze w golfa :)

C # (.NET Core) , 51 bajtów

bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

Wypróbuj online!

-6 bajtów dzięki @Oliver!

To rozwiązanie wykorzystuje dość prostą funkcję rekurencyjną.

• Zmienna nto liczba do przetestowania.
• Zmienne ai bsą 2 najnowszymi liczbami w sekwencji.
• Sprawdza, czy pierwszy z 2 ostatnich numerów jest mniejszy niż wejście. W takim przypadku nawiązywane jest rekurencyjne połączenie z następnymi numerami w serii.
• W przeciwnym razie sprawdź, czy pierwsza liczba jest równa wartości wejściowej, i zwróć wynik.

Łącze TIO pokazuje, że działa on dla 1134903170, który przekracza maksymalną wartość wymaganą przez wyzwanie.

Alchemist , 205 134 bajtów

^{Ogromne podziękowania dla ASCII tylko za dość sprytne scalanie stanów, oszczędzając 71 bajtów !!}

_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

Wypróbuj online lub sprawdź partię!

Bez golfa

# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop

Galaretka , 5 bajtów

ȷḶÆḞi

Wypróbuj online!

Zwraca 0 dla liczb innych niż Fibonacciego, a 1-indeksowana pozycja liczby w sekwencji Fibonacciego dla liczb Fibonacciego.

Wyjaśnienie:

ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found

Dyalog APL, 17 bajtów

0∊1|.5*⍨4 ¯4+5××⍨

Wypróbuj online!

R, 43 40 bajtów

pryr::f(x%in%DescTools::Fibonacci(0:45))  

pryr::f tworzy funkcję:

function (x) 
x %in% DescTools::Fibonacci(0:45)

Używa DescTools::Fibonaccido tworzenia pierwszych x+1liczb Fibonacciego i sprawdza włączenie. x+1ponieważ trzeci fibnum to 2, a to nie wystarczy, aby sprawdzić włączenie 3.

Na szczęście Desctools::Fibonacci(0)=0jest to niezła gratka.

-3 bajty dzięki MickyT

Haskell , 31 bajtów

f=0:scanl(+)1f
(`elem`take 45f)

Wypróbuj online! Wykorzystuje to fakt, że dane wejściowe będą w zakresie od 0 do 1 000 000 000, dlatego musimy sprawdzić tylko pierwsze 45 liczb Fibonacciego. f=0:scanl(+)1fgeneruje nieskończoną listę liczb Fibonacciego, take 45fjest listą pierwszych 45 liczb Fibonacciego i elemsprawdza, czy dane wejściowe znajdują się na tej liście.

Wersja nieograniczona: 36 bajtów

f=0:scanl(+)1f
g n=n`elem`take(n+3)f

Wypróbuj online! Dla każdego n, biorąc pierwsze n+3liczby Fibonacciego zagwarantuje, że nbędzie na tej liście, jeśli jest to liczba Fibonacciego.

Zauważ, że to podejście jest niesamowicie nieefektywne w przypadku wysokich liczb, które nie są liczbami Fibonacciego, ponieważ wszystkie n+3liczby Fibonacciego muszą zostać obliczone.

JavaScript (ES6 bez operatora **), 44 bajty

f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

Opiera się na stosunku kolejnych liczb Fibonacciego zbliżających się do złotego podziału. Wartość c jest ułamkową częścią danych wejściowych podzieloną przez złoty współczynnik - jeśli dane wejściowe to Fibonacciego, będzie to bardzo blisko 1, a wartość c-c² będzie bardzo mała.

Nie tak krótki jak niektóre inne odpowiedzi JS, ale działa w czasie O (1).

Julia 0,4 , 29 bajtów

!m=in(0,sqrt(5*m*m+[4,-4])%1)

Wypróbuj online!

Jeśli nie tak robisz odpowiedź Julii, daj mi znać. Nie jestem pewien, jak działa wejście w TIO.

R, 32 31 bajtów

Pobiera dane wejściowe ze standardowego wejścia, zwraca TRUElub FALSEodpowiednio.

any(!(5*scan()^2+-1:1*4)^.5%%1)

Common Lisp, 61 54 bajtów

(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

Wypróbuj online!

Zmniejszenie rozmiaru w stosunku do poprzedniej wersji:

(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

zrodził się pomysł, że do wygenerowania sekwencji liczb Fibonacciego potrzebne są tylko dwie zmienne, a nie trzy.

Mathematica, 33 bajty

AtomQ@*InverseFunction[Fibonacci]

JS (ES6), 57 bajtów

n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))

Wykorzystuje metodę carusocomputing . Dużo bardziej golfista niż moja inna odpowiedź .

Bez golfa

n=>{
    y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
    return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}