Wprowadzenie

Wszyscy znamy i kochamy naszą sekwencję Fibonacciego i już widzieliśmy tutaj mnóstwo wyzwań. Jednak wciąż brakuje nam bardzo prostego przypadku, który dostarczy ta odpowiedź: Odwrócone fibonacciego! Więc biorąc pod uwagę F_ntwoją pracę, musisz ją znaleźć n.

Specyfikacja

Wejście

Twój wkład będzie nieujemną liczbą całkowitą, która z pewnością jest częścią sekwencji Fibonacciego.

Wynik

Wynik musi być również nieujemną liczbą całkowitą.

Co robić?

Wstęp już powiedział: Biorąc pod uwagę liczbę Fibonacciego, wypisz jej indeks. Numer Fiboancci jest niniejszym zdefiniowany jako F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)i otrzymasz F(n)i musisz wrócić n.

Potencjalne narożne skrzynki

0 jest prawidłowym wejściem i wyjściem.
Jeśli podasz „1” jako dane wejściowe, możesz albo „1”, albo „2”, jak wolisz.
Zawsze możesz założyć, że twój wkład faktycznie jest liczbą Fibonacciego.
Możesz założyć, że wejście jest reprezentowalne jako 32-bitowa liczba całkowita ze znakiem.

Kto wygrywa?

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach!
Oczywiście obowiązują standardowe zasady.

Przypadki testowe

0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46

Właściwie 1 bajt

f

Tak, jest do tego wbudowany od 16 listopada 2015 .

Wypróbuj online

Dla zabawy, bez wbudowanego, ma 9 bajtów:

╗1`F╜=`╓i

Wypróbuj online!

Wyjaśnienie:

╗1`F╜=`╓i
╗          push input to register 0
 1`F╜=`╓   push list containing first value x (starting with x = 0) where:
   F         fib(x)
    ╜=       is equal to the input
        i  flatten the list

Mathematica, 25 bajtów

InverseFunction@Fibonacci

Funkcjonować. Całkiem zrozumiałe, jeśli mnie zapytasz.

Python, 36 34 32 bajty

lambda n:len(str(66*n**6))//1.24

Poprzednie wersje:

f=lambda n:len(str(66*n**6))//1.24
f=lambda n:(n*n*7).bit_length()//1.4

Wyjaśnienie

Podstawową ideą jest odwrócenie formuły

fibonacci(n) ~ ( (1 + sqrt(5)) / 2)**n / sqrt(5)

co nam to mówi

log fibonacci(n) ~ n log((1 + sqrt(5)) / 2) - log(sqrt(5))

dostać

f(n) ~ (log(n) + log(sqrt(5))) / log((1 + sqrt(5))/2)

Optymalizacje gry w golfa to:

• Służy len(str(n))do obliczania bazy danych dziennika 10 bez importowania log(stara wersja używana .bit_length()do obliczania bazy danych dziennika 2)
• Podnieś nmoc, aby zbliżenie logarytmu mogło rozróżniać kolejne liczby Fibonacciego
• Mnożenie przez stałą powoduje skalowanie wartości, aby uzyskać prawidłowy zakres

Następnie dzielnik został obcięty z jak najmniejszą precyzją, a mnożnik został wybrany, aby dać prawidłowe wyniki dla wszystkich 32-bitowych liczb fibonacciego.

05AB1E , 3 bajty

Kod:

ÅFg

Wyjaśnienie:

ÅF   # Generate all Fibonacci numbers <= input.
  g  # Get the length of this list.

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Galaretka, 14 11 bajtów

5½×lØp+.Ḟ»0

Wypróbuj online!

To moja pierwsza w historii odpowiedź na żelki! Wykorzystuje algorytm z odpowiedzi MATL . Dzięki Dennisowi za zgolenie 3 bajtów!

Wyjaśnienie:

   lØp      # Log Base phi
5½          # Of the square root of 5
  ×         # Times the input
      +     # Plus
       .    # 0.5
        Ḟ   # Floored

To jest prawidłowa odpowiedź, teraz musimy poradzić sobie ze specjalnym przypadkiem „0”. Z „0” jako argumentem, otrzymujemy -infinity, więc wracamy

»      # The maximum of 
 0     # Zero
       # And the previous calculated value.

Julia, 27 26 18 bajtów

!n=log(3n+.7)÷.48

Wykorzystuje odwrotność formuły Bineta , z wystarczającą dokładnością dla 32-bitowych liczb całkowitych; faktycznie działa aż do F (153) = 42 230, 279, 266, 998,466,217,810,220,532, 898> 2 ¹⁰⁵ .

Wypróbuj online!

Jak to działa

Formuła Bineta stwierdza, co następuje.

Ograniczanie F do zestawu Fibonacciego, mapie n → F _n ma prawo odwrotną F n → _F .

Mamy to

i wszystko, co pozostaje do zrobienia, to zajmowanie się przypadkiem krawędzi 0 .

Ponieważ dane wejściowe są ograniczone do 32-bitowych liczb całkowitych, możemy użyć krótkich liter dziesiętnych zamiast stałych w formule.

• log φ = 0,481211825059603447… ≈ 0,48

  Niestety 0,5 nie jest wystarczająco precyzyjne.

• √5 = 2,2360679774997896964… ≈ 3

  Na pierwszy rzut oka może się to wydawać okropnym przybliżeniem, ale bierzemy logarytmy, a ponieważ log 3 - log √5 = 0,29389333245105… , wynik przed zaokrągleniem będzie niewielki, stały.

• 0,5 ≈ 0,7

  Z powodu nadmiaru z poprzedniego przybliżenia możemy faktycznie całkowicie pominąć ten termin i nadal uzyskać prawidłowe wyniki dla F> 0 . Jeśli jednak F = 0 , logarytm będzie niezdefiniowany. 0,7 okazało się najkrótszą wartością, która rozszerza naszą formułę do F = 0 .

JavaScript, 54 50 69 50 42 bajtów

b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c

Na pewno nie wygra, tylko dla zabawy :)

Ok, sprawdzanie zera zużywa 19 bajtów. WTF? Głupi ja.

Próbny! Aby zobaczyć ostatni przypadek testowy, musisz trochę przewinąć konsolę.

a=b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c;
console.log('0: '+a(0));
console.log('2: '+a(2));
console.log('3: '+a(3));
console.log('5: '+a(5));
console.log('8: '+a(8));
console.log('13: '+a(13));
console.log('1836311903: '+a(1836311903));

Dzięki @edc za skrócenie o 8 bajtów.

Perl 6  33 30  27 bajtów

{first *==$_,:k,(0,1,*+*...*>$_)}
{first *==$_,:k,(0,1,*+*...*)}
{first $_,:k,(0,1,*+*...*)}

Spróbuj

Wyjaśnienie:

# lambda with implicit ｢$_｣ parameter
{
  first           # find the first element
    $_,           # where something is equal to the block's argument
    :k,           # return the key rather than the value

    # of the Fibonacci sequence
    ( 0, 1, * + * ... * )
    # ^--^ first two values
    #       ^---^ lambda used to generate the next in the series
    #             ^-^ generate until
    #                 ^ Whatever
}

Test:

#! /usr/bin/env perl6
use v6.c;
use Test;

# using the safer version that stops generating
# values bigger than the input
my &fib-index = {first $_,:k,(0,1,*+*...*>$_)}

my @tests = (
  0 => 0,
  2 => 3,
  3 => 4,
  5 => 5,
  8 => 6,
  13 => 7,
  1836311903 => 46,
  1836311904 => Nil, # this is why the safe version is used here
  12200160415121876738 => 93,
  19740274219868223167 => 94,
  354224848179261915075 => 100,
);

plan +@tests + 1;

for @tests -> $_ ( :key($input), :value($expected) ) {
  cmp-ok fib-index($input), &[eqv], $expected, .gist
}

cmp-ok fib-index((0,1,*+*...*)[1000]), &[eqv], 1000, 'works up to 1000th element of Fibonacci sequence'

1..13
ok 1 - 0 => 0
ok 2 - 2 => 3
ok 3 - 3 => 4
ok 4 - 5 => 5
ok 5 - 8 => 6
ok 6 - 13 => 7
ok 7 - 1836311903 => 46
ok 8 - 1836311904 => Nil
ok 9 - 12200160415121876738 => 93
ok 10 - 19740274219868223167 => 94
ok 11 - 354224848179261915075 => 100
ok 12 - works up to 1000th element of Fibonacci sequence

Galaretka , 8 bajtów

1+С0
¢i

Wypróbuj online! Zauważ, że to podejście jest zbyt nieefektywne dla ostatniego przypadku testowego.

Jak to działa

¢i     Main link. Argument: n

¢      Call the helper link niladically (i.e., without arguments).
       This yields the sequence of the first n positive Fibonacci numbers, i.e.,
       [1, 1, 2, 3, 5, ...].
 i     Find the first index of n (1-based, 0 if not found).


1+С0  Helper link. No arguments.

1      Set the left argument to 1.
    0  Yield 0.
 +С   Add both arguments, replacing the left argument with the sum and the right
       argument with the previous value of the left argument.
       Yield the array of all intermediate values of the left argument.

Pyke, 5 bajtów

.f.bq

Wypróbuj tutaj!

.f    - first number where
  .b  -  fib(n)
    q - ^ == input

Python, 29 bajtów

g=lambda n:n>.7and-~g(n/1.61)

Rekurencyjnie dzieli dane wejściowe przez przybliżenie złotego współczynnika 1,61, dopóki nie spadnie poniżej 0,7, i wyprowadza liczbę podziałów.

0, wówczas kod False, który jest równy 0 w Pythonie . Można tego uniknąć dla 2 bajtów

g=lambda n:n//.7and 1+g(n/1.61)

JavaScript (ES6), 39 33 bajtów

f=(n,j=0,k=1)=>n>j?f(n,k,j+k)+1:0

Nawet w przypadku ES7 odwrotna formuła Bineta zajmuje 47 bajtów:

x=>Math.log(x*5**.5)/Math.log(.5+1.25**.5)+.5|0
x=>Math.log(x*5**.5)/Math.log((1+5**.5)/2)+.5|0
x=>Math.log(x*(p=5**.5))/Math.log((1+p)/2)+.5|0

Sage, 49 bajtów

lambda x,s=sqrt(5):x and int(log(x*s,(1+s)/2)+.5)

Dzięki TuukkaX za sugestię na temat zapisywania sqrt(5)jako sogolił kilka bajtów.

Wypróbuj online .

To podejście z odwrotnością formuły Bineta oferuje kilka ulepszeń w stosunku do poprzedniego podejścia: jest szybsze (czas stały w porównaniu do czasu kwadratowego), w rzeczywistości działa dla większych nakładów i jest krótsze!

Użytkownicy Pythona mogą się zastanawiać, dlaczego używam sqrt(5)zamiast krótszego 5**.5- to dlatego, że 5**.5jest obliczany z powfunkcją C i traci precyzję z powodu problemów ze zmiennoprzecinkowymi. Wiele funkcji matematycznych (w tym sqrti log) jest przeciążonych w Sage, aby zwrócić dokładną, symboliczną wartość, która nie traci precyzji.

MATL , 14 bajtów

t?5X^*17L&YlYo

Wypróbuj online!

To używa odwrotności formuły Bineta , a więc jest bardzo szybkie.

Niech K oznaczają n -tej liczby Fibonacciego i cp w stosunku złotej . Następnie

Kod używa tej formuły z dwiema modyfikacjami:

• Zamiast dodawać 1/2, a następnie zaokrąglać w dół, kod po prostu zaokrągla w kierunku najbliższej liczby całkowitej, co zajmuje mniej bajtów.
• Wejście F = 0 należy traktować jako przypadek specjalny.

Jak to jest zrobione

t         % Take input F implicitly. Make a copy
?         % If (copy of) F is positive
  5X^     %   Push sqrt(5)
  *       %   Multiply by F
  17L     %   Push phi (predefined literal)
  &Yl     %   Two-input logarithm: first input is argument, second is base
  Yo      %   Round towards nearest integer
          % Else the input, which is 0, is left on the stack
          % End if implicitly
          % Display implicitly

Python, 38 bajtów

f=lambda n,a=0,b=1:n^a and-~f(n,b,a+b)

Przetestuj na Ideone .

JavaScript, 22 bajty

n=>Math.log(n)/.48+2|0

C, 62 58 bajtów

g(c,a,b){return c-a?g(c,b,a+b)+1:0;}f(c){return g(c,0,1);}

Szczegółowe

int g(int c, int a, int b)
{
    if (c == a)
    {
        return 0;
    }
    else
    {
        return g(c, b, a+b) + 1;
    }
}

int f(c)
{
    return g(c, 0, 1);
}

Java 7, 70 bajtów

int c(int n){int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;}

https://ideone.com/I4rUC5

TSQL, 143 bajty

Wejście wchodzi @njak wDECLARE @n INT = 1836311903;

DECLARE @O BIGINT=0;WITH F(R,P,N)AS(SELECT @O,@O,@O+1 UNION ALL SELECT R+1,N,P+N FROM F WHERE N<=@n)SELECT MAX(R)FROM F OPTION(MAXRECURSION 0);

Haskell, 45 bajtów

f x=round$log(sqrt 5*x+0.9)/log((sqrt 5+1)/2)

Sesos , 28 bajtów

Hexdump:

0000000: 16f8be 766ef7 ae6d80 f90bde b563f0 7ded18 3ceffa  ...vn..m.....c.}..<..
0000015: b1c1bb af9f3f ff                                  .....?.

Wypróbuj online!

(Czas wykładniczy, ponieważ w Sesos kopiowanie liczby wymaga czasu wykładniczego.)

Zespół użyty do wygenerowania pliku binarnego:

set numin
set numout
get
jmp
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz    ;input input
fwd 4
add 1  ;input input 0 1
fwd 2
add 1  ;input input 0 1 0 1
rwd 4
jmp
jmp    ;input input-curr curr next iterations
sub 1
jnz    ;input 0 curr next iterations
fwd 3
add 1
jmp
sub 1
fwd 2
add 1
rwd 2
jnz    ;input 0 curr next 0 0 iterations+1
rwd 1
jmp
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz    ;input 0 curr 0 next next iterations+1
rwd 1
jmp
sub 1
fwd 1
sub 1
fwd 2
add 1
rwd 3
jnz    ;input 0 0 -curr next curr+next iterations+1
rwd 2
jmp
sub 1
fwd 2
add 1
fwd 1
add 1
rwd 3
jnz    ;0 0 input input-curr next curr+next iterations+1
fwd 3
jnz
fwd 3
put

Java 8 61 bajtów

To samo, co odpowiedź @dainichi, tylko krótsza przy użyciu lambda Java 8. Odpowiedź jest prawidłowym wyrażeniem wartości.

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

Nie golfowany:

interface F
{
    int c(int n);
}

public class Main
{

    public static void main(String[] args)
    {
        F f = n->{int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;};
    }
}

Pyth, 13 bajtów

J1tf>=Z+~JZZQ

Zestaw testowy.

Przybliżenie w Pythonie 2:

Z=0;J=1;T=1;Q=input()
while not J+Z>Q:
    temp=J
    J=Z
    Z=temp+J
    T += 1
print(T-1)

alternatywne podejście, 18 bajtów

L?<b2bsyMtBtbs.IyG

Zestaw testowy.

Używa .Iodwrotności.

Java 7, 89 bajtów

int c(int n){int i=-1;while(f(++i)<n);return i;}int f(int n){return n<2?n:f(n-1)+f(n-2);}

Zainspirowany wyjaśnieniem odpowiedzi 05AB1E @Adnana .

Przypadki bez golfa i testy:

Wypróbuj tutaj. (Przekroczono limit czasu dla ostatniego przypadku testowego, ale działa na moim komputerze około 30-45 sekund.)

class Main{
  static int c(int n){
    int i = -1;
    while(f(++i) < n);
    return i;
  }

  static int f(int n){
    return n < 2
             ? n
             : f(n - 1) + f(n - 2);
  }

  public static void main(String[] a){
    System.out.println(c(0));
    System.out.println(c(2));
    System.out.println(c(3));
    System.out.println(c(5));
    System.out.println(c(8));
    System.out.println(c(1836311903));
  }
}

Wynik:

0
3
4
5
6
46

Perl 5.10, 48 bajtów

Zasadniczo szukasz prawa n, aby F(n) = input.

-a przełącznik dodaje jeden bajt.

$b++;while($_>$a){$c=$a;$a+=$b;$b=$c;$n++}say$n

Wypróbuj tutaj!

J, 32 27 17 bajtów

i.~0,+/@(!|.)\@i.

Oblicza pierwsze n liczb Fibonacciego, a następnie znajduje indeks n na tej liście.

Stosowanie

Dodatkowe polecenia są używane do formatowania wielu wejść / wyjść. Ostatni przypadek testowy został pominięty, ponieważ jego obliczenie będzie wymagało znacznie więcej czasu.

   f =: i.~0,+/@(!|.)\@i.
   (,.f"0) 0 1 2 3 5 8 13
 0 0
 1 1
 2 3
 3 4
 5 5
 8 6
13 7

Wyjaśnienie

i.~0,+/@(!|.)\@i.  Input: n
               i.  Get the range [0, 1, ..., n-1]
             \@    For each prefix of that range
          |.         Reverse the prefix
         !           Find the binomial coefficient between each value in the original
                     prefix and the reversed prefix
     +/@             Sum those binomial coefficients
                   This will create the Fibonacci numbers from 1 to n
   0,              Prepend a 0 to the list of Fibonacci numbers
i.~                Find the index of n in that list and return

Mathematica, 30 bajtów

Round@Log[5^.5/2+.5,.8+5^.5#]&

Czysta funkcja; zwraca 2, jeśli wartością wejściową jest 1.

Nie bije drugiego wpisu Mathematica, ale pokazuje niezwykłą metodę: (bardzo fajny) fakt, że N-ta liczba Fibonacciego jest najbliższą liczbą całkowitą do [1 / sqrt (5) razy N-ta moc złotego podziału] („ Wzór Bineta ”).

Dlatego funkcją odwrotną będzie logarytm bazowy [złoty współczynnik] wynoszący [sqrt (5) razy dana liczba Fibonacciego]. .8+Jest hack, aby upewnić się, że nie ma logarytm 0, bez zakręcania inne wartości.

Japt , 10 bajtów

Lo æ@U¥MgX

Wypróbuj online!

Wyjaśnienie

Lo æ@U¥MgX
Lo           // Creates a range from 0 to 99
   æ@        // Iterates through the range. Returns the first item X where:
     U¥      //   Input ==
       MgX   //   Xth Fibonacci number

Brachylog , 14 bajtów

≜∧0;1⟨t≡+⟩ⁱ↖?h

Wypróbuj online!

Pobiera dane wejściowe przez zmienną wyjściową i dane wyjściowe przez zmienną wejściową.

≜                 Label the input variable, trying 0, 1, -1, 2...,
  0               then starting with 0
 ∧                (which is not necessarily the input variable)
   ;1             paired with 1,
     ⟨t≡ ⟩        replace the first element of the pair with the last element
     ⟨ ≡+⟩        and the last element of the pair with the sum of the elements
          ⁱ↖?     a number of times equal to the input variable,
             h    such that the first element of the pair is the output variable.

Nie jestem do końca pewien, dlaczego ≜jest to konieczne.

JavaScript (przy użyciu zewnętrznej biblioteki) (84 bajtów)

n=>_.Until((i,a)=>{l=a.length;if(a[l-1]!=n){return i<=1?i:a[l-1]+a[l-2]}}).Count()-1

Link do lib: https://github.com/mvegh1/Enumerable

Objaśnienie kodu: Biblioteka ma metodę statyczną, która tworzy sekwencję, dopóki predykat nie ma niezdefiniowanej wartości zwracanej. Predykat ma sygnaturę („i” ndex, bieżąca wewnętrzna szyna „a” wygenerowana). Przy każdej iteracji sprawdzamy, czy ostatni element tablicy wewnętrznej jest równy wejściowemu, n. Jeśli nie, zwróć następną wartość w sekwencji Fib. W przeciwnym razie predykat ma niezdefiniowany wynik, który kończy generowanie sekwencji. Następnie zwracamy długość sekwencji (i odejmujemy 1, aby zachować zgodność z 0, jak widać w PO