Definicja

Sekwencja Fibonacciego Przemiennej Mocy jest tworzona w następujący sposób.

1. Zacznij od pustej sekwencji i ustaw n na 1 .

2. Oblicz f _n The n ^p nieujemną liczbę Fibonacciego z powtórzeniami.
   0 to pierwsza, 1 to druga, a trzecia, 2 to czwarta. Wszystkie pozostałe uzyskuje się przez zsumowanie dwóch poprzednich liczb w sekwencji, więc 3 = 1 + 2 to piąta, 5 = 2 + 3 to szósta itd.

3. Jeśli n jest nieparzyste, zmień znak f _n .

4. Dołącz 2 ^n-1 kopii f _n do sekwencji.

5. Zwiększ wartość n i wróć do kroku 2.

Są to pierwsze sto terminów sekwencji 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

Zadanie

Napisz pełny program lub funkcję, która przyjmuje na wejściu dodatnią liczbę całkowitą n i wypisuje lub zwraca n- ^ty ciąg sekwencji APF.

Jeśli wolisz indeksowanie oparte na 0, możesz alternatywnie wziąć nieujemną liczbę całkowitą n i wydrukować lub zwrócić numer APF o indeksie n .

To jest golf golfowy ; niech wygra najkrótszy kod w bajtach!

Przypadki testowe (oparte na 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

Przypadki testowe (oparte na 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

Galaretka , 5 bajtów

BLCÆḞ

Wypróbuj online!

W jaki sposób?

Rozszerzenie serii Fibonacciego z powrotem do indeksów ujemnych, tak że relacja f(i) = f(i-2) + f(i-1)nadal zachowuje:

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

Wracając i=0do liczb, musimy powtórzyć 2 ^n-1 razy, a wbudowane Fibonacciego Jelly'ego to obliczą ÆḞ.

Możemy znaleźć -i(liczbę dodatnią), której potrzebujemy, biorąc długość bitu ni odejmując 1.

Ponieważ chcemy i(liczba ujemna), możemy zamiast tego wykonać, 1-bitLengtha galaretka ma atom 1-x, Cmonada dopełniacza.

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 bajtów

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

Wypróbuj online!

Jeden indeksowany.

Sekwencja wydawała się łamigłówką, czymś, co Dennis wygenerował, mając krótki sposób na wyrażenie tego. Potęga dwóch powtórzeń sugeruje rekurencję poprzez przesunięcie bitów (podział podłogi przez 2). Rekurencja Fibonacciego ze znakiem przemiennym f(n)=f(n-2)-f(n-1)może być dostosowana do przesunięcia bitów zamiast dekrementacji. Podstawowa obudowa działa dobrze, ponieważ wszystko leci do n=0.

Mathematica, 43 36 24 bajtów

Fibonacci@-Floor@Log2@#&

7 bajtów zaoszczędzonych dzięki @GregMartin, a kolejne 12 dzięki @JungHwanMin.

MATL , 19 17 16 11 bajtów

lOiB"yy-]x&

Dane wejściowe są oparte na 1.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Jak to działa

Dla wejścia n opartego na 1 , niech m będzie liczbą cyfr w binarnym rozwinięciu n . N -tego terminu w sekwencji wyjściowej jest m -tego terminu w sekwencji Fibonacciego, ewentualnie z jego znak zmianie.

Jednym z pomysłów byłoby powtórzenie m razy w celu obliczenia warunków sekwencji Fibonacciego. Jest to łatwe dzięki for eachpętli wykorzystującej tablicę cyfr binarnych. Gdyby sekwencję Fibonacciego zainicjalizowano za pomocą 0 , to 1 jak zwykle, iteracja m razy skutkowałaby m + 2 warunkami na stosie, więc dwie pierwsze liczby musiałyby zostać usunięte. Zamiast tego inicjalizujemy za pomocą 1 , a następnie 0 . W ten sposób następne wygenerowane warunki to 1 , 1 , 2 , ... i tylko jedno usunięcie jest potrzebne.

Znak można rozwiązać za pomocą innej pętli, aby zmienić znak m razy. Ale to jest kosztowne. Lepiej zintegrować dwie pętle, co odbywa się po prostu odejmując zamiast dodając iterację Fibonacciego.

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 bajty

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

1-indeksowany.

Port odpowiedzi xnora to 23:

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

Python 2 , 83 82 79 bajtów

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)

Wypróbuj online!

Galaretka , 9 bajtów

BLµ’ÆḞN⁸¡

Używa indeksowania opartego na jednym.

Wypróbuj online!

Wyjaśnienie

Ta metoda działa, jeśli funkcja Fibonacciego obsługuje tylko argumenty nieujemne.

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 bajtów

Mg1-¢l

Przetestuj online!

Jak to działa

Jak wspomniano w innych odpowiedziach, n- ^ty termin w serii Fibonacciego ze znakiem przemiennym jest taki sam, jak -n- ^ty termin w regularnej serii. n można znaleźć, biorąc długość bitu wejścia i odejmując jeden; negowanie tego powoduje 1 minus długość bitu.

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 bajtów

Wykorzystuje indeksowanie 1

Funkcja Fibonacciego 05AB1E zwraca dodatnie liczby Fib mniejsze niż n , co oznacza, że ​​musielibyśmy wygenerować więcej niż to konieczne, uzyskać poprawną przez indeks, a następnie obliczyć znak. Wątpię więc, aby jakakolwiek metoda oparta na tym była krótsza niż iteracyjne obliczanie liczb.

Wykorzystuje świadomość, że możemy zainicjować stos z 1, 0odwróceniem, aby obsłużyć skrzynkę, gdy n=1jest to opisane w odpowiedzi MATL Luisa Mendo .

XÎbgG‚D«`-

Wypróbuj online!

Wyjaśnienie

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 bajtów

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

Prosta implementacja sekwencji, sposób jej opisania.
Zero.

Julia 0,5 , 19 bajtów

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

Wypróbuj online!

Jak to działa

Wykorzystuje to tę samą formułę, co odpowiedź Python @ xnor . Relacja nawrotu
g (n) = g (n-2) + g (n-1) generuje ujemne wyrażenia sekwencji Fibonacciego, które równoważą wyrażenia dodatnie naprzemiennymi znakami. Z dowolnego miejsca w serii 2 ^tys. Powtórzeń o tej samej liczbie możemy wybrać dowolną powtórkę z poprzedniej serii 2 ^tys. Liczb i 2 ^tys. Liczb przed tymi, dzieląc indeks przez 2 i 4 .

Zamiast bezpośredniego

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

możemy ponownie zdefiniować operatora do naszych celów. Również f będzie działać równie dobrze z pływakami, więc otrzymujemy

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

Wreszcie, jeśli zaktualizujemy n dzieleniem przez 4 , możemy zapisać n / 2 jako 2n i pominąć parę parenów, co prowadzi do definicji funkcji 19-bajtowej w tej odpowiedzi.

J , 18 bajtów

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

Używa indeksowania opartego na jednym. Pobiera wejściową liczbę całkowitą n > 0 i oblicza floor(log2(n))ją, znajdując długość jej reprezentacji binarnej, a następnie zmniejsza tę wartość o jeden. Następnie znajduje współczynnik floor(log2(n))-1^th funkcji generującej x / (1 + x - x ² ), który jest gf dla wartości Fibonacciego o indeksie ujemnym.

Wypróbuj online!

Wyjaśnienie

(%>:-*:)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