Apakah saya Angka Fibonacci?

49

Tugas Anda:

Tulis program atau fungsi untuk memeriksa apakah angka yang dimasukkan adalah angka Fibonacci . Angka Fibonacci adalah angka yang terkandung dalam urutan Fibonacci.

Fibonacci Sequence didefinisikan sebagai: F(n) = F(n - 1) + F(n - 2)

Dengan benih sedang F(0) = 0dan F(1) = 1.

Memasukkan:

Integer non-negatif antara 0 dan 1.000.000.000 yang mungkin atau mungkin bukan angka Fibonacci.

Keluaran:

Nilai kebenaran / kepalsuan yang menunjukkan apakah input adalah angka Fibonacci atau tidak.

Contoh:

0-->truthy
1-->truthy
2-->truthy
12-->falsy

Mencetak:

Ini adalah , kemenangan jumlah byte terendah.

Gryphon - Pasang kembali Monica
sumber
2
Bahasa pemrograman yang saya gunakan hanya mendukung angka hingga 9999 (Geometry Dash). Apakah saya boleh jika saya berasumsi bahwa itu mendukung angka hingga 1000000, secara teori?
MilkyWay90

Jawaban:

36

Neim , 2 byte

f𝕚

Penjelasan:

f       Push an infinite fibonacci list
 𝕚      Is the input in that list?

Bekerja sama seperti itu Hip saya menjadi jawaban Square , tetapi menggunakan daftar infinite yang berbeda:, funtuk fibonacci.

Cobalah!

Okx
sumber
1
Wow! Skor mengesankan.
Gryphon - Reinstate Monica
2
Itu bagus, tapi bukan 2 byte. Dalam UTF-8 diwakili sebagai "66 F0 9D 95 9A"
sm4rk0
10
@ sm4rk0 Bagus sekali, tapi Anda salah. Neim menggunakan codepage khusus , jadi representasi byte dari ini adalah66 D5
Okx
Tidakkah loop ini selamanya jika inputnya tidak ada dalam daftar? Jika demikian, apakah itu dianggap sebagai falsey?
Enrico Borba
@EnricoBorba Neim tahu bahwa elemen ke-n dalam daftar tanpa batas ini akan selalu sama dengan atau kurang dari elemen ke-1 dalam daftar. Karena itu, ia dapat menangkap dirinya sendiri dan tidak akan berjalan selamanya. Sudahkah Anda mencoba programnya? : P
Okx
18

JavaScript (ES6), 34 byte

f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

Secara rekursif menghasilkan urutan Fibonacci hingga menemukan item lebih besar dari atau sama dengan input, lalu mengembalikan item == input.

Produksi ETH
sumber
NB: perhitungan rekursif naif dari deret Fibonacci adalah O (Fib (n)) - sekitar O (1,6 ^ n)
Alnitak
f = n => n? n> 2? f (n-1) + f (n-2): 1: 0 28bytes
jackkav
@ jackkav Terima kasih, tetapi tantangannya adalah untuk menentukan apakah input adalah angka Fibonacci.
ETHproduksi
12

Retina , 23 byte

^$|^(^1|(?>\2?)(\1))*1$

Cobalah online!

Input di unary, output 0atau 1.

Penjelasan

Urutan Fibonacci adalah kandidat yang baik untuk solusi dengan referensi ke depan, yaitu "backreference" yang merujuk baik ke kelompok sekitarnya atau yang muncul kemudian di regex (dalam hal ini, kami sebenarnya menggunakan keduanya). Saat mencocokkan angka seperti ini, kita perlu mencari tahu ekspresi rekursif untuk perbedaan antara elemen urutan. Misalnya, untuk mencocokkan angka segitiga, kami biasanya cocok dengan segmen sebelumnya ditambah satu. Untuk mencocokkan angka kuadrat (yang perbedaannya adalah angka ganjil), kami cocok dengan segmen sebelumnya ditambah dua.

Karena kita memperoleh angka-angka Fibonacci dengan menambahkan elemen kedua-ke-terakhir ke yang terakhir, perbedaan di antara mereka juga hanya angka-angka Fibonacci. Jadi kita harus mencocokkan setiap segmen sebagai jumlah dari dua segmen sebelumnya. Inti dari regex adalah ini:

(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

Sekarang ini berakhir sampai menambah angka Fibonacci mulai dari 1 , yaitu 1, 1, 2, 3, 5, ... . Mereka add sampai dengan 1, 2, 4, 7, 12, ... . Yaitu mereka satu kurang dari angka Fibonacci, jadi kami menambahkan 1di akhir. Satu-satunya kasus ini tidak mencakup adalah nol, jadi kami memiliki ^$alternatif di awal untuk membahas itu.

Martin Ender
sumber
2
Sangat elegan! Saya hanya ingin menunjukkan, demi kelengkapan, bahwa itu dapat dipersingkat menjadi 20 byte di PCRE menggunakan quantifier posesif:^$|^(^1|\2?+(\1))*1$
Deadcode
1
@Deadcode Saya sangat merindukan mereka dalam. NET;)
Martin Ender
Hemat 1 byte dengan menghapus yang tidak perlu kedua ^.
Neil
12

Regex (ECMAScript flavour), 392 358 328 224 206 165 byte

Teknik-teknik yang perlu ikut bermain untuk mencocokkan angka Fibonacci dengan regex ECMAScript (dalam unary) jauh dari cara terbaik dilakukan dalam kebanyakan rasa regex lainnya. Kurangnya referensi atau rekursi maju / bersarang berarti bahwa tidak mungkin untuk secara langsung menghitung atau menjaga total apa pun yang berjalan. Kurangnya tampilan membuatnya sering menjadi tantangan bahkan untuk memiliki cukup ruang untuk bekerja.

Banyak masalah harus didekati dari perspektif yang sama sekali berbeda, dan tampaknya tidak dapat diatasi sampai kedatangan beberapa wawasan kunci. Ini memaksa Anda untuk menggunakan jaring yang jauh lebih luas dalam menemukan properti matematika mana dari angka-angka yang Anda kerjakan yang mungkin dapat digunakan untuk membuat masalah tertentu dapat dipecahkan.

Pada bulan Maret 2014, inilah yang terjadi untuk angka Fibonacci. Melihat halaman Wikipedia, pada awalnya saya tidak bisa menemukan jalan, meskipun satu properti tertentu tampak sangat menggoda. Kemudian teukon matematik menguraikan metode yang membuatnya cukup jelas akan mungkin dilakukan, menggunakan properti itu bersama dengan yang lain. Dia enggan untuk benar-benar membangun regex. Reaksinya ketika saya melanjutkan dan melakukannya:

Kamu gila! ... Saya pikir Anda mungkin melakukan ini.

Seperti posting ECMAScript regex matematika unary saya yang lain, saya akan memberikan peringatan: Saya sangat merekomendasikan belajar bagaimana menyelesaikan masalah matematika unary di ECMAScript regex. Ini merupakan perjalanan yang menarik bagi saya, dan saya tidak ingin merusaknya bagi siapa pun yang mungkin ingin mencobanya sendiri, terutama mereka yang tertarik pada teori bilangan. Lihat posting itu untuk daftar masalah yang direkomendasikan untuk ditandai dengan spoiler bertanda satu per satu.

Jadi jangan membaca lebih jauh jika Anda tidak ingin beberapa sihir regex unary dimanjakan untuk Anda . Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan menyelesaikan beberapa masalah dalam ECMAScript regex sebagaimana diuraikan dalam pos yang ditautkan di atas.

Tantangan yang awalnya saya hadapi: Bilangan bulat positif x adalah angka Fibonacci jika dan hanya jika 5x 2 + 4 dan / atau 5x 2 - 4 adalah kuadrat sempurna. Tetapi tidak ada ruang untuk menghitung ini dalam suatu regex. Satu-satunya tempat kita harus bekerja adalah angka itu sendiri. Kami bahkan tidak memiliki cukup ruang untuk mengalikan dengan 5 atau mengambil kuadrat, apalagi keduanya.

ide teukon tentang bagaimana menyelesaikannya ( awalnya diposting di sini ):

Regex disajikan dengan string bentuk ^x*$, misalkan z menjadi panjangnya. Periksa apakah z adalah salah satu dari beberapa angka Fibonacci pertama dengan tangan (hingga 21 harus dilakukan). Jika tidak:

  1. Baca beberapa angka, a <b, sehingga b tidak lebih besar dari 2a.
  2. Gunakan maju melihat ke depan untuk membangun 2 , ab, dan b 2 .
  3. Tegaskan bahwa 5a 2 + 4 atau 5a 2 - 4 adalah kuadrat sempurna (jadi a harus F n-1 untuk beberapa n).
  4. Tegaskan bahwa 5b 2 + 4 atau 5b 2 + 4 adalah kuadrat sempurna (jadi b harus F n ).
  5. Periksa bahwa z = F 2n + 3 atau z = F 2n + 4 dengan menggunakan yang sebelumnya dibangun a 2 , ab, dan b 2 , dan identitas:
    • F 2n-1 = F n 2 + F n-1 2
    • F 2n = (2F n-1 + F n ) F n
Singkatnya: identitas ini memungkinkan kita untuk mengurangi masalah memeriksa bahwa angka yang diberikan adalah Fibonacci untuk memeriksa bahwa sepasang angka yang jauh lebih kecil adalah Fibonacci. Aljabar kecil akan menunjukkan bahwa untuk n yang cukup besar (n = 3 seharusnya dilakukan), F 2n + 3 > F n + 5F n 2 + 4 sehingga harus selalu ada ruang yang cukup.

Dan di sini adalah mockup dari algoritma di C yang saya tulis sebagai tes sebelum mengimplementasikannya di regex.

Jadi tanpa basa-basi lagi, inilah regex:

^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$

Cobalah online!

Dan versi komentar yang dicetak cantik:

^(
  (?=
    (x*)                   # \2+1 = potential number for which 5*(\2+1)^2 ± 4
                           # is a perfect square; this is true iff \2+1 is a Fibonacci
                           # number. Outside the surrounding lookahead block, \2+1 is
                           # guaranteed to be the largest number for which this is true
                           # such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
    .*
    (?=                    # tail = (\2+1) * (\2+1) * 5 + 4
      x{4}
      (                    # \3 = (\2+1) * 5
        x{5}
        (\2{5})            # \4 = \2 * 5
      )
      (?=\3*$)
      \4+$
    )
    (|x{4})                # \5 = parity - determined by whether the index of Fibonacci
                           #               number \2+1 is odd or even
    (?=xx (x*)(\6 x?))     # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
                           #      divided by 2
                           # \7 = the other half, including remainder
    \5
    # require that the current tail is a perfect square
    (x(x*))                # \8 = potential square root, which will be the square root
                           #      outside the surrounding lookahead; \9 = \8-1
    (?=(\8*)\9+$)          # \10 = must be zero for \8 to be a valid square root
    (?=\8*$\10)
    \8*
    (?=(x\2\9+$))          # \11 = result of multiplying \8 * (\2+1), where \8 is larger
    (x*)\12                # \12 = \11 / 2; the remainder will always be the same as it
                           #       is in \7, because \8 is odd iff \2+1 is odd
  )
  \7\11
  (
    \6\11
  |
    \12
  )
|
  x{0,3}|x{5}|x{8}|x{21}   # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

Algoritma multiplikasi tidak dijelaskan dalam komentar-komentar itu, tetapi dijelaskan secara singkat dalam paragraf posting regex angka saya yang berlimpah .

Saya mempertahankan enam versi berbeda dari regex Fibonacci: empat ratchet dari panjang terpendek ke kecepatan tercepat dan menggunakan algoritma yang dijelaskan di atas, dan dua lainnya yang menggunakan algoritma yang berbeda, jauh lebih cepat tetapi jauh lebih panjang, yang seperti yang saya temukan sebenarnya dapat kembali indeks Fibonacci sebagai pertandingan (menjelaskan bahwa algoritma di sini berada di luar cakupan posting ini, tetapi dijelaskan dalam Gist diskusi asli ). Saya tidak berpikir saya akan mempertahankan versi regex yang sangat mirip lagi, karena pada saat itu saya sedang melakukan semua pengujian di PCRE dan Perl, tetapi mesin regex saya cukup cepat sehingga masalah kecepatan tidak lagi penting (dan jika konstruk tertentu menyebabkan kemacetan, saya dapat menambahkan pengoptimalan untuk itu) - walaupun saya mungkin akan mempertahankan satu versi tercepat dan satu versi terpendek, jika perbedaannya dalam kecepatan cukup besar.

Versi "mengembalikan indeks Fibonacci minus 1 sebagai kecocokan" (tidak banyak golf):

Cobalah online!

Semua versi ada di github dengan riwayat komit penuh optimasi golf:

regex untuk pencocokan angka Fibonacci - pendek, kecepatan 0.txt (yang terpendek tetapi paling lambat, seperti dalam posting ini)
regex untuk pencocokan angka Fibonacci - pendek, kecepatan 1.txt
regex untuk pencocokan angka Fibonacci - pendek, kecepatan 2.txt
regex untuk pencocokan angka Fibonacci - pendek, kecepatan 3.txt
regex untuk mencocokkan angka Fibonacci - regex tercepat.txt
untuk mencocokkan angka Fibonacci - return index.txt

Kode mati
sumber
9

Python 3 , 48 byte

lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

Cobalah online!

Dennis
sumber
1
Menjadi Python seharusnya tidak bekerja, diberi sumber daya yang cukup, untuk input besar yang sewenang-wenang?
Jonathan Allan
2
Saya selalu memiliki kesan kami dapat menggunakan algoritma apa pun yang kami inginkan selama itu, karena ia bekerja dalam praktik jika perhitungannya sesuai dengan tipe data dan dalam teori diberikan ketelitian tak terbatas. Tentu saja, menggunakan hanya intakan mengatur bilah lebih tinggi (masih tidak besar sembarang), tetapi kami juga tidak memaksa jawaban C untuk menggunakan bilangan bulat 64-bit (atau 128-bit dengan gcc). Bagaimanapun, diizinkan untuk menggunakan algoritma yang sama dalam satu bahasa tetapi tidak yang lain tampaknya tidak masuk akal.
Dennis
Tampilan algoritmik memang masuk akal (saya selalu berpikir itu adalah domain input yang menentukan kriteria "fit in tipe data"). Satu-satunya hal yang harus diperhatikan adalah area abu-abu antara apa ide dari algoritma dan implementasinya. Di sini orang dapat memeriksa apakah salah satu bilangan bulat persegi tanpa casting ke float. Saya kira pemeran internal sebagai efek samping dapat diterima asalkan merupakan bagian dari algoritma yang sah dan berfungsi (... dan saya cukup yakin bahwa algoritma yang mengandalkan pemeran tidak akan dapat diterima).
Jonathan Allan
@ JonathanAllan Karena nilai maksimum untuk menangani adalah 1e9, saya tidak berpikir input besar sembarang akan menjadi masalah.
JAD
1
@JarkoDubbeldam ya, detail itu benar-benar berubah setelah komentar saya dibuat.
Jonathan Allan
7

Python 2, 48 44 byte

f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

Cobalah online

Terima kasih kepada Jonathan Allan karena telah menghemat 4 byte

mbomb007
sumber
Ini bisa menjadi 47 byte, jika nilai kebenaran bisa Falsedan nilai salah True: TIO!
Tn. Xcoder
Bisa juga digunakan n-asebagai pengganti n==adan memiliki -1 dan 0 sebagai nilai pengembalian Anda.
Magic Gurita Guci
@caruscomputing saya memiliki itu dalam riwayat edit saya, tetapi tidak berhasil, karena untuk nilai tes yang lebih besar, Anda mungkin memiliki -101atau beberapa hasil lainnya sebagai gantinya -1.
mbomb007
@ Mr.Xcoder apakah Anda benar-benar berpikir bahwa menabung 1 byte bernilai kewarasan semua orang?
frarugi87
1
@ frarugi87 Menyimpan byte selalu sepadan
Tn. Xcoder
7

05AB1E , 8 7 byte

>ÅF¹å¹m

Penjelasan:

>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

Cobalah online!

-1 terima kasih kepada Jonathan Allan untuk solusi 0-bukan-fibonacci-nomor.

Guci Gurita Ajaib
sumber
Sebenarnya, tidak akan memperbarui ke 6 byte. Tidak percaya TIDAK ada cara untuk menambahkan 0 ke daftar di bawah 3 byte.
Magic Gurita Guci
@JonathanAllan "menghasilkan fungsi fibbonacci" di 05AB1E tidak mengandung 0.
Magic Octopus Mm
@ Jonathan Allan Saya mengerti sekarang, ide bagus. Butuh waktu sebentar untuk mencari tahu apa yang sebenarnya terjadi di sana.
Magic Gurita Guci
Bukankah itu cukup untuk menghasilkan upto n(menyimpan byte) seperti ÅFinklusif dan ¹åakan menghasilkan apa pun 0untuk n=0?
Emigna
0AF = []. 1AF = [1,1]. Jadi rupanya tidak.
Magic Gurita Guci
5

Perl 6 , 23 byte

{$_∈(0,1,*+*...*>$_)}
Sean
sumber
{(0,1,*+*...^*>$_).tail==$_}adalah apa yang akan saya posting pada awalnya. Saya mungkin sempat untuk mengatur operator pada akhirnya.
Brad Gilbert b2gills
5

Serius , 3 byte

,fu

Cobalah online!

Mengembalikan indeks +1 dalam daftar angka Fibonacci jika benar, jika tidak mengembalikan falsy.

Penjelasan:

,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)
Kamerad SparklePony
sumber
9
Serius kasar ^^
Jonathan Allan
5

Jelly ,  8 7  6 byte

-r‘ÆḞċ

Cobalah online!

Bagaimana?

-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

Catatan:

  • kenaikan tersebut, , diperlukan agar karya ini untuk 2 dan 3 , karena mereka adalah 3 rd dan 4 th nomor Fibonacci - melampaui 3 semua nomor Fibonacci lebih besar dari indeks mereka.
  • yang -diperlukan (bukan hanya ‘R) sehingga karya ini untuk 0 karena 0 adalah 0 th nomor Fibonacci;
Jonathan Allan
sumber
Umm, ini kelihatannya seperti jawabanku ...
Erik the Outgolfer
Oh, saya pindahkan milik saya ke milik Anda, kecuali milik saya bekerja untuk 3:)
Jonathan Allan
Astaga ... Fibonacci itu aneh. (btw menghapus jawaban saya maka jika Anda bilang begitu)
Erik the Outgolfer
Anda yakin dengan nada terakhir itu? Ketika saya menjalankan atom Fibonacci pada daftar mulai dari 0, 0 termasuk dalam output.
Sebar
1
Tampaknya tidak relevan berdasarkan kata-kata dari tantangan, tetapi jika Anda menggunakan atom hitungan dengan 1 sebagai argumen Anda pada daftar angka-angka Fibonacci hasilnya 2 (bukan 1).
FryAmTheEggman
5

ZX81 BASIC 180 151 100 ~ 94 byte BASIC tokenized

Dengan terima kasih kepada Moggy di forum SinclairZXWorld, berikut ini adalah solusi yang jauh lebih rapi yang menghemat lebih banyak byte.

 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

Ini akan menghasilkan 1 jika angka Fibonacci dimasukkan, atau nol jika tidak. Meskipun ini menghemat byte, ini jauh lebih lambat daripada solusi lama di bawah ini. Untuk kecepatan (tetapi lebih banyak byte BASIC), lepaskan VALpembungkus di sekitar angka literal string. Inilah solusi lama dengan beberapa penjelasan:

 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

Amandemen di atas menyimpan byte BASIC lebih lanjut untuk mengkondensasi IFpernyataan menjadi satu PRINTbaris 12; byte lainnya disimpan dengan menggunakan VALkata kunci dan, dan menggunakan GOTO CODE "£", yang dalam set karakter ZX81 adalah 12. String menyimpan lebih banyak byte atas angka karena semua nilai numerik disimpan sebagai float sehingga mengambil lebih banyak ruang di tumpukan VAR.

masukkan deskripsi gambar di sini

Shaun Bebbers
sumber
Sebenarnya, saya bisa menyimpan 6 byte BASIC tokenized lainnya dengan menghapus baris 6 sama sekali dan mengubah baris 5 ke 5 IF R<F THEN NEXT I- buruk saya!
Shaun Bebbers
4

C #, 109 byte

bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

Pasti bisa ditingkatkan, tetapi saya tidak punya waktu.

Kaito Kid
sumber
Selamat datang di PPCG!
Martin Ender
1
Saya menulis jawaban saya sendiri hanya untuk menyadari bahwa itu sama dengan Anda. Anda dapat menggunakan ekspresi lambda dan variabel sederhana untuk mendapatkan ini: n=>{int a=0,b=1,c=0;while(a<n&b<n)if(++c%2>0)a=a+b;else b=a+b;return a==n|b==n;}(hanya 80 byte). Cobalah online!
Charlie
1
@CarlosAlejo Menyimpan 2 byte lebih lanjut dengan itu a+=balih - alih a=a+bdan b+=abukannya b=a+b.
TheLethalCoder
4

> <> , 21 19 + 3 = 24 22 byte

i1\{=n;
?!\:@+:{:}(

Input diharapkan berada di stack saat program dimulai, jadi +3 byte untuk -vflag.

Cobalah online!

Ini bekerja dengan menghasilkan angka-angka Fibonacci sampai lebih besar atau sama dengan angka input, kemudian memeriksa angka yang dihasilkan terakhir untuk kesetaraan dengan input. Output 1jika itu adalah angka Fibonacci,0 jika tidak.

Untuk memastikan bahwa 0ditangani dengan benar, seed adalah -1 1- angka pertama yang dihasilkan akan 0lebih daripada 1.

Terima kasih kepada @cole untuk menunjukkan bahwa idapat digunakan untuk mendorong -1ke stack ketika STDIN kosong. Sangat pintar!

Versi sebelumnya:

01-1\{=n;
}(?!\:@+:{:
Sok
sumber
Sekarang saya merasa bodoh karena membuang byte secara terus menerus memeriksa setiap nomor yang dihasilkan di sepanjang jalan. Bagus sekali!
Emigna
1
22 byte menggunakan ibukan 01-.
cole
@cole tentu saja, menggunakan iseperti -1ketika tidak ada input ke STDIN, saya tidak akan mempertimbangkan itu. Bagus sekali!
Sok
3

Mathematica, 37 byte

!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

-4 byte dari @ngenisis

J42161217
sumber
Fibonacci[0]memberi 0, sehingga Anda dapat menyimpan 4byte dengan memasukkan 0dalam Tablekisaran. Anda dapat menyimpan byte lain menggunakan notasi infiks untuk Table:!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&
ngenisis
3

MATL (16 byte)

2^5*4-t8+hX^tk=s

Cobalah online!

Bukan solusi golf, tetapi ingin menggunakan metode langsung memeriksa apakah "5 * x ^ 2 +/- 4" adalah kotak yang sempurna .

Penjelasan:

2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

catatan:

Dalam kasus "0" ia mengembalikan "2" karena baik 4 dan -4 adalah kuadrat sempurna, sama dengan 1 yang menghasilkan "1 1". Anggap output non-nol sebagai "benar", dan 0 sebagai "palsu".

DrQuarius
sumber
3

PHP , 44 byte

for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

Cobalah online!

PHP , 58 byte

for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

Cobalah online!

Jörg Hülsermann
sumber
2
Golfed lebih: for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;.
user63956
@ user63956 Terima kasih atas upaya pembelajaran dengan tugas variabel chaining
Jörg Hülsermann
3

Java, 72 69 68 63 59 55 50 49 byte

n->{int a=0,b=1;for(;a<n;a=b-a)b+=a;return a==n;}

Uji sendiri!

Alternatif (masih 49 byte)

n->{int a=0,b=1;for(;a<n;b=a+(a=b));return a==n;}

Tidak terlalu orisinal: ini versi iteratif yang polos dan dasar.

Ini berfungsi untuk angka hingga 1,836,311,903 (nomor fibonacci ke-47) disertakan. Di atas itu, hasilnya tidak terdefinisi (termasuk loop infinite potensial).

Terima kasih kepada Kevin Cruijssen dan David Conrad karena membantu bermain golf :)

Olivier Grégoire
sumber
1
Pendekatan yang bagus. Btw, Anda dapat golf byte dengan mengubah n==0ke n<1. Dalam pertanyaan itu menyatakan " Bilangan bulat non-negatif antara 0 dan 1.000.000.000 ".
Kevin Cruijssen
1
@KevinCruijssen Saya bermain golf bukan 1, tetapi 5 byte dengan klausa itu! :-P Terima kasih, saya tidak menyadarinya.
Olivier Grégoire
2
Anda tidak perlu variabel temp untuk urutan Fibonacci. Anda dapat menghitung pasangan berturut-turut denganb+=a;a=b-a;
David Conrad
1
Anda melakukan ilmu hitam, @DavidConrad! Aku beritahu padamu! Sihir hitam! :)
Olivier Grégoire
3

C # (.NET Core) , 51 byte

bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

Cobalah online!

-6 byte terima kasih kepada @Oliver!

Solusi ini menggunakan fungsi rekursif yang cukup mudah.

  • Variabelnya nadalah angka yang akan diuji.
  • Variabel adan bmerupakan 2 angka terbaru dalam urutan.
  • Cek apakah yang pertama dari 2 angka terakhir kurang dari input. Ketika hal ini terjadi, panggilan rekursif dilakukan ke nomor berikutnya dalam seri.
  • Jika tidak, periksa apakah angka pertama sama dengan input dan kembalikan hasilnya.

TIO link menunjukkan ini berfungsi untuk 1134903170 yang melebihi nilai maksimum yang dibutuhkan oleh tantangan.

dana
sumber
Sangat menyenangkan melihat solusi C # belakangan ini :) - Saya pikir Anda dapat memeriksa apakah a<nuntuk 51 byte
Oliver
Terima kasih! Dan tip yang bagus :)
dana
3

Alchemist , 205 134 byte

Terima kasih besar kepada ASCII-only untuk penggabungan yang agak pintar, menghemat 71 byte !!

_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

Cobalah secara online atau verifikasi dalam batch!

Tidak disatukan

# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop
ბიმო
sumber
139 . Anda dapat menghapus beberapa 0cek untuk byte lebih sedikit dengan biaya nondeterminisme
ASCII-satunya
129
ASCII
@ Khusus ASCII: Cukup bagus! Gagal untuk 0, tetapi tidak menambahkan b-atom pada perbaikan inisialisasi itu (dan menyimpan 2 byte): D Terima kasih
ბიმო
2

Jelly , 5 byte

ȷḶÆḞi

Cobalah online!

Mengembalikan 0 untuk angka-angka non-Fibonacci, dan posisi 1-diindeks dari angka dalam urutan Fibonacci untuk angka-angka Fibonacci.

Penjelasan:

ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found
menyebarkan
sumber
Tidak bekerja untuk 0.
Okx
@ComradeSparklePony Anda yakin? Itu bekerja untuk saya.
berhamburan
1
Tidak bekerja untuk 0 atau sesuatu yang lebih besar dari 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
Erik yang Outgolfer
1
@ Mr.Xcoder Konsensus umum adalah bahwa Anda harus dapat menangani apa yang didukung datatype alami Anda, dan Jelly mendukung bilangan bulat presisi-sewenang-wenang.
Erik the Outgolfer
1
Masih tidak bekerja untuk apa pun lebih 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626.
Erik yang Outgolfer
2

Dyalog APL, 17 byte

0∊1|.5*⍨4 ¯4+5××⍨

Cobalah online!

Uriel
sumber
2

R, 43 40 byte

pryr::f(x%in%DescTools::Fibonacci(0:45))  

pryr::f menciptakan fungsi:

function (x) 
x %in% DescTools::Fibonacci(0:45)

Menggunakan DescTools::Fibonacciuntuk membuat x+1angka-angka fibonacci pertama dan memeriksa untuk dimasukkan.x+1karena fibnum ketiga adalah 2, dan itu tidak akan cukup untuk memeriksa dimasukkannya 3.

Untungnya Desctools::Fibonacci(0)=0, itu adalah freebee yang bagus.

-3 byte terima kasih kepada MickyT

JAD
sumber
-1:x+1akan menghemat satu byte, tetapi 0:45akan menghemat tiga dan mencakup rentang yang diperlukan
MickyT
@MickyT Oh, saya pasti mengabaikan spesifikasi rentang yang diperlukan. Terima kasih :)
JAD
Sebuah pendekatan alternatif, hanya 36 byte: pryr::f(any(!(5*n^2+c(-4,4))^.5%%1)).
rturnbull
Saya mendapatkannya hingga 32 byte, lihat di sini .
rturnbull
Saya tidak begitu terbiasa dengan aturan kode golf - apakah mengizinkan paket non-basis masuk akal? Saya bisa menulis kode R sewenang-wenang ke dalam sebuah paket, menginstalnya, dan menjalankannya dengan cara yang sama seperti Anda menjalankan fungsinya pryr.
mb7744
2

Haskell , 31 byte

f=0:scanl(+)1f
(`elem`take 45f)

Cobalah online! Ini mengeksploitasi fakta bahwa input akan berada dalam kisaran 0 hingga 1.000.000.000, maka kita perlu memeriksa hanya 45 angka Fibonacci pertama. f=0:scanl(+)1fmenghasilkan daftar angka Fibonacci yang tak terbatas,take 45f adalah daftar 45 angka Fibonacci pertama dan elemmemeriksa apakah input ada dalam daftar ini.


Versi tidak terbatas: 36 byte

f=0:scanl(+)1f
g n=n`elem`take(n+3)f

Cobalah online! Untuk apa pun n, ambil yang pertaman+3 angka Fibonacci akan menjamin itun akan ada dalam daftar ini jika itu adalah nomor Fibonacci.

Perhatikan bahwa pendekatan ini luar biasa tidak efisien untuk angka tinggi yang bukan angka Fibonacci, karena semua n+3angka Fibonacci perlu dihitung.

Laikoni
sumber
2

Javascript (ES6 tanpa operator **), 44 byte

f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

Bergantung pada rasio antara angka Fibonacci berturut-turut mendekati rasio emas. Nilai c adalah bagian fraksional dari input dibagi dengan rasio emas - jika inputnya adalah Fibonacci maka ini akan sangat dekat dengan 1 dan nilai c-c² akan sangat kecil.

Tidak sesingkat beberapa jawaban JS lainnya tetapi berjalan dalam O (1) waktu.

HP Williams
sumber
Apakah Anda yakin itu tepat?
user259412
Tidak berfungsi untuk nomor fibonacchi 16558014
Black Owl Kai
2

Julia 0,4 , 29 byte

!m=in(0,sqrt(5*m*m+[4,-4])%1)

Cobalah online!


Jika ini bukan bagaimana Anda melakukan jawaban Julia, beri tahu saya. Saya tidak yakin bagaimana input bekerja pada TIO.

Guci Gurita Ajaib
sumber
1
Anda harus menjadikannya fungsi biasa (menghitung !m=) atau lambda (menghitung m->). Lebih penting lagi, ini gagal untuk 0 apa adanya.
Dennis
2

R, 32 31 byte

Mengambil input dari stdin, mengembalikan TRUEatau FALSEjika perlu.

any(!(5*scan()^2+-1:1*4)^.5%%1)
rturnbull
sumber
2

Common Lisp, 61 54 byte

(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

Cobalah online!

Pengurangan ukuran sehubungan dengan versi sebelumnya:

(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

dipicu oleh gagasan bahwa untuk menghasilkan urutan angka Fibonacci hanya diperlukan dua variabel, bukan tiga.

Renzo
sumber
1

Mathematica, 33 byte

AtomQ@*InverseFunction[Fibonacci]
J42161217
sumber
Anda dapat menyimpan beberapa byte dengan @*(dan kemudian menjatuhkan final @#&)
Martin Ender
1

JS (ES6), 57 byte

n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))

Menggunakan metode carusocomputing . Banyak pegolf daripada jawaban saya yang lain .

Tidak disatukan

n=>{
    y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
    return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}

sumber