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_n
twoją 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
Odpowiedzi:
Właściwie 1 bajt
Tak, jest do tego wbudowany od 16 listopada 2015 .
Wypróbuj online
Dla zabawy, bez wbudowanego, ma 9 bajtów:
Wypróbuj online!
Wyjaśnienie:
źródło
Mathematica, 25 bajtów
Funkcjonować. Całkiem zrozumiałe, jeśli mnie zapytasz.
źródło
Python,
363432 bajtyPoprzednie wersje:
Wyjaśnienie
Podstawową ideą jest odwrócenie formuły
co nam to mówi
dostać
Optymalizacje gry w golfa to:
len(str(n))
do obliczania bazy danych dziennika 10 bez importowanialog
(stara wersja używana.bit_length()
do obliczania bazy danych dziennika 2)n
moc, aby zbliżenie logarytmu mogło rozróżniać kolejne liczby FibonacciegoNastę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.
źródło
f=
nie jest liczony.lambda n:~-len(`66*n**6`)//1.24
powinno działać.05AB1E , 3 bajty
Kod:
Wyjaśnienie:
Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .
źródło
Galaretka,
1411 bajtówWypró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:
To jest prawidłowa odpowiedź, teraz musimy poradzić sobie ze specjalnym przypadkiem „0”. Z „0” jako argumentem, otrzymujemy
-infinity
, więc wracamyźródło
Julia,
272618 bajtówWykorzystuje 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 105 .
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 .
źródło
JavaScript,
5450695042 bajtówNa 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ę.
Dzięki @edc za skrócenie o 8 bajtów.
źródło
b=>{for(j=1,i=c=0;b-i;c++)i=j+(j=i);return c}
45,b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c
Perl 6
33 3027 bajtówSpróbuj
Wyjaśnienie:
Test:
źródło
first *==$_
justfirst $_
, ponieważ liczba jest prawidłowym inteligentnym dopasowaniem....
operatora zamiastfirst
Galaretka , 8 bajtów
Wypróbuj online! Zauważ, że to podejście jest zbyt nieefektywne dla ostatniego przypadku testowego.
Jak to działa
źródło
Pyke, 5 bajtów
Wypróbuj tutaj!
źródło
Python, 29 bajtów
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źródło
JavaScript (ES6),
3933 bajtówNawet w przypadku ES7 odwrotna formuła Bineta zajmuje 47 bajtów:
źródło
log
i wstępnie oblicz wszystkie stałe ...f(n,k,j+k)
powinieneś dołączyć zadanief=
i policzyć je jako +2 bajty . Reguła dla nienazwanych lambdas nie powinna mieć tutaj zastosowania.Sage, 49 bajtów
Dzięki TuukkaX za sugestię na temat zapisywania
sqrt(5)
jakos
ogolił 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ótszego5**.5
- to dlatego, że5**.5
jest obliczany zpow
funkcją C i traci precyzję z powodu problemów ze zmiennoprzecinkowymi. Wiele funkcji matematycznych (w tymsqrt
ilog
) jest przeciążonych w Sage, aby zwrócić dokładną, symboliczną wartość, która nie traci precyzji.źródło
sqrt(5)
zmienną i użyć jej dwa razy, zamiast pisaćsqrt(5)
dwa razy?MATL , 14 bajtów
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:
Jak to jest zrobione
źródło
O1G:"yy+]vGmfq
t?17L&YlXkQ
5X^*
. ( Zrobiłem to wcześniej .) I nie znam wystarczająco MATL-a, aby móc go ciągle ulepszać.Python, 38 bajtów
Przetestuj na Ideone .
źródło
JavaScript, 22 bajty
źródło
-Infinity|0
jest0
w JavaScript. Domyśl.-Infinity = FFF00000 00000000
. Z przyjemnością się dowiedziałem, że oszczędza 3 bajty, ponieważ nie musiałem przygotowywać jawnego testu zerowegon&&
. Poza tym głównym celem|0
jest zamiennikMath.trunc()
(jak÷
u Julii).C,
6258 bajtówSzczegółowe
źródło
Java 7, 70 bajtów
https://ideone.com/I4rUC5
źródło
int c(int n){int a=0,b=1,c=0,t;for(;a<n;t=b,b+=a,a=t)c++;return c;}
(nie testowano)int c(int n){int a=0,b=1,c=0;while(a<n){c++;b+=a;a=b-a;}return c;}
(nie testowano)int c(int n){int a=0,b=1,c=0;for(;a<n;b+=a,a=b-a)c++;return c;}
(nie testowano)TSQL, 143 bajty
Wejście wchodzi
@n
jak wDECLARE @n INT = 1836311903;
źródło
Haskell, 45 bajtów
źródło
Sesos , 28 bajtów
Hexdump:
Wypróbuj online!
(Czas wykładniczy, ponieważ w Sesos kopiowanie liczby wymaga czasu wykładniczego.)
Zespół użyty do wygenerowania pliku binarnego:
źródło
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.
Nie golfowany:
źródło
Pyth, 13 bajtów
Zestaw testowy.
Przybliżenie w Pythonie 2:
alternatywne podejście, 18 bajtów
Zestaw testowy.
Używa
.I
odwrotności.źródło
Java 7, 89 bajtów
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.)
Wynik:
źródło
Perl 5.10, 48 bajtów
Zasadniczo szukasz prawa
n
, abyF(n) = input
.-a
przełącznik dodaje jeden bajt.Wypróbuj tutaj!
źródło
J,
322717 bajtówOblicza 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.
Wyjaśnienie
źródło
Mathematica, 30 bajtów
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.źródło
Japt , 10 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Brachylog , 14 bajtów
Wypróbuj online!
Pobiera dane wejściowe przez zmienną wyjściową i dane wyjściowe przez zmienną wejściową.
Nie jestem do końca pewien, dlaczego
≜
jest to konieczne.źródło
JavaScript (przy użyciu zewnętrznej biblioteki) (84 bajtów)
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
źródło
n=>{a=c=t=0,b=1;while(a<n){c++;t=b;b+=a;a=t}return c}
Wypróbuj online!