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
code-golf
math
sequence
fibonacci
code-golf
word
code-golf
cipher
code-golf
string
math
subsequence
code-golf
regular-expression
code-golf
brainfuck
assembly
machine-code
x86-family
code-golf
math
factorial
code-golf
math
geometry
code-golf
math
arithmetic
array-manipulation
math
number
optimization
stack
metagolf
code-golf
tips
assembly
code-golf
tips
lisp
code-golf
number-theory
path-finding
code-golf
number
sequence
generation
code-golf
math
geometry
code-golf
grid
permutations
code-golf
code-golf
graphical-output
geometry
fractal
knot-theory
code-golf
math
arithmetic
code-golf
interpreter
balanced-string
stack
brain-flak
code-golf
math
set-theory
code-golf
math
array-manipulation
code-golf
code-golf
string
natural-language
code-golf
code-golf
math
linear-algebra
matrix
code-golf
string
encode
orlp
sumber
sumber
2
dapat 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.Jawaban:
Jelly ,
1615 byteTidak terlalu cepat atau ramah memori, tetapi cukup efisien untuk semua kasus uji. Cobalah online!
Bagaimana itu bekerja
sumber
Python, 54 byte
Hanya rekursi lama yang bagus.
sumber
Perl,
6963 + 4 (-pl61
bendera) = 67 byteMenggunakan:
Tidak Disatukan:
Ideone .
sumber
061
adalah pengkodean ASCII untuk karakter'1'
. Retas bagus untuk digunakan$\
agar bisa dicetak dengan gratis.JavaScript (ES6),
7842 byteJawaban Port of Sp3000. Versi 78 byte asli:
sumber
> <> , 57 byte
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
...Cobalah online!
sumber
Pyth, 28 byte
Saya pikir itu bisa bermain golf lebih jauh ...
Cobalah online!
sumber
Pyth, 24 byte
Cobalah online: Demonstrasi atau Test Suite
Penjelasan:
Q
ditugaskan dengan nomor input.Bagian
h.WgQeH,eZsZ1
menghitung angka Fibonacci terbesar, yaitu lebih kecil atau sama denganQ
Jadi jika
Q = 10
, itu menghasilkan angka / pasangan:Sisa kode menghitung partisi dan mengalikan angka bersama:
Jelas ada banyak solusi yang lebih pendek (dengan run-times yang sangat buruk), seperti
*FhfqQsTyeM.u,eNsNQ1
.sumber
Haskell, 44 byte
Yay untuk saling rekursi:
a
adalah angka Fibonacci sebelumnyab
adalah angka Fibonacci saat inic
adalah inputf
adalah fungsi yang diinginkanKurang golf:
sumber
Sebenarnya, 22 byte
Cobalah online!
Penjelasan:
sumber
Javascript (ES6)
13410692 byteTerima kasih atas @cat karena telah menemukan tempat.
Hanya versi yang tidak dioptimalkan dibuat pada ponsel saya, saya golf turun, begitu saya pulang. Gagasan dipersilakan.
sumber
KEMBALI , 44 byte
Try it here.
Lambda anonim yang sangat tidak efisien yang meninggalkan hasil pada Stack2. Pemakaian:
CATATAN: ␌ dan ␁ adalah penampung untuk karakternya masing-masing yang tidak dapat dicetak: Umpan Umpan dan Mulai dari Pos .
Penjelasan
sumber
PHP, 119 byte
Kode (dibungkus dua baris untuk dibaca):
Baris pertama menghitung dalam
$f
angka 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:Atau jalankan dengan menggunakan
php -d error_reporting=0 -r '... code here ...' 100
.Kode ungolfed dan test suite dapat ditemukan di Github .
sumber
Q, 47 Bytes
Uji
membacanya sebagai pasangan (i, map (m, i)), di mana m adalah fungsi penghitungan dan i argumen yang berbeda
menulis
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 0
menghasilkan 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 parsialfunction[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.
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
sumber