Desafio
Você precisa gerar um programa ou função que receba um número inteiro positivo N, calcule os primeiros N termos da sequência de Fibonacci em binário, concatene-o em um único número binário, converta esse número de volta para decimal e, em seguida, gera o decimal como um inteiro.
Por exemplo
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
Você não precisa emitir o ->
, apenas o número (por exemplo, se o usuário digitar 4
, apenas o resultado 14
). As setas são apenas para ajudar a explicar o que o programa deve fazer.
Casos de teste
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
O programa deve ser capaz de produzir até o limite do idioma em uso. Não são permitidas tabelas de pesquisa ou soluções alternativas comuns .
Isso é código-golfe , então a resposta com o menor número de bytes vence!
int32_t binary_concat_Fib(int n)
, o que limitaria o valor de saída resultante a 2 ^ 31-1. ou seja, você assume que todos os bits concatenados se encaixam em um número inteiro. Ou a função deve funcionar até o ponto em que o maior número de Fibonacci não se encaixa em um número inteiro por si só, para concatenar os bits requer precisão estendida?Respostas:
Python , 64 bytes
Experimente online!
fonte
Geléia ,
76 bytesExperimente online!
Quão?
fonte
Ṛc’SƲƤ
que poderia ser útil para seqüências semelhantes.Python 3.6 , 61 bytes
Experimente online!
fonte
brainfuck , 397 bytes
Bem, isso foi divertido!
Pega a entrada ASCII (por exemplo
11
), as saídas resultam em ASCII.Nota: para tentar isso online, defina o tamanho da célula para 32 bits (no lado direito da página da web). Se você não inserir uma entrada, seu navegador poderá travar.
O intérprete não pode manipular entrada de
11
e superior porque suporta apenas até 32 bits.Experimente em copy.sh
Explicação
Obtenha entrada decimal e adicione uma (para reduzir o número um por um)
Gere números de fibonacci na fita.
Configurado para o loop de concatenação binária de entrada
Portanto, as células contêm o valor, começando na primeira posição,
Veja estas células:
Vou rotular isso:
pow
existe para encontrar a potência máxima de 2 que é estritamente maior quenum
.sum
é a concatenação de números até agora.cat
é o poder de 2 que eu precisaria multiplicarnum
para concatenarnum
na frente dosum
(para que eu pudesse simplesmente adicionar).Loop: verifique se
f_n
é estritamente menor quepow
.Verdade:
Zere o lixo. Em seguida, adicione
num
*cat
asum
. Em seguida, carregue o próximo número de Fibonacci (=f_(n-1)
; se não existir, saia do loop) e definacat
comocat
*pow
. Prepare-se para o próximo loop (zere mais lixo, mude o escopo por um).Falsey:
Defina
pow
como 2 *pow
, restaurenum
.Repita até que não haja nenhum número de Fibonacci.
Lixo limpo. Pegue cada dígito do número resultante e imprima cada um (em ascii).
fonte
Casca , 7 bytes
Experimente online!
Explicação
fonte
Japonês , 9 bytes
Executá-lo
Explicação:
fonte
Pitão, 22 bytes
Experimente aqui
Explicação
fonte
Perl 6 , 38 bytes
Experimente online!
fonte
JavaScript (Node.js) ,
7065585755 bytesExperimente online!
fonte
-0
no final para salvar outros 2 bytes.05AB1E , 6 bytes
Experimente online!
1 indexado.
fonte
J, 36 bytes
Explicação:
fonte
x86,
372221 bytesChangelog
bsr
. Obrigado Peter Cordes!-2 zerando os registros com
mul
.-1 usando um loop while em vez de
loop
epush
/pop
ecx
(crédito Peter Cordes).Entrada
edi
, saídaedx
.Objdump:
fonte
lea
para alternar e adicionar fib2. Além disso, extrair cada bit, um de cada vez, é desnecessário. Usebsr %eax, %ecx
para encontrar o número de bits na representação binária e use um deslocamento por CL / ou para mesclar, como a resposta Python de Dennis está fazendo.cl
da contagem de turnos, portanto, pegue seu contador de loop em um registro diferente (como%edi
) e usedec %edi / jnz
(3 bytes no código de 32 bits, 4 bytes em 64 bits). No código de 32 bits, isso economiza 1 byte total ao descartar o push / pop ecx. Não caia na armadilha de usarloop
quando isso dificulta, não é mais fácil. (Sua convenção de chamada já é personalizada,%ebx
portanto, não chame sua funçãomain
) Você pode retornar no EAX enquanto ainda aproveita o byte de 1 bytexchg
, não precisa ser não-padrão se não precisar.inc %ecx
da contagem de turnos por um turno extra para a esquerda, à medida que adicionar, usandolea (%eax, %edx, 2), %edx
. Neutro em bytes para 32 bits, salva um em x86-64. Mas salva uma instrução.loop
código de golfe, me sinto suja. Bem, não exatamente, mas desapontado por não encontrar uma implementação igualmente pequena que evitasse essa instrução lenta; fora do código de golfe,loop
é uma das minhas irritações . Eu gostaria que fosse rápido nas CPUs modernas, porque seria muito bom para loops de precisão estendida sem paradas de flag parcial, mas não é e deve ser considerado apenas como uma instrução obscura de otimização de tamanho que torna seu código lento.xor
/mul
truque para zero três registros (Você sempre precisa que muitos zeros?), Mas usando isso como parte da criação de um1
torna mais sensível.APL (Dyalog) ,
2622 bytes4 bytes salvos graças a @ H.PWiz
Experimente online!
fonte
Haskell ,
897675 bytesVersão não destruída:
fonte
f=0:scanl(+)1f
(extraída daqui ). As funções podem ser anônimas, para que você possa abandonar a liderançag=
, consulte o nosso Guia de regras de golfe em Haskell .$realToFrac y
com.read.show$y
um bytePari / GP , 59 bytes
Experimente online!
fonte
APL + WIN, 55 bytes
Solicita a entrada na tela do número inteiro.
A precisão inteira máxima do APL + WIN é 17 e o limite inteiro é da ordem de 10E300, portanto, o número máximo de entrada é 55 e o resultado é: 1.2492739026634838E300
fonte
Python 3 , 94 bytes
Experimente online!
fonte
Gelatina , 6 bytes
Experimente online!
Ḷ
gama owered -> n ºÆḞ
número ibonacci -> a partir de dezembro deB
inary ->F
Latten -> a partirḄ
inary a dezembrofonte
10
e você receberá um16024033463
, está incorreto (a resposta correta é250375522
).10
retorna250375522
MATL , 21 bytes
Experimente online!
Explicação
fonte
J , 25 bytes
Experimente online!
Explicação
fonte
Python 3 , 86 bytes
Experimente online!
fonte
Adicionar ++ , 113 bytes
Experimente online!
fonte
PHP, 124 bytes
Experimente online!
Então, eu estava procurando uma maneira de gerar números de fibonacci usando a série, até encontrar isso . Acontece que você pode calcular a série de fibonacci por arredondamento, então tentei o desafio com uma função recursiva.
Achei a abordagem do "arredondamento" muito interessante, também um professor me mostrou isso há um tempo atrás.
Código
Explicação
Além disso, verifique esta postagem do stackoverflow. A melhor resposta refere-se ao mesmo artigo na Wikipedia.
fonte
Stax , 9 bytes
Execute e depure-o em staxlang.xyz!
Descompactado (10 bytes) e explicação:
fonte
Julia 0.6 , 65 bytes
Experimente online!
fonte
Pitão, 27 bytes
Suíte de teste
Tradução Python 3:37 bytesSuíte de teste
Tradução Python 3:fonte
Ruby , 61 bytes
Experimente online!
fonte
Jotlin , 59 bytes
Programa de teste
Suporta até 10, mudar
.i(2)
para.toLong(2)
suportaria até 14, se necessáriofonte
Python 2, 88 bytes
fonte
R ,
244180179 bytesExperimente online!
Salvou alguns bytes concatenando vetores numéricos, não seqüências de caracteres. Caso especial sangrento para 0!
fonte
sapply
em um vetor devido ao fato de ser recursiva. Não pode ser tudo agrupado em uma linha. Como você vê, o programa solicita a entrada do usuário e, em seguida, retorna a resposta. Um byte pode ser salvo criando um atalho paraifelse
. E ... nós podemos remover,""
a partirscan
, sim.