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.
Respostas:
Táxi ,
19871927 bytes-60 bytes devido à percepção de que as quebras de linha são opcionais.
Experimente online!
Como eu não volto à garagem do táxi no final, meu chefe me despede, então sai com um erro.
fonte
Joyless Park
parece um bom lugar para se visitarSunny Skies Park
.Perl 6 ,
2823 bytesExperimente online!
Anonymous bloco de código que leva uma lista de
1
s e0
s em LSB ordenação e retorna um número.Explicação:
fonte
Gelatina , 5 bytes
Um link monádico que aceita uma lista no formato Little-endian (ou seja, do LSB à esquerda para MSB à direita).
Experimente online!
fonte
J‘ÆḞḋṚ
.Wolfram Language (Mathematica) ,
35322928 bytesExperimente online!
fonte
Haskell , 38 bytes
Experimente online!
Recebe a entrada como uma lista de 1s e 0s.
Explicação
Faz uma lista dos números de Fibonacci sans o primeiro, na variável
f
.Pega a lista de entrada
reverse
, multiplica cada entrada pela entrada correspondentef
e depoissum
os resultados.Haskell , 30 bytes
Experimente online!
Se recebermos a entrada com o bit menos significativo primeiro, não precisamos,
reverse
portanto, podemos salvar 8 bytes.fonte
Python 2 , 43 bytes
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+b
se você ignorarx
.Python 2 , 45 bytes
Experimente online!
Aceita entrada como números decimais.
fonte
Pitão, 13 bytes
A maior parte disso (8 bytes) está apenas gerando os números de Fibonacci.
Experimente com este conjunto de testes!
Explicação:
fonte
Brain-Flak ,
110,102,96,94,78, 74 bytesExperimente online!
fonte
J ,
2414 bytesExperimente online!
Jogou a versão de 24 bytes que usa a base mista para Fibonacci.
Como funciona
J , 21 bytes
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:
Como funciona
J , 24 bytes
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
Alternativas
J , 27 bytes
Experimente online!
A ideia:
J , 30 bytes
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.
Embora o erro (
((1-sqrt(5))/2)^n
termos) possa aumentar, ele nunca excede 0,5, portanto o truque de arredondamento funciona até o infinito. Matematicamente:fonte
MathGolf ,
86 bytesExperimente online!
Explicação
Economizou 1 byte graças ao JoKing e outro byte ao pedido do LSB.
fonte
05AB1E ,
1198 bytesExperimente online!
Explicação:
fonte
Θ
.1
já é verdade em 05AB1E. :) Além disso,2+
pode serÌ
.Python 3 , 63 bytes
Experimente online!
Leva a entrada através de STDIN como uma string.
fonte
Vermelho ,
142, 126106 bytesExperimente online!
fonte
Ruby , 39 bytes
Experimente online!
fonte
Stax , 6 bytes
Execute e depure
Bem direto. Pedido LSB.
fonte
Flak cerebral , 40 bytes
Experimente online!
fonte
C (gcc) , 63 bytes
Recebe a entrada como uma matriz de
1
's0
', juntamente com o comprimento da matriz. Esta solução é um loop reverso bastante direto.Experimente online!
fonte
Prolog (SWI) , 74 bytes
Experimente online!
Recebe a entrada como uma lista de números inteiros 1 e 0 com o bit mais significativo primeiro.
fonte
Retina 0.8.2 , 23 bytes
Experimente online! O link inclui os casos de teste mais rápidos. Explicação:
Insira separadores em todos os lugares e exclua zeros. Por exemplo,
1001
torna-se;1;;;1;
.Substitua repetidamente cada
1
um com a1
em cada um dos próximos dois lugares, pois a soma de seus valores é igual ao valor do original1
.1
s, portanto, migram e se acumulam até atingirem os dois últimos locais, os quais (devido ao novo separador adicionado) agora têm valor1
.Conte os
1
s.fonte
Japonês
-x
, 9 bytesTente
fonte
JavaScript (Node.js) , 41 bytes
Uma porta da resposta do xnor . Recebe a entrada como um literal BigInt.
Experimente online!
JavaScript (ES6), 44 bytes
Recebe a entrada como uma matriz de caracteres, na primeira ordem do LSB.
Experimente online!
fonte
Na verdade , 8 bytes
Experimente online!
A entrada é tomada como uma lista de bits na primeira ordem do LSB.
Explicação:
fonte
Powershell, 68 bytes
Script de teste:
Resultado:
fonte
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.
Experimente online!
Ungolfed
fonte
Z80Golf , 34 bytes
Exemplo com entrada 1001-Experimente online!
Exemplo com entrada 100101000-Experimente online!
Montagem:
fonte