Finden Sie die nächstgelegene Fibonacci-Nummer

30

Wir alle kennen die berühmte Fibonacci-Sequenz , die mit 0und beginnt 1, und jedes Element ist die Summe der beiden vorhergehenden. Hier sind die ersten Begriffe (OEIS A000045 ):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584

Bei einer positiven Ganzzahl geben Sie die nächstliegende Zahl der Fibonacci-Sequenz nach folgenden Regeln zurück:

  • Die nächstliegende Fibonacci-Zahl ist definiert als die Fibonacci-Zahl mit der geringsten absoluten Differenz zur angegebenen ganzen Zahl. Zum Beispiel 34ist die nächstliegende Fibonacci-Zahl 30, weil |34 - 30| = 4, die kleiner ist als die zweitnächste 21, für die |21 - 30| = 9.

  • Wenn die angegebene Ganzzahl zur Fibonacci-Sequenz gehört, ist die nächstgelegene Fibonacci-Zahl genau sie selbst. Beispielsweise ist die nächstliegende Fibonacci-Zahl 13genau 13.

  • Im Falle eines Gleichstands können Sie entweder eine der Fibonacci-Zahlen ausgeben, die beide der Eingabe am nächsten liegen, oder einfach beide ausgeben. Zum Beispiel, wenn der Eingang 17, die alle der folgenden gelten: 21, 13oder 21, 13. Falls Sie beide zurücksenden, geben Sie bitte das Format an.

Es gelten Standardlücken . Sie können die Eingabe und Ausgabe über eine beliebige Standardmethode vornehmen . Ihr Programm / Ihre Funktion darf nur Werte bis 10 8 verarbeiten .


Testfälle

Eingabe -> Ausgabe

1 -> 1
3 -> 3
4 -> 3 oder 5 oder 3, 5
6 -> 5
7 -> 8
11 -> 13
17 -> 13 oder 21 oder 13, 21
63 -> 55
101 -> 89
377 -> 377
467 -> 377
500 -> 610
1399 -> 1597

Wertung

Das ist , also gewinnt der kürzeste Code in Bytes in jeder Sprache !

Mr. Xcoder
quelle
Sandkasten .
Mr. Xcoder
FWIW, hier ist ein Python-Code für SO, um dies effizient für große Eingaben zu tun, zusammen mit einem Skript, das zum Timing verschiedener Algorithmen verwendet werden kann.
PM 2Ring
Wird 0 als positive Ganzzahl betrachtet?
Alix Eisenhardt
@AlixEisenhardt Nein. Positive ganze Zahln impliziert n ≥ 1.
Mr. Xcoder

Antworten:

21

Python 2 , 43 Bytes

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

Probieren Sie es online!

Durchläuft Paare aufeinanderfolgender Fibonacci-Zahlen, (a,b)bis sie eine erreichen, bei der die Eingabe nunter ihrem Mittelpunkt liegt (a+b)/2, und kehrt dann zurück a.

Als Programm geschrieben (47 Bytes):

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

Gleiche Länge :

f=lambda n,a=0,b=1:b/2/n*(b-a)or f(n,b,a+b)
xnor
quelle
15

Neim , 5 Bytes

f𝐖𝕖S𝕔

Erläuterung:

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

In der neuesten Version von Neim kann dies auf 3 Bytes golfen werden:

fS𝕔

Da unendlich viele Listen überarbeitet wurden, um nur ihren Maximalwert zu erreichen.

Probieren Sie es online!

Okx
quelle
Wie ist das 5 Bytes, wenn es 2 Zeichen gibt? Und was ist der Unterschied zwischen der ersten und der zweiten Lösung?
Caird Coinheringaahing
1
Zählen Sie Bytes oder Zeichen? Es sieht so aus, als wären die ersten 15 Bytes und die zweiten 7 Bytes.
Nateowami
Dies hat wahrscheinlich eine Art eigene Codepage, in der jedes Zeichen ein eigenes Byte ist, was bedeutet, dass das erste 5 Byte und das zweite 3 Byte sind. Der Unterschied zwischen den beiden besteht darin, dass das erste die ersten 93 Elemente manuell auswählt, während das zweite Snipet in einer neueren Version automatisch den höchstmöglichen Wert auswählt, den die Sprachen int-Größe verarbeiten kann
Roman Gräf,
1
@cairdcoinheringaahing Ich hatte oft Probleme mit Leuten, die meine Programme nicht sehen konnten. Screenshot
Okx
1
@Okx Oh OK, interessant, ich hätte nicht gedacht.
Nateowami
8

R , 70 67 64 62 60 Bytes

-2 Bytes dank Djhurio!

-2 weitere Bytes dank Djhurio (Junge kann er Golf spielen!)

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

Da wir nur mit Werten bis zu umgehen müssen 10^8, funktioniert dies.

Probieren Sie es online!

Liest nvon stdin. Die whileSchleife generiert die Fibonacci-Zahlen in F(absteigender Reihenfolge). im Falle eines Unentschieden wird der größere zurückgegeben. Dies löst eine Reihe von Warnungen aus, da while(F<1e8)nur die Anweisung für das erste Element von ausgewertet wirdF mit einer Warnung

Ursprünglich habe ich F[which.min(abs(F-n))]den naiven Ansatz verwendet, aber @djhurio schlug vor, (F-n)^2da die Reihenfolge gleichwertig sein wird, und ordernicht which.min. orderGibt eine Permutation von Indizes zurück, um die Eingabe in aufsteigende Reihenfolge zu bringen. Daher müssen wir [1]am Ende nur den ersten Wert abrufen.

schnellere Version:

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

Speichert nur die letzten beiden Fibonacci-Zahlen

Giuseppe
quelle
1
Schön. -2 BytesF=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
Djhurio
1
Und die schnelle Version mit der gleichen Anzahl von BytesF=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
Djhurio
1
@ Djhurio schön! vielen Dank.
Giuseppe
1
Ich mag das. F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
Nochmals
Die Verwendung eines Built-In zur Erzeugung der Fibnums ist kürzer:numbers::fibonacci(x<-scan(),T)
JAD
6

JavaScript (ES6), 41 Byte

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

Rundet nach Belieben auf.

Neil
quelle
Fast identisch mit der Version, an der ich gearbeitet habe. Zumindest haben Sie nicht die gleichen Variablennamen verwendet, sonst wäre ich ausgeflippt.
Grax32
@ Grax Huh, jetzt erwähnen Sie es, Business Cat hat mich geschlagen ...
Neil
(Nun, fast ... Ich habe meine Version mit 0 arbeiten lassen, weil warum nicht?)
Neil
f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y)Da Sie nicht mit 0 arbeiten müssen, können Sie etwas mehr Golf spielen.
Alix Eisenhardt
6

Gelee , 9 7 Bytes

-2 Bytes dank @EriktheOutgolfer

‘RÆḞạÐṂ

Probieren Sie es online!

Golftipps willkommen :). Nimmt ein Int für die Eingabe und gibt eine Int-Liste zurück.

            ' 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
quelle
Sie können entfernen µḢ.
Erik der Outgolfer
@EriktheOutgolfer wie in: "Es gibt eine Möglichkeit, es zu tun, wenn Sie darüber nachdenken" oder wie in "Wenn Sie buchstäblich nur die Leertaste drücken, funktioniert es immer noch"?
nmjcman101
Wie in "Es ist nach den Regeln erlaubt". : P
Erik der Outgolfer
Ah. Vielen Dank! (
Fülltext
5

x86-64-Maschinencode, 24 Byte

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

Die obigen Codebytes definieren eine Funktion im 64-Bit-x86-Maschinencode, die die Fibonacci-Zahl findet, die dem angegebenen Eingabewert am nächsten kommt n.

Die Funktion folgt der Aufrufkonvention von System V AMD64 (Standard bei Gnu / Unix-Systemen), sodass der einzige Parameter ( n) im EDIRegister übergeben und das Ergebnis im EAXRegister zurückgegeben wird.

Ungolfed Assembler-Mnemonik:

; 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

Probieren Sie es online!

Der Code gliedert sich grundsätzlich in drei Teile:

  • Der erste Teil ist sehr einfach: Er initialisiert nur unsere Arbeitsregister. EAXwird auf 0 und EDXauf 1 gesetzt.
  • Der nächste Teil ist eine Schleife, die die Fibonacci-Zahlen auf beiden Seiten des Eingabewerts iterativ berechnet n. Dieser Code basiert auf meiner vorherigen Implementierung von Fibonacci mit Subtraktion , aber ... ähm ... nicht mit Subtraktion. :-) Insbesondere wird derselbe Trick angewendet, bei dem die Fibonacci-Zahl mit zwei Variablen berechnet wird - hier sind dies die EAXund EDX-Register. Dieser Ansatz ist hier äußerst praktisch, weil er uns benachbarte Fibonacci-Zahlen gibt. Der Kandidat, der möglicherweise kleiner als n ist, wird gehalten EAX, während der Kandidat, der möglicherweise größer als n ist, gehalten wirdEDX. Ich bin ziemlich stolz darauf, wie eng ich den Code innerhalb dieser Schleife machen konnte (und noch mehr gekitzelt, dass ich ihn unabhängig wiederentdeckte und erst später erkannte, wie ähnlich er der oben verlinkten Subtraktionsantwort war).

  • Sobald wir die Kandidaten-Fibonacci-Werte in EAXund verfügbar haben EDX, ist es konzeptionell einfach, herauszufinden, welcher näher (in Bezug auf den absoluten Wert) liegt n. Eigentlich nimmt einen Absolutwert kosten würde Art und Weise zu viele Bytes, so dass wir nur eine Reihe von Subtraktionen tun. Der Kommentar rechts neben dem vorletzten Befehl zum bedingten Verschieben erklärt die Logik hier treffend. Dies bewegt sich entweder EDXin EAXoder verlässt es EAXalleine, so dass, wenn die Funktion RETauslöst, die nächstliegende Fibonacci-Zahl zurückgegeben wird EAX.

In the case of a tie, the smaller of the two candidate values is returned, since we've used CMOVG instead of CMOVGE to do the selection. It is a trivial change, if you'd prefer the other behavior. Returning both values is a non-starter, though; only one integer result, please!

Cody Gray
quelle
NASM listings are nice for codegolf answers, since they mix the machine code bytes with the original commented source somewhat compactly. I used nasm foo.asm -l /dev/stdout | cut -b -28,$((28+12))- to trim some columns between the machine code and source in a recent answer.
Peter Cordes
1
In 32-bit code, you can get eax=0 and edx=1 in only 4 bytes instead of 5, with xor eax,eax / cdq / inc edx. So you could make a 32-bit custom-calling-convention version that saved a byte.
Peter Cordes
I used to do that, @Peter, but there's a lot of confusion here over submissions being in "assembly" or "machine code". Apparently some of the experienced users maintain that there is a difference, and object to my counting the bytes of machine code for an answer that is presented using assembly mnemonics. Naturally, I think this is stupid, because "assembly" is just a mnemonic representation of the machine bytes, but I got outvoted. I've found that the separate presentation creates less friction, even though I don't personally like it as well.
Cody Gray
The other trick is nice—thanks. I should have thought of that, I use cdq a lot in code-golf answers. A custom calling convention isn't required. I usually use the Microsoft __fastcall calling convention for 32-bit code. The nice thing about this is it's supported by GCC with an annotation, so you can still use the TIO service that everyone wants to see.
Cody Gray
Ah yes, any old register calling convention works for you . My most recent codegolf answer needed pointers in edi/esi for lodsb/stosb, and only x86-64 SysV does that (fun fact: on purpose for that reason, because some functions pass on their args to memset / memcpy, and I guess gcc at the time liked to inline string ops).
Peter Cordes
4

PowerShell, 80 74 bytes

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

(Try it online! temporarily unresponsive)

Iterative solution. Takes input $n, sets $a,$b to be 1,0, and then loops with Fibonacci until $a is larger than the input. At that point, we index into ($b,$a) based on Boolean of whether the difference between the first element and $n is greater than between $n and the second element. That's left on the pipeline, output is implicit.

AdmBorkBork
quelle
4

JavaScript (ES6), 67 bytes

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)

Test cases

Arnauld
quelle
4

JavaScript (Babel Node), 41 bytes

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

Based on ovs's awesome Python answer

Try it online!

Ungolfed

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
quelle
This was commented on my answer but it would make it stop working for 0 (not that it needs to; I just want it to): f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i)
Neil
4

Python, 74 bytes

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

Try it online!

How it works

For all k ≥ 0, since |φk/√5| < 1/2, Fk = φk/√5 + φk/√5 = round(φk/√5). So the return value switches from Fk − 1 to Fk exactly where k = logφ(n⋅2√5) − 1, or n = φk + 1/(2√5), which is within 1/4 of Fk + 1/2 = (Fk − 1 + Fk)/2.

Anders Kaseorg
quelle
Damn, I knew something like this had to be possible. Well done! (+1)
SteamyRoot
3

C (gcc), 86 85 83 76 bytes

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;}

Try it online!

cleblanc
quelle
3

Python 3, 103 bytes

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)])

Try it online!

Sadly, had to use a def instead of lambda... There's probably much room for improvement here.

Original (incorrect) answer:

Python 3, 72 bytes

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

Try it online!

My first PPCG submission. Instead of either calculating Fibonacci numbers recursively or having them predefined, this code uses how the n-th Fibonacci number is the nearest integer to the n-th power of the golden ratio divided by the root of 5.

SteamyRoot
quelle
Nice job! Welcome to PPCG :)
musicman523
To fairly calculate the byte count of your code I think you need to assign the lambda, as shown in the other Python answers. However, this algorithm doesn't always work correctly for n in range(1, 1+10**8). Eg, n=70 returns 89, but it should return 55. Here are the n values < 120 that it gives wrong answers for: (27, 44, 70, 71, 114, 115, 116). For testing purposes, you may like to use the nearest_fib_PM2R function I linked in my comment on the question.
PM 2Ring
@PM2Ring You're right, I made a stupid mistake... I now have a correct solution, but with a lot more bytes. As for the lambda, I believe you're wrong. I believe the answers assigning lambda only do so because they use recursion. The other Python 3 answers doesn't assign the first lambda, for example.
SteamyRoot
3

Taxi, 2321 bytes

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.

Try it online!
Try it online with comments!

Un-golfed with comments:

[ 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.
Engineer Toast
quelle
2

Python 3, 84 bytes

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)

Try it online!

It may work, but it's certainly not fast...

Outputs True instead of 1, but in Python these are equivalent.

notjagan
quelle
2

dc, 52 bytes

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

Try it online!

Takes input at run using ?

Edited to assume top of stack as input value, -1 byte.

Input is stored in register i. Then we put 1 and 1 on the stack to start the Fibonacci sequence, and we generate the sequence until we hit a value greater than i. At this point we have two numbers in the Fibonacci sequence on the stack: one that is less than or equal to i, and one that is greater than i. We convert these into their respective differences with i and then compare the differences. Finally we reconstruct the Fibonacci number by either adding or subtracting the difference to i.

Oops, I was loading two registers in the wrong order and then swapping them, wasting a byte.

brhfl
quelle
Functions are allowed.
CalculatorFeline
Thanks, I repeatedly missed that in the challenge's text.
brhfl
2

C# (.NET Core), 63 56 bytes

-1 byte thanks to @Neil

-6 bytes thanks to @Nevay

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

Try it online!

jkelm
quelle
Does for(;b<n;a=b,b+=c)c=a; save a byte?
Neil
You can remove c by using b+=a,a=b-a (should save 6 bytes).
Nevay
2

Q/KDB+, 51 bytes

{w where l=min l:abs neg[x]+w:{x,sum -2#x}/[x;0 1]}
aodNap
quelle
2
Welcome to PPCG!
Martin Ender
2

Hexagony, 37 bytes

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

Try it online!

ungolfed:

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

Broken down:

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

Like some other posters, I realized that when the midpoint of last and curr is greater than the target, the smaller of the two is the closest or tied for closest.

The midpoint is at (last + curr)/2. We can shorten that because next is already last + curr, and if we instead multiply our target integer by 2, we only need to check that (next - 2*target) > 0, then return last.

Brigmor
quelle
2

Brachylog, 22 bytes

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

Try it online!

Really all I've done here is paste together Fatalize's classic Return the closest prime number solution and my own Am I a Fibonacci Number? solution. Fortunately, the latter already operates on the output variable; unfortunately, it also includes a necessary cut which has to be isolated for +2 bytes, so the only choice point it discards is , leaving intact.

Unrelated String
quelle
1

Java 7, 244 234 Bytes

 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
quelle
Why don't you use Java 8 and turn this into a lambda? You can also remove static if you want to stick with Java 7.
Okx
You have two errors in your code (r>c&&s<c should be r>=c&&s<=c, s-c should be c-s), You could remove not required whitespace, use int f(int i){return i<2?i:f(--i)+f(--i);}, use a single return statement with ternary operator in c and remove the special handling for c-s==r-c as returning either value is allowed.
Nevay
@Nevay I don't see the error, I've tested it without fails
0x45
1

Pyke, 6 bytes

}~F>R^

Try it online!

}      -    input*2
 ~F    -   infinite list of the fibonacci numbers
   >   -  ^[:input]
    R^ - closest_to(^, input)
Blue
quelle
1

Common Lisp, 69 bytes

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

Try it online!

Renzo
quelle
1

Perl 6, 38 bytes

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

Test it

{   # 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
}

For a potential speed-up add .tail(2) before .sort(…).

In the case of a tie, it will always return the smaller of the two values, because sort is a stable sort. (two values which would sort the same keep their order)

Brad Gilbert b2gills
quelle
1

Pyth, 19 bytes

JU2VQ=+Js>2J)hoaNQJ

Try it here

Explanation

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.

quelle