Herausforderung
Sie müssen ein Programm oder eine Funktion generieren, die eine positive Ganzzahl N aufnimmt, die ersten N Terme der Fibonacci-Sequenz in Binärform berechnet, sie zu einer einzelnen Binärzahl verkettet, diese Zahl zurück in Dezimalform konvertiert und dann die Dezimalform als ausgibt ganze Zahl.
Beispielsweise
1 -> [0] -> 0 to decimal outputs 0
3 -> [0, 1, 1] -> 011 to decimal outputs 3
4 -> [0, 1, 1, 10] -> 01110 to decimal outputs 14
Sie müssen nicht ->
nur die Nummer ausgeben (z. B. wenn der Benutzer tippt 4
, nur ausgeben 14
). Die Pfeile sollen nur erklären, was das Programm tun muss.
Testfälle
1 -> 0
2 -> 1
3 -> 3
4 -> 14
5 -> 59
6 -> 477
7 -> 7640
8 -> 122253
9 -> 3912117
10 -> 250375522
11 -> 16024033463
12 -> 2051076283353
13 -> 525075528538512
14 -> 134419335305859305
15 -> 68822699676599964537
16 -> 70474444468838363686498
17 -> 72165831136090484414974939
18 -> 147795622166713312081868676669
19 -> 605370868394857726287334099638808
20 -> 4959198153890674493745840944241119317
Das Programm muss in der Lage sein, bis zur Grenze der verwendeten Sprache auszugeben. Nachschlagetabellen oder allgemeine Problemumgehungen sind nicht zulässig.
Das ist Code-Golf , also gewinnt die Antwort mit der kürzesten Anzahl von Bytes!
int32_t binary_concat_Fib(int n)
, was den resultierenden Ausgabewert auf 2 ^ 31-1 begrenzen würde. Sie können also annehmen, dass alle verketteten Bits in eine ganze Zahl passen. Oder sollte die Funktion bis zu dem Punkt funktionieren, an dem die größte Fibonacci-Zahl nicht für sich allein in eine Ganzzahl passt, sodass die Verkettung der Bits eine höhere Genauigkeit erfordert?Antworten:
Python , 64 Bytes
Probieren Sie es online!
quelle
Gelee ,
76 BytesProbieren Sie es online!
Wie?
quelle
Ṛc’SƲƤ
denen gefunden werden können, die für ähnliche Sequenzen nützlich sein könnten.Python 3.6 , 61 Bytes
Probieren Sie es online!
quelle
Brainfuck , 397 Bytes
Na das war ein Spaß!
Übernimmt ASCII-Eingaben (zB
11
), gibt ASCII aus.Hinweis: Um dies online zu versuchen, stellen Sie sicher, dass Sie die Zellengröße auf 32 Bit einstellen (auf der rechten Seite der Webseite). Wenn Sie keine Eingabe machen, kann Ihr Browser abstürzen.
Der Interpreter kann keine Eingaben von
11
und höher verarbeiten, da er nur bis zu 32 Bit unterstützt.Probieren Sie es auf copy.sh
Erläuterung
Holen Sie sich eine Dezimaleingabe und fügen Sie eine hinzu
Generieren Sie Fibonacci-Zahlen auf dem Band.
Richten Sie für die eingehende binäre Verkettungsschleife ein
Die Zellen enthalten also den Wert, beginnend mit der ersten Position,
Sehen Sie sich diese Zellen an:
Ich werde dies beschriften:
pow
gibt es die maximale Potenz von 2 zu finden, die streng größer ist alsnum
.sum
ist die Verkettung von Zahlen bisher.cat
ist die Macht der 2 , dass ich die multiplizieren müsste ,num
um zu verkettennum
vor demsum
(so würde ich in der Lage sein, einfach zu hinzufügen).Schleife: Überprüfen Sie, ob
f_n
streng kleiner als istpow
.Wahrheit:
Null Junk raus. Fügen Sie dann
num
*cat
zu hinzusum
. Laden Sie als nächstes die nächste Fibonacci-Zahl (=f_(n-1)
; falls sie nicht existiert, beenden Sie die Schleife) und setzen Sie siecat
aufcat
*pow
. Bereiten Sie sich auf die nächste Schleife vor (Null aus mehr Müll, Bereich um eins verschieben).Falsey:
Auf
pow
2 * setzenpow
, wiederherstellennum
.Wiederholen, bis keine Fibonacci-Nummer mehr vorhanden ist.
Müll säubern. Nimm jede Ziffer der resultierenden Zahl und gib sie aus (in ASCII).
quelle
Schale , 7 Bytes
Probieren Sie es online!
Erläuterung
quelle
Japt , 9 Bytes
Starte es
Erläuterung:
quelle
Pyth, 22 Bytes
Probieren Sie es hier aus
Erläuterung
quelle
Perl 6 , 38 Bytes
Probieren Sie es online!
quelle
JavaScript (Node.js) ,
7065585755 BytesProbieren Sie es online!
quelle
-0
am Ende weglassen, um weitere 2 Bytes zu sparen.05AB1E , 6 Bytes
Probieren Sie es online!
1-indiziert.
quelle
J, 36 Bytes
Erläuterung:
quelle
x86,
372221 BytesÄnderungsprotokoll
bsr
. Vielen Dank, Peter Cordes!-2 durch Nullstellen der Register mit
mul
.-1 durch Verwenden einer while-Schleife anstelle von
loop
undpush
/pop
ecx
(Kredit Peter Cordes).Eingabe in
edi
, Ausgabe inedx
.Objektspeicherauszug:
quelle
lea
diese Option, um fib2 zu verschieben und hinzuzufügen. Außerdem ist es nicht erforderlich, jedes Bit einzeln zu extrahieren. Verwenden Siebsr %eax, %ecx
diese Option , um die Anzahl der Bits in der Binärdarstellung zu ermitteln, und verwenden Sie eine Verschiebung um CL / oder zum Zusammenführen, wie dies bei Dennis 'Python-Antwort der Fall ist.cl
für Verschiebungszählungen, nehmen Sie also Ihren Schleifenzähler in eine andere Position (wie%edi
) und verwenden Siedec %edi / jnz
(3 Bytes im 32-Bit-Code, 4 Bytes im 64-Bit-Code). Bei einem 32-Bit-Code erspart dies insgesamt 1 Byte beim Löschen der Push / Pop-ecx. Gehen Sie nicht in die Falle,loop
wenn das Problem dadurch schwerer und nicht einfacher wird. (Ihre Aufrufkonvention ist bereits benutzerdefiniert,%ebx
also rufen Sie Ihre Funktion nicht auf.main
) Möglicherweise können Sie in EAX zurückkehren, während Sie immer noch 1 Byte nutzen.xchg
Sie müssen nicht dem Standard entsprechen, wenn Sie dies nicht müssen.inc %ecx
Schichtanzahl durch eine zusätzliche Linksverschiebung ersetzen , indem Sie verwendenlea (%eax, %edx, 2), %edx
. Neutral in Bytes für 32-Bit, speichert eine für x86-64. Speichert aber eine Anweisung.loop
Codegolf spiele, fühle ich mich schmutzig. Nun, nicht ganz, aber enttäuscht, dass ich keine ebenso kleine Implementierung finden konnte, die diese langsame Anweisung vermeidet; Außerhalb von Code Golfloop
ist einer meiner Lieblingstiere . Ich wünschte , es wäre auf modernen CPUs schnell, denn es wäre sehr schön für Schleifen mit erweiterter Genauigkeit ohne partielle Unterbrechungen, aber es ist keine und sollte nur als obskure Anweisung zur Größenoptimierung betrachtet werden, die Ihren Code langsam macht.xor
/mul
trick to zero three-Register gibt (brauchen Sie jemals so viele Nullen?), Aber das als Teil der Erstellung eines1
macht es sinnvoller.APL (Dyalog) ,
2622 Bytes4 Bytes gespart dank @ H.PWiz
Probieren Sie es online!
quelle
Haskell ,
897675 BytesUngolfed-Version:
quelle
f=0:scanl(+)1f
(von hier übernommen ). Funktionen können anonym sein, so dass Sie die Führung löschen könneng=
, finden Sie in unserem Leitfaden für Ggolfing-Regeln in Haskell .$realToFrac y
mit.read.show$y
einem für BytePari / GP , 59 Bytes
Probieren Sie es online!
quelle
APL + WIN, 55 Bytes
Fordert zur Eingabe einer Ganzzahl auf.
Die maximale Ganzzahlgenauigkeit von APL + WIN beträgt 17 und das Ganzzahllimit liegt in der Größenordnung von 10E300, daher beträgt die maximale Eingabenummer 55 und das Ergebnis lautet: 1.2492739026634838E300
quelle
Python 3 , 94 Bytes
Probieren Sie es online!
quelle
Gelee , 6 Bytes
Probieren Sie es online!
Ḷ
Wertebereich -> n- teÆḞ
Ibonacci-Zahl -> von Dez bisB
Dez ->F
Latte -> vonḄ
Inary bis Dezquelle
10
und Sie erhalten eine16024033463
, es ist falsch (richtige Antwort ist250375522
).10
kehrt zurück250375522
MATL , 21 Bytes
Probieren Sie es online!
Erläuterung
quelle
J , 25 Bytes
Probieren Sie es online!
Erläuterung
quelle
Python 3 , 86 Bytes
Probieren Sie es online!
quelle
Add ++ , 113 Bytes
Probieren Sie es online!
quelle
PHP, 124 Bytes
Probieren Sie es online!
So war ich auf der Suche nach einer Möglichkeit zur Ausgabe von Fibonacci - Zahlen , die Serie verwenden, bis ich dies . Es hat sich herausgestellt, dass Sie die Fibonacci-Reihe durch Runden berechnen können. Deshalb habe ich die Herausforderung mit einer rekursiven Funktion versucht.
Ich fand den Ansatz des "Rundens" wirklich interessant, auch ein Professor hat mir das vor einiger Zeit gezeigt.
Code
Erläuterung
Überprüfen Sie auch diesen Stackoverflow-Beitrag. Die beste Antwort bezieht sich auf denselben Artikel auf Wikipedia.
quelle
Stax , 9 Bytes
Führen Sie es aus und debuggen Sie es unter staxlang.xyz!
Entpackt (10 Bytes) und Erklärung:
quelle
Julia 0,6 , 65 Bytes
Probieren Sie es online!
quelle
Pyth, 27 Bytes
Testsuite
Python 3 Übersetzung:37 BytesTestsuite
Python 3 Übersetzung:quelle
Ruby , 61 Bytes
Probieren Sie es online!
quelle
Jotlin , 59 Bytes
Testprogramm
Es werden bis zu 10 unterstützt, ein Wechsel
.i(2)
zu.toLong(2)
würde bei Bedarf bis zu 14 unterstützenquelle
Python 2, 88 Bytes
quelle
R ,
244180179 BytesProbieren Sie es online!
Einige Bytes wurden durch Verketten von numerischen Vektoren und nicht von Zeichenfolgen gespeichert. Verdammter Sonderfall für 0!
quelle
sapply
aufgrund der Tatsache, dass sie rekursiv ist, zu einem Vektor gehören muss . Es kann nicht alles in eine Zeile eingeschlossen werden. Wie Sie sehen, fordert das Programm den Benutzer zur Eingabe auf und gibt dann die Antwort zurück. Ein Byte kann durch Erstellen einer Verknüpfung für gespeichert werdenifelse
. Und ... wir können entfernen,""
ausscan
, ja.