Vous avez probablement entendu parler des chiffres de Fibonacci. Vous savez, cette séquence entière qui commence par 1, 1, puis chaque nouveau nombre est la somme des deux derniers?

1 1 2 3 5 8 13...

Etc. Les défis concernant les numéros de Fibonacci sont assez populaires ici . Mais qui a dit que les chiffres de Fibonacci devaient commencer 1, 1? Pourquoi n'ont-ils pas pu commencer 0, 1? D'accord, redéfinissons-les pour commencer à 0:

0 1 1 2 3 5 8 13...

Mais ... Nous ne devons pas nous arrêter là non plus! Si nous pouvons ajouter les deux derniers nombres pour obtenir le suivant, nous pourrions également soustraire le premier nombre du deuxième nombre pour ajouter un nouveau nombre. Cela pourrait donc commencer par 1, 0:

1 0 1 1 2 3 5 8 13...

On peut même se retrouver avec des négatifs:

-1 1 0 1 1 2 3 5 8 13...

Et cette série continue aussi pour toujours. Je pense que c'est intéressant de voir comment cela finit par refléter les nombres réguliers de Fibonacci, juste avec tous les autres nombres rendus négatifs:

13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...

Appelons cette série le «numéro de Fibonacci étendu», ou EFN . Puisqu'il n'y a pas vraiment de nombre négatif évident pour commencer cette série, nous dirons que 0 apparaît à 0 , les nombres de Fibonacci réguliers s'étendent aux indices positifs, et les nombres de Fibonacci négatifs (semi-négatifs?) S'étendent aux indices négatifs, comme ceci:

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

Cela nous amène au défi d'aujourd'hui:

Étant donné un entier N , retournez chaque indice auquel N apparaît dans la série EFN .

Quelques observations aléatoires sur cette tâche:

• 1 apparaît plusieurs fois dans le EFN que tout autre numéro: [-1, 1, 2]. Aucun numéro n'apparaîtra dans plus de 3 endroits.

• Chaque numéro de Fibonacci> 1 apparaîtra une fois (3, 8, 21, etc.) ou deux fois (2, 5, 13, etc.)

Clarifications des règles:

• Si ce abs(N)n'est pas un nombre de Fibonacci, il n'apparaîtra jamais dans la série EFN , donc vous ne devez rien générer / une collection vide si possible, ou si cela n'est pas possible dans votre langue, vous pouvez sortir une valeur non numérique constante.
• Si N apparaît à plusieurs endroits dans l' EFN , votre sortie n'a pas besoin d'être triée. Bien que chaque index doit apparaître exactement une fois.
• Bien que la plupart des défis de séquence vous permettent de choisir si vous souhaitez utiliser l'indexation basée sur 1 ou 0, ce défi doit utiliser l'indexation décrite (où 0 apparaît à 0).
• Vous pouvez utiliser les E / S dans n'importe quel format standard.

Cas de test

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

Et quelques cas de test plus importants:

89: [-11, 11]
1836311903: [46]
10000: []
-39088169: [-38]

Comme d'habitude, la réponse la plus courte en octets gagne!

Haskell , 78 octets

4 octets économisés grâce à 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]}

Essayez-le en ligne!

D'abord, nous configurons (#), prenons (#)deux paramètres, aet b, et retournons la liste a commençant par aet suivie de b#(a-b). Cela crée une liste infinie, mais parce que Haskell est paresseux, nous n'avons pas besoin de nous en soucier en boucle pour toujours. Cela fonctionne essentiellement à l'envers en créant la séquence de Fibonacci avant une certaine paire. Par exemple, (0#1)serait la liste de tous les nombres de Fibonacci avec un indice négatif.

De là, nous faisons f. fprend un argument aqui est le nombre que nous essayons de trouver dans la séquence. Ici, nous utilisons la donotation pour faire une compréhension de liste. Nous commençons par prendre les premiers a*a+1éléments de la liste 0#1¹ . Puisque la fonction a*a+1croît plus vite que l'inverse de la séquence de Fibonacci, nous pouvons être sûrs que si nous vérifions dans cette limite, nous trouverons tous les résultats. Cela nous empêche de rechercher une liste infinie. Ensuite, pour chaque valeur xet indice i, si x==anous avons trouvé adans la moitié négative de la séquence, nous revenons -i, et si abs x==anous revenons iégalement parce que la valeur absolue de la moitié négative est la moitié positive, nous l'avons donc trouvée là.

Puisque cela fait la liste [0,0]pour 0nous codons en dur la sortie correcte pour celle-ci.

^{1: Cette astuce est tirée de la réponse Clean de Οurous ' . La même accélération s'applique ici comme là-bas, remplacez a*a+1par abs a+1pour gagner beaucoup de temps.}

Propre , 132 120 109 octets

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]

Essayez-le en ligne!

g :: Int -> Intest la fonction de Fibonacci.
? :: Int -> [Int]seulement des indices dans les éléments de l'EFN au sein k^2+1de 0.

Pour une version qui s'exécute dans un laps de temps raisonnable, passez k*k+1à abs k+1.

Gelée , 11 octets

A‘ŒRÆḞẹ_A_2

Essayez-le en ligne!

JavaScript (ES6),  94  93 octets

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

Essayez-le en ligne!

$-0$$n=0$

APL (Dyalog Classic) , 52 50 octets

A besoin ⎕IO←0

{X-⍨⍸⍵=F,⍨⌽0,F×1 ¯1⍴⍨≢F←{⍵≤1:1⋄+/∇¨⍵-1 2}¨⍳X←1+|⍵}

Essayez-le en ligne!

0.8.2 Retina , 104 102 octets

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

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

Essayez-le en ligne! Explication:

[1-9].*
$*

Convertir en unaire, sauf si l'entrée est nulle.

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

Calculez l'indice de Fibonacci de la valeur absolue, mais si le nombre n'est pas un nombre de Fibonacci, supprimez-le, sauf s'il était zéro. Cela utilise l'expression régulière de test de Fibonacci de @ MartinEnder.

-1(11)+$

Supprimez les nombres négatifs dont les valeurs absolues sont des nombres de Fibonacci impairs.

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

Ajoutez des indices négatifs pour les nombres de Fibonacci positifs impairs.

1+
$.&

Convertissez en décimal.

^2$
-1,1,2

Ajoutez les indices supplémentaires pour 1.

En fait , 34 octets

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

La force brute sauve la situation

Explication:

;╗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)

Essayez-le en ligne!

Python 3 , 92 octets

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}

Essayez-le en ligne!

Renvoie un ensemble d'indices.

Python 2 , 87 85 octets

f=lambda v,a=0,b=1,i=1:v*v>=a*a and[i]*(v==b)+[1-i]*((-1)**i*a==v)+f(v,b,a+b,i+1)or[]

Essayez-le en ligne!

05AB1E , 36 octets

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

Il doit y avoir une meilleure approche ..>.> Il y a six (ou sept si nous incluons 0) différents scénarios pour ce défi, et ça me tue ..

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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):
    D`Èi       #   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)

Quelques exemples étape par étape:

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]

Python 2 , 95 92 94 octets

x=input()
i=a=0;b=1
while x*x>=a:
 if 0<a==x:print i
 if[-a,a][i%2]==x:print-i
 a,b=b,a+b;i+=1

Essayez-le en ligne!

C # (Visual C # Interactive Compiler) , 144 octets

o=>{int c=0,n=1,i=0,k=Math.Abs(o);for(;c<k;i++,n+=c,c=n-c);return new[]{c>k|o<0?0.1:i,(i>0|o<0)&i%2>0&c==k?-i:0.1,o==1?2:0.1}.Where(p=>p!=0.1);}

Essayez-le en ligne!