Definição
A sequência de Fibonacci de potência alternada é formada como se segue.
Comece com a sequência vazia e defina n como 1 .
Calcular f n , a n th não-negativo número de Fibonacci , com repetições.
0 é o primeiro, 1 é o segundo e o terceiro, 2 é o quarto. Todos os outros são obtidos somando os dois números anteriores na sequência, então 3 = 1 + 2 é o quinto, 5 = 2 + 3 é o sexto, etc.Se n for ímpar, altere o sinal de f n .
Anexe 2 cópias n-1 de f n à sequência.
Incremente n e volte para a etapa 2.
Estes são os primeiros cem termos da sequência APF.
0 1 1 -1 -1 -1 -1 2 2 2 2 2 2 2 2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
Tarefa
Escrever um programa completo ou uma função que leva um número inteiro positivo n como entrada e devolve a gravuras ou n th termo da sequência do APF.
Se você preferir a indexação com base em 0, pode pegar um número inteiro não negativo n e imprimir ou retornar o número APF no índice n .
Isso é código-golfe ; pode ganhar o código mais curto em bytes!
Casos de teste (com base em 1)
1 -> 0
2 -> 1
3 -> 1
4 -> -1
7 -> -1
8 -> 2
100 -> -8
250 -> 13
500 -> -21
1000 -> 34
11111 -> 233
22222 -> -377
33333 -> 610
Casos de teste (com base em 0)
0 -> 0
1 -> 1
2 -> 1
3 -> -1
6 -> -1
7 -> 2
99 -> -8
249 -> 13
499 -> -21
999 -> 34
11110 -> 233
22221 -> -377
33332 -> 610
Respostas:
Gelatina , 5 bytes
Experimente online!
Quão?
Estendendo a série Fibonacci de volta a índices negativos, de modo que a relação
f(i) = f(i-2) + f(i-1)
ainda se mantenha:Voltando
i=0
a esses números, precisamos repetir 2 n-1 vezes, e o Fibonacci de Jelly embutidoÆḞ
calculará isso.Podemos encontrar o
-i
(um número positivo) de que precisamos tomando o comprimento de bitsn
e subtraindo1
.Desde que nós queremos
i
(um número negativo), podemos, em vez realizar1-bitLength
e Jelly tem um átomo para1-x
,C
, a Mônada complemento.fonte
µ
e⁸
Python 2 , 30 bytes
Experimente online!
Um indexado.
A sequência parecia um quebra-cabeça, algo que Dennis gerou por ter uma maneira curta de expressá-la. A potência de duas repetições sugere a repetição por deslocamento de bits (divisão do piso por 2). A recursão de Fibonacci de sinal alternado
f(n)=f(n-2)-f(n-1)
pode ser adaptada ao deslocamento de bits no lugar de decrementar. O caso base funciona muito bem porque tudo se afunilan=0
.fonte
Mathematica,
433624 bytes7 bytes salvos graças a @GregMartin e mais 12 graças a @JungHwanMin.
fonte
Floor@Log2@#
e escrevendoFibonacci[t=...]
(e removendo os espaços no último expoente).Fibonacci@-Floor@Log2@#&
- tambémFibonacci
pode receber argumentos negativos (cuida do sinal para você).MATL ,
19171611 bytesA entrada é baseada em 1.
Experimente online! Ou verifique todos os casos de teste .
Como funciona
Para a entrada 1 com base n , seja m o número de dígitos na expansão binária de n . O n- ésimo termo na sequência de saída é o m- ésimo termo na sequência de Fibonacci, possivelmente com seu sinal alterado.
Uma idéia seria iterar m vezes para calcular os termos da sequência de Fibonacci. Isso é fácil com um
for each
loop usando a matriz de dígitos binários. Se a sequência de Fibonacci fosse inicializada com 0 e , em seguida, 1 como de costume, a repetição de m resultaria em termos de m + 2 na pilha; portanto, os dois primeiros números teriam que ser excluídos. Em vez disso, inicializamos com 1 e depois com 0 . Dessa forma, os próximos termos gerados são 1 , 1 , 2 , ... e apenas uma exclusão é necessária.O sinal pode ser tratado usando outro loop para alterar o sinal m vezes. Mas isso é caro. É melhor integrar os dois loops, o que é feito simplesmente subtraindo em vez de adicionar na iteração Fibonacci.
fonte
JavaScript (ES6), 33 bytes
1 indexado.
Uma porta da resposta do xnor seria 23:
fonte
Python 2 ,
838279 bytesExperimente online!
fonte
or -1
.Geléia , 9 bytes
Usa indexação baseada em um.
Experimente online!
Explicação
Este método funciona se a função Fibonacci oferecer suporte apenas a argumentos não negativos.
fonte
Japonês , 6 bytes
Teste online!
Como funciona
Como mencionado em outras respostas, o n º termo na série de Fibonacci alternando-sinal é o mesmo que o -n th termo na série regular. n pode ser encontrado pegando o comprimento do bit da entrada e subtraindo um; negar isso resulta em 1 menos o comprimento do bit.
fonte
05AB1E ,
1110 bytesUsa indexação baseada em 1
A função Fibonacci de 05AB1E retorna números de fib positivos menores que n , o que significa que teríamos que gerar mais do que o necessário, obter o correto pelo índice e calcular o sinal. Portanto, duvido que qualquer método baseado em que seja mais curto do que calcular os números iterativamente.
Usa a percepção de que podemos inicializar a pilha com
1, 0
reverso para lidar com o caso,n=1
conforme descrito na resposta MATL de Luis Mendo .Experimente online!
Explicação
fonte
Perl 6 , 53 bytes
Implementação direta da sequência, da maneira como foi descrita.
Baseado em zero.
fonte
Julia 0,5 , 19 bytes
Experimente online!
Como funciona
Isso usa a mesma fórmula da resposta Python do @ xnor . A relação de recorrência
g (n) = g (n-2) + g (n-1) gera os termos negativos da sequência de Fibonacci, que igualam os termos positivos com sinais alternados. De qualquer lugar em uma execução de 2 k repetições do mesmo número, podemos escolher qualquer repetição da execução anterior de 2 k-1 números e da execução de 2 k-2 números anteriores àqueles dividindo o índice por 2 e 4 .
Ao invés do simples
podemos redefinir um operador para nossos propósitos. Além disso, f funcionará tão bem com flutuadores, então obtemos
Finalmente, se atualizarmos n com uma divisão por 4 , o wwe poderá escrever n / 2 como 2n e omitir um par de parênteses, levando à definição da função de 19 bytes nesta resposta.
fonte
J , 18 bytes
Usa indexação baseada em um. Pega um número inteiro de entrada n > 0 e calcula
floor(log2(n))
encontrando o comprimento de sua representação binária e, em seguida, diminui esse valor em um. Em seguida, ele encontra o coeficientefloor(log2(n))-1
th da função geradora x / (1 + x - x 2 ), que é o gf para os valores de Fibonacci indexados negativamente.Experimente online!
Explicação
fonte