Convertir un número de la Representación de Zeckendorf a Decimal

Windmill Cookies 10/07/2018. 25 answers, 2.939 views
code-golf fibonacci

Acerca de las Representaciones de Zeckendorf / Números de Fibonacci Base

Este es un sistema numérico que utiliza los números de Fibonacci como su base. Los números constan de 0 y 1 y cada 1 significa que el número contiene el número correspondiente de Fibonacci, y 0 significa que no.

Por ejemplo, convertimos todos los números naturales <= 10 a base Fibonacci.

  • 1 se convertirá en 1, porque es la suma de 1, que es un número de Fibonacci,

  • 2 se convertirá en 10, porque es la suma de 2, que es un número de Fibonacci, y no necesita 1, porque ya hemos alcanzado la suma deseada.

  • 3 se convertirá en 100, porque es la suma de 3, que es un número de Fibonacci y no necesita 2 ni 1 porque ya hemos alcanzado la suma deseada.

  • 4 se convertirá en 101, porque es la suma de [3,1], ambos de los cuales son números de Fibonacci.
  • 5 se convertirá en 1000, porque es la suma de 5, que es un número de Fibonacci, y no necesitamos ninguno de los otros números.
  • 6 se convertirá en 1001, porque es la suma de los números 5 y 1 de Fibonacci.
  • 7 se convertirá en 1010, porque es la suma de los números 5 y 2 de Fibonacci.
  • 8 se convertirá en 10000, porque es un número de Fibonacci.
  • 9 se convertirá en 10001, porque es la suma de los números 8 y 1 de Fibonacci.
  • 10 se convertirá en 10010, porque es la suma de los números 8 y 2 de Fibonacci.

Convirtamos un número de Fibonacci base aleatorio, 10101001010 a decimal: Primero, escribimos los números de Fibonacci correspondientes. Luego calculamos la suma de los números debajo de 1.

1   0   1   0   1   0   0   1   0   1   0
 144 89  55  34  21  13  8   5   3   2   1  -> 144+55+21+5+2 = 227. 

Lea más sobre los números de Base Fibonacci: enlace , también tiene una herramienta que convierte enteros regulares en Fibonacci base. Puedes experimentar con ello.

Ahora la pregunta:

Su tarea es tomar un número en la Representación de Zeckendorf y generar su valor decimal.

La entrada es una cadena que contiene solo 0 y 1 (aunque puede tomar la entrada de la forma que desee).

Salida un número en decimal.

Casos de prueba: (en el formato de entrada-> salida)

1001 -> 6
 100101000 -> 73
 1000000000 -> 89
 1001000000100100010 -> 8432
 1010000010001000100001010000 -> 723452 

Este es el código de golf, por lo que la respuesta más corta en bytes gana.

Nota: La entrada no contendrá ningún 0 inicial o 1 consecutivo.

25 Answers


JosiahRyanW 10/08/2018.

Taxi , 1987 1927 bytes.

-60 bytes debido a la constatación de que los saltos de línea son opcionales.

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to Chop Suey.Go to Chop Suey:n 1 r 1 l 4 r 1 l.[B]Switch to plan C if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 3 l.Pickup a passenger going to Narrow Path Park.Pickup a passenger going to Sunny Skies Park.Go to Zoom Zoom:n.Go to Sunny Skies Park:w 2 l.Go to Narrow Path Park:n 1 r 1 r 1 l 1 r.Go to Chop Suey:e 1 r 1 l 1 r.Switch to plan B.[C]1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 3 l 3 l 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[D]Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:n 2 r 1 r.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Multiplication Station.Go to Zoom Zoom:n.Go to Narrow Path Park:w 1 l 1 l 1 r.Switch to plan E if no one is waiting.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:e 1 r.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:n 1 r 2 l.Pickup a passenger going to Joyless Park.Go to Joyless Park:n 2 l 1 r 1 r.Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Addition Alley.Switch to plan D.[E]Go to Addition Alley:w 1 l 1 r 1 l.Pickup a passenger going to Riverview Bridge.Go to Riverview Bridge:n 1 r.Go to Joyless Park:e 1 r 2 l.Pickup a passenger going to Addition Alley.[F]Switch to plan G if no one is waiting.Pickup a passenger going to Addition Alley.Go to Fueler Up:w 1 l.Go to Addition Alley:n 3 l 1 l.Pickup a passenger going to Addition Alley.Go to Joyless Park:n 1 r 1 r 2 l.Switch to plan F.[G]Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:n 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r. 

Pruébalo en línea!

Como no regreso al Taxi Garage al final, mi jefe me despide, por lo que sale con un error.


Jo King 10/08/2018.

Perl 6 , 28 23 bytes

 {[+] (1,2,*+*...*)Z*$_} 

Pruébalo en línea!

Bloque de código anónimo que toma una lista de 1 sy 0 s en el pedido de LSB y devuelve un número.

Explicación:

 {                     }   # Anonymous codeblock
 [+]                      # The sum of
     (1,2,*+*...*)        # The infinite Fibonacci sequence starting from 1,2
                  Z*      # Zip multiplied by
                    $_    # The input list in LSB form 

nixpower 10/08/2018.

Wolfram Language (Mathematica) , 35 32 29 28 bytes

Fibonacci[Range@Tr[#!]+1].#& 

Pruébalo en línea!


Jonathan Allan 10/08/2018.

Jalea , 5 bytes

T‘ÆḞS 

Un enlace monádico que acepta una lista en forma de Little-endian (es decir, desde el LSB a la izquierda hasta el MSB a la derecha).

Try it online!


Haskell , 38 bytes

 f=1:scanl(+)2f
sum.zipWith(*)f.reverse 

Pruébalo en línea!

Toma la entrada como una lista de 1s y 0s.

Explicación


 f=1:scanl(+)2f 

Hace una lista de los números de Fibonacci sin el primero, en la variable f .

 sum.zipWith(*)f.reverse 

Toma la lista de entrada en reverse si multiplica cada entrada por la entrada correspondiente en f , luego sum los resultados.

Haskell , 30 bytes

 f=1:scanl(+)2f
sum.zipWith(*)f 

Pruébalo en línea!

Si tomamos la entrada con el bit menos significativo primero, no necesitamos reverse por lo que podemos guardar 8 bytes.


xnor 10/11/2018.

Python 2 , 43 bytes

 a=b=0
for x in input():b+=a+x;a=b-a
print b 

Pruébalo en línea!

Toma entrada como una lista. La actualización es una versión más corta de a,b=b+x,a+b+x , que es como la actualización de Fibonacci a,b=b,a+b si ignora x .


Python 2 , 45 bytes

 f=lambda n,a=1,b=1:n and n%10*b+f(n/10,b,a+b) 

Pruébalo en línea!

Toma la entrada como números decimales.


Steven H. 10/07/2018.

Pyth, 13 bytes

La mayoría de esto (8 bytes) está generando los números de Fibonacci.

s*V_m=+Z|~YZ1 

¡Pruébalo con este conjunto de pruebas!

Explicación:

s*V_m=+Z|~YZ1QQ     Autofill variables
    m=+Z|~YZ1Q      Generate the first length(input) Fibonacci numbers as follows:
       Z             Start with Z=0
         ~YZ         And Y=[] (update it to Y=Z, return old Y)
        |   1        if Y is [], then replace with 1
      +              Sum Z and Y
     =               Replace Z with sum
    m                Repeat process
             Q       once for each element of the input
   _                Reverse the order of the Fibonacci numbers
 *V                 Vectorize multiplication
s                   Sum 

Bubbler 10/09/2018.

J , 24 21 bytes

1#.|.*[:+/@(!~#-])\#\ 

Pruébalo en línea!

Versión refinada de la solución de 25 bytes de Galen Ivanov .

Usa la suma diagonal del triángulo de Pascal, que es equivalente a la suma de los coeficientes binomiales:

\ $ F_n = \ sum \ limits_ {i = 0} ^ {n} {} _ {ni} C_ {i} \ $

Cómo funciona

1#.|.*[:+/@(!~#-])\#\
                       Example input: 1 0 0 1 0
                   #\  Generate 1-based index; 1 2 3 4 5
      [:          \    For each prefix of above... (ex. 1 2 3)
              #-]        Subtract each element from the length (ex. 2 1 0)
           (!~   )       Compute binomial coefficient (ex. 3C0 + 2C1 + 1C2)
        +/@              Sum
                       The result is Fibonacci numbers; 1 2 3 5 8
   |.*                 Multiply with mirrored self; 0 2 0 0 8
1#.                    Sum; 10 

J , 24 bytes

3 :'y#.~|.(1+%)^:(<#y)2' 

Pruébalo en línea!

Verbo explícito monádico. Genera la base mixta que representa la base de Fibonacci y luego se alimenta a la base de conversión #. .

Cómo funciona

y#.~|.(1+%)^:(<#y)2  Explicit verb, input: y = Fibonacci digit array, n = length of y
      (1+%)          x -> 1 + 1/x
           ^:(<#y)2  Apply the above 0..n-1 times to 2
                     The result looks like 2/1, 3/2, 5/3, 8/5, 13/8, ...
    |.               Reverse
                     Now, if it is fed into #. on the left, the digit values become
                     ...(8/5 * 5/3 * 3/2 * 2/1), (5/3 * 3/2 * 2/1), (3/2 * 2/1), 2/1, 1
                     which is ... 8 5 3 2 1 (Yes, it's Fibonacci.)
y#.~                 Convert y to a number using Fibonacci base 

Alternativas

J , 27 bytes

}.@(+#{.3#{.)^:(<:@#)@(,&0) 

Pruébalo en línea!

La idea:

1  0  0  1  0  1
-1 +1 +1
------------------
    1  1  1  0  1
   -1 +1 +1
------------------
       2  2  0  1
      -2 +2 +2
------------------
          4  2  1
         -4 +4 +4
------------------
             6  5
            -6 +6 +6 <- Add an imaginary digit that has value 1
---------------------
               11  6
              -11+11
---------------------
                  17 <- the answer 

J , 30 bytes

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0 

Pruébalo en línea!

Este tomó el mayor esfuerzo para construir. Utiliza la expresión de forma cerrada con el truco de redondeo. En la expresión, los valores 0 y 1 son 0 y 1 respectivamente, por lo que la potencia del dígito real debe comenzar con 2.

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0  Tacit verb.
                         ,&0 0  Add two zeroes at the end
              (-:>:%:5)#.       Convert to a number using base phi (golden ratio)
       (%:5)%~                  Divide by sqrt(5)
0.5<.@+                         Round to nearest integer 

Si bien el error (( ((1-sqrt(5))/2)^n términos) puede acumularse, nunca supera 0,5, por lo que el truco de redondeo funciona hasta el infinito. Matemáticamente:

\ $ \ max (| error |) = \ frac {1} {\ sqrt {5}} \ sum \ limits_ {1} ^ {\ infty} (\ frac {1- \ sqrt {5}} {2}) ^ {2n} = \ frac {1} {\ sqrt {5}} \ sum \ limits_ {0} ^ {\ infty} (\ frac {1- \ sqrt {5}} {2}) ^ {n} = \ frac {\ sqrt {5} -1} {2 \ sqrt {5}} <\ frac {1} {2} \ $


Brain-Flak , 110 , 102 , 96 , 94 , 78 , 74 bytes

([[]]<>((()))){({}()<([({})]({}({})))>)}{}{}({<>{<{}><>({})(<>)}{}<><{}>}) 

Pruébalo en línea!


maxb 10/08/2018.

MathGolf , 8 6 bytes

{î)f*+ 

Pruébalo en línea!

Explicación

{        Start block (foreach in this case)
 î)      Push loop index (1-based) and increment by 1
   f     Get fibonacci number of that index
    *    Multiply with the array value (0 or 1)
     +   Add top two elements of stack. This implicitly pops the loop index the first iteration, which makes the addition become 0+a, where a is the top of the stack. 

Se guardó 1 byte gracias a JoKing y otro byte gracias al pedido de LSB.


Arnav Borborah 10/09/2018.

05AB1E , 11 9 8 bytes

vyiNÌÅfO 

Pruébalo en línea!

Explicación:

v             : For each character in input string (implicit) in LSB order
  yi          : If the current character is truthy (1)
    NÌ        : Add 2 to the current index
       ÅfO    : Add the fibonacci of this number to the stack 
  • -2 bytes : ¡Gracias a @KevinCruijssen por señalar pequeñas formas de acortar este código!
  • -1 byte : ¡Gracias a @JonathanAllan por señalar el pedido de LSB para la entrada!

JosiahRyanW 10/07/2018.

Python 3 , 63 bytes

 a=b=n=1
for i in input()[::-1]:n+=b*int(i);a,b=b,a+b
print(n-1) 

Pruébalo en línea!

Toma entrada a través de STDIN como una cadena.


Galen Ivanov 10/08/2018.

Rojo , 142, 126 106 bytes.

func[a][b: copy[1 1]reverse a s: 0 n: 1
until[s: b/1 * a/:n + s insert b b/1 + b/2(n: n + 1)> length? a]s] 

Pruébalo en línea!


Multi 10/08/2018.

Stax , 6 bytes

çéC◘0â 

Ejecutar y depurar

:1F^|5+           #Full program, unpacked, implicit input as array    
:1                #Get indicies of truthy
  F               #Use rest of program to loop through elements
   ^              #Increment current element
    |5+           #Get n-th fib and Add 

Muy claro. Pedidos de LSB.


Nitrodon 10/08/2018.

Cerebro , 40 bytes

([]){{}([({}<>{})]({}{}))<>([])}<>({}{}) 

Pruébalo en línea!


Rogem 10/08/2018.

C (gcc) , 63 bytes

Toma la entrada como una matriz de 1 y 0 , junto con la longitud de la matriz. Esta solución es un bucle hacia atrás bastante directo.

 f(_,l,a,b,t)int*_;NO 

Pruébalo en línea!


0 ' 10/09/2018.

Prólogo (SWI) , 74 bytes.

\D-->[X,Y],{D is 2*X+Y};[D];a,\D.
a,[A],[B]-->[X,Y,Z],{A is X+Y,B is X+Z}. 

Pruébalo en línea!

Toma la entrada como una lista de enteros 1 y 0 con el bit más significativo primero.


Neil 10/07/2018.

Retina 0.8.2 , 23 bytes

0?
;
+`1;(1*);
;1$1;1
1 

Pruébalo en línea! El enlace incluye los casos de prueba más rápidos. Explicación:

0?
; 

Insertar separadores en todas partes y eliminar los ceros. Por ejemplo, 1001 convierte en ;1;;;1; .

+`1;(1*);
;1$1;1 

Reemplace repetidamente cada 1 con un 1 en cada uno de los dos lugares siguientes, ya que la suma de sus valores es igual al valor del 1 original. 1 s por lo tanto, migran y acumulen hasta que alcancen los dos últimos lugares, que (debido al nuevo separador agregado) ahora tienen valor 1 .

1 

Cuenta los 1 s.


Shaggy 10/07/2018.

Japt -x , 9 bytes

Ë*MgUÊa´E 

Intentalo


Arnauld 10/08/2018.

JavaScript (Node.js) , 41 bytes

Un puerto de la respuesta de Xnor . Toma la entrada como un literal BigInt.

 f=(n,a=1n,b=a)=>n&&n%10n*b+f(n/10n,b,a+b) 

Pruébalo en línea!


JavaScript (ES6), 44 bytes

Toma la entrada como una matriz de caracteres, en primer orden de LSB.

 s=>s.map(k=>t+=k*(z=x,x=y,y+=z),x=t=0,y=1)|t 

Pruébalo en línea!


G B 10/08/2018.

Ruby , 39 bytes

 ->nNO 

Pruébalo en línea!


Mego 10/08/2018.

En realidad , 8 bytes.

;r⌐@░♂FΣ 

Pruébalo en línea!

La entrada se toma como una lista de bits en primer orden de LSB.

Explicación:

;r⌐@░♂FΣ
;r        range(0, len(input))
  ⌐       add 2 to every element in range (range(2, len(input)+2))
   @░     filter: take values in range that correspond to 1s in input
     ♂F   Fibonacci number at index of each element in list (Actually uses the F(0)=F(1)=1 definition, which is why we needed to add 2 earlier)
       Σ  sum 

mazzy 10/08/2018.

Powershell, 68 bytes

 param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x 

Guión de prueba:

 $f = {
param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x
}

@(
    ,("1001", 6)
    ,("100101000", 73)
    ,("1000000000", 89)
    ,("1001000000100100010", 8432)
    ,("1010000010001000100001010000", 723452)
) | % {
    $s,$e = $_
    $r = &$f $s
    "$($r-eq$e): $r"
} 

Salida:

 True: 6
True: 73
True: 89
True: 8432
True: 723452 

Luke Stevens 10/09/2018.

Java (OpenJDK 8) , 65 bytes

Bastante pequeño para una respuesta de Java, estoy contento con eso. Toma la entrada como una matriz ordenada primero de LSB de entradas.

 d->{int s=0,f=1,h=1;for(int i:d){s+=i>0?f:0;f=h+(h=f);}return s;} 

Pruébalo en línea!

Ungolfed

 d->{                        // Lambda function that takes array of ints
    int s=0,f=1,h=1;        // Initialise sum and fibonacci vars
    for(int i:d){           // Loop through each input integer
        s+=i>0?f:0;         // If it's 1 add current fibonacci number to sum
        f=h+(h=f);          // Increase fibonacci number 
    }return s;              // return sum
} 

Logern 10/10/2018.

Z80Golf , 34 bytes

00000000: dde1 f1b7 2819 fe30 2812 4504 aff5 3cf5  ....(..0(.E...<.
00000010: d1f1 82d5 f510 f9c1 f17c 8067 2c18 e3dd  .........|.g,...
00000020: e5c9                                     .. 

Ejemplo con entrada 1001-¡Pruébelo en línea!

Ejemplo con entrada 100101000-¡Pruébelo en línea!

Montaje:

zeck:		; input=push on stack in MSB order (eg top is LSB) output=reg h
pop ix		; save return addr in ix
f:
pop af		; get next digit
or a
jr z, return	; if current digit==0, return
cp 0x30
jr z, skip	; if current digit=='0' (e.g. not '1'), skip loop
ld b, l		; find fib of counter
fib:
	inc b	; 1-indexing for func to work
	xor a	; set a to 0 (1st fibo num)
	push af
	inc a	; set a to 1 (2nd fibo num)
	push af
	fib_loop:
		pop de
		pop af
		add d
		push de
		push af
		djnz fib_loop
pop bc		; get the fibo num just calculated
pop af		; pop just to reset stack frame
ld a, h
add b		; add current fibo number to sum
ld h, a
skip:
inc l		; increment counter reg
jr f		; repeat loop
return:
push ix		; push the return addr to ret to it
ret 

HighResolutionMusic.com - Download Hi-Res Songs

Related questions

Hot questions

Language

Popular Tags