Definition
Die Wechselstrom-Fibonacci-Sequenz wird wie folgt gebildet.
Beginnen Sie mit der leeren Sequenz und setzen Sie n auf 1 .
Berechnen Sie f n , die n- te nicht negative Fibonacci-Zahl , mit Wiederholungen.
0 ist die erste, 1 ist die zweite und die dritte, 2 ist die vierte. Alle anderen werden durch Summieren der beiden vorherigen Zahlen in der Folge erhalten, also ist 3 = 1 + 2 die fünfte, 5 = 2 + 3 die sechste usw.Wenn n ungerade ist, ändern Sie das Vorzeichen von f n .
Fügen Sie der Sequenz 2 n-1 Kopien von f n hinzu .
Inkrementiere n und gehe zurück zu Schritt 2.
Dies sind die ersten hundert Terme der APF-Sequenz.
0 1 1 -1 -1 -1 -1 2 2 2 2 2 2 2 2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
Aufgabe
Schreiben Sie ein vollständiges Programm oder eine Funktion, die eine positive ganze Zahl n als Eingabe verwendet und den n- ten Term der APF-Sequenz ausgibt oder zurückgibt .
Wenn Sie eine 0-basierte Indizierung bevorzugen, können Sie alternativ eine nicht-negative Ganzzahl n verwenden und die APF-Nummer am Index n ausgeben oder zurückgeben .
Das ist Code-Golf ; möge der kürzeste Code in Bytes gewinnen!
Testfälle (1-basiert)
1 -> 0
2 -> 1
3 -> 1
4 -> -1
7 -> -1
8 -> 2
100 -> -8
250 -> 13
500 -> -21
1000 -> 34
11111 -> 233
22222 -> -377
33333 -> 610
Testfälle (0-basiert)
0 -> 0
1 -> 1
2 -> 1
3 -> -1
6 -> -1
7 -> 2
99 -> -8
249 -> 13
499 -> -21
999 -> 34
11110 -> 233
22221 -> -377
33332 -> 610
Antworten:
Gelee , 5 Bytes
Probieren Sie es online!
Wie?
Erweiterung der Fibonacci-Reihe zurück in negative Indizes, sodass die Beziehung
f(i) = f(i-2) + f(i-1)
weiterhin gilt:Wenn
i=0
wir von den Zahlen zurückgehen, müssen wir diese 2 n-1- mal wiederholen , und Jellys Fibonacci ist eingebautÆḞ
, um diese zu berechnen.Wir können die
-i
(eine positive Zahl) finden, die wir brauchen, indem wir die Bitlänge vonn
und subtrahieren1
.Da wir wollen
i
(eine negative Zahl) können wir stattdessen durchführen1-bitLength
und Jelly hat ein Atom für1-x
,C
, das Komplement Monade.quelle
µ
und⁸
Python 2 , 30 Bytes
Probieren Sie es online!
Einindexiert.
Die Sequenz fühlte sich wie ein Rätsel an, etwas, das Dennis durch einen kurzen Weg erzeugte, es auszudrücken. Die Zweierpotenz-Wiederholungen deuten auf eine Rekursion durch Bitverschiebung (Floor-Division durch 2) hin. Die Fibonacci-Rekursion
f(n)=f(n-2)-f(n-1)
mit alternierendem Vorzeichen kann anstelle der Dekrementierung an die Bitverschiebung angepasst werden. Das Basisgehäuse funktioniert sehr gut, weil alles funktioniertn=0
.quelle
Mathematica,
433624 BytesDank @GregMartin wurden 7 Byte und dank @JungHwanMin weitere 12 Byte eingespart.
quelle
Floor@Log2@#
und durch SchreibenFibonacci[t=...]
(und durch Entfernen der Leerzeichen im letzten Exponenten) sparen .Fibonacci@-Floor@Log2@#&
-Fibonacci
Kann auch negative Argumente enthalten (kümmert sich für Sie um das Vorzeichen).MATL ,
19171611 BytesDie Eingabe ist 1-basiert.
Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Wie es funktioniert
Für die 1-basierte Eingabe n sei m die Anzahl der Stellen in der binären Erweiterung von n . Der n- te Term in der Ausgabesequenz ist der m- te Term in der Fibonacci-Sequenz, möglicherweise mit geändertem Vorzeichen.
Eine Idee wäre, m- mal zu iterieren , um Terme der Fibonacci-Sequenz zu berechnen. Dies ist einfach mit einer
for each
Schleife, die ein Array von Binärziffern verwendet. Wenn die Fibonacci-Sequenz wie üblich mit 0 und dann mit 1 initialisiert würde, würde eine m- malige Iteration zu m + 2 Termen auf dem Stapel führen, sodass die beiden oberen Zahlen gelöscht werden müssten. Stattdessen initialisieren wir mit 1 und dann mit 0 . Auf diese Weise sind die nächsten generierten Terme 1 , 1 , 2 , ... und es ist nur eine Löschung erforderlich.Mit dem Vorzeichen könnte umgegangen werden, indem eine andere Schleife verwendet wird, um das Vorzeichen m- mal zu ändern . Aber das ist teuer. Es ist besser, die beiden Schleifen zu integrieren, indem einfach subtrahiert wird, anstatt die Fibonacci-Iteration hinzuzufügen.
quelle
JavaScript (ES6), 33 Byte
1-indiziert.
Eine Antwort von xnor wäre 23:
quelle
Python 2 ,
838279 BytesProbieren Sie es online!
quelle
or -1
.Gelee , 9 Bytes
Verwendet eine einseitige Indizierung.
Probieren Sie es online!
Erläuterung
Diese Methode funktioniert, wenn Ihre Fibonacci-Funktion nur nicht negative Argumente unterstützt.
quelle
Japt , 6 Bytes
Testen Sie es online!
Wie es funktioniert
Wie in anderen Antworten erwähnt, ist der n- te Term in der Fibonacci-Reihe mit Wechselzeichen der gleiche wie der -n- te Term in der regulären Reihe. n kann gefunden werden, indem die Bitlänge der Eingabe genommen und eine subtrahiert wird; Negiert man dies, ergibt sich 1 minus der Bitlänge.
quelle
05AB1E ,
1110 BytesVerwendet 1-basierte Indizierung
Die Fibonacci-Funktion von 05AB1E gibt positive Fib-Zahlen kleiner als n zurück , dh, wir müssten mehr als nötig generieren, die richtige nach Index ermitteln und dann das Vorzeichen berechnen. Daher bezweifle ich, dass eine Methode, die darauf basiert, kürzer ist als die iterative Berechnung der Zahlen.
Verwendet die Erkenntnis, dass wir den Stapel
1, 0
umgekehrt initialisieren können , um den Fall zu behandeln,n=1
wie in Luis Mendos MATL-Antwort beschrieben .Probieren Sie es online!
Erläuterung
quelle
Perl 6 , 53 Bytes
Einfache Umsetzung des Ablaufs, wie er beschrieben wurde.
Nullbasiert.
quelle
Julia 0,5 , 19 Bytes
Probieren Sie es online!
Wie es funktioniert
Dies verwendet die gleiche Formel wie die Python-Antwort von @ xnor . Die Wiederholungsrelation
g (n) = g (n-2) + g (n-1) erzeugt die negativen Terme der Fibonacci-Sequenz, die den positiven Terme mit wechselnden Vorzeichen entsprechen. Von jeder Stelle in einem Durchlauf von 2 k Wiederholungen derselben Zahl können wir eine beliebige Wiederholung des vorherigen Durchlaufs von 2 k-1 Zahlen und des Durchlaufs von 2 k-2 Zahlen vor diesen auswählen, indem wir den Index durch 2 und 4 teilen .
Eher als das Unkomplizierte
Wir können einen Operator für unsere Zwecke neu definieren. Auch f funktioniert genauso gut mit Schwimmern, also bekommen wir
Wenn wir schließlich n durch eine Division durch 4 aktualisieren, können wir n / 2 als 2n schreiben und ein Paar von Parens weglassen, was zu der 19-Byte-Funktionsdefinition in dieser Antwort führt.
quelle
J , 18 Bytes
Verwendet eine einseitige Indizierung. Nimmt eine Eingabe-Ganzzahl n > 0 und berechnet sie,
floor(log2(n))
indem sie die Länge ihrer Binärdarstellung ermittelt und diesen Wert dann um eins dekrementiert. Es wird dann derfloor(log2(n))-1
dritte Koeffizient der Erzeugungsfunktion x / (1 + x - x 2 ) ermittelt, der die gf für die negativ indizierten Fibonacci-Werte ist.Probieren Sie es online!
Erläuterung
quelle