Możesz rozłożyć liczbę większą niż 0 jako unikalną sumę dodatnich liczb Fibonacciego. W tym pytaniu robimy to poprzez wielokrotne odejmowanie największej możliwej dodatniej liczby Fibonacciego. Na przykład:

1 = 1
2 = 2
3 = 3
4 = 3 + 1
12 = 8 + 3 + 1
13 = 13
100 = 89 + 8 + 3

Teraz nazywam produkt Fibonacciego tymi samymi listami, co powyżej, ale z dodatkiem zastąpionym mnożeniem. Na przykład f(100) = 89 * 8 * 3 = 2136.

Napisz program lub funkcję, która podając dodatnią liczbę całkowitą n zwraca iloczyn Fibonacciego o tej liczbie.

Przypadki testowe:

1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236

Galaretka , 16 15 bajtów

Rf1+С¤ṪạµÐĿIAP

Niezbyt szybki lub przyjazny dla pamięci, ale wystarczająco wydajny dla wszystkich przypadków testowych. Wypróbuj online!

Jak to działa

Rf1+С¤ṪạµÐĿIAP  Main link. Argument: n (integer)

         µ       Combine the chain to the left into a link.
          ÐĿ     Apply that link until the results are no longer unique.
                 Return the list of unique results.
      ¤            Combine the two links to the left into a niladic chain.
  1                  Set the left (and right) argument to 1.
   +D¡               Apply + to the left and right argument, updating the left
                     argument with the sum, and the right argument with the
                     previous value of the left one. Return the list of results.
                     Repeat this process n times.
                   This yields n + 1 Fibonacci numbers, starting with 1, 2.
R                  Range; map k to [1, ..., k].
 f                 Filter; keep the items in the range that are Fibonacci numbers.
       Ṫ           Tail; yield the last one or 0 if the list is empty.
        ạ          Absolute difference with k.
                   This is the argument of the next iteration.
            I    Compute the increments of the arguments to the loop, yielding
                 the selected Fibonacci numbers (with changed sign).
             A   Apply absolute value to each.
              P  Compute their product.  

Python, 54 bajty

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

Po prostu jakaś dobra stara rekurencja.

Perl, 69 63 + 4 ( -pl61flaga) = 67 bajtów

#!perl -pl61
while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{

Za pomocą:

> echo 42 | perl -pl61e 'while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{'

Nie golfowany:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ = 1 by -l61
    while ($_ != 0) {
        my $n = 1;
        my $m = 1;
        while ($m <= $_) {
            ($n, $m) = ($m, $n + $m);
        }
        $_ -= $n;
        $\ *= $n;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

Ideone .

JavaScript (ES6), 78 42 bajtów

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

Port odpowiedzi @ Sp3000. Oryginalna 78-bajtowa wersja:

f=(n,a=[2,1])=>n>a[0]?f(n,[a[0]+a[1],...a]):a.map(e=>e>n?0:(r*=e,n-=e),r=1)&&r

> <> , 57 bajtów

111\ ;n{/
:@+>:{:})?\$:@@
~{*}:0=?\}>:0${:})?$~:{$-$:1@?$

Oczekuje, że numer wejściowy będzie obecny na stosie podczas uruchamiania programu.

Tworzy sekwencję Fibonacciego ( f0, f1, f2, ..., fn) na stosie, dopóki nie zostanie osiągnięta liczba większa niż liczba wejściowa ( i). Następnie za pomocą produktu ( p) zainicjowanego w celu 1...

while (i != 0)
   if (fn <= i)
      i = i - fn
      p = p * fn
   else
      i = i - 0
      p = p * 1
   discard fn
output p

Wypróbuj online!

Pyth, 28 bajtów

K1WQJ0 .WgQH+Z~JZ1=*KJ=-QJ;K

Myślę, że można grać w golfa znacznie dalej ...

Wypróbuj online!

Pyth, 24 bajty

W=-QeaYh.WgQeH,eZsZ1;*FY

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

Q jest przypisany z numerem wejściowym.

Część h.WgQeH,eZsZ1oblicza największą liczbę Fibonacciego, która jest mniejsza lub równaQ

h.WgQeH,eZsZ1
            1   start with H=Z=1
 .WgQeH         while Q >= end(H):
       ,eZsZ       H=Z=(end(Z), sum(Z))
h               first

Więc jeśli Q = 10generuje liczby / pary:

1 -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8) -> (8,13) -> 8

Reszta kodu oblicza partycję i mnoży liczby razem:

W=-QeaY...;*FY    implicit: Y = empty list
     aY...        add the calculated Fibonacci number to the empty list
    e             take the last element of Y (yes the number we just added)
 =-Q              and update Q with the difference of Q and ^
W         ;       continue until Q == 0
           *FY    multiply all number in Y and print

Istnieje oczywiście wiele krótszych rozwiązań (z naprawdę kiepskimi czasami uruchamiania) *FhfqQsTyeM.u,eNsNQ1.

Haskell, 44 bajty

Yay dla wzajemnej rekurencji:

(a&b)c|c<1=1|b>c=a*f(c-a)|d<-a+b=b&d$c
f=0&1

• a jest poprzednim numerem Fibonacciego
• b jest bieżącą liczbą Fibonacciego
• c jest wejściem
• f jest pożądaną funkcją

Mniej golfa:

(a & b) c | c == 0    = 1
          | c <  b    = a * f (c-a)
          | otherwise = b & (a + b) $ c
f x = (0 & 1) x

Właściwie 22 bajty

W;╗uR♂F;`╜≥`M░M;╜-WXkπ

Wypróbuj online!

Wyjaśnienie:

W;╗uR♂F;`╜≥`M░M;╜-WXkπ
                        (implicit input)
W                 W     while top of stack is truthy:
 ;╗                       push a copy of n to reg0
   uR♂F;                  push 2 copies of [Fib(a) for a in range(1, n+2)]
        `╜≥`M░            filter: take values where n <= Fib(a)
              M;          two copies of maximum (call it m)
                ╜-        subtract from n (this leaves n-m on top of the stack to be the new n next iteration, with a copy of m below it)
                   X    discard the 0 left over after the loop ends
                    kπ  product of all stack values

JavaScript (ES6) 134 106 92 bajtów

Dzięki za @cat za zauważenie spacji.

n=>{for(c=[a=b=s=1,1];a+b<=n;)a+=b,c.unshift(b+=a,a);c.map(i=>i<=n&&(n-=i)&(s*=i));alert(s)}

Po prostu niezoptymalizowana wersja wykonana na mój telefon. Po powrocie do gry gram w golfa. Pomysły są mile widziane.

ZWROT , 44 bajty

[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]

Try it here.

Zadziwiająco mało wydajna anonimowa lambda, która pozostawia wynik na Stack2. Stosowanie:

12345[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]!

UWAGA: ␌ i ␁ są symbolami zastępczymi dla ich odpowiednich niedrukowalnych znaków: Form Feed i Początek nagłówka .

Wyjaśnienie

[                                           ]  lambda
 a:                                            store input to a
   [  ][                         ]#            while loop
    a;                                           check if a is truthy
        1$[¤¤+$a;->~][]#%                        if so, generate all fibonacci numbers less than a 
                         $␌                      push copy of TOS to stack2
                           a;\-a:                a-=TOS
                                   ␁[¤][×]#   get product of stack2

PHP, 119 bajtów

Kod (owinięty w dwa wiersze dla czytelności):

for($o=$c=1;$c<=$n=$argv[1];$f[++$k]=$c,$a=$b,$b=$c,$c+=$a);
for($i=$k;$i;$i--)for(;$n>=$d=$f[$i];$n-=$d,$o*=$d);echo$o;

Pierwszy wiersz oblicza $fliczby Fibonacciego mniejsze niż $n(argument podany w wierszu poleceń). Drugi wiersz oblicza współczynniki Fibonacciego (przez odjęcie) i mnoży je, aby obliczyć iloczyn $o.

Przygotuj kod za pomocą <?php(technicznie nie jest częścią programu), umieść go w pliku ( fibonacci-factors.php), a następnie uruchom jako:

$ php -d error_reporting=0 fibonacci-factors.php 100
# The output:
2136

Lub uruchom go za pomocą php -d error_reporting=0 -r '... code here ...' 100.

Niegolfowany kod i zestaw testów można znaleźć na Github .

P, 47 bajtów

m:{*/1_-':|(0<){y-x x bin y}[*+60(|+\)\1 0]\x}

Test

+(i;m'i:1 2 3 4 5 6 7 8 9 42 1000 12345)

odczytaj to jako pary (i, mapa (m, i)), gdzie m jest funkcją obliczeniową, a ja różnymi argumentami

pisze

1     1
2     2
3     3
4     3
5     5
6     5
7     10
8     8
9     8
42    272
1000  12831
12345 138481852236

Wyjaśnienie

n funtion\arg stosuje funkcję (funkcja (funkcja (... funkcja (argumenty))) n razy (wewnętrznie używa rekurencji talowej) i zwraca sekwencję wyników. Obliczamy 60 pierwszych pozycji serii fibonnaci jako *+60(|+\)\1 0. W takim przypadku funkcją jest ( | +): + \ zastosowane w sekwencji oblicza sumy cząstkowe (ex + \ 1 2 3 to 1 3 6) i | odwraca sekwencję, więc każda 'iteracja' obliczamy sumy cząstkowe dwóch poprzednich liczb Fibonacciego i zwracamy częściowe sumy odwrócone 60(|+\)\1 0generują sekwencje 1 0, 1 1, 2 1, 3 2, 5 3, 8 5, 13 8, 21 13, ... *+nakładane na ten wynik przerzucają (trasują go) i przyjmują pierwszą. Wynik jest sekwencją 1 1 2 3 5 8 13 21 34 55 ..

(cond)function\args stosuje funkcję (function (.. function (args))) podczas warunku true i zwraca sekwencję częściowych wyników

function[arg] nałożone na funkcję więcej niż jednego argumentu tworzy rzut (częściowe zastosowanie)

Możemy podać nazwę argumentom, ale implikowane nazwy to x, y, z

{y-x x bin y}[*+60(|+\)\1 0]deklaruje lambda za pomocą argumentów x, y z rzutowaniem częściowym (arg x jest serią Fibonacciego, oblicza się jako * + 60 (| +) \ 1 0). x oznacza wartości Fibonacciego, a y liczbę do przetworzenia. Wyszukiwanie binarne (bin) służy do zlokalizowania indeksu większej liczby Fibonacciego <= y ( x bin y) i odjęcia odpowiedniej wartości x.

Aby obliczyć iloczyn z częściowych wyników, odwracamy je i obliczamy różnicę dla każdej pary ( -':|), upuszczamy pierwszą ( 1_ponieważ wynosi 0) i mnożymy przez ( */).

Jeśli interesuje nas skumulowana suma, kod jest taki sam, ale z +/zamiast */. Możemy również użyć dowolnego innego operatora diadic zamiast + lub *

O wydajności wykonania

Wiem, że w tym konkursie wydajność nie stanowi problemu. Ale w tym problemie możemy wahać się od kosztu liniowego do kosztu wykładniczego, więc jestem ciekawy.

Opracowałem drugą wersję (długość 48 bajtów bez komentarza) i powtarzałem przypadki testowe baterii 1000 razy w obu wersjach.

f:*+60(|+\)\1 0;m:{*/1_-':|(0<){x-f f bin x}\x}    /new version

czas wykonania to: oryginalna wersja 0'212 seg, nowa wersja 0'037 seg

Oryginalna wersja oblicza serię fibbonaci raz na aplikację funkcji; Nowa wersja oblicza Fibonacciego tylko jeden.

W obu przypadkach obliczenia serii Fibonacciego wykorzystują rekurencję ogona