Wir alle kennen die Fibonacci-Sequenz :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
Stattdessen nehmen f(n) = f(n-1) + f(n-2)
wir jedoch die digitale Summe der vorherigen 2 Einträge.
Die Sequenz sollte immer noch beginnen 0, 1
, danach werden die Unterschiede schnell sichtbar. Diese Liste ist 0-indiziert. Sie können auch 1-indiziert verwenden und angeben, welche Liste Sie verwendet haben.
f(0) = 0
f(1) = 1
f(2) = 1 # 0 + 1
f(3) = 2 # 1 + 1
f(4) = 3 # 1 + 2
f(5) = 5 # 2 + 3
f(6) = 8 # 3 + 5
f(7) = 13 # 8 + 5
f(8) = 12 # 8 + 1 + 3
f(9) = 7 # 1 + 3 + 1 + 2
f(10) = 10 # 1 + 2 + 7
f(11) = 8 # 7 + 1 + 0
f(12) = 9 # 1 + 0 + 8
f(13) = 17 # 8 + 9
f(14) = 17 # 9 + 1 + 7
f(15) = 16 # 1 + 7 + 1 + 7
f(16) = 15 # 1 + 7 + 1 + 6
f(17) = 13 # 1 + 6 + 1 + 5
f(18) = 10 # 1 + 5 + 1 + 3
f(19) = 5 # 1 + 3 + 1 + 0
f(20) = 6 # 1 + 0 + 5
f(21) = 11 # 5 + 6
f(22) = 8 # 6 + 1 + 1
f(23) = 10 # 1 + 1 + 8
f(24) = 9 # 8 + 1 + 0
f(25) = 10 # 1 + 0 + 9
f(26) = 10 # 9 + 1 + 0
f(27) = 2 # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)
Hinweis: Ich habe die Wiederholung erst bemerkt, als ich die Herausforderung selbst veröffentlicht habe, und hier dachte ich, es wäre unmöglich, eine weitere neuartige Fibonacci-Herausforderung zu schreiben.
Ihre Aufgabe ist es, unter Angabe einer Nummer n
die n-te Stelle dieser Sequenz auszugeben.
Die ersten 3 Ziffern: [0,1,1]
,
24-stelliges wiederholtes Muster: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]
Tipp: Möglicherweise können Sie diese Wiederholung zu Ihrem Vorteil ausnutzen.
Dies ist Code-Golf , die niedrigste Byte-Anzahl ist der Gewinner.
BONUS: Wenn Sie in Ihrer Antwort die Wiederholung verwenden, erteile ich der Antwort mit der niedrigsten Byteanzahl, die die Wiederholung in der Sequenz nutzt, eine Prämie von 100 Punkten. Dies sollte als Teil Ihrer ursprünglichen Antwort nach Ihrer ursprünglichen Antwort eingereicht werden. Sehen Sie sich diesen Beitrag als Beispiel für das an, worüber ich spreche: https://codegolf.stackexchange.com/a/108972/59376
Um sich für diesen Bonus zu qualifizieren, muss Ihr Code in konstanter Zeit ( O(1)
) mit einer Erklärung ausgeführt werden.
Bonussieger: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis hat gewonnen.
Einzigartigste Implementierung: https://codegolf.stackexchange.com/a/108970/59376
(Erhält auch 100 Punkte, finalisiert nach Auswahl der richtigen Antwort)
quelle
%24
eine "normale" Lösung hinzu?O(1)
. Ihr Code sollte in konstanter Zeit ausgeführt werden, wenn die Wiederholung wirklich ausgenutzt wird.Antworten:
Oase , 5 Bytes
Code:
Probieren Sie es online!
Erweiterte Version:
Erläuterung:
quelle
JavaScript (ES6), 45 Byte
x
undy
kann nicht beides sein9
, da dies die vorherige Zahl erfordern würde0
, so dass ihre digitale Summe nicht übersteigen kann17
. Dies bedeutet, dass die digitale Wurzel für Zahlen, die größer als9
sind, mit dem Restmodulo identisch ist9
.quelle
Python 2, 53 Bytes
Rekursive Funktion. Die Basisfälle von
n=0
undn=1
ergebenn
, dass größere Zahlen den Wert berechnen , indem sie jedes Zeichen aufrufenf(n-1)
undf(n-2)
in eine Zeichenfolge konvertieren, die beiden Zeichenfolgen verketten, jedes Zeichenmap
mit derint
Funktion in eine Ganzzahl konvertieren und dann die resultierende Liste summieren.Unter Verwendung der Modulo-24-Informationen kann ich derzeit eine nicht rekursive unbenannte 56-Byte-Funktion erhalten:
quelle
JavaScript (ES6), 34 Byte
Kann Ihren Browser für Eingaben über 27 oder so einfrieren, funktioniert aber für alle Eingabewerte. Dies kann mit einem einfachen Cache überprüft werden:
Wie in Neils brillanter Antwort hervorgehoben , kann die Ausgabe 17 nicht überschreiten, sodass die digitale Summe aller Ausgaben über 9 gleich ist
n%9
. Dies funktioniert auch mit Ausgängen unter 9; Wir können es auch für 9 arbeiten lassen, indem wir 1~-
vor dem Modul abziehen und danach wieder 1 hinzufügen.Das Beste, was ich mit Hardcoding anfangen kann, sind 50 Bytes:
quelle
Gelee , 8 Bytes
Probieren Sie es online!
Wie es funktioniert
Alternative Lösung, 19 Bytes, konstante Zeit
Probieren Sie es online!
Wie es funktioniert
quelle
JavaScript (ES6),
52 4645 BytesVerwendung
Ausgabe
Erläuterung
Diese Funktion überprüft, ob die Eingabe kleiner als 2 ist, und gibt in diesem Fall die Eingabe zurück. Andernfalls wird ein Array mit zwei Werten erstellt, die als Zeichenfolgen aneinander angehängt werden. Diese beiden Werte ergeben sich aus dem Aufruf der Funktion mit
input - 1
undinput - 2
.Der
...
Operator teilt diese Zeichenfolge in ein Array von Zeichen auf, das dann erneut in eine Zeichenfolge konvertiert wird, jetzt jedoch mit einem+
Abstand zwischen den Werten. Diese Zeichenfolge wird dann als Code interpretiert, sodass die Summe berechnet wird, die dann zurückgegeben wird.Dies ist ein doppelt rekursiver Algorithmus, der ziemlich ineffizient ist. Es werden 2
n-2
Funktionsaufrufe für die Eingabe benötigtn
. Als solche ist hier eine längere, aber schnellere Lösung. Vielen Dank an ETHproductions für die Entwicklung.quelle
[..._(--$)+[_(--$)]]
:-)05AB1E , 8 Bytes
Probieren Sie es online!
Erläuterung
quelle
CJam,
2220 Bytes2 Bytes gespart dank Martin Ender
Einfacher rekursiver Algorithmus, nichts Besonderes. 0-indiziert.
Probieren Sie es online! oder auf 0-50 testen (läuft eigentlich ziemlich schnell).
Erläuterung
CJam, 42 Bytes
Lösung mit der Wiederholung. Ähnlicher Algorithmus wie bei Jonathan Allan.
Probieren Sie es online!
quelle
Perl 6 ,
4137 BytesVersuch es
Versuch es
quelle
*.comb.sum+*.comb.sum
.MATL , 15 Bytes
Probieren Sie es online!
quelle
Python 2 ,
5446 BytesSehr inspiriert von der Antwort von @ETHproductions auf ES6 .
Probieren Sie es online!
quelle
C 96 Bytes
oder 61 Bytes, die die Escape-Codes als jeweils 1 Byte zählen
0 indiziert. Ähnlich wie bei einigen anderen Antworten indiziere ich eine Wertetabelle, habe sie jedoch in 4-Byte-Blöcke komprimiert. Ich habe mich nicht darum gekümmert, die Mod 24-Version zu untersuchen, weil ich es nicht so interessant fand, da die anderen dies bereits getan haben, aber seien wir ehrlich, C wird sowieso nicht gewinnen.
Erläuterung:
Probieren Sie es online!
quelle
Japt ,
2725 BytesProbieren Sie es online!
2 Bytes gespart dank ETHproductions.
quelle
´
anstelle von--
zwei Bytes speichern.Haskell , 54 Bytes
Probieren Sie es online! Verwendung:
(g!!) 12
quelle
Mathematica, 49 Bytes
Einfache rekursive Definition. Wird nach einer Weile ziemlich langsam.
Mathematica,
7971 BytesHardcodierung des periodischen Musters. Blitzschnell und für Mathematica in befriedigender Weise missbräuchlich :) Danke an JungHwan Min für die Einsparung von 8 Bytes!
quelle
LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"
sind 8 Bytes kürzer als43626804920391712116157158790~IntegerDigits~18
.LetterNumber
...Python 2 , 56 Bytes
Einfache iterative Lösung.
Probieren Sie es online!
Das Verwenden
(a%9or a)+(b%9or b)
stellte sich tatsächlich als kürzer heraus alssum(map(int(`a`+`b`)))
!quelle
sum(map(int,a+b))
(kann nicht herausfinden, wie man in Kommentaren verwendet)PowerShell , 79 Byte
Probieren Sie es online!
Langwierige iterative Lösung, die für jede
for
Schleife direkte Ziffernsummenberechnungen durchführt . Am Ende der Schleife befindet sich die gewünschte Zahl in$b
der Pipeline und die Ausgabe ist implizit. Beachten Sie, dass bei einer Eingabe0
die Schleife nicht aktiviert wird, da die Bedingung false ist und somit erhalten$b
bleibt0
.quelle
Batch, 85 Bytes
Ich habe mich gefragt, wie ich meine JavaScript-Antwort auf Batch portieren wollte, aber der Hinweis lag in @ Dennis 'Python-Lösung.
quelle
Pyth, 20 Bytes
Ein Programm, das die Eingabe einer Ganzzahl mit Nullindex annimmt und das Ergebnis ausgibt.
Testsuite (Erster Teil zur Formatierung)
Wie es funktioniert
[Erklärung kommt später]
quelle
Ruby, 58 Bytes
Die einfache Hardcodelösung.
quelle
gestapelt , 40 Bytes
Dieses Lambda entspricht dem folgenden Lambda:
Probieren Sie es online!
quelle
Oktave, 148 Bytes
quelle
Haskell, 151 Bytes
Rufen Sie die Funktion
f 123456789012345678901234567890123456789012345678
beispielsweise mit auf.Der Code funktioniert auch mit sehr großen Indizes. Aufgrund der implementierten Modulo 24-Funktionalität ist es sehr schnell.
Der unkomprimierte Code:
quelle
R, 90 Bytes
Eine schrecklich lange Lösung, aber sie ist besser als die 108, die ich ursprünglich hatte. Ich vermute, dass es einen viel besseren Weg gibt, aber ich kann es im Moment nicht sehen.
Dies ist eine Funktion , dass unnamed Verwendungen
gsub
undscan(t=
die Zahlen in dem Vektor in Stellen zu spalten. Die Summe davon wird zum Vektor addiert, während das erste Objekt abgelegt wird.repeat
wird verwendet, um die Sequenzzeiten zu durchlaufen,n
und das Ergebnis ist das erste Element des Vektors.quelle
PHP, 80 Bytes
Online Version
quelle
Mathematica, 67 Bytes
quelle