Wszyscy znamy słynną sekwencję Fibonacciego , która zaczyna się od 0
i 1
, a każdy element jest sumą dwóch poprzednich. Oto kilka pierwszych warunków (OEIS A000045 ):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
Biorąc pod uwagę dodatnią liczbę całkowitą , zwróć najbliższą liczbę sekwencji Fibonacciego, zgodnie z następującymi regułami:
Najbliższa liczba Fibonacciego jest definiowana jako liczba Fibonacciego o najmniejszej różnicy bezwzględnej z danej liczby całkowitej. Na przykład,
34
jest najbliższą liczbą Fibonacciego30
, ponieważ|34 - 30| = 4
, która jest mniejsza niż druga najbliższa21
, dla której|21 - 30| = 9
.Jeśli podana liczba całkowita należy do sekwencji Fibonacciego, najbliższa liczba Fibonacciego jest dokładnie sama. Na przykład najbliższa liczba Fibonacciego
13
to dokładnie13
.W przypadku remisu możesz wybrać wyjście jednej z liczb Fibonacciego, które są najbliżej wejścia, lub po prostu wyprowadzić je obie. Na przykład, jeśli wejście jest
17
, wszystkie z poniższych są ważne:21
,13
lub21, 13
. Jeśli zwrócisz je oba, podaj format.
Obowiązują domyślne luki . Możesz pobierać dane wejściowe i dostarczać dane wyjściowe dowolną standardową metodą . Twój program / funkcja może obsługiwać tylko wartości do 10 8 .
Przypadki testowe
Wejście -> Wyjście 1 -> 1 3 -> 3 4 -> 3 lub 5 lub 3, 5 6 -> 5 7 -> 8 11 -> 13 17 -> 13 lub 21 lub 13, 21 63 -> 55 101 -> 89 377 -> 377 467 -> 377 500 -> 610 1399 -> 1597
Punktacja
To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach w każdym języku !
n
implikujen ≥ 1
.Odpowiedzi:
Python 2 , 43 bajty
Wypróbuj online!
Iteruje parami kolejnych liczb Fibonacciego,
(a,b)
aż osiągnie wartość, w której wartość wejściowan
jest mniejsza niż ich punkt środkowy(a+b)/2
, a następnie wracaa
.Zapisany jako program (47 bajtów):
Ta sama długość :
źródło
Neim , 5 bajtów
Wyjaśnienie:
W najnowszej wersji Neima można grać w golfa do 3 bajtów:
Ponieważ nieskończone listy zostały przerobione, aby wzrosły tylko do maksymalnej wartości.
Wypróbuj online!
źródło
Python ,
5552 bajtówWypróbuj online!
źródło
R ,
7067646260 bajtów-2 bajty dzięki djhurio!
-2 dodatkowe bajty dzięki djhurio (chłopiec może on golf!)
Ponieważ musimy obsługiwać tylko wartości
10^8
, działa to.Wypróbuj online!
Czyta
n
ze standardowego.while
pętli generuje Fibonacciego wF
(malejące); w przypadku remisu zwracany jest większy. Spowoduje to wywołanie wielu ostrzeżeń, ponieważwhile(F<1e8)
ocenia tylko instrukcję dla pierwszego elementuF
z ostrzeżeniemPierwotnie użyłem
F[which.min(abs(F-n))]
naiwnego podejścia, ale @djhurio zasugerował,(F-n)^2
ponieważ kolejność będzie równoważna, aorder
zamiastwhich.min
.order
zwraca permutację indeksów, aby uporządkować dane wejściowe w porządku rosnącym, więc[1]
na końcu potrzebujemy tylko pierwszej wartości.szybsza wersja:
przechowuje tylko dwie ostatnie liczby Fibonacciego
źródło
F=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
numbers::fibonacci(x<-scan(),T)
JavaScript (ES6), 41 bajtów
Zaokrągla w górę według preferencji.
źródło
f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y)
Ponieważ nie musisz pracować z 0, możesz grać w golfa trochę więcej.Galareta ,
97 bajtów-2 bajty dzięki @EriktheOutgolfer
Wypróbuj online!
Zapraszamy do gry w golfa :). Pobiera liczbę całkowitą dla danych wejściowych i zwraca liczbę całkowitą.
źródło
µḢ
.Mathematica, 30 bajtów
Wypróbuj online!
źródło
Kod maszynowy x86-64, 24 bajty
Powyższe bajty kodu definiują funkcję w 64-bitowym kodzie maszynowym x86, który znajduje liczbę Fibonacciego najbliższą podanej wartości wejściowej,
n
.Funkcja jest zgodna z konwencją wywoływania AMD64 w Systemie V (standard w systemach Gnu / Unix), dzięki czemu jedyny parametr (
n
) jest przekazywany w parametrzeEDI
rejestru, a wynik jest zwracany doEAX
rejestru.Mnemoniki do montażu bez golfa:
Wypróbuj online!
Kod dzieli się zasadniczo na trzy części:
EAX
jest ustawiony na 0 iEDX
jest ustawiony na 1.Następna część jest pętla iteracyjnie oblicza numery Fibonacciego na dowolnej stronie poziomu wejściowego
n
. Ten kod jest oparty na mojej poprzedniej implementacji Fibonacciego z odejmowaniem , ale… um… nie jest z odejmowaniem. :-) W szczególności wykorzystuje tę samą sztuczkę obliczania liczby Fibonacciego przy użyciu dwóch zmiennych - tutaj są to rejestryEAX
iEDX
. To podejście jest tutaj wyjątkowo wygodne, ponieważ daje nam sąsiednie liczby Fibonacciego. Kandydat potencjalnie mniej niżn
jest przetrzymywanyEAX
, podczas gdy kandydat potencjalnie większy niżn
jest przetrzymywanyEDX
. Jestem dość dumny z tego, jak ścisły byłem w stanie zrobić kod wewnątrz tej pętli (i jeszcze bardziej łaskotałem, że odkryłem go niezależnie, a dopiero później zdałem sobie sprawę, jak podobny jest do odpowiedzi odejmowania powiązanej powyżej).Kiedy mamy już dostępne wartości Fibonacciego
EAX
iEDX
, jest to koncepcyjnie prosta kwestia ustalenia, która z nich jest bliższa (pod względem wartości bezwzględnej)n
. Właściwie biorąc wartość bezwzględną kosztowałoby sposób zbyt wiele bajtów, więc po prostu zrobić serię odejmowania. Komentarz po prawej stronie przedostatniej instrukcji warunkowego przeniesienia trafnie wyjaśnia logikę tutaj. To przenosi sięEDX
doEAX
lub pozostawia wEAX
spokoju, więc gdy funkcja sięRET
urnie, zwracana jest najbliższa liczba FibonacciegoEAX
.W przypadku remisu zwracana jest mniejsza z dwóch wartości kandydujących, ponieważ użyliśmy
CMOVG
zamiastCMOVGE
wyboru. Jest to trywialna zmiana, jeśli wolisz inne zachowanie. Zwrócenie obu wartości nie jest jednak początkowe; proszę tylko jeden wynik liczb całkowitych!źródło
nasm foo.asm -l /dev/stdout | cut -b -28,$((28+12))-
niedawnej odpowiedzi przycinałem niektóre kolumny między kodem maszynowym a źródłem.xor eax,eax
/cdq
/inc edx
. Możesz więc stworzyć 32-bitową wersję konwencji niestandardowych wywołań, która oszczędza bajt.cdq
dużo używam w odpowiedziach na golfa. Niestandardowa konwencja wywoływania nie jest wymagana. Zazwyczaj używam__fastcall
konwencji wywoływania Microsoft dla kodu 32-bitowego. Zaletą tego jest to, że jest obsługiwany przez GCC z adnotacją, dzięki czemu możesz nadal korzystać z usługi TIO, którą każdy chce zobaczyć.edi
/esi
forlodsb
/stosb
, i robi to tylko SysV x86-64 (fajny fakt: celowo z tego powodu, ponieważ niektóre funkcje przekazują swoje argumenty do memset / memcpy, i myślę, że gcc w tym czasie lubił do wstawiania ciągów operacji).PowerShell ,
8074 bajtów(Wypróbuj online! Tymczasowo nie odpowiada)
Iteracyjne rozwiązanie. Staje wejściowych
$n
, zestawy$a,$b
się1,0
, a następnie pętle Fibonacciego dopóki$a
jest większa niż na wejściu. W tym momencie indeksujemy w($b,$a)
oparciu o wartość logiczną tego, czy różnica między pierwszym elementem i$n
jest większa niż między$n
drugim elementem. Pozostaje w przygotowaniu, wynik jest domyślny.źródło
JavaScript (ES6), 67 bajtów
Przypadki testowe
Pokaż fragment kodu
źródło
JavaScript (węzeł Babel) , 41 bajtów
Oparte na niesamowitej odpowiedzi Pythona ovs
Wypróbuj online!
Nie golfił
źródło
0
(nie jest to konieczne; po prostu chcę):f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i)
Python, 74 bajty
Wypróbuj online!
Jak to działa
Dla wszystkich k ≥ 0, ponieważ | φ - k / √5 | <1/2, F k = φ k / √5 + φ - k / √5 = okrągły (φ k / √5). Zatem wartość zwracana zmienia się z F k - 1 na F k dokładnie tam, gdzie k = log φ ( n ⋅2⋅5) - 1 lub n = φ k + 1 / (2√5), co jest w zakresie 1/4 F k + 1/2 = ( F k - 1 + F k ) / 2.
źródło
05AB1E , 6 bajtów
Wypróbuj online!
źródło
C (gcc) ,
86858376 bajtówWypróbuj online!
źródło
Java (OpenJDK 8) ,
605756 bajtówWypróbuj online!
-1 bajt dzięki @Neil
źródło
Python 3 , 103 bajty
Wypróbuj online!
Niestety musiałem użyć def zamiast lambda ... Prawdopodobnie jest tu dużo miejsca na ulepszenia.
Oryginalna (niepoprawna) odpowiedź:
Python 3 , 72 bajtyWypróbuj online!
Moje pierwsze zgłoszenie PPCG. Zamiast albo obliczać rekurencyjnie liczby Fibonacciego, albo mieć ich predefiniowane, ten kod używa tego, w jaki sposób n-ta liczba Fibonacciego jest najbliższą liczbą całkowitą do n-tej potęgi złotego podziału podzielonej przez pierwiastek z 5.
źródło
nearest_fib_PM2R
funkcji, którą podłączyłem w komentarzu do pytania.Taxi, 2321 bajtów
Wypróbuj online!
Wypróbuj online z komentarzami!
Nie grał w golfa z komentarzami:
źródło
Python 3 , 84 bajtów
Wypróbuj online!
Może to działać, ale z pewnością nie jest szybkie ...
Wyjścia
True
zamiast1
, ale w Pythonie są one równoważne.źródło
dc, 52 bajty
Wypróbuj online!
Pobiera dane wejściowe przy uruchomieniu przy użyciu?
Edytowane, aby przyjąć górną część stosu jako wartość wejściową, -1 bajt.
Wejście jest przechowywane w rejestrze
i
. Następnie kładziemy 1 i 1 na stosie, aby rozpocząć sekwencję Fibonacciego i generujemy sekwencję, dopóki nie osiągniemy wartości większej niżi
. W tym momencie na stosie mamy dwie liczby w sekwencji Fibonacciego: jedną, która jest mniejsza lub równai
i jedną, która jest większa niżi
. Przekształcamy je w odpowiednie różnice,i
a następnie porównujemy różnice. Wreszcie rekonstruujemy liczbę Fibonacciego, dodając lub odejmując różnicę doi
.Ups, ładowałem dwa rejestry w niewłaściwej kolejności, a następnie zamieniałem je, marnując bajt.
źródło
C # (.NET Core) ,
6356 bajtów-1 bajt dzięki @Neil
-6 bajtów dzięki @Nevay
Wypróbuj online!
źródło
for(;b<n;a=b,b+=c)c=a;
zapisuje bajt?c
za pomocąb+=a,a=b-a
(powinno zaoszczędzić 6 bajtów).Q / KDB +, 51 bajtów
źródło
Sześciokąt , 37 bajtów
Wypróbuj online!
bez golfa:
Zepsuty:
Podobnie jak niektóre inne plakaty, zdałem sobie sprawę, że kiedy punkt środkowy ostatniego i curr jest większy niż cel, mniejszy z dwóch jest najbliższy lub związany z najbliższym.
Punkt środkowy to (ostatni + curr) / 2. Możemy to skrócić, ponieważ next jest już ostatnim + curr, a jeśli zamiast tego pomnożymy docelową liczbę całkowitą przez 2, musimy tylko sprawdzić, czy (dalej - 2 * cel)> 0, a następnie wrócić na końcu.
źródło
Brachylog , 22 bajty
Wypróbuj online!
Naprawdę wszystko, co tutaj zrobiłem, to wkleić razem Klasyczny Fatalize Zwróć najbliższe rozwiązanie liczby pierwszej i moje własne Czy jestem liczbą Fibonacciego? rozwiązanie. Na szczęście ten ostatni działa już na zmiennej wyjściowej; niestety zawiera także niezbędne cięcie, które należy odizolować dla +2 bajtów, więc jedynym punktem, który odrzuca, jest
ⁱ
pozostawienie≜
nienaruszone.źródło
Japt
-g
, 8 bajtówSpróbuj
źródło
Java 7,
244234 bajtówźródło
static
jeśli chceszr>c&&s<c
powinno byćr>=c&&s<=c
,s-c
powinno byćc-s
), możesz usunąć niepotrzebne białe znaki, użyćint f(int i){return i<2?i:f(--i)+f(--i);}
, użyć pojedynczej instrukcji return z operatorem trójskładnikowym w c oraz usunąć specjalną obsługę,c-s==r-c
ponieważ zwracanie którejkolwiek z wartości jest dozwolone.Pyke , 6 bajtów
Wypróbuj online!
źródło
Common Lisp, 69 bajtów
Wypróbuj online!
źródło
Perl 6 , 38 bajtów
Sprawdź to
Aby dodać potencjalne przyspieszenie, dodaj
.tail(2)
wcześniej.sort(…)
.W przypadku remisu zawsze zwróci mniejszą z dwóch wartości, ponieważ
sort
jest to rodzaj stabilny. (dwie wartości, które posortowałyby to samo, zachowują swoją kolejność)źródło
Pyth, 19 bajtów
Wypróbuj tutaj
Wyjaśnienie
źródło
Haskell, 48 bajtów
Wypróbuj online!
źródło