Sie haben wahrscheinlich von Fibonacci-Zahlen gehört. Weißt du, diese Ganzzahlsequenz, die mit beginnt 1, 1
, und dann ist jede neue Zahl die Summe der letzten beiden?
1 1 2 3 5 8 13...
Und so weiter. Herausforderungen bezüglich der Fibonacci-Zahlen sind hier sehr beliebt . Aber wer sagt, dass die Fibonacci-Zahlen anfangen müssen 1, 1
? Warum konnten sie nicht mit anfangen 0, 1
? Okay, definieren wir sie neu, um bei 0 zu beginnen:
0 1 1 2 3 5 8 13...
Aber ... da müssen wir auch nicht aufhören! Wenn wir die letzten beiden Zahlen addieren können, um die nächste zu erhalten, können wir auch die erste Zahl von der zweiten Zahl abziehen, um eine neue Zahl voranzustellen. So könnte es beginnen mit 1, 0
:
1 0 1 1 2 3 5 8 13...
Wir können sogar mit Negativen enden:
-1 1 0 1 1 2 3 5 8 13...
Und diese Serie geht auch für immer weiter. Ich finde es interessant, wie es zu einer Art Spiegelung der regulären Fibonacci-Zahlen kommt, nur mit jeder anderen negativen Zahl:
13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...
Nennen wir diese Serie die "Extended Fibonacci Number" oder EFN . Da es keine offensichtliche negative Zahl gibt, an der diese Reihe beginnen könnte, werden wir sagen, dass 0 bei 0 auftaucht , die regulären Fibonacci-Zahlen sich auf die positiven Indizes erstrecken und die negativen (halbnegativen?) Fibonacci-Zahlen sich erstrecken in den negativen Indizes, wie so:
Indices: ...-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
Values: ...13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...
Dies führt zur heutigen Herausforderung:
Gegeben eine ganze Zahl N , Rückkehr jeden Index , bei dem N im erscheint EFN - Serie.
Einige zufällige Beobachtungen zu dieser Aufgabe:
1 erscheint mehrmals in der EFN als jede andere Zahl:
[-1, 1, 2]
. Keine Nummer erscheint an mehr als 3 Stellen.Jede Fibonacci-Zahl> 1 wird entweder einmal (3, 8, 21 usw.) oder zweimal (2, 5, 13 usw.) angezeigt.
Regelklärungen:
- Wenn
abs(N)
es sich nicht um eine Fibonacci-Zahl handelt, wird sie niemals in der EFN- Reihe angezeigt. Sie müssen daher nach Möglichkeit nichts oder eine leere Sammlung ausgeben. Wenn dies in Ihrer Sprache nicht möglich ist, können Sie einen konstanten nicht numerischen Wert ausgeben. - Wenn N an mehreren Stellen in der EFN angezeigt wird , muss Ihre Ausgabe nicht sortiert werden. Obwohl jeder Index genau einmal erscheinen muss.
- Obwohl Sie bei den meisten Sequenzherausforderungen auswählen können, ob Sie eine 1-basierte oder eine 0-basierte Indizierung verwenden möchten, muss für diese Herausforderung die beschriebene Indizierung verwendet werden (wobei 0 bei 0 angezeigt wird).
- Sie können I / O durch jedes Standardformat führen.
Testfälle
-13: []
-12: []
-11: []
-10: []
-9: []
-8: [-6]
-7: []
-6: []
-5: []
-4: []
-3: [-4]
-2: []
-1: [-2]
0: 0
1: [-1, 1, 2]
2: [-3, 3]
3: [4]
4: []
5: [-5, 5]
6: []
7: []
8: [6]
9: []
10: []
11: []
12: []
13: [-7, 7]
Und einige größere Testfälle:
89: [-11, 11]
1836311903: [46]
10000: []
-39088169: [-38]
Wie immer gewinnt die kürzeste Antwort in Bytes!
Antworten:
Haskell , 78 Bytes
4 Bytes gespart dank nimi
Probieren Sie es online!
Zuerst richten wir ein
(#)
,(#)
nehmen zwei Parametera
undb
und geben die Liste a zurück, die mita
und gefolgt von beginntb#(a-b)
. Dies erzeugt eine unendliche Liste, aber da Haskell faul ist, brauchen wir uns keine Gedanken darüber zu machen, dass es für immer eine Schleife gibt. Dies funktioniert im Wesentlichen rückwärts, indem die Fibonacci-Sequenz vor einem bestimmten Paar erstellt wird. Zum Beispiel(0#1)
wäre die Liste aller Fibonacci-Zahlen mit negativem Index.Von hier aus machen wir
f
.f
Nimmt ein Argument,a
das die Nummer ist, die wir in der Sequenz zu finden versuchen. Hier verwenden wir diedo
Notation, um ein Listenverständnis zu erstellen. Wir beginnen mit den erstena*a+1
Elementen der Liste0#1
1 . Da die Funktiona*a+1
schneller wächst als die Umkehrung der Fibonacci-Sequenz, können wir sicher sein, dass wir alle Ergebnisse finden, wenn wir innerhalb dieser Grenze prüfen. Dies hindert uns daran, eine unendliche Liste zu durchsuchen. Wenn wir dann für jeden Wertx
und Index in der negativen Hälfte der Sequenz gefunden haben, kehren wir zurück , und wenn wir auch zurück, weil der absolute Wert der negativen Hälfte die positive Hälfte ist, haben wir ihn dort gefunden.i
x==a
a
-i
abs x==a
i
Da dies die Liste
[0,0]
für macht0
, codieren wir die richtige Ausgabe für diese.1: Dieser Trick stammt aus fromurous 'Clean-Antwort . Hier gilt die gleiche Beschleunigung wie dort, ersetzen Sie sie
a*a+1
durchabs a+1
, um viel Zeit zu sparen.quelle
u
mita#b=a:b#(a-b)
Plus wird0#1
ein Byte gespeichert: Probieren Sie es online aus!Sauber ,
132120109 BytesProbieren Sie es online!
g :: Int -> Int
ist die Fibonacci-Funktion.? :: Int -> [Int]
Indiziert nur die Elemente der EFN innerhalbk^2+1
von0
.Ändern Sie für eine Version, die in einer vernünftigen Zeit ausgeführt wird,
k*k+1
zuabs k+1
.quelle
Jelly , 11 Bytes
Probieren Sie es online!
quelle
JavaScript (ES6),
94.93ByteProbieren Sie es online!
quelle
APL (Dyalog Classic) ,
52 bis50 ByteBenötigt
⎕IO←0
Probieren Sie es online!
quelle
Retina 0.8.2 ,
104102 BytesProbieren Sie es online! Erläuterung:
In Unary konvertieren, es sei denn, die Eingabe ist Null.
Berechnen Sie den Fibonacci-Index des Absolutwerts. Wenn die Zahl jedoch keine Fibonacci-Zahl ist, löschen Sie sie, es sei denn, sie war Null. Dies verwendet @ MartinEnders Fibonacci-Test-Regex.
Löschen Sie negative Zahlen, deren Absolutwerte ungerade Fibonacci-Zahlen sind.
Fügen Sie negative Indizes für ungerade positive Fibonacci-Zahlen hinzu.
In Dezimalzahl konvertieren.
Fügen Sie die zusätzlichen Indizes für hinzu
1
.quelle
Eigentlich 34 Bytes
Brute-Force rettet den Tag
Erläuterung:
Probieren Sie es online!
quelle
Python 3 , 92 Bytes
Probieren Sie es online!
Gibt eine Reihe von Indizes zurück.
quelle
Python 2 ,
87-85BytesProbieren Sie es online!
quelle
05AB1E , 36 Bytes
Es muss einen besseren Ansatz geben.>.> Es gibt sechs (oder sieben, wenn wir
0
verschiedene Szenarien einschließen ) für diese Herausforderung, und das bringt mich um.Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
Einige schrittweise Beispiele:
quelle
Python 2 ,
959294 BytesProbieren Sie es online!
quelle
C # (Visual C # Interactive Compiler) , 144 Byte
Probieren Sie es online!
quelle