Tantangan
Anda perlu membuat program atau fungsi yang mengambil dalam bilangan bulat positif N, menghitung persyaratan N pertama dari urutan Fibonacci dalam biner, menggabungkannya menjadi angka biner tunggal, mengonversi angka itu kembali ke desimal, dan kemudian mengeluarkan desimal sebagai sebuah bilangan bulat.
Sebagai contoh
1 -> [0] -> 0 to decimal outputs 0
3 -> [0, 1, 1] -> 011 to decimal outputs 3
4 -> [0, 1, 1, 10] -> 01110 to decimal outputs 14
Anda tidak perlu menampilkan ->
, hanya nomornya (mis. Jika pengguna mengetik4
, cukup keluaran 14
). Panah hanya untuk membantu menjelaskan apa yang harus dilakukan program.
Uji kasus
1 -> 0
2 -> 1
3 -> 3
4 -> 14
5 -> 59
6 -> 477
7 -> 7640
8 -> 122253
9 -> 3912117
10 -> 250375522
11 -> 16024033463
12 -> 2051076283353
13 -> 525075528538512
14 -> 134419335305859305
15 -> 68822699676599964537
16 -> 70474444468838363686498
17 -> 72165831136090484414974939
18 -> 147795622166713312081868676669
19 -> 605370868394857726287334099638808
20 -> 4959198153890674493745840944241119317
Program harus dapat menampilkan hingga batas bahasa yang digunakan. Tidak ada tabel pencarian atau solusi umum diizinkan.
Ini kode-golf , jadi jawabannya dengan jumlah byte terpendek menang!
int32_t binary_concat_Fib(int n)
, yang akan membatasi nilai output yang dihasilkan menjadi 2 ^ 31-1. yaitu Anda bisa mengasumsikan semua bit gabungan cocok dalam bilangan bulat. Atau haruskah fungsi bekerja sampai pada titik di mana angka Fibonacci terbesar tidak muat dalam bilangan bulat sendiri, jadi menggabungkan bit membutuhkan presisi yang diperluas?Jawaban:
Python, 64 bytes
Try it online!
sumber
Jelly,
76 bytesTry it online!
How?
sumber
Ṛc’SƲƤ
which could be useful for similar sequences.Python 3.6, 61 bytes
Try it online!
sumber
brainfuck, 397 bytes
Well, that was fun!
Takes ASCII input (e.g.
11
), outputs result in ASCII.Note: to try this online, make sure you set the cell size to 32 bits (on the right side of the webpage). If you do not enter an input, your browser might crash.
The interpreter cannot handle input of
11
and higher because it only supports up to 32 bits.Try it on copy.sh
Explanation
Get decimal input and add one (to mitigate off-by-one)
Generate fibonacci numbers on the tape.
Set up for the incoming binary concatenation loop
So the cells contain the value, starting from the first position,
Look at these cells:
I'll label this:
pow
is there to find the maximal power of 2 that is strictly greater thannum
.sum
is the concatenation of numbers so far.cat
is the power of 2 that I would need to multiply thenum
in order to concatenatenum
in front of thesum
(so I would be able to simply add).Loop: Check whether
f_n
is strictly less thanpow
.Truthy:
Zero out junk. Then, add
num
*cat
tosum
. Next, load the next Fibonacci number (=f_(n-1)
; if it doesn't exist, exit loop) and setcat
tocat
*pow
. Prepare for next loop (zero out more junk, shift scope by one).Falsey:
Set
pow
to 2 *pow
, restorenum
.Repeat until there is no Fibonacci number left.
Clean garbage. Take each digit of the resulting number and output each (in ascii).
sumber
Husk, 7 bytes
Try it online!
Explanation
sumber
Japt, 9 bytes
Run it
Explanation:
sumber
Pyth, 22 bytes
Try it here
Explanation
sumber
Perl 6, 38 bytes
Try it online!
sumber
JavaScript (Node.js),
7065585755 bytesTry it online!
sumber
-0
at the end to save another 2 bytes.05AB1E, 6 bytes
Try it online!
1-indexed.
sumber
J, 36 Bytes
Explanation:
sumber
x86,
372221 bytesChangelog
bsr
. Thanks Peter Cordes!-2 by zeroing registers with
mul
.-1 by using a while loop instead of
loop
andpush
/pop
ecx
(credit Peter Cordes).Input in
edi
, output inedx
.Objdump:
sumber
lea
to shift-and-add in fib2. Also, extracting each bit one at a time is unnecessary. Usebsr %eax, %ecx
to find the number of bits in the binary representation, and use a shift by CL / or to merge, like Dennis's Python answer is doing.cl
for shift counts, so take your loop counter in a different reg (like%edi
) and usedec %edi / jnz
(3 bytes in 32-bit code, 4 bytes in 64-bit). In 32-bit code, that saves 1 byte total from dropping the push/pop ecx. Don't fall into the trap of usingloop
when it makes the problem harder, not easier. (Your calling convention is already custom, clobbering%ebx
, so don't call your functionmain
) You might be able to return in EAX while still taking advantage of 1-bytexchg
, no need to be non-standard if you don't need to.inc %ecx
of the shift count with an extra left-shift as you add, usinglea (%eax, %edx, 2), %edx
. Neutral in bytes for 32-bit, saves one for x86-64. But saves an instruction.loop
in code golf, I feel dirty. Well not quite, but disappointed that I couldn't find an equally small implementation that avoided that slow instruction; outside of code golf,loop
is one of my pet peeves. I wish it was fast on modern CPUs, because it would be very nice for extended-precision loops without partial-flag stalls, but it's not and should be considered only as an obscure size optimization instruction that makes your code slow.xor
/mul
trick to zero three registers (do you ever need that many zeroes?), but using that as part of creating a1
makes it more sensible.APL (Dyalog),
2622 bytes4 bytes saved thanks to @H.PWiz
Try it online!
sumber
Haskell,
897675 bytesUngolfed version:
sumber
f=0:scanl(+)1f
(taken from here). Functions can be anonymous, so you can drop the leadingg=
, see our Guide to Ggolfing Rules in Haskell.$realToFrac y
with.read.show$y
for one bytePari/GP, 59 bytes
Try it online!
sumber
APL+WIN, 55 bytes
Prompts for screen input of integer.
APL+WIN's maximum integer precision is 17 and integer limit is of the order of 10E300 therefore the maximum input number is 55 and the result is: 1.2492739026634838E300
sumber
Python 3, 94 bytes
Try it online!
sumber
Jelly, 6 bytes
Try it online!
Ḷ
owered range -> nthÆḞ
ibonacci number -> from dec toB
inary ->F
latten -> fromḄ
inary to decsumber
10
and you will get an16024033463
, it is incorrect (correct answer is250375522
).10
returns250375522
MATL, 21 bytes
Try it online!
Explanation
sumber
J, 25 bytes
Try it online!
Explanation
sumber
Python 3, 86 bytes
Try it online!
sumber
Add++, 113 bytes
Try it online!
sumber
PHP, 124 Bytes
Try it online!
So I was looking for a way to output fibonacci numbers using the series, until I found this. It turns out you can calculate the fibonacci series via rounding, so I tried the challenge with a recursive function.
I found the approach of "rounding" really interesting, also a professor showed me this a while ago.
Code
Explanation
Also check this stackoverflow post the best answer refers to the same article on Wikipedia.
sumber
Stax, 9 bytes
Run and debug it at staxlang.xyz!
Unpacked (10 bytes) and explanation:
sumber
Julia 0.6, 65 bytes
Try it online!
sumber
Pyth, 27 bytes
Test suite
Python 3 translation:37 bytesTest suite
Python 3 translation:sumber
Ruby, 61 bytes
Try it online!
sumber
Jotlin, 59 bytes
Test Program
It supports up to 10, changing
.i(2)
for.toLong(2)
would support up to 14 if neededsumber
Python 2, 88 bytes
sumber
R,
244180179 bytesTry it online!
Saved some bytes by concatenating numeric vectors, not strings. Bloody special case for 0!
sumber
sapply
’d to a vector due to the fact that it is recursive. It cannot be all wrapped into one line. As you see, the programme prompts for user’s input and then returns the answer. One byte can be saved by creating a shortcut forifelse
. And... we can remove,""
fromscan
, yes.