Znajdź najbliższy numer Fibonacciego

30

Wszyscy znamy słynną sekwencję Fibonacciego , która zaczyna się od 0i 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, 34jest najbliższą liczbą Fibonacciego 30, ponieważ |34 - 30| = 4, która jest mniejsza niż druga najbliższa 21, 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 13to dokładnie 13.

  • 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, 13lub 21, 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 , więc wygrywa najkrótszy kod w bajtach w każdym języku !

Pan Xcoder
źródło
Piaskownica .
Pan Xcoder,
FWIW, oto kod Pythona na SO do robienia tego skutecznie dla dużych danych wejściowych, wraz ze skryptem, którego można użyć do pomiaru różnych algorytmów.
PM 2, dzwoni
Czy 0 jest uważane za dodatnią liczbę całkowitą?
Alix Eisenhardt
@AlixEisenhardt Nie. Dodatnia liczba całkowitan implikuje n ≥ 1.
Pan Xcoder,

Odpowiedzi:

21

Python 2 , 43 bajty

f=lambda n,a=0,b=1:a*(2*n<a+b)or f(n,b,a+b)

Wypróbuj online!

Iteruje parami kolejnych liczb Fibonacciego, (a,b)aż osiągnie wartość, w której wartość wejściowa njest mniejsza niż ich punkt środkowy (a+b)/2, a następnie wraca a.

Zapisany jako program (47 bajtów):

n=input()
a=b=1
while 2*n>a+b:a,b=b,a+b
print a

Ta sama długość :

f=lambda n,a=0,b=1:b/2/n*(b-a)or f(n,b,a+b)
xnor
źródło
15

Neim , 5 bajtów

f𝐖𝕖S𝕔

Wyjaśnienie:

f       Push infinite Fibonacci list
 𝐖                     93
  𝕖     Select the first ^ elements
        This is the maximum amount of elements we can get before the values overflow
        which means the largest value we support is 7,540,113,804,746,346,429
   S𝕔   Closest value to the input in the list

W najnowszej wersji Neima można grać w golfa do 3 bajtów:

fS𝕔

Ponieważ nieskończone listy zostały przerobione, aby wzrosły tylko do maksymalnej wartości.

Wypróbuj online!

Okx
źródło
Co to za 5 bajtów, gdy są tam 2 znaki? Jaka jest różnica między pierwszym a drugim rozwiązaniem?
caird coinheringaahing
1
Czy liczysz bajty lub znaki? Wydaje się, że pierwszy ma 15 bajtów, a drugi 7 bajtów.
Nateowami,
Prawdopodobnie ma to jakąś własną stronę kodową, w której każdy znak ma własny bajt, co oznacza, że ​​pierwszy ma 5 bajtów, a drugi 3 bajty. Różnica między nimi polega na tym, że pierwszy wybiera manualnie pierwsze 93 elementy, podczas gdy drugi fragment w nowszej wersji automatycznie wybiera najwyższą możliwą wartość, jaką mogą obsłużyć języki int
Roman Gräf
1
@cairdcoinheringaahing Często miałem problemy z tym, że ludzie nie mogli zobaczyć moich programów. Zrzut ekranu
Okx,
1
@Okx Oh OK, ciekawe, nie zgadłbym.
Nateowami,
8

R , 70 67 64 62 60 bajtów

-2 bajty dzięki djhurio!

-2 dodatkowe bajty dzięki djhurio (chłopiec może on golf!)

F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]

Ponieważ musimy obsługiwać tylko wartości 10^8, działa to.

Wypróbuj online!

Czyta nze standardowego. whilepętli generuje Fibonacciego w F(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 elementu Fz ostrzeżeniem

Pierwotnie użyłem F[which.min(abs(F-n))]naiwnego podejścia, ale @djhurio zasugerował, (F-n)^2ponieważ kolejność będzie równoważna, a orderzamiast which.min. orderzwraca 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:

F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][‌​1]

przechowuje tylko dwie ostatnie liczby Fibonacciego

Giuseppe
źródło
1
Niezłe. -2 bajtyF=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
djhurio
1
I szybka wersja z taką samą liczbą bajtówF=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
djhurio
1
@djhurio nice! Dziękuję Ci bardzo.
Giuseppe,
1
Lubię to. Ponownie -2 bajtyF=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
djhurio
Korzystanie z wbudowanego narzędzia do generowania fibnum jest krótsze:numbers::fibonacci(x<-scan(),T)
JAD
6

JavaScript (ES6), 41 bajtów

f=(n,x=0,y=1)=>y<n?f(n,y,x+y):y-n>n-x?x:y
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0

Zaokrągla w górę według preferencji.

Neil
źródło
Prawie identyczny z wersją, nad którą pracowałem. Przynajmniej nie używałeś tych samych nazw zmiennych, inaczej bym się przeraził.
Grax32,
@Grax Huh, teraz o tym wspominasz, Business Cat mnie pobił ...
Neil
(Cóż, prawie ... Zmusiłem moją wersję do pracy z 0, bo dlaczego nie?)
Neil
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.
Alix Eisenhardt
6

Galareta , 9 7 bajtów

-2 bajty dzięki @EriktheOutgolfer

‘RÆḞạÐṂ

Wypróbuj online!

Zapraszamy do gry w golfa :). Pobiera liczbę całkowitą dla danych wejściowych i zwraca liczbę całkowitą.

            ' input -> 4
‘           ' increment -> 5
 R          ' range -> [1,2,3,4,5]
  ÆḞ        ' fibonacci (vectorizes) -> [1,1,2,3,5,8]
     ÐṂ     ' filter and keep the minimum by:
    ạ       ' absolute difference -> [3,3,2,1,1,4]
            ' after filter -> [3,5]
nmjcman101
źródło
Możesz usunąć µḢ.
Erik the Outgolfer,
@EriktheOutgolfer jak w: „Istnieje sposób, aby to zrobić, jeśli się nad tym zastanowić”, lub jak w „Jeśli dosłownie po prostu cofasz je, nadal działa”?
nmjcman101,
Jak w „jest to dozwolone przez reguły”. : P
Erik the Outgolfer
Ach Dziękuję Ci! (Tekst wypełniający)
nmjcman101,
5

Kod maszynowy x86-64, 24 bajty

31 C0 8D 50 01 92 01 C2 39 FA 7E F9 89 D1 29 FA 29 C7 39 D7 0F 4F C1 C3

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 do EAXrejestru.

Mnemoniki do montażu bez golfa:

; unsigned int ClosestFibonacci(unsigned int n);
    xor    eax, eax        ; initialize EAX to 0
    lea    edx, [rax+1]    ; initialize EDX to 1

  CalcFib:
    xchg   eax, edx        ; swap EAX and EDX
    add    edx, eax        ; EDX += EAX
    cmp    edx, edi
    jle    CalcFib         ; keep looping until we find a Fibonacci number > n

    mov    ecx, edx        ; temporary copy of EDX, because we 'bout to clobber it
    sub    edx, edi
    sub    edi, eax
    cmp    edi, edx
    cmovg  eax, ecx        ; EAX = (n-EAX > EDX-n) ? EDX : EAX
    ret

Wypróbuj online!

Kod dzieli się zasadniczo na trzy części:

  • Pierwsza część jest bardzo prosta: po prostu inicjuje nasze działające rejestry. EAXjest 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 rejestry EAXi EDX. To podejście jest tutaj wyjątkowo wygodne, ponieważ daje nam sąsiednie liczby Fibonacciego. Kandydat potencjalnie mniej niż n jest przetrzymywany EAX, 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 EAXi EDX, 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ę EDXdo EAXlub pozostawia w EAXspokoju, więc gdy funkcja się RETurnie, zwracana jest najbliższa liczba Fibonacciego EAX.

W przypadku remisu zwracana jest mniejsza z dwóch wartości kandydujących, ponieważ użyliśmy CMOVGzamiast CMOVGEwyboru. 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!

Cody Gray
źródło
Listy NASM są dobre dla odpowiedzi codegolf, ponieważ mieszają bajty kodu maszynowego z oryginalnym komentarzem źródłowym nieco zwięźle. W 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.
Peter Cordes,
1
W kodzie 32-bitowym możesz otrzymać eax = 0 i edx = 1 tylko w 4 bajtach zamiast 5, za pomocą xor eax,eax/ cdq/ inc edx. Możesz więc stworzyć 32-bitową wersję konwencji niestandardowych wywołań, która oszczędza bajt.
Peter Cordes,
Kiedyś to robiłem, @Peter, ale tutaj jest dużo zamieszania, jeśli chodzi o „składanie” lub „kod maszynowy”. Najwyraźniej niektórzy doświadczeni użytkownicy utrzymują, że istnieje różnica, i sprzeciwiają się mojemu liczeniu bajtów kodu maszynowego w celu uzyskania odpowiedzi, która jest prezentowana przy użyciu mnemoników asemblera. Oczywiście myślę, że to głupie, ponieważ „asembler” to po prostu mnemoniczna reprezentacja bajtów maszyny, ale przegłosowałem. Przekonałem się, że osobna prezentacja powoduje mniejsze tarcie, nawet jeśli osobiście mi się to nie podoba.
Cody Gray
Druga sztuczka jest miła - dzięki. Powinienem był o tym myśleć, cdqdużo używam w odpowiedziach na golfa. Niestandardowa konwencja wywoływania nie jest wymagana. Zazwyczaj używam __fastcallkonwencji 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ć.
Cody Gray
Ach tak, każda stara konwencja wywoływania rejestru działa dla ciebie. Moja ostatnia odpowiedź codegolf wymagała wskazówek wedi / esifor lodsb/ 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).
Peter Cordes
4

PowerShell , 80 74 bajtów

param($n)for($a,$b=1,0;$a-lt$n;$a,$b=$b,($a+$b)){}($b,$a)[($b-$n-gt$n-$a)]

(Wypróbuj online! Tymczasowo nie odpowiada)

Iteracyjne rozwiązanie. Staje wejściowych $n, zestawy $a,$bsię 1,0, a następnie pętle Fibonacciego dopóki $ajest 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 $njest większa niż między $ndrugim elementem. Pozostaje w przygotowaniu, wynik jest domyślny.

AdmBorkBork
źródło
4

JavaScript (ES6), 67 bajtów

f=(n,k,y)=>(g=k=>x=k>1?g(--k)+g(--k):k)(k)>n?x+y>2*n?y:x:f(n,-~k,x)

Przypadki testowe

Arnauld
źródło
4

JavaScript (węzeł Babel) , 41 bajtów

f=(n,i=1,j=1)=>j<n?f(n,j,j+i):j-n>n-i?i:j

Oparte na niesamowitej odpowiedzi Pythona ovs

Wypróbuj online!

Nie golfił

f=(n,i=1,j=1)=> // Function f: n is the input, i and j are the most recent two Fibonacci numbers, initially 1, 1
 j<n?           // If j is still less than n
  f(n,j,j+i)    //  Try again with the next two Fibonacci numbers
 :              // Else:
  j-n>n-i?i:j   //  If n is closer to i, return i, else return j
Business Cat
źródło
Zostało to skomentowane w mojej odpowiedzi, ale sprawiłoby, że przestałby działać 0(nie jest to konieczne; po prostu chcę):f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i)
Neil
4

Python, 74 bajty

import math
r=5**.5
p=r/2+.5
lambda n:round(p**int(math.log(n*2*r,p)-1)/r)

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.

Anders Kaseorg
źródło
Cholera, wiedziałem, że coś takiego musi być możliwe. Dobra robota! (+1)
SteamyRoot,
3

C (gcc) , 86 85 83 76 bajtów

f(n){n=n<2?:f(n-1)+f(n-2);}i,j,k;g(n){for(;k<n;j=k,k=f(i++));n=k-n<n-j?k:j;}

Wypróbuj online!

cleblanc
źródło
3

Python 3 , 103 bajty

import math
def f(n):d=5**.5;p=.5+d/2;l=p**int(math.log(d*n,p))/d;L=[l,p*l];return round(L[2*n>sum(L)])

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 bajty

lambda n:r(p**r(math.log(d*n,p))/d)
import math
d=5**.5
p=.5+d/2
r=round

Wypró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.

SteamyRoot
źródło
Dobra robota! Witamy w PPCG :)
musicman523
Aby rzetelnie obliczyć liczbę bajtów twojego kodu, myślę, że musisz przypisać lambda, jak pokazano w innych odpowiedziach w języku Python. Jednak ten algorytm nie zawsze działa poprawnie dla nw zakresie (1, 1 + 10 ** 8). Np. N = 70 zwraca 89, ale powinno zwracać 55. Oto n wartości <120, dla których daje błędne odpowiedzi: (27, 44, 70, 71, 114, 115, 116). Do celów testowych możesz użyć nearest_fib_PM2Rfunkcji, którą podłączyłem w komentarzu do pytania.
PM 2, dzwoni
@ PM2Ring Masz rację, popełniłem głupi błąd ... Mam teraz prawidłowe rozwiązanie, ale z dużo większą liczbą bajtów. Co do lambda, uważam, że się mylisz. Wierzę, że odpowiedzi przypisujące lambda robią to tylko dlatego, że używają rekurencji. Inne odpowiedzi w Pythonie 3 nie przypisują na przykład pierwszej lambda.
SteamyRoot,
3

Taxi, 2321 bajtów

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Trunkers.Go to Trunkers:n 1 l 1 l.0 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 2 l.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[a]Pickup a passenger going to Rob's Rest.Pickup a passenger going to Magic Eight.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Rob's Rest:n.Go to Trunkers:s 1 l 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Trunkers.Pickup a passenger going to Magic Eight.Go to Zoom Zoom:n.Go to Trunkers:w 3 l.Go to Magic Eight:e 1 r.Switch to plan "b" if no one is waiting.Pickup a passenger going to Firemouth Grill.Go to Firemouth Grill:w 1 r.Go to Rob's Rest:w 1 l 1 r 1 l 1 r 1 r.Pickup a passenger going to Cyclone.Go to Bird's Bench:s.Pickup a passenger going to Addition Alley.Go to Cyclone:n 1 r 1 l 2 l.Pickup a passenger going to Addition Alley.Pickup a passenger going to Bird's Bench.Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Switch to plan "a".[b]Go to Trunkers:w 1 l.Pickup a passenger going to Cyclone.Go to Bird's Bench:w 1 l 1 r 1 l.Pickup a passenger going to Cyclone.Go to Rob's Rest:n.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to What's The Difference.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 l.Pickup a passenger going to Magic Eight.Go to Sunny Skies Park:e 1 r 1 l.Go to Cyclone:n 1 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to What's The Difference.Go to Sunny Skies Park:n 1 r.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 r 1 l.Pickup a passenger going to Magic Eight.Go to Magic Eight:e 1 r 2 l 2 r.Switch to plan "c" if no one is waiting.Go to Sunny Skies Park:w 1 l 1 r.Pickup a passenger going to The Babelfishery.Go to Cyclone:n 1 l.Switch to plan "d".[c]Go to Cyclone:w 1 l 2 r.[d]Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 2 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

Wypróbuj online!
Wypróbuj online z komentarzami!

Nie grał w golfa z komentarzami:

[ Find the Fibonacci number closest to the input ]
[ Inspired by: https://codegolf.stackexchange.com/q/133365 ]


[ n = STDIN ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Trunkers.
Go to Trunkers: north 1st left 1st left.


[ Initialize with F0=0 and F1=1 ]
0 is waiting at Starchild Numerology.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd left.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 1st right 4th left.


[ For (i = 1; n > F(i); i++) { Store F(i) at Rob's Rest and F(i-1) at Bird's Bench } ]
[a]
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Magic Eight.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Rob's Rest: north.
Go to Trunkers: south 1st left 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Trunkers.
Pickup a passenger going to Magic Eight.
Go to Zoom Zoom: north.
Go to Trunkers: west 3rd left.
Go to Magic Eight: east 1st right.
Switch to plan "b" if no one is waiting.

[ n >= F(i) so iterate i ]
Pickup a passenger going to Firemouth Grill.
Go to Firemouth Grill: west 1st right.
Go to Rob's Rest: west 1st left 1st right 1st left 1st right 1st right.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: south.
Pickup a passenger going to Addition Alley.
Go to Cyclone: north 1st right 1st left 2nd left.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Bird's Bench.
Go to Addition Alley: north 2nd right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left.
Switch to plan "a".


[b]
[ F(i) > n which means n >= F(i-1) and we need to figure out which is closer and print it]
Go to Trunkers: west 1st left.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: west 1st left 1st right 1st left.
Pickup a passenger going to Cyclone.
Go to Rob's Rest: north.
Pickup a passenger going to Cyclone.
Go to Cyclone: south 1st left 1st left 2nd left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to What's The Difference.
Pickup a passenger going to What's The Difference.
[ Passengers:n, n, F(i-1) ]
Go to What's The Difference: north 1st left.
Pickup a passenger going to Magic Eight.
[ Passengers:n, n-F(i-1) ]
Go to Sunny Skies Park: east 1st right 1st left.
Go to Cyclone: north 1st left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to What's The Difference.
[ Passengers: n-F(i-1), F(i-1), F(i) ]
Go to Sunny Skies Park: north 1st right.
Pickup a passenger going to What's The Difference.
[ Passengers: n-F(i-1), F(i), n ]
Go to What's The Difference: north 1st right 1st left.
[ Passengers: n-F(i-1), F(i)-n ]
Pickup a passenger going to Magic Eight.
Go to Magic Eight: east 1st right 2nd left 2nd right.
Switch to plan "c" if no one is waiting.

[ If no one was waiting, then {n-F(i-1)} < {F(i)-n} so we return F(i-1) ]
Go to Sunny Skies Park: west 1st left 1st right.
Pickup a passenger going to The Babelfishery.
Go to Cyclone: north 1st left.
Switch to plan "d".

[c]
[ Otherwise {n-F(i-1)} >= {F(i)-n} so we return F(i) ]
[ Note: If we didn't switch to plan c, we still pickup F(i) but F(i-1) will be the *first* passenger and we only pickup one at The Babelfishery ]
[ Note: Because of how Magic Eight works, we will always return F(i) in the event of a tie ]
Go to Cyclone: west 1st left 2nd right.
[d]
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 2nd right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Inżynier Toast
źródło
2

Python 3 , 84 bajtów

lambda k:min(map(f,range(2*k)),key=lambda n:abs(n-k))
f=lambda i:i<3or f(i-1)+f(i-2)

Wypróbuj online!

Może to działać, ale z pewnością nie jest szybkie ...

Wyjścia Truezamiast 1, ale w Pythonie są one równoważne.

notjagan
źródło
2

dc, 52 bajty

si1d[dsf+lfrdli>F]dsFxli-rlir-sdd[lild-pq]sDld<Dli+p

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ówna ii jedną, która jest większa niż i. Przekształcamy je w odpowiednie różnice, ia następnie porównujemy różnice. Wreszcie rekonstruujemy liczbę Fibonacciego, dodając lub odejmując różnicę do i.

Ups, ładowałem dwa rejestry w niewłaściwej kolejności, a następnie zamieniałem je, marnując bajt.

brhfl
źródło
Funkcje są dozwolone.
CalculatorFeline
Dzięki, wielokrotnie mi tego brakowało w tekście wyzwania.
brhfl
2

C # (.NET Core) , 63 56 bajtów

-1 bajt dzięki @Neil

-6 bajtów dzięki @Nevay

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

Wypróbuj online!

jkelm
źródło
Czy for(;b<n;a=b,b+=c)c=a;zapisuje bajt?
Neil,
Możesz usunąć cza pomocą b+=a,a=b-a(powinno zaoszczędzić 6 bajtów).
Nevay
2

Q / KDB +, 51 bajtów

{w where l=min l:abs neg[x]+w:{x,sum -2#x}/[x;0 1]}
aodNap
źródło
2
Witamy w PPCG!
Martin Ender
2

Sześciokąt , 37 bajtów

?\=-${&"*.2}+".|'=='.@.&}1.!_|._}$_}{

Wypróbuj online!

bez golfa:

   ? \ = - 
  $ { & " * 
 . 2 } + " .
| ' = = ' . @
 . & } 1 . !
  _ | . _ }
   $ _ } { 

Zepsuty:

start:
? { 2 ' * //set up 2*target number
" ' 1     //initialize curr to 1

main loop:
} = +     //next + curr + last
" -       //test = next - (2*target)
branch: <= 0 -> continue; > 0 -> return

continue:
{ } = &   //last = curr
} = &     //curr = next


return:
{ } ! @   //print last

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.

Brigmor
źródło
2

Brachylog , 22 bajty

;I≜-.∧{0;1⟨t≡+⟩ⁱhℕ↙.!}

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.

Niepowiązany ciąg
źródło
1

Java 7, 244 234 bajtów

 String c(int c){for(int i=1;;i++){int r=f(i);int s=f(i-1);if(r>c && s<c){if(c-s == r-c)return ""+r+","+s;else if(s-c > r-c)return ""+r;return ""+s;}}} int f(int i){if(i<1)return 0;else if(i==1)return 1;else return f(i-2)+f(i-1);}
0x45
źródło
Dlaczego nie używasz Java 8 i zamieniasz go w lambda? Możesz również usunąć, staticjeśli chcesz
pozostać
Masz dwa błędy w kodzie ( r>c&&s<cpowinno być r>=c&&s<=c, s-cpowinno 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-cponieważ zwracanie którejkolwiek z wartości jest dozwolone.
Nevay
@Nigdy nie widzę błędu, przetestowałem go bezbłędnie
0x45
1

Pyke , 6 bajtów

}~F>R^

Wypróbuj online!

}      -    input*2
 ~F    -   infinite list of the fibonacci numbers
   >   -  ^[:input]
    R^ - closest_to(^, input)
niebieski
źródło
1

Common Lisp, 69 bajtów

(lambda(n)(do((x 0 y)(y 1(+ x y)))((< n y)(if(<(- n x)(- y n))x y))))

Wypróbuj online!

Renzo
źródło
1

Perl 6 , 38 bajtów

{(0,1,*+*...*>$_).sort((*-$_).abs)[0]}

Sprawdź to

{   # bare block lambda with implicit parameter 「$_」

  ( # generate Fibonacci sequence

    0, 1,  # seed the sequence
    * + *  # WhateverCode lambda that generates the rest of the values
    ...    # keep generating until
    * > $_ # it generates one larger than the original input
           # (that larger value is included in the sequence)

  ).sort(           # sort it by
    ( * - $_ ).abs  # the absolute difference to the original input
  )[0]              # get the first value from the sorted list
}

Aby dodać potencjalne przyspieszenie, dodaj .tail(2)wcześniej .sort(…).

W przypadku remisu zawsze zwróci mniejszą z dwóch wartości, ponieważ sortjest to rodzaj stabilny. (dwie wartości, które posortowałyby to samo, zachowują swoją kolejność)

Brad Gilbert b2gills
źródło
1

Pyth, 19 bajtów

JU2VQ=+Js>2J)hoaNQJ

Wypróbuj tutaj

Wyjaśnienie

JU2VQ=+Js>2J)hoaNQJ
JU2                  Set J = [0, 1].
   VQ=+Js>2J)        Add the next <input> Fibonacci numbers.
              oaNQJ  Sort them by distance to <input>.
             h       Take the first.

źródło