Convertendo um número de Zeckendorf Representation para Decimal

18

Sobre as representações da Zeckendorf / números base de Fibonacci

Este é um sistema numérico que usa os números de Fibonacci como base. Os números consistem em 0 e 1 e cada 1 significa que o número contém o número correspondente de Fibonacci e 0 significa que não.

Por exemplo, vamos converter todos os números naturais <= 10 em Fibonacci base.

  • 1 se tornará 1, porque é a soma de 1, que é um número de Fibonacci,

  • 2 se tornará 10, porque é a soma de 2, que é um número de Fibonacci, e não precisa de 1, porque já alcançamos a soma desejada.

  • 3 se tornará 100, porque é a soma de 3, que é um número de Fibonacci e não precisa de 2 ou 1, porque já alcançamos a soma desejada.

  • 4 se tornará 101, porque é a soma de [3,1], sendo ambos os números de Fibonacci.
  • 5 se tornará 1000, porque é a soma de 5, que é um número de Fibonacci, e não precisamos de nenhum dos outros números.
  • 6 se tornará 1001, porque é a soma dos números de Fibonacci 5 e 1.
  • 7 se tornará 1010, porque é a soma dos números 5 e 2 de Fibonacci.
  • 8 se tornará 10000, porque é um número de Fibonacci.
  • 9 se tornará 10001, porque é a soma dos números de Fibonacci 8 e 1.
  • 10 se tornará 10010, porque é a soma dos números 8 e 2 de Fibonacci.

Vamos converter um número aleatório de Fibonacci base, 10101001010 para decimal: primeiro, escrevemos os números correspondentes de Fibonacci. Em seguida, calculamos a soma dos números abaixo de 1s.

 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.

Leia mais sobre os números de Fibonacci base: link , também possui uma ferramenta que converte números inteiros regulares em Fibonacci base. Você pode experimentar com isso.

Agora a pergunta:

Sua tarefa é pegar um número na representação Zeckendorf e gerar seu valor decimal.

Input é uma string que contém apenas 0 e 1 (embora você possa receber a entrada da maneira que desejar).

Imprima um número em decimal.

Casos de teste: (no formato entrada-> saída)

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

Isso é código-golfe, então a resposta mais curta em bytes vence.

Nota: A entrada não conterá nenhum 0 inicial ou 1 consecutivo.

Bolinhos de moinho de vento
fonte
Podemos considerar a entrada como uma lista de bits?
Assistente de trigo 07/10
Tipo, pegue a entrada codificada como ASCII e depois a converta em binária ou algo assim?
9788 Windmill Cookies
4
Podemos receber informações na primeira ordem do LSB ?
Mego
1
@Mego Sim, você pode
Windmill Cookies

Respostas:

19

Táxi , 1987 1927 bytes

-60 bytes devido à percepção de que as quebras de linha são opcionais.

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.

Experimente online!

Como eu não volto à garagem do táxi no final, meu chefe me despede, então sai com um erro.

JosiahRyanW
fonte
Joyless Parkparece um bom lugar para se visitar
aloisdg diz Reinstate Monica
Bem, tem menos caracteres que Sunny Skies Park.
JosiahRyanW
11

Perl 6 , 28 23 bytes

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

Experimente online!

Anonymous bloco de código que leva uma lista de 1s e 0s em LSB ordenação e retorna um número.

Explicação:

{                     }   # 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
Brincadeira
fonte
7

Gelatina , 5 bytes

T‘ÆḞS

Um link monádico que aceita uma lista no formato Little-endian (ou seja, do LSB à esquerda para MSB à direita).

Experimente online!

Jonathan Allan
fonte
Bom, eu tinha uma alternativa de 6 Byter: J‘ÆḞḋṚ.
Mr. Xcoder
4

Haskell , 38 bytes

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

Experimente online!

Recebe a entrada como uma lista de 1s e 0s.

Explicação


f=1:scanl(+)2f

Faz uma lista dos números de Fibonacci sans o primeiro, na variável f.

sum.zipWith(*)f.reverse

Pega a lista de entrada reverse, multiplica cada entrada pela entrada correspondente fe depois sumos resultados.

Haskell , 30 bytes

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

Experimente online!

Se recebermos a entrada com o bit menos significativo primeiro, não precisamos, reverseportanto, podemos salvar 8 bytes.

Assistente de Trigo
fonte
4

Python 2 , 43 bytes

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

Experimente online!

Leva a entrada como uma lista. A atualização é uma versão mais curta a,b=b+x,a+b+x, semelhante à atualização Fibonacci, a,b=b,a+bse você ignorar x.


Python 2 , 45 bytes

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

Experimente online!

Aceita entrada como números decimais.

xnor
fonte
3

Pitão, 13 bytes

A maior parte disso (8 bytes) está apenas gerando os números de Fibonacci.

s*V_m=+Z|~YZ1

Experimente com este conjunto de testes!

Explicação:

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
Steven H.
fonte
3

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

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

Experimente online!

Assistente de Trigo
fonte
3

J , 24 14 bytes

#.~2+&%&1~#-#\

Experimente online!

Jogou a versão de 24 bytes que usa a base mista para Fibonacci.

Como funciona

#.~2+&%&1~#-#\  Example input: y=1 0 0 1 0
          #-#\  Length minus 1-based indices; 4 3 2 1 0
   2     ~      Starting from 2, run the following (4,3,2,1,0) times:
    +&%&1         Given y, compute 1 + 1 / y
                The result is 13/8 8/5 5/3 3/2 2
#.~             Mixed base conversion of y into base above; 2+8=10

J , 21 bytes

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

Experimente online!

Versão refinada da solução de 25 bytes de Galen Ivanov .

Usa a soma diagonal do triângulo de Pascal, que é equivalente à soma dos coeficientes binomiais:

Fn=Eu=0 0nn-EuCEu

Como 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'

Experimente online!

Verbo explícito monádico. Gera a base mista que representa a base de Fibonacci e, em seguida, alimenta a conversão da base #..

Como 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)

Experimente online!

A ideia:

 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

Experimente online!

Este levou o maior esforço para construir. Usa a expressão de forma fechada com o truque de arredondamento. Na expressão, os valores 0 e 1 são 0 e 1 respectivamente, portanto, a potência real do dígito deve começar com 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

Embora o erro ( ((1-sqrt(5))/2)^ntermos) possa aumentar, ele nunca excede 0,5, portanto o truque de arredondamento funciona até o infinito. Matematicamente:

max(|error|)=151(1-52)2n=150 0(1-52)n=5-125<12

Bubbler
fonte
Ótima solução! Fico feliz em ver um verbo explícito vencer a solução tácita.
Galen Ivanov
Estou tentando encontrar uma solução tácita mais curta, mas sem sucesso. 25 bytes por enquanto . Eu uso o triange de Pascal.
Galen Ivanov
@GalenIvanov Revisitando o desafio depois de um ano, recebi uma nova solução tácita super curta :)
Bubbler
Isso é ótimo! Vou ver isso em mais detalhes em breve.
Galen Ivanov
2

MathGolf , 8 6 bytes

{î)f*+

Experimente online!

Explicação

{        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.

Economizou 1 byte graças ao JoKing e outro byte ao pedido do LSB.

maxb
fonte
A ordem LSB é realmente permitida. além disso, -1 byte
Jo King
@JoKing Claro, eu até implementei a adição implícita na semana passada ... Bom toque, agora o MathGolf está em primeiro lugar!
maxb
2

05AB1E , 11 9 8 bytes

vyiNÌÅfO

Experimente online!

Explicação:

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 : Obrigado a @ KevinCruijssen por apontar pequenas maneiras de reduzir esse código!
  • -1 byte : Obrigado a JonathanAllan por apontar a ordem LSB para entrada!
Arnav Borborah
fonte
1
Você pode remover o Θ. 1já é verdade em 05AB1E. :) Além disso, 2+pode ser Ì.
Kevin Cruijssen
1
Podemos pegar a entrada na forma Little-endian (ou seja, invertida), o que deve salvar um byte (ou dois?).
Jonathan Allan
1

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)

Experimente online!

Leva a entrada através de STDIN como uma string.

JosiahRyanW
fonte
1

Vermelho , 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]

Experimente online!

Galen Ivanov
fonte
1

Stax , 6 bytes

çéC◘0â

Execute e depure

: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

Bem direto. Pedido LSB.

Multi
fonte
1

C (gcc) , 63 bytes

Recebe a entrada como uma matriz de 1's 0', juntamente com o comprimento da matriz. Esta solução é um loop reverso bastante direto.

f(_,l,a,b,t)int*_;{a=b=1;for(t=0;l--;b=(a+=b)-b)t+=a*_[l];_=t;}

Experimente online!


fonte
1

Prolog (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}.

Experimente online!

Recebe a entrada como uma lista de números inteiros 1 e 0 com o bit mais significativo primeiro.

0 '
fonte
0

Retina 0.8.2 , 23 bytes

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

Experimente online! O link inclui os casos de teste mais rápidos. Explicação:

0?
;

Insira separadores em todos os lugares e exclua zeros. Por exemplo, 1001torna-se ;1;;;1;.

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

Substitua repetidamente cada 1um com a 1em cada um dos próximos dois lugares, pois a soma de seus valores é igual ao valor do original 1. 1s, portanto, migram e se acumulam até atingirem os dois últimos locais, os quais (devido ao novo separador adicionado) agora têm valor 1.

1

Conte os 1s.

Neil
fonte
0

Japonês -x, 9 bytes

Ë*MgUÊa´E

Tente

Shaggy
fonte
0

Na verdade , 8 bytes

;r⌐@░♂FΣ

Experimente online!

A entrada é tomada como uma lista de bits na primeira ordem do LSB.

Explicação:

;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
Mego
fonte
0

Powershell, 68 bytes

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

Script de teste:

$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"
}

Resultado:

True: 6
True: 73
True: 89
True: 8432
True: 723452
confuso
fonte
0

Java (OpenJDK 8) , 65 bytes

Muito pequeno para uma resposta Java, estou feliz com isso. Recebe a entrada como uma matriz de entradas ordenada pela LSB.

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

Experimente online!

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
}
Luke Stevens
fonte
0

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                                     ..

Exemplo com entrada 1001-Experimente online!

Exemplo com entrada 100101000-Experimente online!

Montagem:

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
Logern
fonte