Você provavelmente já ouviu falar dos números de Fibonacci. Você sabe, aquela sequência inteira que começa com 1, 1
, e então cada novo número é a soma dos dois últimos?
1 1 2 3 5 8 13...
E assim por diante. Os desafios sobre os números de Fibonacci são bastante populares por aqui . Mas quem disse que os números de Fibonacci precisam começar 1, 1
? Por que eles não podiam começar 0, 1
? Tudo bem, vamos redefini-los para começar em 0:
0 1 1 2 3 5 8 13...
Mas ... Nós também não temos que parar por aí! Se pudermos adicionar os dois últimos números para obter o próximo, também podemos subtrair o primeiro número do segundo número para adicionar um novo número. Então, pode começar com 1, 0
:
1 0 1 1 2 3 5 8 13...
Podemos até acabar com negativos:
-1 1 0 1 1 2 3 5 8 13...
E esta série também continua para sempre. Eu acho interessante como isso acaba refletindo os números regulares de Fibonacci, apenas com todos os outros números negativos:
13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...
Vamos chamar essa série de "Número Estendido de Fibonacci", ou EFN . Como não há realmente um número negativo óbvio para iniciar esta série, diremos que 0 aparece em 0 , os números regulares de Fibonacci se estendem aos índices positivos e os números negativos (meio-negativos?) De Fibonacci se estendem para os índices negativos, assim:
Indices: ...-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
Values: ...13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...
Isso leva ao desafio de hoje:
Dado um número inteiro N , retorne todos os índices nos quais N aparece na série EFN .
Algumas observações aleatórias sobre esta tarefa:
1 aparece mais vezes no EFN do que qualquer outro número:
[-1, 1, 2]
. Nenhum número aparecerá em mais de 3 lugares.Todo número de Fibonacci> 1 será exibido uma vez (3, 8, 21 etc.) ou duas vezes (2, 5, 13 etc.)
Esclarecimentos sobre as regras:
- Se
abs(N)
não for um número de Fibonacci, ele nunca aparecerá na série EFN ; portanto, você não deve produzir nada / uma coleção vazia, se possível, ou se isso não for possível no seu idioma, você poderá gerar algum valor não numérico constante. - Se N aparecer em vários locais no EFN , sua saída não precisará ser classificada. Embora cada índice deva aparecer exatamente uma vez.
- Embora a maioria dos desafios de sequência permita que você escolha se deseja usar a indexação com base em 1 ou em 0, esse desafio deve usar a indexação descrita (onde 0 aparece em 0).
- Você pode levar a E / S através de qualquer formato padrão.
Casos de teste
-13: []
-12: []
-11: []
-10: []
-9: []
-8: [-6]
-7: []
-6: []
-5: []
-4: []
-3: [-4]
-2: []
-1: [-2]
0: 0
1: [-1, 1, 2]
2: [-3, 3]
3: [4]
4: []
5: [-5, 5]
6: []
7: []
8: [6]
9: []
10: []
11: []
12: []
13: [-7, 7]
E alguns casos de teste maiores:
89: [-11, 11]
1836311903: [46]
10000: []
-39088169: [-38]
Como sempre, a resposta mais curta em bytes vence!
Respostas:
Haskell , 78 bytes
4 bytes salvos graças a nimi
Experimente online!
Primeiro, configuramos
(#)
, obtemos(#)
dois parâmetrosa
eb
, e retorna a lista a iniciando coma
e seguida porb#(a-b)
. Isso cria uma lista infinita, mas, como Haskell é preguiçoso, não precisamos nos preocupar com isso para sempre. Isso funciona essencialmente para trás, criando a sequência de Fibonacci antes de um determinado par. Por exemplo,(0#1)
seria a lista de todos os números de Fibonacci com índice negativo.A partir daqui, fazemos
f
.f
usa um argumentoa
que é o número que estamos tentando encontrar na sequência. Aqui usamos ado
notação para fazer uma compreensão da lista. Começamos com os primeirosa*a+1
elementos da lista0#1
1 . Como a funçãoa*a+1
cresce mais rápido que o inverso da sequência de Fibonacci, podemos ter certeza de que, se verificarmos dentro desse limite, encontraremos todos os resultados. Isso nos impede de pesquisar uma lista infinita. Então, para cada valorx
e índicei
, sex==a
encontramosa
na metade negativa da sequência, retornamos-i
e seabs x==a
retornamosi
, porque o valor absoluto da metade negativa é a metade positiva, e então a encontramos.Como isso faz com que a lista
[0,0]
para0
nós codifique a saída correta para essa.1: Esse truque foi retirado da resposta limpa do ousurous . A mesma aceleração se aplica aqui e ali, substitua
a*a+1
porabs a+1
para economizar muito tempo.fonte
u
pora#b=a:b#(a-b)
mais0#1
salva um byte: Experimente online!Limpo ,
132120109 bytesExperimente online!
g :: Int -> Int
é a função de Fibonacci.? :: Int -> [Int]
apenas indexa os elementos do EFN dentrok^2+1
de0
.Para uma versão que é executada em uma quantidade razoável de tempo, altere
k*k+1
paraabs k+1
.fonte
Gelatina , 11 bytes
Experimente online!
fonte
JavaScript (ES6),
9493 bytesExperimente online!
fonte
APL (Dyalog Classic) ,
5250 bytesRequer
⎕IO←0
Experimente online!
fonte
Retina 0.8.2 ,
104102 bytesExperimente online! Explicação:
Converta para unário, a menos que a entrada seja zero.
Calcule o índice de Fibonacci do valor absoluto, mas se o número não for um número de Fibonacci, exclua-o, a menos que seja zero. Isso usa o regex de teste de Fibonacci do @ MartinEnder.
Exclua números negativos cujos valores absolutos são números ímpares de Fibonacci.
Adicione índices negativos para números de Fibonacci positivos ímpares.
Converta para decimal.
Adicione os índices extras para
1
.fonte
Na verdade , 34 bytes
Força bruta salva o dia
Explicação:
Experimente online!
fonte
Python 3 , 92 bytes
Experimente online!
Retorna um conjunto de índices.
fonte
Python 2 ,
8785 bytesExperimente online!
fonte
05AB1E , 36 bytes
Tem que haver uma abordagem melhor ..>.> Existem seis (ou sete, se incluirmos
0
) cenários diferentes para esse desafio, e isso está me matando.Experimente online ou verifique todos os casos de teste .
Explicação:
Alguns exemplos passo a passo:
fonte
Python 2 ,
959294 bytesExperimente online!
fonte
C # (compilador interativo do Visual C #) , 144 bytes
Experimente online!
fonte