Sekwencja Fibonacciego przemiennego

24

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 ; 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
Dennis
źródło
Czy są jakieś ograniczenia dla n ?
Okx,
2
Tak długo, jak algorytm działa na dowolnie duże wartości n , możesz założyć, że pasuje on do twojego typu danych.
Dennis
1
Czy to ma numer OEIS?
Mindwin
@Mindwin Nie.
Dennis

Odpowiedzi:

12

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
Jonathan Allan
źródło
Wiedziałem, że jest krótsza droga, ale nie za bardzo, pomyślałem, że będzie to 7 bajtów ze sposobem na usunięcie µi
mile
Twoje powtarzające się negowanie było jednak sprytne, patrzyłem na moce minus jeden, co dodaje kilka bajtów, aż przypomniałem sobie o ujemnych wartościach Fibonacciego i spróbowałem podłączyć je do monady Jelly.
Jonathan Allan
4
Szczerze mówiąc, jestem zaskoczony, że Jelly nie ma wbudowanego jednobajtowego kodu, aby uzyskać binarną długość liczby ...
ETHproductions
22

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.

xnor
źródło
6

Mathematica, 43 36 24 bajtów

Fibonacci@-Floor@Log2@#&

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

jaskółka oknówka
źródło
1
Możesz zapisać kilka bajtów za pomocą Floor@Log2@#i, pisząc Fibonacci[t=...](i usuwając spacje w ostatnim wykładniku).
Greg Martin
1
-12 bajtów: Fibonacci@-Floor@Log2@#&- Fibonaccimoże również przyjmować argumenty negatywne (dba o znak dla ciebie).
JungHwan Min
5

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
Luis Mendo
źródło
4

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)
ETHprodukcje
źródło
4

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!

ovs
źródło
Biała spacja nie jest wymagana w or -1.
Yytsi
3

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)
mile
źródło
3

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.
ETHprodukcje
źródło
3

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
Emigna
źródło
2

Perl 6 , 53 bajtów

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

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

smls
źródło
2

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.

Dennis
źródło
1

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))-1th funkcji generującej x / (1 + x - x 2 ), 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
mile
źródło