Wir alle kennen die berühmte Fibonacci-Sequenz , die mit 0
und 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
34
ist die nächstliegende Fibonacci-Zahl30
, weil|34 - 30| = 4
, die kleiner ist als die zweitnächste21
, 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
13
genau13
.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
,13
oder21, 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 Code-Golf , also gewinnt der kürzeste Code in Bytes in jeder Sprache !
n
impliziertn ≥ 1
.Antworten:
Python 2 , 43 Bytes
Probieren Sie es online!
Durchläuft Paare aufeinanderfolgender Fibonacci-Zahlen,
(a,b)
bis sie eine erreichen, bei der die Eingaben
unter ihrem Mittelpunkt liegt(a+b)/2
, und kehrt dann zurücka
.Als Programm geschrieben (47 Bytes):
Gleiche Länge :
quelle
Neim , 5 Bytes
Erläuterung:
In der neuesten Version von Neim kann dies auf 3 Bytes golfen werden:
Da unendlich viele Listen überarbeitet wurden, um nur ihren Maximalwert zu erreichen.
Probieren Sie es online!
quelle
Python ,
5552 BytesProbieren Sie es online!
quelle
R ,
7067646260 Bytes-2 Bytes dank Djhurio!
-2 weitere Bytes dank Djhurio (Junge kann er Golf spielen!)
Da wir nur mit Werten bis zu umgehen müssen
10^8
, funktioniert dies.Probieren Sie es online!
Liest
n
von stdin. Diewhile
Schleife generiert die Fibonacci-Zahlen inF
(absteigender Reihenfolge). im Falle eines Unentschieden wird der größere zurückgegeben. Dies löst eine Reihe von Warnungen aus, dawhile(F<1e8)
nur die Anweisung für das erste Element von ausgewertet wirdF
mit einer WarnungUrsprünglich habe ich
F[which.min(abs(F-n))]
den naiven Ansatz verwendet, aber @djhurio schlug vor,(F-n)^2
da die Reihenfolge gleichwertig sein wird, undorder
nichtwhich.min
.order
Gibt 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:
Speichert nur die letzten beiden Fibonacci-Zahlen
quelle
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 Byte
Rundet nach Belieben auf.
quelle
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.Gelee ,
97 Bytes-2 Bytes dank @EriktheOutgolfer
Probieren Sie es online!
Golftipps willkommen :). Nimmt ein Int für die Eingabe und gibt eine Int-Liste zurück.
quelle
µḢ
.Mathematica, 30 Bytes
Probieren Sie es online!
quelle
x86-64-Maschinencode, 24 Byte
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
) imEDI
Register übergeben und das Ergebnis imEAX
Register zurückgegeben wird.Ungolfed Assembler-Mnemonik:
Probieren Sie es online!
Der Code gliedert sich grundsätzlich in drei Teile:
EAX
wird auf 0 undEDX
auf 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 dieEAX
undEDX
-Register. Dieser Ansatz ist hier äußerst praktisch, weil er uns benachbarte Fibonacci-Zahlen gibt. Der Kandidat, der möglicherweise kleiner alsn
ist, wird gehaltenEAX
, während der Kandidat, der möglicherweise größer alsn
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
EAX
und verfügbar habenEDX
, ist es konzeptionell einfach, herauszufinden, welcher näher (in Bezug auf den absoluten Wert) liegtn
. 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 entwederEDX
inEAX
oder verlässt esEAX
alleine, so dass, wenn die FunktionRET
auslöst, die nächstliegende Fibonacci-Zahl zurückgegeben wirdEAX
.In the case of a tie, the smaller of the two candidate values is returned, since we've used
CMOVG
instead ofCMOVGE
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!quelle
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.xor eax,eax
/cdq
/inc edx
. So you could make a 32-bit custom-calling-convention version that saved a byte.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.edi
/esi
forlodsb
/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).PowerShell,
8074 bytes(Try it online! temporarily unresponsive)
Iterative solution. Takes input
$n
, sets$a,$b
to be1,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.quelle
JavaScript (ES6), 67 bytes
Test cases
Show code snippet
quelle
JavaScript (Babel Node), 41 bytes
Based on ovs's awesome Python answer
Try it online!
Ungolfed
quelle
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)
Python, 74 bytes
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.
quelle
05AB1E, 6 bytes
Try it online!
quelle
C (gcc),
86858376 bytesTry it online!
quelle
Java (OpenJDK 8),
605756 bytesTry it online!
-1 byte thanks to @Neil
quelle
Python 3, 103 bytes
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 bytesTry 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.
quelle
nearest_fib_PM2R
function I linked in my comment on the question.Taxi, 2321 bytes
Try it online!
Try it online with comments!
Un-golfed with comments:
quelle
Python 3, 84 bytes
Try it online!
It may work, but it's certainly not fast...
Outputs
True
instead of1
, but in Python these are equivalent.quelle
dc, 52 bytes
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 thani
. At this point we have two numbers in the Fibonacci sequence on the stack: one that is less than or equal toi
, and one that is greater thani
. We convert these into their respective differences withi
and then compare the differences. Finally we reconstruct the Fibonacci number by either adding or subtracting the difference toi
.Oops, I was loading two registers in the wrong order and then swapping them, wasting a byte.
quelle
C# (.NET Core),
6356 bytes-1 byte thanks to @Neil
-6 bytes thanks to @Nevay
Try it online!
quelle
for(;b<n;a=b,b+=c)c=a;
save a byte?c
by usingb+=a,a=b-a
(should save 6 bytes).Q/KDB+, 51 bytes
quelle
Hexagony, 37 bytes
Try it online!
ungolfed:
Broken down:
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.
quelle
Brachylog, 22 bytes
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.quelle
Japt
-g
, 8 bytesTry it
quelle
Java 7,
244234 Bytesquelle
static
if you want to stick with Java 7.r>c&&s<c
should ber>=c&&s<=c
,s-c
should bec-s
), You could remove not required whitespace, useint 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 forc-s==r-c
as returning either value is allowed.Pyke, 6 bytes
Try it online!
quelle
Common Lisp, 69 bytes
Try it online!
quelle
Perl 6, 38 bytes
Test it
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)quelle
Pyth, 19 bytes
Try it here
Explanation
quelle
Haskell, 48 bytes
Try it online!
quelle