pengantar
Kita semua tahu dan menyukai urutan Fibonacci kami dan telah melihat segudang tantangan di sini. Namun, kami masih kekurangan kasus yang sangat sederhana yang akan diberikan jawaban ini: Reversed fibonacci! Jadi, F_n
tugas Anda adalah menemukan n
.
Spesifikasi
Memasukkan
Input Anda akan berupa bilangan bulat non-negatif, yang dijamin menjadi bagian dari deret fibonacci.
Keluaran
Outputnya juga harus bilangan bulat non-negatif.
Melakukan apa?
Pendahuluan sudah mengatakan: Diberi nomor Fibonacci, tampilkan indeksnya. Nomor Fiboancci dengan ini didefinisikan sebagai F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
dan Anda diberikan F(n)
dan harus kembali n
.
Kasus Pojok Potensial
0 adalah in- dan output yang valid.
Jika diberi "1" sebagai input, Anda dapat menampilkan "1" atau "2", sesuai keinginan.
Anda mungkin selalu menganggap bahwa input Anda sebenarnya adalah nomor fibonacci.
Anda dapat mengasumsikan bahwa input tersebut mewakili sebagai integer bertanda 32-bit.
Yang menang?
Ini adalah kode-golf sehingga jawaban tersingkat dalam byte menang!
Aturan standar berlaku tentu saja.
Kasus uji
0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
Jawaban:
Sebenarnya 1 byte
Ya, ada builtin untuk ini, sejak 16 November 2015 .
Cobalah online
Untuk bersenang-senang, tanpa builtin, 9 byte:
Cobalah online!
Penjelasan:
sumber
Mathematica, 25 byte
Fungsi. Cukup jelas jika Anda bertanya kepada saya.
sumber
Python,
363432 byteVersi sebelumnya:
Penjelasan
Gagasan intinya adalah membalik formula
yang memberitahu kita itu
mendapatkan
Optimalisasi golf adalah:
len(str(n))
untuk menghitung basis log 10 tanpa mengimporlog
(versi lama digunakan.bit_length()
untuk menghitung basis log 2)n
kekuatan, sehingga perkiraan logaritma dapat membedakan antara angka Fibonacci yang berurutanKemudian pembagi dipotong sesedikit mungkin yang saya bisa kelola dan pengali dipilih untuk memberikan hasil yang benar untuk semua angka-angka fibonacci 32-bit.
sumber
f=
tidak dihitung.lambda n:~-len(`66*n**6`)//1.24
seharusnya berhasil.05AB1E , 3 byte
Kode:
Penjelasan:
Menggunakan pengkodean CP-1252 . Cobalah online! .
sumber
Jelly,
1411 byteCobalah online!
Ini adalah jawaban Jelly pertamaku! Ini menggunakan algoritma dari jawaban MATL . Terima kasih kepada Dennis untuk mencukur 3 byte!
Penjelasan:
Ini mendapatkan jawaban yang benar, sekarang kita hanya perlu menangani kasus khusus '0'. Dengan '0' sebagai argumen, kami dapat
-infinity
, jadi kami kembalisumber
Julia,
272618 byteIni menggunakan kebalikan dari rumus Binet , dengan cukup presisi untuk bilangan bulat 32-bit; sebenarnya bekerja hingga F (153) = 42.230.279.526.998.466.217.810.220.532.898> 2 105 .
Cobalah online!
Bagaimana itu bekerja
Rumus Binet menyatakan sebagai berikut.
Membatasi F ke set dari peta Fibonacci, n → F n memiliki hak terbalik F → n F .
Kami memilikinya
dan semua yang tersisa untuk dilakukan adalah berurusan dengan kasus tepi 0 .
Karena input dibatasi untuk bilangan bulat 32-bit, kita dapat menggunakan liter desimal pendek alih-alih konstanta dalam rumus.
log φ = 0.481211825059603447… ≈ 0.48
Sayangnya, 0,5 tidak cukup tepat.
√5 = 2.2360679774997896964… ≈ 3
Itu mungkin tampak seperti perkiraan yang mengerikan pada pandangan pertama, tapi kami mengambil logaritma dan karena log 3 - log √5 = 0,29389333245105 ... , hasil sebelum pembulatan akan dimatikan oleh faktor konstan kecil.
0,5 ≈ 0,7
Karena kelebihan dari perkiraan sebelumnya, kami sebenarnya bisa menghilangkan istilah ini sama sekali dan masih mendapatkan hasil yang benar untuk F> 0 . Namun, jika F = 0 , logaritma tidak akan ditentukan. 0,7 ternyata menjadi nilai terpendek yang memperpanjang rumus kami ke F = 0 .
sumber
JavaScript,
5450695042 byteTentunya itu tidak akan menang, hanya untuk bersenang-senang :)
Ok, mengecek nol untuk konsumsi 19 byte. WTF?Bodohnya aku.Demo! Untuk melihat test case terakhir, Anda harus sedikit menggulir konsol.
Terima kasih @edc untuk mempersingkat 8 byte.
sumber
b=>{for(j=1,i=c=0;b-i;c++)i=j+(j=i);return c}
45,b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c
Perl 6
33 3027 byteCobalah
Penjelasan:
Uji:
sumber
first *==$_
dengan adilfirst $_
, karena angka adalah pencocokan pintar yang valid....
operator alih-alihfirst
Jelly , 8 byte
Cobalah online! Perhatikan bahwa pendekatan ini terlalu tidak efisien untuk kasus uji terakhir.
Bagaimana itu bekerja
sumber
Pyke, 5 byte
Coba di sini!
sumber
Python, 29 byte
Membagi input secara rekursif dengan perkiraan rasio emas 1,61 hingga di bawah 0,7, dan mengeluarkan jumlah divisi.
Untuk 0, output kode
False
, yang sama dengan 0 dalam Python . Ini dapat dihindari untuk 2 bytesumber
JavaScript (ES6),
3933 byteBahkan dengan ES7, rumus Binet terbalik mengambil 47 byte:
sumber
log
dan precompute semua konstanta ...f(n,k,j+k)
,, Anda harus memasukkan tugasf=
dan menghitungnya sebagai +2 byte . Aturan untuk lambda yang tidak disebutkan namanya seharusnya tidak berlaku di sini.Sage, 49 byte
Berkat TuukkaX untuk saran tentang menyimpan
sqrt(5)
sebagais
mencukur beberapa byte.Cobalah online .
Pendekatan ini menggunakan kebalikan dari formula Binet menawarkan beberapa perbaikan dibandingkan pendekatan sebelumnya: lebih cepat (waktu-konstan versus waktu kuadratik), ini sebenarnya bekerja untuk input yang lebih besar, dan lebih pendek!
Pengguna Python mungkin bertanya-tanya mengapa saya menggunakan
sqrt(5)
bukan yang lebih pendek5**.5
- itu karena5**.5
dihitung denganpow
fungsi C , dan kehilangan presisi karena masalah floating point. Banyak fungsi matematika (termasuksqrt
danlog
) kelebihan beban di Sage untuk mengembalikan nilai simbolik yang tepat, yang tidak kehilangan presisi.sumber
sqrt(5)
variabel dan menggunakannya dua kali, bukannya mengetiksqrt(5)
dua kali?MATL , 14 byte
Cobalah online!
Ini menggunakan kebalikan dari rumus Binet , dan itu sangat cepat.
Misalkan F menyatakan n th nomor Fibonacci, dan φ yang rasio emas . Kemudian
Kode menggunakan rumus ini dengan dua modifikasi:
Bagaimana itu dilakukan
sumber
O1G:"yy+]vGmfq
t?17L&YlXkQ
5X^*
. ( Saya telah melakukan ini sebelumnya .) Dan saya tidak tahu cukup MATL untuk terus meningkatkannya.Python, 38 byte
Uji di Ideone .
sumber
JavaScript, 22 byte
sumber
-Infinity|0
adalah0
dalam JavaScript. Sosok pergi.-Infinity = FFF00000 00000000
. Saya senang mengetahui, itu menghemat 3 byte karena tidak harus menambahkan tes nol eksplisit sepertin&&
. Terlepas dari itu, tujuan utama|0
adalah sebagai penggantiMath.trunc()
(seperti÷
dalam Julia).C,
6258 byteTerperinci
sumber
Java 7, 70 byte
https://ideone.com/I4rUC5
sumber
int c(int n){int a=0,b=1,c=0,t;for(;a<n;t=b,b+=a,a=t)c++;return c;}
(tidak diuji)int c(int n){int a=0,b=1,c=0;while(a<n){c++;b+=a;a=b-a;}return c;}
(tidak diuji)int c(int n){int a=0,b=1,c=0;for(;a<n;b+=a,a=b-a)c++;return c;}
(tidak diuji)TSQL, 143 byte
Input masuk
@n
seperti padaDECLARE @n INT = 1836311903;
sumber
Haskell, 45 byte
sumber
Sesos , 28 byte
Hexdump:
Cobalah online!
(Waktu eksponensial karena dalam Sesos menyalin nomor perlu waktu eksponensial.)
Majelis yang digunakan untuk menghasilkan file biner:
sumber
Java 8 61 byte
Sama seperti jawaban @dainichi hanya dibuat lebih pendek dengan menggunakan Java 8 lambdas. Jawabannya adalah ekspresi rvalue yang valid.
Tidak Disatukan:
sumber
Pyth, 13 byte
Suite uji.
Perkiraan dalam Python 2:
pendekatan alternatif, 18 byte
Suite uji.
Ini digunakan
.I
untuk terbalik.sumber
Java 7, 89 byte
Terinspirasi oleh penjelasan @Adnan 's jawaban 05AB1E .
Kasus yang tidak disatukan & uji:
Coba di sini. (Batas waktu terlampaui untuk test case terakhir, tetapi bekerja dalam waktu sekitar 30-45 detik pada PC saya.)
Keluaran:
sumber
Perl 5.10, 48 byte
Pada dasarnya mencari yang benar
n
sehinggaF(n) = input
.-a
switch menambahkan satu byte.Coba di sini!
sumber
J,
322717 byteMenghitung angka Fibonacci n pertama dan kemudian menemukan indeks n dalam daftar itu.
Pemakaian
Perintah tambahan digunakan untuk memformat beberapa input / output. Kasing uji terakhir dihilangkan karena akan membutuhkan lebih banyak waktu untuk menghitung.
Penjelasan
sumber
Mathematica, 30 byte
Fungsi murni; mengembalikan 2 jika inputnya 1.
Tidak mengalahkan entri Mathematica lainnya, tetapi menampilkan metode yang tidak biasa: Ini fakta (sangat keren) bahwa angka Fibonacci N adalah bilangan bulat terdekat dengan [1 / sqrt (5) kali kekuatan N dari rasio emas] (" Rumus Binet ").
Oleh karena itu fungsi invers akan menjadi basis- [rasio emas] logaritma [sqrt (5) kali angka Fibonacci yang dimaksud]. Ini
.8+
adalah hack untuk memastikan kita tidak mengambil logaritma 0, tanpa mengacaukan nilai-nilai lainnya.sumber
Japt , 10 byte
Cobalah online!
Penjelasan
sumber
Brachylog , 14 byte
Cobalah online!
Mengambil input melalui variabel output dan output melalui variabel input.
Saya tidak sepenuhnya yakin mengapa
≜
itu perlu.sumber
Javascript (menggunakan perpustakaan eksternal) (84 byte)
Tautan ke lib: https://github.com/mvegh1/Enumerable
Penjelasan kode: Perpustakaan memiliki metode statis yang membuat urutan hingga predikat memiliki nilai balik yang tidak ditentukan. Predikat memiliki tanda tangan ("i" ndex, internal "a" rray yang dihasilkan). Pada setiap iterasi, kami memeriksa apakah elemen terakhir dari array internal sama dengan input, n. Jika tidak, kembalikan nilai berikutnya dalam urutan fib. Jika tidak, predikat memiliki hasil yang tidak ditentukan yang mengakhiri pembuatan urutan. Kemudian, kami mengembalikan panjang urutan (dan mengurangi 1 untuk mematuhi 0-ness berbasis seperti yang terlihat dalam OP
sumber
n=>{a=c=t=0,b=1;while(a<n){c++;t=b;b+=a;a=t}return c}
Coba online!