Définition

La séquence de Fibonacci de puissance alternative est formée comme suit.

1. Commencez avec la séquence vide et réglez n sur 1 .

2. Calculez f _n , le n ^ième nombre de Fibonacci non négatif , avec répétitions.
   0 est le premier, 1 est le deuxième et le troisième, 2 est le quatrième. Tous les autres sont obtenus en additionnant les deux nombres précédents dans la séquence, donc 3 = 1 + 2 est le cinquième, 5 = 2 + 3 est le sixième, etc.

3. Si n est impair, changez le signe de f _n .

4. Ajoutez 2 ^n-1 copies de f _n à la séquence.

5. Incrémentez n et revenez à l'étape 2.

Ce sont les cent premiers termes de la séquence APF.

 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

Tâche

Écrivez un programme complet ou une fonction qui prend un entier positif n en entrée et imprime ou retourne le n ^ème terme de la séquence APF.

Si vous préférez une indexation basée sur 0, vous pouvez également prendre un entier non négatif n et imprimer ou renvoyer le numéro APF à l'index n .

C'est du golf de code ; que le code le plus court en octets gagne!

Cas de test (basés sur 1)

    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

Cas de test (basés sur 0)

    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

Gelée , 5 octets

BLCÆḞ

Essayez-le en ligne!

Comment?

Extension de la série de Fibonacci à des indices négatifs de telle sorte que la relation f(i) = f(i-2) + f(i-1)est toujours valable:

  i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ...

Pour revenir i=0aux chiffres, nous devons répéter 2 ^{à 1} fois, et Jelly's Fibonacci intégré ÆḞ, les calculera.

Nous pouvons trouver le -i(un nombre positif) dont nous avons besoin en prenant la longueur de bits net en soustrayant 1.

Puisque nous voulons i(un nombre négatif) , nous pouvons effectuer à la place 1-bitLengthet Jelly a un atome pour 1-x, Cla monade du complément.

BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21

Python 2 , 30 octets

f=lambda n:n<1or f(n/4)-f(n/2)

Essayez-le en ligne!

Un index.

La séquence ressemblait à un puzzle, quelque chose que Dennis a généré en ayant un moyen court de l'exprimer. Les répétitions de puissance de deux suggèrent une récurrence par décalage de bits (division du plancher par 2). La récursion de Fibonacci à signe alternatif f(n)=f(n-2)-f(n-1)peut être adaptée au décalage de bits au lieu de décrémenter. Le cas de base fonctionne bien car tout est acheminé vers n=0.

Mathematica, 43 36 24 octets

Fibonacci@-Floor@Log2@#&

7 octets enregistrés grâce à @GregMartin, et 12 autres grâce à @JungHwanMin.

MATL , 19 17 16 11 octets

lOiB"yy-]x&

L'entrée est basée sur 1.

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

Comment ça marche

Pour une entrée n basée sur 1 , soit m le nombre de chiffres dans l'expansion binaire de n . Le n- ème terme de la séquence de sortie est le m- ème terme de la séquence de Fibonacci, éventuellement avec son signe changé.

Une idée serait d'itérer m fois pour calculer les termes de la séquence de Fibonacci. C'est facile avec une for eachboucle utilisant le tableau de chiffres binaires. Si la séquence de Fibonacci était initialisée avec 0 , puis 1 comme d'habitude, l'itération de m fois entraînerait m + 2 termes sur la pile, de sorte que les deux premiers chiffres devraient être supprimés. Au lieu de cela, nous initialisons avec 1 , puis 0 . De cette façon, les prochains termes générés sont 1 , 1 , 2 , ... et une seule suppression est nécessaire.

Le signe pourrait être traité en utilisant une autre boucle pour changer le signe m fois. Mais c'est coûteux. Il est préférable d'intégrer les deux boucles, ce qui se fait simplement en soustrayant au lieu d'ajouter dans l'itération de Fibonacci.

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack

JavaScript (ES6), 33 octets

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p

1 indexé.

Un port de la réponse de xnor serait 23:

f=n=>n<1||f(n/4)-f(n/2)

Python 2 , 83 82 79 octets

def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1)

Essayez-le en ligne!

Gelée , 9 octets

BLµ’ÆḞN⁸¡

Utilise l'indexation à base unique.

Essayez-le en ligne!

Explication

Cette méthode fonctionne si votre fonction Fibonacci prend uniquement en charge les arguments non négatifs.

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1)

Japt , 6 octets

Mg1-¢l

Testez-le en ligne!

Comment ça marche

Comme mentionné dans d' autres réponses, le n ^ième terme de la série de Fibonacci signe alternatif est le même que le -n ^e terme de la série régulière. n peut être trouvé en prenant la longueur de bit de l'entrée et en soustrayant celle-ci; la négation de ceci entraîne 1 moins la longueur de bit.

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index.

05AB1E , 11 10 octets

Utilise l'indexation basée sur 1

05AB1ELa fonction Fibonacci de renvoie des nombres de fib positifs inférieurs à n , ce qui signifie que nous devons générer plus que nécessaire, obtenir le bon par index puis calculer le signe. Je doute donc que toute méthode basée sur cela soit plus courte que le calcul itératif des nombres.

Utilise la réalisation que nous pouvons initialiser la pile avec 1, 0inversé pour gérer le cas lorsque n=1comme décrit dans la réponse MATL de Luis Mendo .

XÎbgG‚D«`-

Essayez-le en ligne!

Explication

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements

Perl 6 , 53 octets

{flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]}

Mise en œuvre simple de la séquence, telle qu'elle a été décrite.
Base zéro.

Julia 0,5 , 19 octets

!n=n<1||!(n/=4)-!2n

Essayez-le en ligne!

Comment ça marche

Cela utilise la même formule que la réponse Python @ xnor . La relation de récurrence
g (n) = g (n-2) + g (n-1) génère les termes négatifs de la séquence de Fibonacci, qui égalent les termes positifs avec des signes alternés. De n'importe où dans une série de 2 ^k répétitions du même nombre, nous pouvons choisir n'importe quelle répétition de la série précédente de 2 ^k-1 et de la série de 2 ^k-2 avant celles en divisant l'index par 2 et 4 .

Plutôt que le simple

f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes

nous pouvons redéfinir un opérateur pour nos besoins. De plus, f fonctionnera tout aussi bien avec des flotteurs, donc nous obtenons

!n=n<1||!(n/4)-!(n/2)   # 21 bytes

Enfin, si nous mettons à jour n avec une division par 4 , nous pouvons écrire n / 2 comme 2n et omettre une paire de parens, conduisant à la définition de fonction de 19 octets dans cette réponse.

J , 18 octets

(%>:-*:)t.@<:@#@#:

Utilise l'indexation à base unique. Prend un entier d'entrée n > 0 et calcule floor(log2(n))en trouvant la longueur de sa représentation binaire, puis décrémente cette valeur de un. Il trouve alors le floor(log2(n))-1^e coefficient de la fonction génératrice x / (1 + x - x ² ) qui est le gf pour les valeurs de Fibonacci indexées négativement.

Essayez-le en ligne!

Explication

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value