Fibonacci binario

31

Reto

Debe generar un programa o función que tome un número entero positivo N, calcule los primeros N términos de la secuencia de Fibonacci en binario, lo concatene en un solo número binario, convierta ese número de nuevo en decimal y luego muestre el decimal como un entero.

Por ejemplo

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

No es necesario que muestre el ->, solo el número (por ejemplo, si el usuario escribe 4, solo muestra 14). Las flechas son solo para ayudar a explicar lo que debe hacer el programa.

Casos de prueba

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

El programa debe poder generar hasta el límite del idioma en uso. No se permiten tablas de búsqueda ni soluciones alternativas comunes .

Este es el código de golf , por lo que gana la respuesta con el menor número de bytes.

code-golf binary fibonacci Nathan Wood
fuente
1
Se agregaron casos de prueba de 0 a 20 desde tio.run/##DYxBCoQwDAC/… . Crédito a @alephalpha por el programa.
Nathan Wood
66
Como aún no se ha dicho: ¡Bienvenido a PPCG! Bonito primer desafío.
Laikoni
@Laikoni ¡Gracias!
Nathan Wood
¿Dónde se aplica exactamente el límite específico del idioma? ¿Se permitiría una función C que devuelva un entero de 32 bits? Como int32_t binary_concat_Fib(int n), lo que limitaría el valor de salida resultante a 2 ^ 31-1. es decir, puede suponer que todos los bits concatenados encajan en un número entero. ¿O debería funcionar la función hasta el punto en que el número de Fibonacci más grande no cabe en un entero por sí solo, por lo que concatenar los bits requiere una mayor precisión?
Peter Cordes
1
¿Y los "conversos a decimales" tienen que ser explícitos, llamando a una función de cadena entera o> o escribiendo uno usted mismo? Concatenar los bits en un solo entero le da una representación del valor final. Si lo entiendo correctamente, la respuesta de Dennis en Python está devolviendo un número entero, dejando que la persona que llama convierta ese valor en una cadena decimal o haga lo que sea con él. Los valores enteros en lenguajes de computadora que admiten operadores de desplazamiento de bits son naturalmente binarios, no decimales, a menos que estén almacenados en cadenas. En idiomas sin turnos / operadores bit a bit, nada implica ninguna base.
Peter Cordes

Respuestas:

11

Python , 64 bytes

f=lambda n,a=0,b=1,r=0:n and f(n-1,b,a+b,r<<len(bin(a))-2|a)or r

Pruébalo en línea!

Dennis
fuente
1
Bien, solo estaba tratando de lograr este estilo.
Jonathan Allan
10

Gelatina ,  7  6 bytes

ḶÆḞBẎḄ

Pruébalo en línea!

¿Cómo?

ḶÆḞBẎḄ - Link: integer, n
Ḷ      - lowered range -> [0,1,2,3,4,5,...,n]
 ÆḞ    - Fibonacci (vectorises) -> [0,1,1,2,3,5...,F(n)]
   B   - to binary (vectorises) -> [[0],[1],[1],[1,0],[1,1],[1,0,1],...,B(F(n))]
    Ẏ  - tighten -> [0,1,1,1,0,1,1,1,0,1,...,B(F(n))[0],B(F(n))[1],...]
     Ḅ - from binary -> answer
Jonathan Allan
fuente
1
Jugueteando con los nuevos rápidos, descubrí que los primeros n números de Fibonacci también se pueden encontrar usando lo Ṛc’SƲƤque podría ser útil para secuencias similares.
millas
7

brainfuck , 397 bytes

>,[<++++++[->--------<]>>[->++++++++++<]>[-<+>]<<[->+<],]>+[-<<+>>[-[->+<]<<[->+>+<<]<[->+>+<<]>[-<+>]>>[-<<+>>]>]]<<[->+>>>>>+<<<<<<]>[-<+>]>+>>+>>>+<[[->-[<<]>]>[[-]<<<<<<<[->>[-<+>>+<]>[-<+>]<<<]<[->+>>>>>+<<<<<<]>[-<+>]>[-<+>]>[->>[-<+<<+>>>]<[->+<]<]>+>[-]>>+>]<<<<<[[->++>+>++<<<]>[-<+>]<<]>>>]>[-]<<<[-]<<[-]<<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>]<+[->++++++[-<++++++++>]<.<<<+]

¡Bueno eso fue divertido!

Toma entrada ASCII (p 11. Ej. ), Las salidas dan como resultado ASCII.

Nota: para probar esto en línea, asegúrese de establecer el tamaño de celda en 32 bits (en el lado derecho de la página web). Si no ingresa una entrada, su navegador podría fallar.

El intérprete no puede manejar la entrada de 11y superior porque solo admite hasta 32 bits.

Pruébalo en copy.sh

Explicación

>,[<++++++[->--------<]>>[->++++++++++<]>[-<+>]<<[->+<],]>+

Obtenga entrada decimal y agregue uno (para mitigar off-by-one)

[-<<+>>[-[->+<]<<[->+>+<<]<[->+>+<<]>[-<+>]>>[-<<+>>]>]]

Genera números de fibonacci en la cinta.

<<[->+>>>>>+<<<<<<]>[-<+>]>+>>+>>>+<

Configurar para el bucle de concatenación binario entrante

Entonces las celdas contienen el valor, comenzando desde la primera posición,

1 | 0 | 1 | 1 | 2 | 3 | 5 | ... | f_n | 0 | 1 | 0 | 1 | 0 | f_n | 1 | 0 | 0 | 0...

Mira estas celdas:

f_n | 0 | 1 | 0 | 1 | 0 | f_n | 1

Voy a etiquetar esto:

num | sum | cat | 0 | pow | 0 | num | pow

powestá ahí para encontrar la potencia máxima de 2 que es estrictamente mayor que num. sumes la concatenación de números hasta ahora. cates el poder de 2 que necesitaría multiplicar numpara poder concatenar numdelante del sum(por lo que podría simplemente agregar).

[[->-[<<]>]>

Bucle: compruebe si f_nes estrictamente menor que pow.

Verdad:

[[-]<<<<<<<[->>[-<+>>+<]>[-<+>]<<<]<[->+>>>>>+<<<<<<]>[-<+>]>[-<+>]>[->>[-<+<<+>>>]<[->+<]<]>+>[-]>>+>]

Cero basura. Luego, agregue num* cata sum. Luego, cargue el siguiente número de Fibonacci (= f_(n-1); si no existe, salga del bucle) y configúrelo caten cat* pow. Prepárese para el próximo ciclo (cero más basura, cambie el alcance en uno).

Falsey

<<<<<[[->++>+>++<<<]>[-<+>]<<]

Establecer powen 2 * pow, restaurar num.

]

Repita hasta que no quede ningún número de Fibonacci.

>[-]<<<[-]<<[-]<<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>]<+[->++++++[-<++++++++>]<.<<<+]

Basura limpia Tome cada dígito del número resultante y genere cada uno (en ascii).

JungHwan Min
fuente
7

Casco , 7 bytes

ḋṁḋ↑Θİf

Pruébalo en línea!

Explicación

ḋṁḋ↑Θİf                              4
     İf    The Fibonacci numbers     [1,1,2,3,5,8..]
    Θ      Prepends 0                [0,1,1,2,3,5..]
   ↑     Take n elements from list   [0,1,1,2]
  ḋ        Convert to binary digits  [[0],[1],[1],[1,0]]
 ṁ       Map function then concat    [0,1,1,1,0]
ḋ        Convert from base 2         14
Fyr
fuente
Bienvenido a PPCG! :)
DJMcMayhem
5

Japt , 9 bytes

ÆMgX ¤Ã¬Í

Ejecutarlo

Explicación:

ÆMgX ¤Ã¬Í
Æ     Ã     | Iterate X through the range [0...Input]
 MgX        |   Xth Fibonacci number
     ¤      |   Binary
       ¬    | Join into a string
        Í   | Convert into a base-2 number
Oliver
fuente
1
¡Bah! ¡Golpéame!
Shaggy
1
@ Shaggy Sabía que esta iba a ser una carrera contra ti: P
Oliver
4

Pyth, 22 bytes

JU2VQ=+Js>2J)is.BM<JQ2

Pruébalo aquí

Explicación

JU2VQ=+Js>2J)is.BM<JQ2
JU2                       Set J = [0, 1].
   VQ       )             <Input> times...
     =+Js>2J              ... add the last 2 elements of J and put that in J.
                  <JQ     Take the first <input> elements...
               .BM        ... convert each to binary...
              s           ... concatenate them...
             i       2    ... and convert back to decimal.

fuente
3

Perl 6 , 38 bytes

{:2([~] (0,1,*+*...*)[^$_]>>.base(2))}

Pruébalo en línea!

nwellnhof
fuente
1
Tenga en cuenta que esto comienza a ser notablemente más lento con entradas superiores a 200. Se tarda unos 8 segundos en generar la salida con una entrada de 1000. (20 segundos si incluye la impresión)
Brad Gilbert b2gills
3

JavaScript (Node.js) , 70 65 58 57 55 bytes

  • gracias a Shaggy por reducir 2 bytes ('0b + C-0 a' 0b '+ C)
f=(n,a=C=0,b=1)=>--n?f(n,b,a+b,C+=b.toString(2)):'0b'+C

Pruébalo en línea!

DanielIndie
fuente
Puede deshacerse de él -0al final para guardar otros 2 bytes.
Shaggy
2

J, 36 bytes

3 :'#.;<@#:"0]2}.(,{:+_2&{)^:y _1 1'

Explicación:

3 :'#.;<@#:"0]2}.(,{:+_2&{)^:y _1 1' | Explicit function
                 (,{:+_2&{)^:y _1 1  | Make n fibonacci numbers, with _1 1 leading
              2}.                    | Drop the _1 1
       <@#:"0]                       | Convert each item to binary and box
      ;                              | Unbox and join
    #.                               | Convert back from binary
Bolce Bussiere
fuente
2

x86, 37 22 21 bytes

Registro de cambios

  • -13 mediante el uso bsr. Gracias Peter Cordes!

  • -2 al poner a cero los registros conmul .

  • -1 mediante el uso de un bucle while en lugar de loopy push/ pop ecx(crédito Peter Cordes).

Entrada edi, salida en edx.

.section .text
.globl main
main:
        mov     $5, %edi            # n = 5

start:
        dec     %edi                # Adjust loop count
        xor     %ebx, %ebx          # b = 0
        mul     %ebx                # a = result = 0
        inc     %ebx                # b = 1

fib:
        add     %ebx, %eax          # a += b
        xchg    %eax, %ebx          # swap a,b
        bsr     %eax, %ecx          # c = (bits of a) - 1
        inc     %ecx                # c += 1
        sal     %cl, %edx           # result >>= c
        add     %eax, %edx          # result += a

        dec     %edi                # n--; do while(n)
        jnz     fib 

        ret

Objdump:

00000005 <start>:
   5:   4f                      dec    %edi
   6:   31 db                   xor    %ebx,%ebx
   8:   f7 e3                   mul    %ebx
   a:   43                      inc    %ebx

0000000b <fib>:
   b:   01 d8                   add    %ebx,%eax
   d:   93                      xchg   %eax,%ebx
   e:   0f bd c8                bsr    %eax,%ecx
  11:   41                      inc    %ecx
  12:   d3 e2                   shl    %cl,%edx
  14:   01 c2                   add    %eax,%edx
  16:   4f                      dec    %edi
  17:   75 f2                   jne    b <fib>
  19:   c3                      ret
qwr
fuente
1
Use leapara cambiar y agregar en fib2. Además, extraer cada bit uno a la vez es innecesario. Use bsr %eax, %ecxpara encontrar el número de bits en la representación binaria, y use un cambio por CL / o para fusionar, como lo está haciendo la respuesta Python de Dennis.
Peter Cordes
1
Necesita contar los clturnos, así que tome su contador de bucle en un registro diferente (como %edi) y use dec %edi / jnz(3 bytes en código de 32 bits, 4 bytes en 64 bits). En el código de 32 bits, eso ahorra un total de 1 byte al soltar el ecx push / pop. No caiga en la trampa de usar loopcuando hace que el problema sea más difícil, no más fácil. (Su convención de llamadas ya es personalizada, %ebxno se puede llamar a su función main). Es posible que pueda regresar a EAX sin dejar de aprovechar 1 byte xchg, no es necesario que no sea estándar si no lo necesita.
Peter Cordes
1
Puede reemplazar el extra inc %ecxdel conteo de turnos con un desplazamiento a la izquierda adicional a medida que agrega, usando lea (%eax, %edx, 2), %edx. Neutro en bytes para 32 bits, guarda uno para x86-64. Pero guarda una instrucción.
Peter Cordes
1
Cada vez que termino usando el loopcódigo golf, me siento sucio. Bueno, no del todo, pero decepcionado porque no pude encontrar una implementación igualmente pequeña que evitara esa instrucción lenta; fuera del código de golf, loopes una de mis manías . Me gustaría que era rápido en las CPU modernas, ya que sería muy agradable para los bucles de precisión extendida sin puestos de bandera parcial, pero no lo es y debe ser considerada sólo como una instrucción optimización del tamaño oscuro que hace que su código lento.
Peter Cordes
1
De todos modos, buen trabajo. Aparte de push / pop / loop -> dec / jnz, no veo ningún ahorro, solo la aceleración de LEA que es neutral en tamaño de código. Siempre me pregunté si alguna vez hubo un caso de uso real para el xor/ multruco a cero tres registros (¿alguna vez necesita tantos ceros?), Pero usar eso como parte de la creación de un 1hace que sea más sensible.
Peter Cordes
2

Haskell , 89 76 75 bytes

f=0:scanl(+)1f
foldr1(\x y->y+x*2*2^floor(logBase 2.read.show$y)).(`take`f)

Versión sin golf:

import Data.Bits

fib = 0:scanl (+) 1 fib

catInt :: Integer -> Integer -> Integer
catInt x y = x' + y where
    position = floor $ succ $ logBase 2 $ realToFrac y
    x' = shift x position

answer :: Integer -> Integer
answer n = foldr1 catInt fib' where
    fib' = take n fib
usuario9549915
fuente
1
¡Bienvenido a PPCG y al golf Haskell en particular! Una forma más corta de generar una lista infinita de números de Fibonacci es f=0:scanl(+)1f(tomada de aquí ). Las funciones pueden ser anónimas, por lo que puede quitar el liderazgo g=, consulte nuestra Guía de reglas de Ggolfing en Haskell .
Laikoni
¡Gracias! Eso compensa algunas de las funciones más largas utilizadas. Pasé un tiempo tratando de encontrar una manera de implementar el desplazamiento de bits de una manera más concisa, pero me quedé corto.
user9549915
Se puede reemplazar $realToFrac ycon .read.show$yun byte
H.PWiz
1

APL + WIN, 55 bytes

Solicita la entrada de pantalla de entero.

v←b←0 1⋄⍎∊(⎕-2)⍴⊂'v←v,c←+/¯2↑v⋄b←b,((1+⌊2⍟c)⍴2)⊤c⋄'⋄2⊥b

La precisión entera máxima de APL + WIN es 17 y el límite entero es del orden de 10E300, por lo tanto, el número máximo de entrada es 55 y el resultado es: 1.2492739026634838E300

Graham
fuente
1

Jalea , 6 bytes

ḶÆḞBFḄ

Pruébalo en línea!

Ḷgama owered -> n º ÆḞnúmero ibonacci -> de DEC para Bciertas piezas -> Flatten -> de Ḅciertas piezas a diciembre

cromático
fuente
No entendí este lenguaje pero pensé que la salida no siempre es correcta. Por ejemplo, ingrese 10y obtendrá un 16024033463, es incorrecto (la respuesta correcta es 250375522).
Guoyang Qin
@AbrahamChin Input 10regresa250375522
Dennis
Equivalente, respuesta duplicada , solo un
aviso
1

MATL , 21 bytes

0li:"yy+]xx&h"@B]&hXB

Pruébalo en línea!

Explicación

0l        % Push 0, then 1 (initial terms of the Fibonacci sequence)
i:"       % Do n times, where n is the input
  yy+     %   Duplicate top two numbers and push their sum
  ]       % End
xx        % Delete the last two results. The stack now contains the
          % first n Fibonacci numbers, starting at 0
&h        % Concatenate all numbers into a row vector
"         % For each
  @       %   Push current number
  B       %   Convert to binary. Gives a vector of 0 and 1
]         % End
&h        % Concatenate all vectors into a row vector
XB        % Convert from binary to decimal. Implicitly display
Luis Mendo
fuente
1

J , 25 bytes

2(#.;)<@#:@(1#.<:!|.)\@i.

Pruébalo en línea!

Explicación

2(#.;)<@#:@(1#.<:!|.)\@i.  Input: n
                       i.  Range [0, n)
                     \@    For each prefix
                  |.         Reverse
                 !           Binomial coefficient (vectorized)
               <:            Decrement
            1#.              Sum
        #:                   Convert to binary
      <                      Box
    ;                        Link. Join the contents in each box
2 #.                         Convert to decimal from base 2
millas
fuente
1

Agregar ++ , 113 bytes

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,k,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{k}
D,w,@,BBbR
D,l,@,ßR€gp€w@0b]@¦+VcG2$Bb

Pruébalo en línea!

caird coinheringaahing
fuente
1

PHP, 124 bytes

Pruébalo en línea!

Así que estaba buscando una manera de generar números de Fibonacci usando la serie, hasta que encontré esto . Resulta que puedes calcular la serie de Fibonacci a través del redondeo, así que probé el desafío con una función recursiva.

El enfoque de "redondeo" me pareció realmente interesante, también un profesor me lo mostró hace un tiempo.

Código

function f($n,$i=0,$b=''){ if($n>$i){$b.=
decbin(round(pow((sqrt(5)+1)/2,$i)/sqrt(5)));f($n,$i+1,$b);}else{echo bindec($b);}}

Explicación

function f($n,$i=0,$b=''){           #the function starts with $i=0, our nth-fib number
if($n>$i){                           #it stops once $n (the input) = the nth-fib
    $b.=decbin(                      #decbin returns an integer as bin, concatenates
        round(pow((sqrt(5)+1)/2,$i)/sqrt(5))    
                                       #the formula, basically roundign the expression
        );                           #it returns the (in this case) $i-th fib-number   
    f($n,$i+1,$b);                   #function is called again for the next index
}else{                               #and the current string for fibonacci

    echo bindec($b);                 #"echo" the result, bindec returns the base 10
                                     #value of a base 2 number
}
}

También revise esta publicación de stackoverflow, la mejor respuesta se refiere al mismo artículo en Wikipedia.

Francisco Hahn
fuente
Interesante forma de hacerlo!
Nathan Wood
1

Stax , 9 bytes

ü1∞╓♪εw≤+

¡Ejecútelo y depúrelo en staxlang.xyz!

Desempaquetado (10 bytes) y explicación:

vr{|5|Bm|B
v             Decrement integer from input. Stax's Fibonacci sequence starts with 1 :(
 r            Integer range [0..n).
  {    m      Map a block over each value in an array.
   |5           Push nth Fibonacci number.
     |B         Convert to binary.
        |B    Implicit concatenate. Convert from binary. Implicit print.
Khuldraeseth na'Barya
fuente
1

Pyth, 27 bytes

JU2V-Q2=aJ+eJ@J_2)is.BM<JQ2

Banco de pruebas

Traducción de Python 3: 
Q=eval(input())
J=list(range(2))
for i in range(Q-2):
    J.append(J[-1]+J[-2])
print(int(''.join(map("{0:b}".format,J[:Q])),2))

37 bytes

J[Z1)W<lJQ=aJ+eJ@J_2)Ig1QZ.?ijkm.BdJ2

Banco de pruebas

Traducción de Python 3: 
Q=eval(input())
J=[0,1]
while len(J)<Q:
    J.append(J[-1]+J[-2])
if 1>=Q:
    print(0)
else:
    print(int(''.join(map("{0:b}".format,J)),2))

hakr14
fuente
0

Jotlin , 59 bytes

g(l(0,1)){l(a.sum(),a[0])}.take(this).j(""){a[0].s(2)}.i(2)

Programa de prueba

data class Test(val input: Int, val output: Long)

val tests = listOf(
    Test(1, 0),
    Test(2, 1),
    Test(3, 3),
    Test(4, 14),
    Test(5, 59),
    Test(6, 477),
    Test(7, 7640),
    Test(8, 122253),
    Test(9, 3912117),
    Test(10, 250375522)
)
fun Int.r() = g(l(0,1)){l(a.sum(),a[0])}.take(this).j(""){a[0].s(2)}.i(2)

fun main(args: Array<String>) {
    for (r in tests) {
        println("${r.input.r()} vs ${r.output}")
    }
}

Admite hasta 10, cambiando .i(2)para .toLong(2)admitiría hasta 14 si es necesario

jrtapsell
fuente
0

Python 2, 88 bytes

def f(n):
 a,b,r=0,1,"0"
 for _ in range(n-1):a,b=b,a+b;r+=bin(a)[2:]
 print int(r,2)
sonrad10
fuente
0

R , 244 180 179 bytes

i=ifelse;g=function(n)i(n<3,1,g(n-1)+g(n-2))
a=scan(,"");i(a==1,0,sum(2^(which(rev(unlist(sapply(g(2:a-1),function(x)(y=rev(as.numeric(intToBits(x))))[which(!!y)[1]:32]))>0))-1)))

Pruébalo en línea!

Guardado algunos bytes concatenando vectores numéricos, no cadenas. ¡Caso especial sangriento para 0!

Andreï Kostyrka
fuente
Las funciones son aceptables. También es mucho más eficiente cambiar el resultado a la izquierda por el número de bits que molestarse con vectores numéricos. Vea mi respuesta de Python o la de Dennis. Esto tiene el beneficio adicional de manejar el caso 0.
qwr
codegolf.stackexchange.com/questions/4024/tips-for-golfing-in-r R jugar al golf es demasiado para mí: /
qwr
@qwr La respuesta no es una función; Estoy creando una función auxiliar porque debe ser sapply'd a un vector debido al hecho de que es recursiva. No puede estar todo envuelto en una sola línea. Como puede ver, el programa solicita la entrada del usuario y luego devuelve la respuesta. Se puede guardar un byte creando un acceso directo para ifelse. Y ... podemos quitar ,""de scansí.
Andreï Kostyrka