Definicja
Sekwencja Fibonacciego F(n)
na dodatnich liczbach całkowitych jest zdefiniowana jako taka:
1. F(1) = 1
2. F(2) = 1
3. F(n) = F(n-1) + F(n-2), where n is an integer and n > 2
Wyrażenie Fibonacciego dodatniej liczby całkowitej jest iloczynem [F(1), F(2), ..., F(n)]
.
Zadanie
Biorąc pod uwagę dodatnią liczbę całkowitą n
, znajdź oralny Fibonacciego n
.
Okular
Fibonacci-orial 100
musi być obliczony w czasie krótszym niż 5 sekund na rozsądnym komputerze.
Przypadki testowe
n Fibonacci-orial of n
1 1
2 1
3 2
4 6
5 30
6 240
7 3120
8 65520
9 2227680
10 122522400
11 10904493600
12 1570247078400
13 365867569267200
14 137932073613734400
15 84138564904377984000
16 83044763560621070208000
17 132622487406311849122176000
18 342696507457909818131702784000
19 1432814097681520949608649339904000
20 9692987370815489224102512784450560000
100 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Odpowiedzi:
Mathematica, 10 bajtów
Kolejny wbudowany Mathematica został pokonany przez język golfowy bez wbudowanego.
źródło
Galaretka , 6 bajtów
Wejście 100 kończy lokalnie w 500 ms. Wypróbuj online!
Jak to działa
źródło
+¡1
wbudowane n-te Fibonacciego i+С1
czy pierwsze n liczb Fibonacciego?Właściwie 4 bajty
Uruchamia wejście 100 w ciągu 0,2 sekundy. Kod:
Wyjaśnienie:
Wykorzystuje kodowanie CP-437 . Wypróbuj online! .
źródło
Brainfuck,
11981067817770741657611603Bez kompresji, z komentarzami:
Wypróbuj online!
Czas działania dla n = 100 jest krótszy niż 1 sekunda w przypadku tłumacza online (około 0,2 s lokalnie przy użyciu mojego własnego tłumacza). Maksymalne wejście to 255, ale wymagałoby od interpretera obsługi ~ 54000 komórek (interpreter online wydaje się owijać na 64k).
Zmień dziennik
Oszczędność około 130 bajtów dzięki lepszemu wyodrębnieniu bieżącej cyfry do pomnożenia przez i poprzez połączenie dodawania i przenoszenia w jednym przejściu. Wydaje się również, że jest nieco szybszy.
Zapisano kolejne 250 bajtów. Udało mi się zredukować swoją tabliczkę mnożenia o dwie komórki, co oszczędza bajty prawie wszędzie, ponieważ nie muszę do tej pory przesuwać się między cyframi. Zrzuciłem również przeniesienie po pomnożeniu przez cyfrę i zamiast tego wykonałem pełne przeniesienie, dodając do sumy bieżącej.
Pokroiłem kolejne 50, ponownie z lepszym wyodrębnieniem bieżącej cyfry, aby ją pomnożyć, po prostu nie przesuwając jej do przodu pierwszej iteracji i pracując od tego, gdzie ona jest. Kilka mikrooptymalizacji dalej stanowi około ~ 10 bajtów.
30 innych już nie ma. Oznaczanie cyfr, które zostały już zajęte przez 0 zamiast 1, ułatwia ich lokalizację. Sprawia również, że sprawdzenie, czy pętla mnożenia zakończyła się nieco łatwiej.
Zmniejszyłem notatnik o kolejną komórkę, dla jeszcze 80 bajtów. Zrobiłem to, łącząc znacznik dla poprzedniego produktu i bieżącej sumy bieżącej, co zmniejsza przesunięcia między przerwami i ułatwia księgowanie.
Uratowałem kolejne 50, eliminując jeszcze jedną komórkę, ponownie wykorzystując znacznik cyfr Fibonacciego, aby oznaczyć również ostatnią cyfrę. Byłem także w stanie scalić pętlę, aby przesunąć poprzednie sumy za pomocą cyfrowej pętli mnożenia.
Zapisano 8 bajtów podczas analizowania danych wejściowych. Ups
źródło
Python, 45 bajtów
Dane wejściowe są pobierane ze standardowego wejścia. Dane wyjściowe dla n = 100 kończą się zbyt szybko, aby dokładnie określić czas. n = 1000 zajmuje około 1s.
Przykładowe użycie
źródło
Haskell
4129 bajtów1 + 11 bajtów zapisanych przez uwagi @ Laikoni.
1
,f
I!!
są oddzielne tokeny. Pierwsze linie definiują sekwencję Fibonacciego, druga to funkcja, która oblicza sekwencję Fibonacciego i zwraca n-ty dla danego n. Zaczyna drukować cyfry niemal natychmiast, nawet dla n = 1000.źródło
(scanl(*)1f!!)
.f=1:scanl(+)1f
42+
jako funkcję, która dodaje 42? Nie powinieneś, ponieważ jest to niedokończone wyrażenie. Ale w Haskell możemy dodać nawiasy i uzyskać sekcję(42+)
, sposób na napisanie funkcji\n->42+n
. Tutaj jest tak samo, tylko z!!
(operatorem binarnej poprawki dla indeksowania) zamiast+
i bardziej skomplikowanym pierwszym operandem.Python 2, 39 bajtów
Przetestuj na Ideone .
źródło
True
w niektórych przypadkach zwraca .True
dane wejściowe 0 , co nie jest dodatnie.J,
1716 bajtów1 bajt jest golfowany z jeszcze lepszym rozwiązaniem o mile.
Pomysł jest taki sam jak oryginał, ale zamiast formować matrycę do działania na mniejszych przekątnych, tworzymy przekątne w locie.
Oryginalny
Aby uzyskać pierwsze n fibonomials:
Czytanie od prawej do lewej ...
Utwórz tablicę kolejnych liczb całkowitych (
i.
) do określonej, z tej tablicy utwórz tabelę (/~
) współczynników dwumianowych (!
) obliczonych z każdej pary w tablicy, ta tabela jest trójkątem Pascala umieszczonym na koniec pierwszego rzędu i wszystkie elementy pod główną przekątną wynoszą 0, na szczęście za wdrożenie!
. Jeśli zsumujesz (+/
) wszystkie drobne przekątne (/.
), otrzymasz liczby Fibonacciego, ale musisz wziąć ({.
) tyle pierwszych elementów z wynikowej tablicy, ile długość (#
) samej tabeli. Następnie iloczyn (*/
) zastosowany do kolejnych prefiksów (\
) tablicy daje pożądaną sekwencję fonografów.Jeśli chcesz, możesz wziąć tylko ostatni, używając 2 dodatkowych bajtów ({:
), ale pomyślałem, że wyświetlanie ich wszystkich nie jest grzechem:)
.NB. the previous code block is not a J function
.W przypadku dużych liczb w J używasz
x
na końcu:Program działa na średnich 0.11s .
źródło
[:*/+/@(!|.)\@i.
użycie 16 bajtów. Tworzy te same współczynniki dwumianowe wzdłuż tabeli, którą generujesz, z!/~
wyjątkiem tego, że tworzy to, przyjmując prefiksyi.
.Pyth, 13 bajtów
Demonstracja
Wykorzystuje to sprytną, nietypową sztuczkę. Pięć znaków (
u*G ... Q1
) mówi, że wynik jest iloczynem wielu liczb. Reszta kodu generuje liczby.=[sZhZ)
aktualizuje zmiennąZ
do listy[s(Z), h(Z)]
. Następnies
sumuje tę listę do pomnożenia.Z
jest początkowo 0.s
, na ints, jest funkcją tożsamości.h
, na jego jest+ 1
funkcja. Tak więc przy pierwszej iteracjiZ
staje się[0, 1]
.s
na listach jest funkcja sumowania, jak wspomniano powyżej.h
jest funkcją głowy. Więc druga iteracja jest[1, 0]
.Oto lista:
Te sumy są mnożone, aby dać wynik.
źródło
Mathematica
2524 bajtyDzięki dzięki Martinowi Enderowi.
Czas: 63 mikrosekundy.
źródło
1##&@@Fibonacci~Array~#&
Galaretka, 8 bajtów
Moje pierwsze zgłoszenie w Galaretce. Nie jest tak krótki jak odpowiedź @Dennis , ale ma tylko 2 bajty dłużej przy użyciu innej metody.
Lokalnie wymaga około 400 ms w porównaniu do 380 ms z wersją @Dennis dla n = 100.
Wypróbuj online!
Wyjaśnienie
źródło
PARI / GP, 29 bajtów
Lub alternatywnie:
źródło
R,
9996787666 bajtówTa odpowiedź używa Formuły Bineta , a także
prod(x)
funkcji. Ponieważ R nie ma wbudowanejPhi
wartości, sam ją zdefiniowałem:Działa poniżej 5 sekund, ale R daje
Inf
odpowiedź na te duże liczby ...Nie golfowany:
-2 bajty dzięki @Cyoce!
Och, kocham tę stronę! -10 bajtów dzięki @ user5957401
źródło
sqrt(5)
zmiennąN
raz, możesz po prostu wywołać skanowanie wewnątrz1:N
bitu. tjfor(n in 1:scan())
. Możesz także zapisać kilka znaków, używając po prostu*
zamiastprod()
funkcji w pętli for. Twoja pętla for ma tylko jedną linię, więc nie potrzebujesz również nawiasów klamrowych.function(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
R,
82,53, 49 bajtów (48 bajtów z innym stylem wprowadzania)Jeśli możemy po prostu poprzedzić kod liczbą wejściową, otrzymamy 48 bajtów
EDYCJA: Nowy kod. Oryginał znajduje się poniżej:
a(100)
Jednak nie zwróci niczego innego niż Inf . I nie będzie działać na nic oprócz liczb całkowitych nieujemnych.Nie golfowany:
źródło
Java, 165 bajtów
Gra w golfa:
Jest to kolejny przypadek, gdy
BigInteger
jest wymagany ze względu na dużą liczbę. Udało mi się jednak ograniczyć tekstBigInteger
do minimum, zmniejszając jego rozmiar. Porównałem również z importem statycznym, dzięki czemu całkowita długość była dłuższa.Ten program śledzi trzy liczby w tablicy. Pierwsze dwie to dwie poprzednie liczby Fibonacciego. Trzecia to skumulowana wartość. Pętla rozpoczyna się od obliczenia następnej wartości i zapisania jej w naprzemiennych indeksach tablicy (0, 1, 0, 1, ...). Pozwala to uniknąć konieczności zmiany wartości przy kosztownych (pod względem wielkości źródła) operacjach przypisywania. Następnie chwyć tę nową wartość i pomnóż ją w akumulatorze.
Unikając obiektów tymczasowych i ograniczając pętlę do dwóch operatorów przypisania, udało mi się wycisnąć sporo bajtów.
Nie golfowany:
Wyjście programu:
źródło
Brachylog , 31 bajtów
Wypróbuj online!
źródło
Rubin, 39 bajtów
źródło
JavaScript (ES6),
5139 bajtówImplementacja rekurencyjna (39 bajtów)
Oryginalna implementacja (51 bajtów)
Uwaga: Rozpoczyna błędy zaokrąglania dla liczby Fibonacciego 16, 100 to po prostu Nieskończoność, działa w czasie, który wydaje się <1 sekunda.
źródło
n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)
tylko po to, aby odkryć, że policzyłeś to,f=
co nie jest wymagane, oszczędzając ci 2 bajty.DC (smak GNU lub OpenBSD) , 36 bajtów
Plik
A003266-v2.dc
:(brak końcowego nowego wiersza)
... teraz wynik jest przechowywany na stosie zamiast używania nazwanego rejestru (jest
Y
w wersji 1).r
Polecenie nie jest dostępne w oryginaledc
(patrz strona RosettaCode za Dc ).Biegać:
Próbuję wyjaśnić:
tos
jest zawartością góry stosu bez jego usuwania.nos
jest elementem poniżejtos
.DC , 41 bajtów
... prosto, bez sztuczek:
Plik
A003266-v1.dc
:(brak końcowego nowego wiersza)
Biegać:
źródło
dc
kodu jest zdecydowanie łatwiejsze niż wyjaśnianie ...n
przedmioty na inny stos. Na razie jednak wciąż nie wiem, jak skompilowaćdc
ze źródła. : /C #
11010910710310194 bajtówWyjaśnienie
Algorytm iteracyjnego Fib
źródło
Brain-Flak , 54 bajty
Wypróbuj online!
Mnożenie w Brain-Flak zajmuje dużo czasu przy dużych nakładach. Po prostu pomnożenie F 100 przez F 99 za pomocą ogólnego algorytmu mnożenia zajęłoby miliardy lat.
Na szczęście istnieje szybszy sposób. Uogólniona sekwencja Fibonacciego rozpoczynająca się od
(k, 0)
wygeneruje te same warunki, co zwykła sekwencja, pomnożona przezk
. Korzystając z tej obserwacji, Brain-Flak może pomnożyć liczbę Fibonacciego tak samo łatwo, jak może wygenerować liczby Fibonacciego.Jeśli stos składa się z
-n
dwiema liczbami,{({}()<([({})]({}{}))>)}{}{}
obliczan
iteracje uogólnionej sekwencji Fibonacciego i odrzuca wszystkie do ostatniej. Reszta programu po prostu ustawia wartość początkową 1 i wykonuje pętle dla wszystkich liczb w zakresien...1
.Oto ten sam algorytm w innych językach dostarczonych przez tego tłumacza:
Brain-Flak Classic, 52 bajty
Wypróbuj online!
Brain-Flueue, 58 bajtów
Wypróbuj online!
Mini-Flak, 62 bajty
Wypróbuj online!
źródło
Mathematica -
3226 bajtów@MartinEnder pokroił 6 bajtów!
źródło
GAP 28 bajtów
Nie wiedziałem wcześniej, że GAP ma
Fibonacci
wbudowaną funkcję .źródło
Ruby, 85 bajtów
Okazało się dobrze, ale prawdopodobnie istnieje krótsze rozwiązanie.
Szybkie obliczenia Fibonnaci pobrane stąd: link
Sprawdź to tutaj
źródło
Julia, 36 bajtów
źródło
Brain-Flak ,
110104100 bajtówWypróbuj online!
Wyjaśnienie
Najpierw uruchamiamy ulepszoną wersję generatora sekwencji Fibonacciego - dr Green Eggs i Iron Man
Następnie, gdy na stosie znajduje się więcej niż jeden przedmiot
pomnóż dwa najlepsze elementy
i pop dodatkowe zero
źródło
Clojure, 70 bajtów
Clojure nie jest dobrym językiem do gry w golfa kodowego. No cóż.
Wypróbuj na http://tryclj.com .
źródło
Dalej, 55 bajtów
Stosuje iteracyjne podejście, oparte na mojej odpowiedzi Fibonacciego w Forth. Wyniki przelewają się arytmetycznie dla
n > 10
. Odpowiedź nie uwzględnia wielkości liter.Wypróbuj online
źródło
Szybki, 68 bajtów
źródło
JavaScript (ES6), 46 bajtów
Wykorzystuje zmienne rekurencyjne i akumulatorowe. Błędy zaokrąglania zaczynają się od
f(16)
.źródło