Definicja
Sekwencja Fibonacciego Przemiennej Mocy jest tworzona w następujący sposób.
Zacznij od pustej sekwencji i ustaw n na 1 .
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.Jeśli n jest nieparzyste, zmień znak f n .
Dołącz 2 n-1 kopii f n do sekwencji.
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
Odpowiedzi:
Galaretka , 5 bajtów
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:Wracając
i=0
do 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ść bitun
i odejmując1
.Ponieważ chcemy
i
(liczba ujemna), możemy zamiast tego wykonać,1-bitLength
a galaretka ma atom1-x
,C
monada dopełniacza.źródło
µ
i⁸
Python 2 , 30 bajtów
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 don=0
.źródło
Mathematica,
433624 bajtów7 bajtów zaoszczędzonych dzięki @GregMartin, a kolejne 12 dzięki @JungHwanMin.
źródło
Floor@Log2@#
i, piszącFibonacci[t=...]
(i usuwając spacje w ostatnim wykładniku).Fibonacci@-Floor@Log2@#&
-Fibonacci
może również przyjmować argumenty negatywne (dba o znak dla ciebie).MATL ,
19171611 bajtówDane 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 each
pę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.
źródło
JavaScript (ES6), 33 bajty
1-indeksowany.
Port odpowiedzi xnora to 23:
źródło
Python 2 ,
838279 bajtówWypróbuj online!
źródło
or -1
.Galaretka , 9 bajtów
Używa indeksowania opartego na jednym.
Wypróbuj online!
Wyjaśnienie
Ta metoda działa, jeśli funkcja Fibonacciego obsługuje tylko argumenty nieujemne.
źródło
Japt , 6 bajtów
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.
źródło
05AB1E ,
1110 bajtówWykorzystuje 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, 0
odwróceniem, aby obsłużyć skrzynkę, gdyn=1
jest to opisane w odpowiedzi MATL Luisa Mendo .Wypróbuj online!
Wyjaśnienie
źródło
Perl 6 , 53 bajtów
Prosta implementacja sekwencji, sposób jej opisania.
Zero.
źródło
Julia 0,5 , 19 bajtów
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
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
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.
źródło
J , 18 bajtów
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ółczynnikfloor(log2(n))-1
th funkcji generującej x / (1 + x - x 2 ), który jest gf dla wartości Fibonacciego o indeksie ujemnym.Wypróbuj online!
Wyjaśnienie
źródło