Indizierung der Extended Fibonacci Numbers

21

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 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!

DJMcMayhem
quelle
Verbunden , aber kein Duplikat, da keine Negative oder Nicht-Fibonacci-Zahlen verarbeitet werden müssen.
DJMcMayhem
12
Übrigens gibt es einen weiteren guten Grund, warum die Fibonacci-Zahlen immer indiziert werden sollten, damit $ F_0 = 0 $, auch wenn nur positive Fibonacci-Zahlen verwendet werden. Das ist die Indizierung, die diese schöne Eigenschaft ermöglicht: Wenn $ k $ $ n $ dividiert, dann dividiert $ F_k $ $ F_n $.
Greg Martin

Antworten:

9

Haskell , 78 Bytes

4 Bytes gespart dank nimi

a#b=a:b#(a-b)
f 0=[0]
f a=do{(i,x)<-zip[0..a*a+1]$0#1;[-i|x==a]++[i|abs x==a]}

Probieren Sie es online!

Zuerst richten wir ein (#), (#)nehmen zwei Parameter aund bund geben die Liste a zurück, die mit aund gefolgt von beginnt b#(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. fNimmt ein Argument, adas die Nummer ist, die wir in der Sequenz zu finden versuchen. Hier verwenden wir die doNotation, um ein Listenverständnis zu erstellen. Wir beginnen mit den ersten a*a+1Elementen der Liste 0#11 . Da die Funktion a*a+1schneller 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 Wert xund 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.ix==aa-iabs x==ai

Da dies die Liste [0,0]für macht 0, 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+1durch abs a+1, um viel Zeit zu sparen.

Weizen-Assistent
quelle
Durch Ersetzen umit a#b=a:b#(a-b)Plus wird 0#1ein Byte gespeichert: Probieren Sie es online aus!
nimi
@nimi Es werden 4 Bytes gespart, Ihr tio-Link verfügt über 3 zusätzliche Leerzeichen.
Weizen-Zauberer
5

Sauber , 132 120 109 Bytes

import StdEnv
g n|n<2=n=g(n-1)+g(n-2)
?k=[e\\p<-[0..k*k+1],e<-if(isOdd p)([~p,p]%(0,k))[p*sign k]|g p==abs k]

Probieren Sie es online!

g :: Int -> Intist die Fibonacci-Funktion.
? :: Int -> [Int]Indiziert nur die Elemente der EFN innerhalb k^2+1von 0.

Ändern Sie für eine Version, die in einer vernünftigen Zeit ausgeführt wird, k*k+1zu abs k+1.

Οurous
quelle
1
Dieser Listenverständnis-Trick ist ziemlich ordentlich! Speichert meine 14 Bytes in meiner Antwort.
Weizen-Zauberer
2

JavaScript (ES6),  94.93  Byte

n=>(g=a=>a*a<n*n?g(b,b+=a,i++):a%n)(i=0,b=1)?[]:i&1?n<0?~n?[]:-2:i-1?[-i,i]:[-i,i,2]:n<0?-i:i

Probieren Sie es online!

-0n=0

Arnauld
quelle
1

Retina 0.8.2 , 104 102 Bytes

[1-9].*
$*
(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*
-1(11)+$

^1(11)+$
-$&,$&
1+
$.&
^2$
-1,1,2

Probieren Sie es online! Erläuterung:

[1-9].*
$*

In Unary konvertieren, es sei denn, die Eingabe ist Null.

(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*

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.

-1(11)+$

Löschen Sie negative Zahlen, deren Absolutwerte ungerade Fibonacci-Zahlen sind.

^1(11)+$
-$&,$&

Fügen Sie negative Indizes für ungerade positive Fibonacci-Zahlen hinzu.

1+
$.&

In Dezimalzahl konvertieren.

^2$
-1,1,2

Fügen Sie die zusätzlichen Indizes für hinzu 1.

Neil
quelle
1

Eigentlich 34 Bytes

;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░

Brute-Force rettet den Tag

Erläuterung:

;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░
;╗                                  save a copy of the input (let's call it N) to register 0 (the main way to get additional values into functions)
  3*;±                              -3*N, 3*N
      kSi                           push to list, sort, flatten (sort the two values on the stack so that they are in the right order for x)
         x                          range(min(-3*N, 3*N), max(-3*N, 3*N))
          ⌠;;AF@;1&@0>*YτD(s**╜=⌡░  filter (remove values where function leaves a non-truthy value on top of the stack):
           ;;                         make two copies of parameter (let's call it n)
             AF                       absolute value, Fib(|n|)
               @;                     bring a copy of n to the top of the stack and make another copy
                 1&                   0 if n is divisible by 2 else 1
                   @0>                1 if n is negative else 0 (using another copy of n)
                      *               multiply those two values (acts as logical AND: is n negative and not divisible by 2)
                       YτD            logical negate, double, decrement (maps [0, 1] to [1, -1])
                          (s          sign of n (using the last copy)
                            **        multiply Fib(|n|), sign of n, and result of complicated logic (deciding whether or not to flip the sign of the value for the extended sequence)
                              ╜=      push value from register 0, equality comparison (1 if value equals N else 0)

Probieren Sie es online!

Mego
quelle
1

Python 3 , 92 Bytes

f=lambda x,l=[],i=0,a=0,b=1:i<x*x+2and f(x,l+[i][:a==x]+[-i][:i%2*2*a-a==x],i+1,b,a+b)or{*l}

Probieren Sie es online!

Gibt eine Reihe von Indizes zurück.

Erik der Outgolfer
quelle
0

05AB1E , 36 Bytes

x*ÝʒÅfIÄQ}Ii®šë1KIdiÐ`ÉiD(ì}ëD`Èi(ë¯

Es muss einen besseren Ansatz geben.>.> Es gibt sechs (oder sieben, wenn wir 0verschiedene 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:

x            # Create a list in the range [0, (implicit) input * input * 2]
   ʒ     }     # Filter this list by:
    Åf         #  Where the Fibonacci value at that index
      IÄQ      #  Is equal to the absolute value of the input
Ii             # If the input is exactly 1:
  ®š           #  Prepend -1 to the list
ë              # Else:
 1K            #  Remove all 1s (only applies to input -1)
 Idi           #  If the input is non-negative:
    Ð`Éi   }   #   If the found index in the list is odd:
        D    #    Prepend its negative index to the list
   ë           #  Else (the input is negative):
    Di       #   If the found index in the list is even:
        (      #    Negate the found index
       ë       #   Else (found index is odd):
        ¯      #    Push an empty array
               # (Output the top of the stack implicitly as result)

Einige schrittweise Beispiele:

Input:  Filtered indices:  Path it follows (with actions) and result:

-8      [6]                NOT 1 → neg → even index → negate index: [-6]
-5      [5]                NOT 1 → neg → odd index → push empty array: []
-1      [1,2]              NOT 1 → (remove 1) neg → even remaining index: negate index: [-2]
0       [0]                NOT 1 → even index → negate index: [0]    
1       [1,2]              1 → prepend -1: [-1,1,2]
5       [5]                NOT 1 → non-neg → odd index → Prepend neg index: [-5,5]
8       [6]                NOT 1 → non-neg → even index → (nothing): [6]
Kevin Cruijssen
quelle