Produkty Fibonacciego


13

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

6
Oświadczenie nie jest całkiem poprawne. Np. 2Można rozłożyć jako -1 + 3. Prawidłowe stwierdzenie twierdzenia Zeckendorfa jest takie, że dodatnią liczbę Fibonacciego można jednoznacznie rozłożyć jako sumę niesekwencyjnych liczb Fibonacciego o dodatnim indeksie.
Peter Taylor

1
@PeterTaylor Nie uważam ujemnych liczb Fibonacciego za część tego pytania. Kolejne lub nie tylko ma znaczenie, gdy chcesz indeksów, nie dbamy o wskaźniki dla tego pytania.
lub

1
Nie mówię, że powinieneś zmienić pytanie, aby obsługiwać ujemne liczby Fibonacciego: Mówię, że powinieneś je edytować, aby wyraźnie określić założenia, które przyjmujesz.
Peter Taylor

1
@orlp z rzędu lub nie ma większego znaczenia, ponieważ dwie różne formy dawałyby dwa różne produkty. Opisałeś już problem w sposób, który już domyślnie wyklucza kolejne terminy Fibonacciego, więc nie ma się o co martwić.
hobbs

2
(w szczególności: F (n) i F (n + 1) nie mogą pojawić się na wyjściu, ponieważ algorytm gwarantuje, że przed ich rozważeniem reszta jest już mniejsza niż F (n + 2) = F (n) + F (n + 1))
hobbs

Odpowiedzi:


5

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.  

6
To wydaje się duże, Dennis.
lub

9

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.


5

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 .


Wyjaśnienie powinno zawierać wzmiankę, że ósemka 061jest kodowaniem ASCII tego znaku '1'. Fajny hack w użyciu, $\aby wydrukować go prawie za darmo.
Peter Cordes

2

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

2

> <> , 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!


Ładny! Proponuję opublikować link za pomocą kompilatora internetowego
Luis Mendo


1

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.


1

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

1

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

Czy w rzeczywistości ma własne kodowanie? Liczę 35 bajtów na 22 znaki. mothereff.in/…
kot

1
@cat Podobnie jak Seriously, używa CP437.
Mego

1

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.


Jest jedna zbędna biała spacja. : P
kot

1

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

Liczę 46 bajtów na 42 znaki. Jeśli RETURN używa jakiegoś specjalnego kodowania, powinien mieć 42 bajty w 42 znakach, ale wydaje się być Unicode, więc 46.
cat

Właściwie właśnie zdałem sobie sprawę, że zapomniałem umieścić trochę materiałów do drukowania.
Mama Fun Roll

Potrzebowałem mikroskopu, aby powiedzieć, jakie są, więc połączyłem się z nimi dla ciebie. : D (nie wiem, czy to SOH czy BOM)
kot

0

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 .


0

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.