Hintergrund
Die meisten von Ihnen wissen, was eine Fibonacci-Zahl ist. Einige von Ihnen wissen vielleicht, dass alle positiven ganzen Zahlen nach dem Satz von Zeckendorf als Summe von einer oder mehreren unterschiedlichen Fibonacci-Zahlen dargestellt werden können . Wenn die Anzahl der Terme in der optimalen Zeckendorf-Darstellung einer ganzen Zahl n
selbst eine Fibonacci-Zahl ist, werden wir n
"heimlich" Fibonacci nennen.
Beispielsweise:
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci
140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci
Anmerkungen
- Die optimale Zeckendorf-Darstellung kann mit einem Greedy-Algorithmus ermittelt werden. Nehmen Sie einfach die größte Fibonacci-Zahl <= n und subtrahieren Sie sie von n, bis Sie 0 erreichen
- Alle Fibonacci-Zahlen können als Summe von 1 Fibonacci-Zahl (selbst) dargestellt werden. Da 1 eine Fibonacci-Zahl ist, sind alle Fibonacci-Zahlen auch insgeheim Fibonacci.
Herausforderung
Ihre Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die eine Ganzzahl akzeptiert und zurückgibt, ob diese Ganzzahl heimlich Fibonacci ist.
Eingang
Sie können Eingaben in jedem vernünftigen Format vornehmen. Sie können davon ausgehen, dass die Eingabe eine einzelne positive Ganzzahl ist.
Ausgabe
Geben Sie eines von zwei unterschiedlichen Ergebnissen aus, um festzustellen, ob es sich bei der Eingabe um Fibonacci handelt. Beispiele sind True
/ False
, 1
/ 0
usw.
Wertung
Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes! Standardlücken sind verboten.
Testfälle
Truthy (secretly Fibonacci)
1
2
4
50
140
300099
Falsey (NOT secretly Fibonacci)
33
53
54
139
118808
quelle
Antworten:
JavaScript (Node.js) , 54 Byte
Probieren Sie es online!
quelle
Python 2 , 77 Bytes
Probieren Sie es online!
Dies nutzt den Satz, dass die beiden Beschreibungen von OEIS A003714 äquivalent sind:
z
Dann bleibt zu prüfen, ob
z[n]
es sich um eine Fibonacci-Zahl handelt, dhz[z[n]] == 1
.quelle
bin(x)
. Sie können einen auch durch Ändern entfernenrange(n*n+1)
zurange(n<<n)
. (Angenommen, 0 ist ungültig)bin(x)
, haha. Und, hm,1<<n
ist schon viel, viel mehr als genug, aber ich möchte die Laufzeit nicht astronomisch haltenGelee , 15 Bytes
Ein monadischer Link, der eine nicht negative Ganzzahl akzeptiert, die
1
"Secretly Fibonacci" ergibt,0
andernfalls.Probieren Sie es online! (zu ineffizient für die größeren Testfälle)
Wie?
quelle
R 83 Bytes
Probieren Sie es online!
quelle
C # (.NET Core) ,
12411598 BytesProbieren Sie es online!
-3 Bytes: geändert in while-Schleife nach for (danke an Olivier Grégoire )
-6 Bytes: Umgeschaltete Rückgabe zur Verwendung von variablen, initialisierten b und c außerhalb von Schleifen (danke an Kevin Cruijssen )
-17 Bytes: geänderter Zustand in der zweiten Schleife zum Bewegen von if out of loop und kombiniere mit return, wiederverwendete b und c Variablen in der letzten Schleife (danke an raznagul )
Ungolfed:
quelle
for(;c<=a;b=c-b)c+=b;
Sie sparen 3 Bytes.{}
Klammern deiner Schleifen entfernt und alles in Schleifen gestecktfor
. Außerdem habe ich eine Variable hinzugefügt,r
die wir1
in your festgelegt habenif(e==n)
und am Ende zurückgeben, sodass Sie nur eine habenreturn
.e<n
Sie das Zeichenif
nach der Schleife verschieben und sie anschließend mit dem Zeichenreturn
für 101 Bytes kombinieren .b
undc
in der letzten Schleife und Entfernend
unde
.Perl 6 , 58 Bytes
Probieren Sie es online!
1, &[+] ... * > $_
ist nur die Fibonacci-Sequenz, die an einer bequemen, nicht unendlichen Stelle (der eingegebenen Nummer) angehalten wird.$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0
ist eine Folge von Zahlen, beginnend mit der eingegebenen Zahl und jedem nachfolgenden Element, das durch Subtrahieren der größten Fibonacci-Zahl, die kleiner oder gleich dem vorherigen Element ist, vom vorherigen Element erhalten wird. Die Sequenz endet, wenn0
erreicht ist. Wenn zum Beispiel$_
ist140
, dann ist diese Sequenz140, 51, 17, 4, 1, 0
.Das Subtrahieren von eins von dieser Sequenz behandelt es als eine Zahl, seine Länge und die Differenz ist die Anzahl der Fibonacci-Zahlen, die zusammen die eingegebene Zahl ergeben. Dann wird diese Nummer auf Mitgliedschaft in der ersten Fibonacci-Sequenz überprüft.
quelle
&[+]
! Schön, dass Sie nicht zwei anfängliche Begriffe definieren müssenPerl 6 , 48 Bytes
Probieren Sie es online!
Transformiert die Eingabe wiederholt in eine Liste der Zeckendorf-Darstellung, bis eine einzelne Zahl erreicht ist, und überprüft dann, ob die Länge der Sequenz kürzer als 4 war.
Die Zenckendorf-Funktion in der Mitte stammt größtenteils aus Seans Antwort mit ein paar Verbesserungen.
Erläuterung:
Zum Beispiel kann die Sequenz für
2
IS2 1
da2
bereits eine Fibonacci - Zahl. Die Sequenz für140
ist140 5 1
, und da 5 eine Fibonacci-Zahl ist, gibt dies wahr zurück. Die Folge für33
ist33 4 2 1
, und da4
es sich nicht um eine Fibonacci-Zahl handelt, hat die Folge die Länge 4.quelle
05AB1E , 14 Bytes
Probieren Sie es online aus . Keine Testsuite für alle Testfälle, da
counter_variable
diese nicht auf 0 zurückgesetzt werden können. Ich habe sie jedoch alle von Hand überprüft und sie sind korrekt.Erläuterung:
ANMERKUNG: Das
counter_variable
wäre5
für die Eingabe139
und6
für die Eingabe140
, daΔ
es natürlich eine zusätzliche Iteration gibt, damit die Schleife den Stapel überprüft.quelle
Haskell , 64 Bytes
Probieren Sie es online!
quelle
Retina 0.8.2 , 61 Bytes
Probieren Sie es online! Link enthält Testfälle. Erläuterung:
In Unary konvertieren.
Zählen Sie die Anzahl der benötigten Fibonacci-Zahlen.
Die erste Alternative behandelt Fibonacci-Zahlen, die mindestens 2 sind. Im ersten Durchgang ist sie
\2
noch nicht vorhanden, aber zum Glück ist sie optional, sodass wir sie nicht abgleichen müssen.\1
gibt es auch nicht, aber zum Glück haben wir die Alternative,\G.
bei der zu Beginn des Spiels ein einzelnes Zeichen gefunden wird. Beide\2
und\1
nehmen daher den Wert 1 an.In den folgenden Durchläufen ist
\2
vorhanden, daher versuchen wir, eine Übereinstimmung zu erzielen. Dieses Mal, wenn es fehlschlägt,\1
schlägt es ebenfalls fehl (da es größer als ist\2
), aber wenn es erfolgreich ist,(?>)
verhindert das das Zurückverfolgen. Wenn also\2
Übereinstimmungen vorliegen,\1
versuchen wir es nicht einfach\1
. (\G1
Schlägt immer fehl, da wir den Patch-Start überschritten haben.) Nimmt schließlich\2
den vorherigen Wert von\1
while an\1
nimmt die Summe der beiden Werte an.Wir gleichen daher so viele Fibonacci-Zahlen wie möglich ab und addieren sie nacheinander. Da die Teilsummen der Folge
1, 2, 3, 5...
sind0, 1, 3, 6, 11...
also zwei weniger als die Fibonacci - Zahlen , die wir durch passende 2 am Ende zu beenden.Dies entspricht offensichtlich nicht 1 selbst, so dass eine Abwechslung diesen Fall behandelt.
In Unary konvertieren.
Testen Sie, ob dies eine Fibonacci-Zahl ist. Hierbei wird die gleiche Idee wie beim ersten Test verwendet, jedoch
^
nicht\G
Außerdem müssen wir genau übereinstimmen. Daher wird anstelle einer Abwechslung ein optionales Capture verwendet, da dies Golfspieler ist (jedoch werden die Capture-Nummern um 1 erhöht).Retina , 35 Bytes
Probieren Sie es online! Link enthält Testfälle. Erläuterung:
In Unary konvertieren.
Zählen Sie die Anzahl der benötigten Fibonacci-Zahlen. (Durch Schleifen von Konvertierung und Zählung wird ein ganzes Byte gespart, da die Zählung erst einmal unärgerlich wird.)
Führen Sie die vorherigen Schritte insgesamt zweimal aus. Dies berechnet die Anzahl der Fibonacci-Zahlen, die benötigt werden, um die Anzahl der Fibonacci-Zahlen zu summieren.
Wenn die Zahl heimlich Fibonacci war, ist das Ergebnis 1.
quelle
Python 2 ,
146137 BytesProbieren Sie es online!
f () ist eine rekursive Funktion, die den Wert der n-ten Fibonacci-Zahl zurückgibt. Aus dieser Antwort entnommen .
g () ist eine rekursive Funktion, die die Zeckendorf-Darstellung der angegebenen Zahl als Liste von ganzen Zahlen zurückgibt.
Da alle Fibonacci-Zahlen eine Rückgabelänge von einem Element von g () haben, prüft h (), ob die Länge von g () von g (n) == 1 ist.
BEARBEITEN: 9 Bytes dank nedla2004 gespeichert . Ich vergesse immer wieder, dass Lambdas nicht immer die beste Lösung sind ...
quelle
g
eine Funktion erstellt, damit ich sief(n-1)
für eine Variable definieren kann. Paar andere Änderungen von==
zu ,<
wo sie gleich sind.