Produk-produk Fibonacci

13

Anda dapat menguraikan angka lebih besar dari 0 sebagai jumlah unik dari angka Fibonacci positif. Dalam pertanyaan ini kami melakukan ini dengan berulang kali mengurangi angka Fibonacci positif terbesar yang mungkin . Misalnya:

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

Sekarang, saya menyebut produk Fibonacci dengan daftar yang sama seperti di atas, tetapi dengan penambahan digantikan oleh perkalian. Sebagai contoh f(100) = 89 * 8 * 3 = 2136,.

Tulis program atau fungsi yang diberi bilangan bulat positif dan kembalikan produk Fibonacci dari angka itu.


Testcases:

1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236
orlp
sumber
6
Pernyataan itu tidak sepenuhnya benar. Misalnya 2dapat didekomposisi sebagai -1 + 3. Pernyataan yang benar dari teorema Zeckendorf adalah bahwa angka Fibonacci positif dapat secara unik diuraikan sebagai jumlah angka Fibonacci non-berturut-turut dengan indeks positif.
Peter Taylor
1
@PeterTaylor Saya tidak menganggap angka Fibonacci negatif bagian dari seri untuk pertanyaan ini. Berturut-turut atau tidak hanya penting ketika Anda menginginkan indeks, kami tidak peduli dengan indeks untuk pertanyaan ini.
orlp
1
Saya tidak mengatakan bahwa Anda harus mengubah pertanyaan untuk mendukung angka Fibonacci negatif: Saya mengatakan bahwa Anda harus mengeditnya secara eksplisit tentang asumsi yang Anda buat.
Peter Taylor
1
@ orlp berturut-turut atau tidak terlalu penting, karena dua bentuk berbeda akan memberikan dua produk yang berbeda. Anda sudah menyatakan masalah dengan cara yang sudah secara implisit mengesampingkan syarat Fibonacci berturut-turut, jadi tidak ada yang perlu dikhawatirkan di sana.
hobbs
2
(khusus: F (n) dan F (n + 1) tidak dapat keduanya muncul dalam output karena algoritma menjamin bahwa, sebelum mempertimbangkan mereka, sisanya sudah kurang dari F (n + 2) = F (n) + F (n +1))
hobbs

Jawaban:

5

Jelly , 16 15 byte

Rf1+С¤ṪạµÐĿIAP

Tidak terlalu cepat atau ramah memori, tetapi cukup efisien untuk semua kasus uji. Cobalah online!

Bagaimana itu bekerja

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.  
Dennis
sumber
6
Ini sepertinya besar, Dennis.
orlp
9

Python, 54 byte

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

Hanya rekursi lama yang bagus.

Sp3000
sumber
5

Perl, 69 63 + 4 ( -pl61bendera) = 67 byte

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

Menggunakan:

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

Tidak Disatukan:

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 .

Denis Ibaev
sumber
Penjelasan harus menyebutkan bahwa oktal 061adalah pengkodean ASCII untuk karakter '1'. Retas bagus untuk digunakan $\agar bisa dicetak dengan gratis.
Peter Cordes
2

JavaScript (ES6), 78 42 byte

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

Jawaban Port of Sp3000. Versi 78 byte asli:

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
Neil
sumber
2

> <> , 57 byte

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

Mengharapkan nomor input untuk hadir pada tumpukan saat program dimulai.

Membangun urutan Fibonacci ( f0, f1, f2, ..., fn) pada tumpukan hingga angka yang dicapai lebih besar daripada input ( i). Kemudian, dengan produk ( p) diinisialisasi ke1 ...

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

Cobalah online!

Sok
sumber
Bagus! Saya sarankan Anda memposting tautan menggunakan kompiler online
Luis Mendo
1

Pyth, 28 byte

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

Saya pikir itu bisa bermain golf lebih jauh ...

Cobalah online!

Biarawati Bocor
sumber
1

Pyth, 24 byte

W=-QeaYh.WgQeH,eZsZ1;*FY

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

Q ditugaskan dengan nomor input.

Bagian h.WgQeH,eZsZ1menghitung angka Fibonacci terbesar, yaitu lebih kecil atau sama denganQ

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

Jadi jika Q = 10, itu menghasilkan angka / pasangan:

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

Sisa kode menghitung partisi dan mengalikan angka bersama:

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

Jelas ada banyak solusi yang lebih pendek (dengan run-times yang sangat buruk), seperti *FhfqQsTyeM.u,eNsNQ1.

Jakube
sumber
1

Haskell, 44 byte

Yay untuk saling rekursi:

(a&b)c|c<1=1|b>c=a*f(c-a)|d<-a+b=b&d$c
f=0&1
  • a adalah angka Fibonacci sebelumnya
  • b adalah angka Fibonacci saat ini
  • c adalah input
  • f adalah fungsi yang diinginkan

Kurang golf:

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

Sebenarnya, 22 byte

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

Cobalah online!

Penjelasan:

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
Mego
sumber
Apakah Sebenarnya memiliki penyandian sendiri? Saya menghitung 35 byte di 22 karakter. mothereff.in/…
cat
1
@ kucing Sama seperti Serius, ia menggunakan CP437.
Mego
1

Javascript (ES6) 134 106 92 byte

Terima kasih atas @cat karena telah menemukan tempat.

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)}

Hanya versi yang tidak dioptimalkan dibuat pada ponsel saya, saya golf turun, begitu saya pulang. Gagasan dipersilakan.

Bálint
sumber
Ada satu ruang putih superflouous. : P
cat
1

KEMBALI , 44 byte

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

Try it here.

Lambda anonim yang sangat tidak efisien yang meninggalkan hasil pada Stack2. Pemakaian:

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

CATATAN: ␌ dan ␁ adalah penampung untuk karakternya masing-masing yang tidak dapat dicetak: Umpan Umpan dan Mulai dari Pos .

Penjelasan

[                                           ]  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
Mama Fun Roll
sumber
Saya menghitung 46 byte di 42 karakter. Jika RETURN menggunakan beberapa pengkodean yang agak khusus, seharusnya 42 byte di 42 karakter, tetapi tampaknya unicode, jadi 46.
cat
Sebenarnya, saya baru sadar bahwa saya lupa memasukkan beberapa yang tidak patut.
Mama Fun Roll
Saya membutuhkan mikroskop untuk memberi tahu mereka apa itu, jadi saya menautkannya untuk Anda. : D (Saya tidak tahu apakah itu SOH atau BOM)
cat
0

PHP, 119 byte

Kode (dibungkus dua baris untuk dibaca):

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;

Baris pertama menghitung dalam $fangka Fibonacci lebih kecil dari$n (argumen yang disediakan di baris perintah). Baris kedua menghitung faktor Fibonacci (dengan pengurangan) dan mengalikannya untuk menghitung produk dalam $o.

Tambahkan kode dengan <?php(secara teknis bukan bagian dari program), masukkan ke dalam file ( fibonacci-factors.php) kemudian jalankan sebagai:

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

Atau jalankan dengan menggunakan php -d error_reporting=0 -r '... code here ...' 100 .

Kode ungolfed dan test suite dapat ditemukan di Github .

aksioma
sumber
0

Q, 47 Bytes

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

Uji

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

membacanya sebagai pasangan (i, map (m, i)), di mana m adalah fungsi penghitungan dan i argumen yang berbeda

menulis

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

Penjelasan

n funtion\arg menerapkan fungsi (fungsi (fungsi (... fungsi (argumen)))) n kali (secara internal menggunakan rekursi tal), dan mengembalikan urutan hasil. Kami menghitung 60 item pertama dari seri fibonnaci sebagai *+60(|+\)\1 0. Dalam hal ini fungsinya adalah ( | +): + \ diterapkan pada urutan menghitung jumlah parsial (ex + \ 1 2 3 adalah 1 3 6), dan | membalikkan seq. Jadi setiap 'iterasi' kita menghitung jumlah parsial dari dua nomor fibonacci sebelumnya dan mengembalikan parsial jumlah terbalik, 60(|+\)\1 0menghasilkan urutan 1 0, 1 1, 2 1, 3 2, 5 3, 8 5, 13 8, 21 13, ... *+diterapkan pada hasil ini membalik (traspose) dan mengambil yang pertama. Hasil adalah urutan 1 1 2 3 5 8 13 21 34 55 ..

(cond)function\args berlaku function (function (.. function (args))) sementara cond true, dan mengembalikan urutan hasil parsial

function[arg] diterapkan pada fungsi lebih dari satu argumen membuat proyeksi (aplikasi sebagian)

Kita bisa memberi nama pada args, tetapi nama implisitnya adalah x, y, z

{y-x x bin y}[*+60(|+\)\1 0]mendeklarasikan lambda dengan args x, y dengan proyeksi parsial (arg x adalah deret fibonacci, dihitung sebagai * + 60 (| +) \ 1 0). x mewakili nilai fibonacci, dan y angka untuk diproses. Pencarian biner (bin) digunakan untuk mencari indeks angka fibonacci yang lebih besar <= y ( x bin y), dan mengurangi nilai yang sesuai dari x.

Untuk menghitung produk dari resuls parsial, kami membalikkannya dan menghitung perbedaan masing-masing pasangan ( -':|), jatuhkan yang pertama ( 1_karena 0) dan dikalikan ( */).

Jika kita tertarik pada jumlah akumulasi kodenya sama, tetapi dengan +/alih - alih */. Kami juga dapat menggunakan operator diadik lain alih-alih + atau *

Tentang efisiensi eksekusi

Saya tahu bahwa dalam kontes ini efisiensi tidak menjadi masalah. Tetapi dalam masalah ini kita dapat berkisar dari biaya linier ke biaya eksponensial, jadi saya ingin tahu tentang hal itu.

Saya mengembangkan versi kedua (panjang 48 Bytes tidak termasuk komentar) dan menguji ulang baterai 1000 kali pada kedua versi.

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

waktu eksekusi adalah: versi asli 0'212 seg, versi baru 0'037 seg

Versi asli menghitung seri fibbonaci sekali per aplikasi fungsi; versi baru menghitung fibonacci hanya satu.

Dalam kedua kasus perhitungan seri fibonacci menggunakan rekursi ekor

J. Sendra
sumber