Fibonacciego-orial

36

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 100musi 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

Referencje

Leaky Nun
źródło
Związane .
Leaky Nun
1
@LuisMendo Suma fibonacci jest ... zgadłeś, fibonacci. Cóż, minus jeden.
Leaky Nun
2
@LeakyNun Obecnie odpowiedź JavaScript wypełnia tylko przypadki testowe do 15, ponieważ JavaScript nie może poprawnie porównywać (ani manipulować) liczbami przekraczającymi 2 ^ 53 - 1. Jest to prawdopodobnie podobne w przypadku wielu zgłoszeń, ponieważ większość języków nie obsługuje tak duże liczby
MayorMonty
1
Co rozumiesz przez „rozsądny komputer”?
Erik the Outgolfer
2
-1, ponieważ wydaje się, że jest to kilka wyzwań połączonych razem (zasięg, fibonacci każdego, silnia) bez żadnych szczególnie interesujących skrótów.
Esolanging Fruit

Odpowiedzi:

63

Mathematica, 10 bajtów

Fibonorial

Kolejny wbudowany Mathematica został pokonany przez język golfowy bez wbudowanego.

Martin Ender
źródło
49
Ja… c-co… dlaczego, Mathematica ?!
Lynn
3
Zapomniałem, że ta funkcja nawet istniała!
LegionMammal978
3
@Lynn Reguła 35 : Jeśli istnieje, istnieje jej funkcja Mathematica;)
Rozpad Beta
9
@BetaDecay Myślałem, że ustaliliśmy, że jest to reguła 110 .
Martin Ender
1
Nie, reguła 110 jest czymś zupełnie innym. Chociaż jestem pewien, że Mathematica też ma do tego wbudowaną funkcję.
AdmBorkBork,
27

Galaretka , 6 bajtów

+С1ḊP

Wejście 100 kończy lokalnie w 500 ms. Wypróbuj online!

Jak to działa

+С1ḊP  Niladic link. No input.
        Since the link doesn't start with a nilad, the argument 0 is used.

   1    Yield 1.
+       Add the left and right argument.
 С     Read a number n from STDIN.
        Repeatedly call the dyadic link +, updating the right argument with
        the value of the left one, and the left one with the return value.
        Collect all values of the left argument into an array.
    Ḋ   Dequeue; discard the first Fibonacci number (0).
     P  Product; multiply the remaining ones.
Dennis
źródło
Czyli nie jest +¡1wbudowane n-te Fibonacciego i +С1czy pierwsze n liczb Fibonacciego?
caird coinheringaahing 11.10.17
@cairdcoinheringaahing Pretty much.
Dennis
Myślałem, że jest wbudowana funkcja Fibonacciego?
MilkyWay90
21

Właściwie 4 bajty

Uruchamia wejście 100 w ciągu 0,2 sekundy. Kod:

R♂Fπ

Wyjaśnienie:

R     # Get the range [1, ..., input].
 ♂F   # Map over the array with the fibonacci command.
   π  # Take the product.

Wykorzystuje kodowanie CP-437 . Wypróbuj online! .

Adnan
źródło
1
To odpowiednie narzędzie do pracy :) Dzięki ulepszeniom funkcji Fibonacciego, które Leaky Nun zrobiła jakiś czas temu, 100 przypadków testowych działa na TIO w 0,1 sekundy .
Mego
16

Brainfuck, 1198 1067 817 770 741 657 611 603

,[>++++++[-<-------->]<<[->++++++++++<]>>,]>+>+>>+>+<<<<<<[->>>[[-]
<[->+<]>>[-<+<+>>]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->
[-]>>>>>>+>+<<<<<<<<[->+<]]]]]]]]]]]+>>>>>>>>]<<<<<<<<[->[-<+<<+>>>
]<[->+<]>>>[<<<<<[->>>>>>>>+<<<<<<<<]>>>>>>>>>>>>>]<<<<<<<<[->>>[-<
<<<<<<<+>>>>[->+>>+<<<]>[-<+>]>>>]<<[->>>>>>>+>+<<<<<<<<]<+<<<<<<<<
]>>>[-]>>>>>[[-]>[->+<]>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<
+>[->>>>>>+>+<<<<<<<<[-]]]]]]]]]]>]<<[<]+>>>>>>>>]<<<<<<<<[<<<<<<<<
]>>>>>[>>>>>>>>]+<<<<<<<<]>>>>>>>>>>>[<[-]>>[-<<+>>]>>>>>>>]<<<<<<<
<[<<<<<<<<]>>]>>>>>>[>>>>>>>>]<<<<<<<<[+++++[-<++++++++>]<.<<<<<<<]

Bez kompresji, z komentarzami:

# parse input (max 255)
,[>++++++[-<-------->]<<[->++++++++++<]>>,]
>+>+>>+>+<<<<<<
[->>>
  # compute next fibonacci number
  [[-]<
    [->+<]>>
    [-<+<+>>]<
    # perform carries
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<
      [->[-]>>>>>>+>+<<<<<<<<[->+<]]
    ]]]]]]]]]+>>>>>>>>
  ]<<<<<<<<
  # multiplication
  [->
    # extract next digit of F_n (most significant first)
    [-<+<<+>>>]<
    [->+<]>>>
    # move back to the end
    [<<<<<
      [->>>>>>>>+<<<<<<<<]>>>>>>>>>>>>>
    ]<<<<<<<<
    # digit wise multiplication (shifting current digit)
    [->>>
      [-<<<<<<<<+>>>>
        [->+>>+<<<]>
        [-<+>]>>>
      ]<<
      # shift previous total over one gap (in effect multiplying by 10)
      [->>>>>>>+>+<<<<<<<<]<+<<<<<<<<
    ]>>>[-]>>>>>
    # add product to total
    [[-]>
      [->+<]>
      # perform carries
      [-<+>
        [-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>
          [->>>>>>+>+<<<<<<<<[-]]
        ]]]]]]]]>
      ]<<[<]+>>>>>>>>
    ]<<<<<<<<
    [<<<<<<<<]>>>>>
    [>>>>>>>>]+<<<<<<<<
  ]>>>>>>>>>>>
  # overwrite previous product
  [<[-]>>
    [-<<+>>]>>>>>>>
  ]<<<<<<<<
  [<<<<<<<<]>>
]>>>>>>
# output product
[>>>>>>>>]<<<<<<<<
[+++++
  [-<++++++++>]<.<<<<<<<
]

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

primo
źródło
14

Python, 45 bajtów

a=b=o=1
exec"o*=a;a,b=b,a+b;"*input()
print o

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

$ echo 10 | python fib-orial.py
122522400

$ echo 100 | python fib-orial.py
3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
primo
źródło
13

Haskell 41 29 bajtów

1 + 11 bajtów zapisanych przez uwagi @ Laikoni.

f=1:scanl(+)1f
(scanl(*)1f!!)

1, fI !!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.

Christian Sievers
źródło
1
Możesz pozbyć się przestrzeni (scanl(*)1f!!).
Laikoni
2
I jest krótszy generator Fibonacci tutaj :f=1:scanl(+)1f
Laikoni
@Laikoni To niesamowite, dzięki!
Christian Sievers
2
@WillNess Myślę, że jestem uzasadniony nie tylko tym, co robią inni użytkownicy, ale także meta.codegolf.stackexchange.com/questions/2419/... i meta.codegolf.stackexchange.com/questions/9031/... (ale istnieje o wiele więcej i nie przeczytałem wszystkich)
Christian Sievers
1
@flawr Czy zaakceptowałbyś 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.
Christian Sievers
11

Python 2, 39 bajtów

f=lambda n,a=1,b=1:n<1or a*f(n-1,b,a+b)

Przetestuj na Ideone .

Dennis
źródło
Możesz chcieć określić, że Truew niektórych przypadkach zwraca .
Leaky Nun
5
Zwróciłoby to tylko Truedane wejściowe 0 , co nie jest dodatnie.
Dennis
6

J, 17 16 bajtów

1 bajt jest golfowany z jeszcze lepszym rozwiązaniem o mile.

[:*/+/@(!|.)\@i.

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:

*/\(#{.+//.)!/~i.

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.

   {:*/\(#{.+//.)!/~i. 10
122522400

W przypadku dużych liczb w J używasz xna końcu:

   {:*/\(#{.+//.)!/~i. 100x
3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225...

Program działa na średnich 0.11s .

   100 timex '{:*/\(#{.+//.)!/~i.100x'
0.112124
Dan Oak
źródło
1
Alternatywą, która jest funkcją jest [:*/+/@(!|.)\@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 prefiksy i..
mile
4

Pyth, 13 bajtów

u*Gs=[sZhZ)Q1

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ą Zdo listy [s(Z), h(Z)]. Następnie ssumuje tę listę do pomnożenia.

Zjest początkowo 0. s, na ints, jest funkcją tożsamości. h, na jego jest + 1funkcja. Tak więc przy pierwszej iteracji Zstaje się [0, 1]. sna listach jest funkcja sumowania, jak wspomniano powyżej. hjest funkcją głowy. Więc druga iteracja jest [1, 0].

Oto lista:

Iter  Z          Sum
0     0          Not used
1     [0, 1]     1
2     [1, 0]     1
3     [1, 1]     2
4     [2, 1]     3
5     [3, 2]     5

Te sumy są mnożone, aby dać wynik.

isaacg
źródło
4

Mathematica 25 24 bajty

Dzięki dzięki Martinowi Enderowi.

1##&@@Fibonacci@Range@#&

1##&@@Fibonacci@Range@#&@100

Czas: 63 mikrosekundy.

{0.000063, 
3371601853146468125386964065447576689828006172937411310662486977801540
6711385898686165008341900290675836651822917015531720110825745874313823
1009903039430687777564739516714333248356092511296002464445971530050748
1235056111434293619038347456390454209587101225261757371666449068625033
9995735521655245297254676280601708866020010771376138030271586483293355
0772869860576999281875676563330531852996518618404399969665040724619325
7877568825245646129366994079739720698147440310773871269639752334356493
6789134243905645353892122400388956268116279491329780860702550826683922
9003714114129148483959669418215206272639036409444764264391237153249138
8089634845995941928089653751672688740718152064107169357399466473375804
9722605947689699525073466941890502338235963164675705844341280523988912
2373033501909297493561702963891935828612435071136036127915741683742890
4150054292406756317837582840596331363581207781793070936765786629772999
8328572573496960944166162599743042087569978353607028409125185326833249
36435856348020736000000000000000000000000}
DavidC
źródło
Na przemian z tą samą liczbą bajtów:1##&@@Fibonacci~Array~#&
Greg Martin
4

Galaretka, 8 bajtów

RḶUc$S€P

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ḶUc$S€P  Input: n
R         Generate the range [1, 2, ..., n]
          For each value x in that range
 Ḷ          Create another range [0, 1, ..., x-1]
  U         Reverse that list
   c        Compute the binomial coefficients between each pair of values
    $       Bind the last two links (Uc) as a monad
     S€   Sum each list of binomial coefficients
          This will give the first n Fibonacci numbers
       P  Take the product of those to compute the nth Fibonacci-orial
mile
źródło
3

PARI / GP, 29 bajtów

f=n->prod(i=1,n,fibonacci(i))

Lub alternatywnie:

f=n->prod(i=a=!b=0,n,b=a+a=b)
primo
źródło
3

R, 99 96 78 76 66 bajtów

Ta odpowiedź używa Formuły Bineta , a także prod(x)funkcji. Ponieważ R nie ma wbudowanej Phiwartości, sam ją zdefiniowałem:

p=(1+sqrt(5))/2;x=1;for(n in 1:scan())x=x*(p^n-(-1/p)^n)/sqrt(5);x

Działa poniżej 5 sekund, ale R daje Infodpowiedź na te duże liczby ...

Nie golfowany:

r=sqrt(5)
p=(1+r)/2 
x=1
for(n in 1:scan())        
    x=x*(p^n-(-1/p)^n)/r    
x

-2 bajty dzięki @Cyoce!
Och, kocham tę stronę! -10 bajtów dzięki @ user5957401

Frédéric
źródło
Być może uda się trochę zaoszczędzić, przechowując sqrt(5)zmienną
Cyoce,
ponieważ używasz tylko Nraz, możesz po prostu wywołać skanowanie wewnątrz 1:Nbitu. tj for(n in 1:scan()). Możesz także zapisać kilka znaków, używając po prostu *zamiast prod()funkcji w pętli for. Twoja pętla for ma tylko jedną linię, więc nie potrzebujesz również nawiasów klamrowych.
user5957401,
Fajny pomysł na użycie formuły Bineta. W twoim duchu, ale tylko 53 bajty tofunction(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
Michael M
3

R, 82 , 53 , 49 bajtów (48 bajtów z innym stylem wprowadzania)

b=d=1;a=0;for(i in 1:scan()){d=d*b;b=a+b;a=b-a};d

Jeśli możemy po prostu poprzedzić kod liczbą wejściową, otrzymamy 48 bajtów

->n;b=d=1;a=0;for(i in 1:n){d=d*b;b=a+b;a=b-a};d

EDYCJA: Nowy kod. Oryginał znajduje się poniżej:

a=function(n)ifelse(n<3,1,{v=c(1,1,3:n);for(i in 3:n)v[i]=v[i-1]+v[i-2];prod(v)})

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:

a=function(n){
   if(n<3) return(1)
   v=c(1,1,3:n)
   for(i in 3:n)
       v[i]=v[i-1]+v[i-2]
   prod(v)
}
użytkownik5957401
źródło
3

Java, 165 bajtów

Gra w golfa:

BigInteger f(int n){BigInteger[]a={BigInteger.ZERO,BigInteger.ONE,BigInteger.ONE};for(int i=0;i<n;){a[++i%2]=a[0].add(a[1]);a[2]=a[2].multiply(a[i%2]);}return a[2];}

Jest to kolejny przypadek, gdy BigIntegerjest wymagany ze względu na dużą liczbę. Udało mi się jednak ograniczyć tekst BigIntegerdo 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:

import java.math.BigInteger;

public class Fibonacci_orial {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "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" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new Fibonacci_orial().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  BigInteger f(int n) {
    BigInteger[] a = { BigInteger.ZERO, BigInteger.ONE, BigInteger.ONE };
    for (int i = 0; i < n;) {
      a[++i % 2] = a[0].add(a[1]);
      a[2] = a[2].multiply(a[i % 2]);
    }
    return a[2];
  }
  // End golf

}

Wyjście programu:

Input: 1
Expected: 1
Actual:   1

Input: 2
Expected: 1
Actual:   1

Input: 3
Expected: 2
Actual:   2

Input: 4
Expected: 6
Actual:   6

Input: 5
Expected: 30
Actual:   30

Input: 6
Expected: 240
Actual:   240

Input: 7
Expected: 3120
Actual:   3120

Input: 8
Expected: 65520
Actual:   65520

Input: 9
Expected: 2227680
Actual:   2227680

Input: 10
Expected: 122522400
Actual:   122522400

Input: 11
Expected: 10904493600
Actual:   10904493600

Input: 12
Expected: 1570247078400
Actual:   1570247078400

Input: 13
Expected: 365867569267200
Actual:   365867569267200

Input: 14
Expected: 137932073613734400
Actual:   137932073613734400

Input: 15
Expected: 84138564904377984000
Actual:   84138564904377984000

Input: 16
Expected: 83044763560621070208000
Actual:   83044763560621070208000

Input: 17
Expected: 132622487406311849122176000
Actual:   132622487406311849122176000

Input: 18
Expected: 342696507457909818131702784000
Actual:   342696507457909818131702784000

Input: 19
Expected: 1432814097681520949608649339904000
Actual:   1432814097681520949608649339904000

Input: 20
Expected: 9692987370815489224102512784450560000
Actual:   9692987370815489224102512784450560000

Input: 100
Expected: 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Actual:   3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000

źródło
2

Rubin, 39 bajtów

->n{f=i=b=1;n.times{f,i,b=i,f+i,b*f};b}
Lynn
źródło
36: -> n {f = i = b = 1; n. Razy {b * = f; i = f + f = i}; b}
GB
2

JavaScript (ES6), 51 39 bajtów

Implementacja rekurencyjna (39 bajtów)

f=(n,a=p=i=b=1)=>++i<n?f(n,b,p*=b+=a):p

Oryginalna implementacja (51 bajtów)

n=>{for(i=a=b=p=1;++i<n;){c=a;a=b;p*=b+=c}return p}

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.

Pandacoder
źródło
Zrobiłem alternatywną 53-bajtową wersję 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.
Neil
Uczciwy punkt. Moje uzasadnienie było takie, że można je było wywołać i nadawać się do wielokrotnego użytku, a nie tylko.
Pandacoder
Jasne, ale jeśli ktoś chce go ponownie użyć, nadal ma możliwość nadania mu nazwy.
Neil
@Neil Cóż, teraz poszedłem i ponownie go zaimplementowałem, a teraz f = jest obowiązkowe, bo inaczej nie można go wykonać. : D
Pandacoder
Przynajmniej poprawiłeś liczbę bajtów dla oryginalnej implementacji.
Neil
2

DC (smak GNU lub OpenBSD) , 36 bajtów

Plik A003266-v2.dc:

0sA1sB1?[1-d0<LrlBdlA+sBdsA*r]dsLxrp

(brak końcowego nowego wiersza)

... teraz wynik jest przechowywany na stosie zamiast używania nazwanego rejestru (jest Yw wersji 1). rPolecenie nie jest dostępne w oryginale dc(patrz strona RosettaCode za Dc ).

Biegać:

$ time dc -f A003266-v2.dc <<< 100
337160185314646812538696406544757668982800617293741131066248697780154\
067113858986861650083419002906758366518229170155317201108257458743138\
231009903039430687777564739516714333248356092511296002464445971530050\
748123505611143429361903834745639045420958710122526175737166644906862\
503399957355216552452972546762806017088660200107713761380302715864832\
933550772869860576999281875676563330531852996518618404399969665040724\
619325787756882524564612936699407973972069814744031077387126963975233\
435649367891342439056453538921224003889562681162794913297808607025508\
266839229003714114129148483959669418215206272639036409444764264391237\
153249138808963484599594192808965375167268874071815206410716935739946\
647337580497226059476896995250734669418905023382359631646757058443412\
805239889122373033501909297493561702963891935828612435071136036127915\
741683742890415005429240675631783758284059633136358120778179307093676\
578662977299983285725734969609441661625997430420875699783536070284091\
2518532683324936435856348020736000000000000000000000000

real    0m0.005s
user    0m0.004s
sys     0m0.000s

Próbuję wyjaśnić:

tosjest zawartością góry stosu bez jego usuwania.
nosjest elementem poniżej tos.

0 sA # push(0) ; A=pop()
1 sB # push(1) ; B=pop()
1    # push(1)
     # this stack position will incrementally hold the product
?    # push( get user input and evaluate it )
[    # start string
 1-  # push(pop()-1)
 d   # push(tos)
 0   # push(0)
 <L  # if pop() < pop() then evaluate contents of register L
 r   # exchange tos and nos
     # now nos is the loop counter
     # and tos is the bucket for the product of the fibonacci numbers
 lB  # push(B)
 d   # push(tos)
 lA  # push(A)
 +   # push(pop()+pop())
     # now tos is A+B, nos still is B 
 sB  # B=pop()
     # completes B=A+B
 d   # push(tos)
 sA  # A=pop()
     # completes B=A
     # tos (duplicated new A from above) is the next fibonacci number
 *   # push(nos*tos)
     # tos now is the product of all fibonacci numbers calculated so far
 r   # exchange tos and nos
     # now tos is the loop counter, nos is the product bucket
]    # end string and push it
d    # push(tos)
sL   # L=pop()
x    # evaluate(pop())
r    # exchange tos and nos
     # nos now is the former loop counter
     # tos now is the complete product. \o/
p    # print(tos)
     # this does not pop() but who cares? :-P

DC , 41 bajtów

... prosto, bez sztuczek:

Plik A003266-v1.dc:

0sA1sB1sY?[1-d0<LlBdlA+sBdsAlY*sY]dsLxlYp

(brak końcowego nowego wiersza)

Biegać:

$ for i in $(seq 4) ; do dc -f A003266-v1.dc <<< $i ; done
1
1
2
6
$ time dc -f A003266-v1.dc <<< 100
337160185314646812538696406544757668982800617293741131066248697780154\
067113858986861650083419002906758366518229170155317201108257458743138\
231009903039430687777564739516714333248356092511296002464445971530050\
748123505611143429361903834745639045420958710122526175737166644906862\
503399957355216552452972546762806017088660200107713761380302715864832\
933550772869860576999281875676563330531852996518618404399969665040724\
619325787756882524564612936699407973972069814744031077387126963975233\
435649367891342439056453538921224003889562681162794913297808607025508\
266839229003714114129148483959669418215206272639036409444764264391237\
153249138808963484599594192808965375167268874071815206410716935739946\
647337580497226059476896995250734669418905023382359631646757058443412\
805239889122373033501909297493561702963891935828612435071136036127915\
741683742890415005429240675631783758284059633136358120778179307093676\
578662977299983285725734969609441661625997430420875699783536070284091\
2518532683324936435856348020736000000000000000000000000

real    0m0.006s
user    0m0.004s
sys     0m0.004s

źródło
1
* westchnienie! * ... pisanie dckodu jest zdecydowanie łatwiejsze niż wyjaśnianie ...
1
Tak, naprawdę potrzebujemy IDE z jakimś szalonym gadżetem do wizualizacji na wielu stosach ... byłoby miło.
Joe
1
Mam kilka pomysłów, które należy dodać jako nowe polecenia, ale wydaje się, że największy wpływ ma: Dodaj polecenie „zmień domyślny stos”. ;-)
2
... lub zamień domyślny stos na nazwany rejestr. To spowodowałoby więcej węzłów w mózgach użytkowników, ale nie potrzebowałby domyślnego stosu, aby mieć nazwę ...] :-)
1
Tak, to na pewno byłoby przydatne! Chciałbym również wyczyścić pojedynczy przedmiot, obrócić przedmioty, które nie znajdują się na szczycie stosu, a może przenieść jednocześnie najwyższe nprzedmioty na inny stos. Na razie jednak wciąż nie wiem, jak skompilować dcze źródła. : /
Joe
2

C # 110 109 107 103 101 94 bajtów

using i=System.Numerics.BigInteger;i f(i n){i a=0,b=1,x=1;for(;n-->0;)x*=a=(b+=a)-a;return x;}

Wyjaśnienie

//Aliasing BigInteger saves a few bytes
using i=System.Numerics.BigInteger;

//Since BigInteger has an implicit from int we can also change the input
//and save two more bytes.
i f(i n)
{
    //using an alternative iterative algorithm (link to source below) to cut out the temp variable
    //b is next iteration, a is current iteration, and x is the running product
    i a = 0, b = 1, x = 1; 

    //post decrement n down to zero instead of creating a loop variable
    for (; n-- > 0;)

        //The bracket portion sets the next iteration             
        //get the current iteration and update our running product
        x *= a = (b += a) - a;

    return x;
}

Algorytm iteracyjnego Fib

JustinM - Przywróć Monikę
źródło
Biorąc pod uwagę, że działało to o wiele lepiej, niż się spodziewałem, chciałem znaleźć maksymalny N, który powróciłby w ciągu 5 sekund, wyszedłem z 1540, co daje liczbę o długości 247441 cyfr.
JustinM - Przywróć Monikę
Imponujący. Jak długo trwa 1541 z ciekawości?
Pandacoder,
@ Pandacoder Dzięki ostatniej zmianie algorytmu stało się znacznie szybsze. 1541 w 755 ms, więc znajdę teraz nową sub 5 max.
JustinM - Przywróć Monikę
@ Pandacoder, więc czas działania różni się o około 100 ms, ale 2565 wydaje się średnio około 5 sekund
JustinM - Przywróć Monikę
Jak długo jest na to liczba?
Pandacoder,
2

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 przez k. 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 -ndwiema liczbami, {({}()<([({})]({}{}))>)}{}{}oblicza niteracje 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 zakresie n...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!

Nitrodon
źródło
1

Mathematica - 32 26 bajtów

Fibonacci@i~Product~{i,#}&

@MartinEnder pokroił 6 bajtów!

Yytsi
źródło
1

GAP 28 bajtów

Nie wiedziałem wcześniej, że GAP ma Fibonacciwbudowaną funkcję .

n->Product([1..n],Fibonacci)
Christian Sievers
źródło
Czy możesz połączyć się z GAP? Nie mam pojęcia co to jest.
Leaky Nun
Och, jasne (ale nie jestem pierwszym, który użył go tutaj ...)
Christian Sievers
1

Ruby, 85 bajtów

g =->x{(1..x).to_a.collect{|y|(0..y).inject([1,0]){|(a,b),_|[b, a+b]}[0]}.inject(:*)}

Okazało się dobrze, ale prawdopodobnie istnieje krótsze rozwiązanie.

Szybkie obliczenia Fibonnaci pobrane stąd: link

Sprawdź to tutaj

Seims
źródło
1

Julia, 36 bajtów

!x=[([1 1;1 0]^n)[2]for n=1:x]|>prod
Lynn
źródło
1

Brain-Flak , 110 104 100 bajtów

Wypró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

{}
Kreator pszenicy
źródło
1
Niestety, myślę, że jest to nieprawidłowe, ponieważ wejście zajmuje 25 sekund. Algorytm jest bardzo nieefektywny (podobnie jak język), więc obliczenie go dla 100 prawdopodobnie zajęłoby godziny.
DJMcMayhem
1

Clojure, 70 bajtów

Clojure nie jest dobrym językiem do gry w golfa kodowego. No cóż.

Wypróbuj na http://tryclj.com .

(last(nth(iterate(fn[[a b r]][b(+ a b)(* r(+ a b))])[0N 1 1])(dec n)))
użytkownik16973
źródło
1

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.

: f >r 1 1 r@ 0 DO 2dup + LOOP 2drop 1 r> 0 DO * LOOP ;

Wypróbuj online

mbomb007
źródło
1

Szybki, 68 bajtów

func f(n:Int,_ a:Int=1,_ b:Int=1)->Int{return n<1 ?1:a*f(n-1,b,a+b)}
Alexander - Przywróć Monikę
źródło
1

JavaScript (ES6), 46 bajtów

f=(n,a=1,b=1,c=i=1)=>n==i?c:f(n,b,a+b,c*b,++i)

Wykorzystuje zmienne rekurencyjne i akumulatorowe. Błędy zaokrąglania zaczynają się od f(16).

cPu1
źródło