Liczby Fibonacciego
Liczby Fibonacciego zaczynają się od f(1) = 1
if(2) = 1
(niektórzy obejmuje f(0) = 0
, ale to nie ma znaczenia do tego wyzwania. Następnie, dla n > 2
, f(n) = f(n-1) + f(n-2)
.
Wyzwanie
Twoim zadaniem jest znalezienie i wydrukowanie pliku n
-tej liczby dodatniej, którą można wyrazić jako iloczyn liczb Fibonacciego. Możesz wybrać opcję indeksowania 0 lub indeksowania 1, w zależności od tego, który bardziej Ci odpowiada, ale musisz to określić w swojej odpowiedzi.
Twoja odpowiedź musi również obliczyć 100. termin w rozsądnym czasie.
Przypadki testowe
n result corresponding product (for reference)
1 1 1
2 2 2
3 3 3
4 4 2*2
5 5 5
6 6 2*3
7 8 2*2*2 or 8
8 9 3*3
9 10 2*5
10 12 2*2*3
11 13 13
12 15 3*5
13 16 2*2*2*2 or 2*8
14 18 2*3*3
15 20 2*2*5
16 21 21
17 24 2*2*2*3 or 3*8
18 25 5*5
19 26 2*13
20 27 3*3*3
100 315 3*5*21
Referencje
code-golf
number-theory
fibonacci
Leaky Nun
źródło
źródło
7
nie można wyrazić jako iloczyn liczb Fibonacciego. Dlatego1
st wymaganą liczbą jest1
,2
nd jest2
, ...,6
th jest6
, ale7
th jest8
.corresponding product
” służy jedynie wyjaśnieniu. Twój kod musi tylko wyświetlać „result
”.Odpowiedzi:
Galaretka ,
26242321 bajtówWypróbuj online!
Jak to działa
źródło
Julia, 79 bajtów
Wypróbuj online!
tło
W Zaawansowanych problemach i rozwiązaniach H-187: Fibonacci jest kwadratem , o czym mówi wnioskodawca
gdzie L n oznacza n- tą liczbę Lucasa i odwrotnie - jeśli
następnie n jest liczbą Fibonacciego, a m jest liczbą Lucasa.
Jak to działa
Definiujemy operatora binarnego
<|
do naszych celów. Nie jest zdefiniowane w najnowszych wersjach Julii, ale nadal jest rozpoznawane przez parser jako operator.Gdy zostanie wywołany tylko z jednym argumentem ( n ),
<|
inicjuje k jako 1 . Chociaż n jest dodatnie, odejmuje ! K ( 1, jeśli k jest iloczynem liczb Fibonacciego, 0, jeśli nie) od n i rekurencyjnie wywołuje siebie, zwiększa k o 1 . Gdy n osiągnie wartość 0 , znaleziono żądaną liczbę produktów, więc<|
zwraca poprzednią wartość k , tj. ~ -K = k - 1 .Jeden operator
!
, na nowo zdefiniowany jako test dla produktów liczbowych Fibonacciego, spełnia swoje zadanie w następujący sposób.Jeśli k = 1 , k jest iloczynem liczb Fibonacciego. W tym przypadku zwiększamy wartość zwracaną
any(...)
do potęgi ~ -k = k - 1 = 0 , więc wynik będzie wynosił 1 .Jeśli k> 1 , wynikiem będzie wartość
any(....)
, która zwróci wartość true wtedy i tylko wtedy, gdy predykat√(5i^2+[4,-4])%1∋k%i<!(k÷i)
zwróci wartość true dla pewnej liczby całkowitej i takiej, że 2 ≤ i ≤ k .Warunki powiązane w łańcuchu predykatów są, jeśli
k%i
należą do√(5i^2+[4,-4])%1
ik%i
są mniejsze niż!(k÷i)
.√(5i^2+[4,-4])%1
bierze pierwiastek kwadratowy z 5i 2 + 4 i 5i 2 - 4 i oblicza ich reszty modulo 1 . Każdy moduł wynosi 0, jeśli odpowiednia liczba jest kwadratem idealnym, a liczba dodatnia mniejsza niż 1 w przeciwnym razie.Ponieważ
k%i
zwraca liczbę całkowitą, może należeć do tablicy modułów tylko wtedy, gdy k% i = 0 (tj. K jest podzielne przez i ) i co najmniej jeden spośród 5i 2 + 4 i 5i 2 - 4 jest kwadratem idealnym (tj. i jest liczbą Fibonacciego).!(k÷i)
rekurencyjnie wywołuje 1 z argumentem k ÷ i (dzielenie całkowite), który będzie większy niż 0 wtedy i tylko wtedy, gdy k ÷ i jest iloczynem liczb Fibonacciego.Przez indukcję ! ma pożądaną właściwość.
źródło
Python, 90 bajtów
Główna funkcja
g
generujek
th produkt Fibonacciego, 1-indeksowany. Obliczag(100)
jak315
niemal natychmiast. Jest tak z ogólnym rekurencyjnym przepisem liczenia liczb wn
poszukiwaniuk
instancji spełniających tę funkcjęf
. Każde takie wystąpienie obniża wymaganą liczbę,k
aż do osiągnięcia0
.Funkcja pomocnicza
f
sprawdza liczbę jako produkt Fibonacciego. Rekurencyjnie generuje liczby Fibonacciego w opcjonalnych argumentacha
ib
. Zwraca „tak”, jeśli spełniony jest jeden z poniższych warunków:n<2
. Oznacza ton==1
, że trywialny produkt)n%a<f(n/a)
. Wymagan%a==0
af(n/a)==True
, czyli żen
jest wielokrotnością liczby Fibonacciegoa
, a usunięcie tego czynnikaa
nadal daje produkt Fibonacciego.n-a>0<f(n,b,a+b)
, równoważne zn>a and f(n,b,a+b)
. Sprawdza, czy bieżąca testowana liczba Fibonacciego nie jest przynajmniejn
, i działa pewna większa liczba Fibonacciego. Dzięki Dennisowi za 2 bajty oszczędnościowe zamiast zwarcia z nierównościąand
.Funkcja
g
może być o jeden bajt krótsza jakojeśli
g(k)
zawsze jest co najwyżejk*k
, co nie jestem pewny, jest asymptotycznie prawdziwe. Granica2**k
wystarcza, ale potemg(100)
trwa zbyt długo. Może zamiast tegog
można wykonać rekurencjęf
.źródło
g(k)
przekraczak*k
kiedyk = 47000
i więcej.Perl 6 ,
9593 bajtów(Indeks 0)
Test:
Wyjaśnienie:
źródło
Python 3,
175170148 bajtówDzięki @Dennis za -22 bajty
Pobiera dane wejściowe ze STDIN i drukuje do STDOUT. Jest to jeden indeks. Obliczenie setnego terminu zajmuje około jednej dziesiątej sekundy.
Jak to działa
Wypróbuj na Ideone
źródło
Python 2,
120107 bajtówPrzetestuj na Ideone .
Jak to działa
Inicjalizujemy F jako krotkę (2, 3) (pierwsze dwie liczby Fibonacciego większe niż 1 ), k jako 0 i n jako liczbę całkowitą odczytaną ze STDIN.
Chociaż n jest dodatnie, wykonujemy następujące czynności:
Dołącza następna liczba Fibonacciego, obliczony jako F [K] + C [1] , to znaczy suma dwóch ostatnich elementów F na krotki F .
Przyrost k .
Odejmij g (k) od n .
g zwraca 1 wtedy i tylko wtedy, gdy k jest iloczynem liczb Fibonacciego, więc gdy n osiągnie 0 , k jest n- tą liczbą Fibonacciego i wypisujemy ją do STDOUT.
g osiąga swój cel w następujący sposób.
Jeśli k wynosi 1 , jest to iloczyn liczb Fibonacciego i
1/k
upewnia się, że zwracamy 1 .Jeśli k jest większe niż 1 , nazywamy
g(k/i)
rekurencyjnie dla wszystkich liczb Fibonacciego I w F .g(k/i)
rekursywnie sprawdza, czy k / i jest iloczynem liczby Fibonacciego. Jeślig(k/i)
zwraca 1 i i dzieli równomiernie k , k% i = 0, a warunek pozostajek%i<g(k/i)
, więc g zwróci 1 wtedy i tylko wtedy, gdy istnieje liczba Fibonacciego taka, że k jest iloczynem tej liczby Fibonacciego i innego iloczynu liczb Fibonacciego.źródło
JavaScript (ES6), 136
W ten sposób grałem w golfa dość wolno, obliczając termin 100 w około 8 sekund na moim komputerze.
Mniej golfowy i szybszy (unikanie
eval
)Test
źródło
Haskell, 123 bajty
Bardzo leniwy, nieskończony!
Być może nie jest to najkrótsza droga, ale musiałem wypróbować to podejście, uogólnienie dość dobrze znanej metody obliczania listy liczb hamujących.
f
jest listą liczb Fibonacciego zaczynającą się od 2. Dla zwięzłości powiedzmy, że lol (lista list) jest nieskończoną listą uporządkowanych nieskończonych list, uporządkowanych według ich pierwszych elementów.m
jest funkcją scalania lol, usuwania duplikatów. Wykorzystuje dwie funkcje pomocnicze infix.?
wstawia nieskończoną posortowaną listę do lol.#
usuwa wartość z LOL, która może pojawić się jako nagłówek pierwszych list, ponownie wstawiając pozostałą listę za pomocą?
.Na koniec
l
znajduje się lista liczb, które są iloczynami liczb Fibonacciego, zdefiniowana jako 1, po której następuje scalenie wszystkich list uzyskanych przez pomnożenie przezl
liczbę Fibonacciego. Ostatni wiersz podaje wymaganą funkcję (jak zwykle bez wiązania jej z nazwą, więc nie kopiuj jej w obecnej postaci), używając!!
do indeksowania listy, co powoduje, że funkcja jest indeksowana.Nie ma problemu z obliczeniem 100. lub 100 000. liczby.
źródło
Łuska , 13 bajtów
Zauważ, że Łuska jest nowsza od tego wyzwania. Jednak to i najbardziej przydatna funkcja dla tego golfa (
Ξ
) nie zostały stworzone z myślą o tym wyzwaniu.Wypróbuj online!
Bardziej wydajna wersja na 14 bajtów:
Wypróbuj online!
źródło
Python 2,
129128125123121 bajtówPrzetestuj na Ideone .
źródło