Definisi
Urutan Fibonacci F(n)
, pada bilangan bulat positif, didefinisikan sebagai berikut:
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
Fibonacci-orial dari bilangan bulat positif adalah produk dari [F(1), F(2), ..., F(n)]
.
Tugas
Diberikan bilangan bulat positif n
, temukan Fibonacci-orial dari n
.
Spesifikasi
The fibonacci-orial of 100
harus menghitung di bawah 5 detik pada komputer yang masuk akal.
Testcases
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
Jawaban:
Mathematica, 10 byte
Built-in Mathematica lain dipukuli dengan baik oleh bahasa golf tanpa built-in.
sumber
Jelly , 6 byte
Input 100 selesai dalam 500 ms secara lokal. Cobalah online!
Bagaimana itu bekerja
sumber
+¡1
non-built in nth fibonacci dan+С1
n bilangan Fibonacci pertama?Sebenarnya , 4 byte
Menjalankan input 100 dalam 0,2 detik. Kode:
Penjelasan:
Menggunakan pengkodean CP-437 . Cobalah online! .
sumber
Brainfuck,
11981067817770741657611603Terkompresi, dengan komentar:
Cobalah online!
Runtime untuk n = 100 kurang dari 1 detik dengan penerjemah online (sekitar 0,2 detik menggunakan interpreter saya sendiri). Input maksimum adalah 255, tetapi akan membutuhkan penerjemah untuk mendukung ~ 54000 sel (penerjemah online tampaknya menggunakan 64k).
Ubah Log
Disimpan sekitar 130 byte dengan ekstraksi yang lebih baik dari digit saat ini untuk dikalikan dengan, dan dengan menggabungkan menambah dan membawa ke dalam satu pass. Tampaknya juga sedikit lebih cepat.
Menyimpan 250 byte lagi. Saya berhasil mengurangi multiplikasi goresan dua sel, yang menghemat byte di mana-mana dengan tidak harus bergeser sejauh ini di antara digit. Saya juga menjatuhkan carry setelah mengalikannya dengan digit, dan sebagai gantinya melakukan carry penuh sambil menambah total running.
Cincang 50 lagi, lagi dengan ekstraksi yang lebih baik dari digit saat ini untuk dikalikan, hanya dengan tidak bergerak maju iterasi pertama, dan bekerja dari tempat itu. Beberapa optimasi mikro lebih lanjut menyumbang sekitar ~ 10 byte.
30 lagi hilang. Menandai digit yang telah diambil dengan angka 0 daripada angka 1 membuatnya lebih mudah ditemukan. Itu juga membuat pemeriksaan apakah loop multiplikasi telah selesai agak lebih sederhana.
Saya mengurangi bantalan awal dengan sel lain, untuk 80 byte lebih. Saya melakukan ini dengan menggabungkan penanda untuk produk sebelumnya dan total berjalan saat ini, yang mengurangi pergeseran antara celah, dan membuat pembukuan sedikit lebih mudah.
Menyimpan 50 lainnya, dengan menghilangkan sel lagi, menggunakan kembali marker untuk digit fibonacci untuk menandai digit terakhir yang diambil juga. Saya juga bisa menggabungkan loop untuk menggeser total sebelumnya dengan loop multiplikasi digit-wise.
Disimpan 8 byte pada parsing input. Ups.
sumber
Python, 45 Bytes
Input diambil dari stdin. Output untuk n = 100 selesai terlalu cepat untuk waktu yang akurat. n = 1000 membutuhkan waktu sekitar 1s.
Contoh Penggunaan
sumber
Haskell
4129 Bytes1 + 11 byte disimpan oleh pernyataan @ Laikoni.
1
,f
dan!!
merupakan token yang terpisah. Baris pertama mendefinisikan urutan fibonacci, yang kedua adalah fungsi yang menghitung urutan fibonacci-orials dan mengembalikan n-th untuk n yang diberikan. Ini mulai mencetak angka segera bahkan untuk n = 1000.sumber
(scanl(*)1f!!)
.f=1:scanl(+)1f
42+
sebagai fungsi yang menambahkan 42? Anda tidak boleh, karena itu hanya ekspresi yang belum selesai. Tetapi di Haskell kita bisa menambahkan tanda kurung dan mendapatkan bagian(42+)
, cara untuk menulis fungsinya\n->42+n
. Ini dia sama, hanya dengan!!
(operator infiks biner untuk pengindeksan) bukan+
dan operan pertama yang lebih rumit.Python 2, 39 byte
Uji di Ideone .
sumber
True
dalam beberapa kasus.True
input 0 , yang tidak positif.J,
1716 byte1 byte di-golf-kan dengan solusi yang bahkan lebih baik.
Idenya sama dengan aslinya tetapi alih-alih membentuk matriks untuk beroperasi pada diagonal minor, kita membentuk diagonal dengan cepat.
Asli
Untuk mendapatkan yang pertama n fibonomial :
Membaca dari kanan ke kiri ...
Buat larik bilangan bulat berurutan (
i.
) hingga yang ditentukan, dari larik itu buat tabel (/~
) dari koefisien binomial (!
) yang dihitung dari setiap pasangan dalam larik, tabel ini adalah puncak segitiga Pascal di mana terletak di akhir baris pertama dan semua elemen di bawah diagonal utama adalah 0, untungnya untuk implementasi!
. Jika Anda menjumlahkan (+/
) semua diagonal minor (/.
), Anda mendapatkan angka Fibonacci, tetapi Anda perlu mengambil ({.
) sebanyak mungkin elemen pertama dari array yang dihasilkan sebagai panjang (#
) dari tabel itu sendiri. Kemudian produk (*/
) yang diterapkan pada awalan berurutan (\
) dari hasil array ke dalam urutan fibonorial yang diinginkan.Jika Anda mau, Anda hanya dapat mengambil yang terakhir menggunakan 2 byte lebih ({:
) tapi saya pikir menampilkan semuanya bukan dosa:)
.NB. the previous code block is not a J function
.Untuk angka besar di J yang Anda gunakan
x
di akhir:Program ini berjalan pada rata-rata 0,11s .
sumber
[:*/+/@(!|.)\@i.
menggunakan 16 byte. Ini membentuk koefisien binomial yang sama di sepanjang tabel yang Anda hasilkan menggunakan!/~
kecuali bahwa ia membentuk dengan mengambil awalani.
.Pyth, 13 byte
Demonstrasi
Ini menggunakan trik yang cerdas dan tidak aman. Lima karakter (
u*G ... Q1
) mengatakan bahwa output adalah produk dari input banyak angka. Sisa kode menghasilkan angka.=[sZhZ)
memperbarui variabelZ
ke daftar[s(Z), h(Z)]
. Kemudians
jumlahkan daftar itu, untuk dikalikan.Z
awalnya 0.s
, di int, adalah fungsi identitas.h
, pada itu, adalah+ 1
fungsinya. Jadi pada iterasi pertama,Z
jadilah[0, 1]
.s
pada daftar adalah fungsi penjumlahan, seperti yang disebutkan di atas.h
adalah fungsi kepala. Jadi iterasi kedua adalah[1, 0]
.Berikut daftarnya:
Jumlah ini dikalikan untuk memberikan hasilnya.
sumber
Mathematica
2524 byteTerima kasih kepada Martin Ender.
Waktu: 63 mikrodetik.
sumber
1##&@@Fibonacci~Array~#&
Jelly, 8 byte
Kiriman pertama saya di Jelly. Ini tidak sesingkat jawaban @ Dennis , tetapi hanya 2 byte lagi dengan metode yang berbeda.
Secara lokal, ini membutuhkan sekitar 400ms dibandingkan dengan 380ms dengan versi @ Dennis 'untuk n = 100.
Cobalah online!
Penjelasan
sumber
PARI / GP, 29 byte
Atau sebagai alternatif:
sumber
R,
9996787666 byteJawaban ini menggunakan Formula Binet , serta
prod(x)
fungsinya. Karena R tidak memilikiPhi
nilai bawaan, saya mendefinisikannya sendiri:Ini bekerja di bawah 5 detik, tetapi R cenderung memberikan
Inf
jawaban untuk angka-angka besar ...Tidak Disatukan:
-2 byte terima kasih kepada @Cyoce!
Oh, aku suka situs ini! -10 byte terima kasih kepada @ user5957401
sumber
sqrt(5)
ke variabelN
sekali, Anda bisa memanggil pemindaian di dalam1:N
bit. yaitufor(n in 1:scan())
. Anda juga dapat menyimpan beberapa karakter hanya dengan menggunakan*
alih-alihprod()
fungsi dalam for for Anda. Loop for Anda hanya satu baris, jadi Anda tidak perlu kurung kurawal.function(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
R,
82,53, 49 byte (48 byte dengan gaya input berbeda)Jika kita bisa mendahului kode dengan nomor input, kita mendapatkan 48 byte
Sunting: Kode baru. Asli di bawah:
Tidak akan mengembalikan apa pun selain Inf untuk
a(100)
. Dan itu tidak akan bekerja untuk apa pun kecuali bilangan bulat non-negatif.Tidak Disatukan:
sumber
Java, 165 byte
Golf:
Ini adalah kasus lain di mana
BigInteger
diperlukan karena jumlah besar. Namun, saya dapat menyimpan teksBigInteger
minimum, menjaga ukurannya tetap rendah. Saya juga membandingkan dengan impor statis, dan itu membuat total panjangnya lebih lama.Program ini bekerja dengan melacak tiga angka dalam sebuah array. Dua yang pertama adalah dua angka Fibonacci sebelumnya. Yang ketiga adalah nilai akumulasi. Loop dimulai dengan menghitung nilai berikutnya dan menyimpannya dalam indeks array bergantian (0, 1, 0, 1, ...). Ini menghindari perlunya mengubah nilai dengan operasi penugasan yang mahal (dalam hal ukuran sumber). Kemudian ambil nilai baru itu dan gandakan ke akumulator.
Dengan menghindari objek sementara dan membatasi loop ke dua operator penugasan, saya bisa memeras beberapa byte.
Tidak Disatukan:
Output program:
sumber
Brachylog , 31 byte
Cobalah online!
sumber
Ruby, 39 byte
sumber
Javascript (ES6),
5139 byteImplementasi rekursif (39 byte)
Implementasi asli (51 byte)
Note: Starts rounding errors for the Fibonacci-orial of 16, 100 is just Infinity, runs in what appears to be <1 second.
sumber
n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)
only to discover that you'd counted thef=
which isn't required saving you 2 bytes.DC (rasa GNU atau OpenBSD) , 36 byte
File
A003266-v2.dc
:(tidak ada baris baru)
... sekarang hasilnya disimpan di tumpukan alih-alih menggunakan register bernama (
Y
dalam versi 1). Ther
perintah ini tidak tersedia dalam bahasa aslinyadc
(lihat halaman Dc RosettaCode ini ).Menjalankan:
Mencoba menjelaskan:
tos
adalah isi bagian atas tumpukan tanpa mengeluarkannya.nos
adalah elemen di bawah initos
.DC , 41 byte
... lurus ke depan, tidak ada trik:
File
A003266-v1.dc
:(tidak ada baris baru)
Menjalankan:
sumber
dc
kode pasti lebih mudah daripada menjelaskannya ...n
item teratas ke tumpukan lain sekaligus. Untuk saat ini, saya masih tidak tahu bagaimana cara mengkompilasidc
dari sumber. : /C #
11010910710310194 BytesPenjelasan
Algoritma Iterative Fib
sumber
Brain-Flak, 54 bytes
Try it online!
Multiplication in Brain-Flak takes a long time for large inputs. Just multiplying F100 by F99 with a generic multiplication algorithm would take billions of years.
Fortunately, there's a faster way. A generalized Fibonacci sequence starting with
(k, 0)
will generate the same terms as the usual sequence, multiplied byk
. Using this observation, Brain-Flak can multiply by a Fibonacci number just as easily as it can generate Fibonacci numbers.If the stack consists of
-n
followed by two numbers,{({}()<([({})]({}{}))>)}{}{}
will computen
iterations of the generalized Fibonacci sequence and discard all by the last. The rest of the program just sets up the initial 1 and loops through this for all numbers in the rangen...1
.Here's the same algorithm in the other languages provided by this interpreter:
Brain-Flak Classic, 52 bytes
Try it online!
Brain-Flueue, 58 bytes
Try it online!
Mini-Flak, 62 bytes
Try it online!
sumber
Mathematica -
3226 bytes@MartinEnder chopped 6 bytes!
sumber
GAP 28 Bytes
Didn't know before today that GAP has a
Fibonacci
builtin.sumber
Ruby, 85 Bytes
Turned out fine, but there's probably a shorter solution.
Fast Fibonnaci calculation taken from here: link
Test it here
sumber
Julia, 36 bytes
sumber
Brain-Flak,
110104100 bytesTry it online!
Explanation
First we run an improved version of the Fibonacci sequence generator curtesy of Dr Green Eggs and Iron Man
Then while the stack has more than one item on it
multiply the top two items
and pop the extra zero
sumber
Clojure, 70 bytes
Clojure isn't really a good language for code golf. Oh well.
Try it at http://tryclj.com.
sumber
Forth, 55 bytes
Uses an iterative approach, built upon my Fibonacci answer in Forth. The results overflow arithmetically for
n > 10
. The answer is case-insensitive.Try it online
sumber
Swift, 68 Bytes
sumber
JavaScript (ES6), 46 bytes
Uses recursion and accumulator variables. Rounding errors start at
f(16)
.sumber