Dada uma entrada inteiro positivo N , a saída dos dois números não-negativos, uma e b , onde a <b , com o valor médio mais baixo possível que irá resultar no número N sendo parte da sequência de relação recorrentes:
f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)
No caso de haver mais de uma solução em que a média de a e b é mínima, você deve gerar a solução com o menor b .
Você pode assumir que N está dentro do intervalo representativo de números inteiros no seu idioma / sistema.
Casos de teste
N = 1
a = 0, b = 1
N = 15
a = 0, b = 3
N = 21
a = 0, b = 1
N = 27
a = 0, b = 9 <- Tricky test case. [3, 7] is not optimal and [4, 3] is not valid
N = 100
a = 4, b = 10
N = 101
a = 1, b = 12
N = 102
a = 0, b = 3
N = 1000
a = 2, b = 10
a>=0
ea<b
sempre existem várias soluções?1,4
e2,3
daria5
, e eles têm a mesma média. Acho que é possível encontrar casos semelhantes a esse, onde esses são os valores médios mais baixos. Se você pode mostrar / provar que não há várias soluções, não precisa verificar essa condição.Respostas:
Husk ,
191816141315 bytesObrigado Zgarb por economizar 1 byte.
Experimente online!
Explicação:
Isenção de responsabilidade: eu realmente não entendo a
ȯƒẊ++
seção do código.Editar: parece ser traduzido para o Haskell
fix.(mapad2(+).).(++)
, ondemapad2
é aplicada a função a todos os pares adjacentes em uma lista. (Embora, conhecendo Husk, no contexto deste programa possa significar outra coisa)fonte
JavaScript (Node.js) ,
92 90 89 91 8382 bytes-3 bytes-1 byte graças a ThePirateBay-8-9 bytes graças a Neil.Experimente online!
Nota: esta solução depende do fato de nunca haver várias soluções mínimas.
Prova de que nunca existem várias soluções:
Let
FIB(a,b,k)
Ser a seqüência de Fibonacci-like começando coma,b
:Lema 1
A diferença entre sequências do tipo Fibonacci é ela própria do tipo Fibonacci, ie
FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)
. A prova é deixada ao leitor.Lema 2
Pois
n >= 5
,a,b
existe uma solução satisfatóriaa+b < n
:se
n
é par,FIB(0,n/2,3) = n
se
n
é impar,FIB(1,(n-1)/2,3) = n
Prova
Casos onde
n < 5
podem ser verificados exaustivamente.Suponha que tenhamos duas soluções mínimas para
n >= 5
,a0,b0
ea1,b1
coma0 + b0 = a1 + b1
ea0 != a1
.Então existe
k0,k1
tal queFIB(a0,b0,k0) = FIB(a1,b1,k1) = n
.Caso 1:
k0 = k1
O WLOG assume
b0 < b1
(e, portantoa0 > a1
)Seja
DIFF(k)
a diferença entre as seqüências do tipo Fibonnaci começando coma1,b1
ea0,b0
:DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)
(Lema 1)DIFF(0) = a1 - a0 < 0
DIFF(1) = b1 - b0 > 0
DIFF(2) = (a1+b1) - (a0+b0) = 0
DIFF(3) = DIFF(1) + DIFF(2) = DIFF(1) > 0
DIFF(4) = DIFF(2) + DIFF(3) = DIFF(3) > 0
Uma vez que uma sequência semelhante a Fibonnaci tenha 2 termos positivos, todos os termos subsequentes serão positivos.
Assim, o único momento
DIFF(k) = 0
é quandok = 2
, então a única opçãok0 = k1
é2
.Assim sendo
n = FIB(a0,b0,2) = a0 + b0 = a1 + b1
A minimalidade dessas soluções contradiz o Lema 2.
Caso 2
k0 != k1
:WLOG assume
k0 < k1
.Nós temos
FIB(a1,b1,k1) = n
Deixei
a2 = FIB(a1,b1,k1-k0)
Deixei
b2 = FIB(a1,b1,k1-k0+1)
Então
FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)
(exercício para o leitor)Como
FIB(a1,b1,k)
não é negativo parak >= 0
, também não é decrescente.Isso nos dá
a2 >= b1 > a0
eb2 >= a1+b1 = a0+b0
.Então vamos
DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)
(Lema 1)DIFF(0) = a2 - a0 > 0
DIFF(1) = b2 - b0 >= (a0 + b0) - b0 = a0 >= 0
DIFF(2) = DIFF(0) + DIFF(1) >= DIFF(0) > 0
DIFF(3) = DIFF(1) + DIFF(2) >= DIFF(2) > 0
Mais uma vez,
DIFF
possui 2 termos positivos e, portanto, todos os termos subsequentes são positivos.Assim, o único momento em que é possível que
DIFF(k) = 0
ék = 1
, por isso, a única opção parak0
é1
.FIB(a0,b0,1) = n
b0 = n
Isso contradiz o lema 2.
fonte
b
vez de minimizara+b
e, portanto, sua solução fornece,f(27) = [3,7]
mas a solução ideal éf(27)=[0,9]
. Depois de reverter as alterações mais recentes, reduzimos para 83 bytes.b-~a
vez dea+b+1
.a2 >= a1 + b1
não está correto quandok1-k0=1
. Em vez disso, você pode usara2 >= b1 > a0
eb2 >= a1+b1 = a0+b0
, e depois o resto.Haskell ,
76 7274 bytesEDITAR:
/
vez dediv
, embora isso exija o uso de um tipo de número fracionário.Enum
intervalos adicionando-1
.f
pega um valorDouble
ouRational
digite e retorna uma tupla do mesmo.Double
deve ser suficiente para todos os valores que não são grandes o suficiente para causar erros de arredondamento, enquantoRational
é teoricamente ilimitado.Experimente online!(com os ajustes de cabeçalho de H.PWiz para entrada / saída
Rational
s no formato inteiro)Como funciona
?
é um operador localmente aninhado no escopo def
.a?b
percorre recursivamente a sequência semelhante a Fibonacci, começando coma,b
atéb>=n
, retornandoTrue
se acertarn
exatamente.s
itera todos os números de1
cima para baixo, representando a soma dea
eb
.a
itera através dos números de0
paras/2-1
. (Ses
for ímpar, o final do intervalo será arredondado.)a?(s-a)
testa se a sequência que começa coma,s-a
hitsn
. Nesse caso, a compreensão da lista inclui a tupla(a,s-a)
. (Ou seja,b=s-a
embora tenha sido muito curto para valer a pena nomear.)!!0
seleciona o primeiro elemento (ocorrência) na compreensão.fonte
APL (Dyalog) ,
7571645953484443 bytes2 bytes salvos graças a @ Adám
12 bytes salvos graças a @ngn
Experimente online!
Usos
⎕IO←0
.Quão? Isso tinha enlouquecido de verdade.
k←⎕
- atribuir entrada parak
⍳2⍴1+k←⎕
- Produto cartesiano da gama0
parak
si próprio|-\¨
- subtrair cada elemento do par direito da esquerda e obter valores absolutosa←,⍉
- transpor, achatar e atribuir aa
o←a/⍨</¨a
- mantenha apenas pares onde o elemento esquerdo é menor que o direito e atribua ao
o
agora contém uma lista de todos os pares coma < b
, ordenados por sua média aritemática+\∘⌽⍣{k≤⊃⍺}¨o
- para cada paro
, aplique fibonacci (inverta o par e o cumsum) até que ok
prazo seja alcançadok∊¨
- decida sek
esse último termo (ou seja, está contido na sequência)o/⍨
- e mantenha pareso
onde a verificação anterior se aplica⊃
- retorna o primeiro resultado.fonte
Python 2 ,
127109107 bytes-2 bytes graças a ovs (alterando
and
para*
)Experimente online!
Quaisquer pontos de bônus para
n,a,s-a
?Explicação:
g
, que verifica se seráa, b
expandida como uma sequência de Fibonaccix
. Ele também verifica quea <= b
, um dos critérios da questão. (Isso permitiria casos em quea == b
, mas nesse caso0, a
, já teriam sido descobertos e retornados).a<=b<x
executa duas tarefas úteis ao mesmo tempo: verificara <= b
e queb < x
.b < x
produzirTrue
, a função se chamará novamente com os próximos dois números na sequência de Fibonacci:b, a+b
. Isso significa que a função continuará elaborando novos termos até ...b < x
cederFalse
, chegamos ao ponto em que precisamos verificar seb==x
. Nesse caso, isso retornaráTrue
, significando que o par iniciala, b
chegará eventualmentex
. Caso contrário, seb > x
o par for inválido.f
, que encontra a solução para um determinado valorn
. Tenta recursivamente novos pares iniciaisa, b
, atég(n, a, b)
obterTrue
. Esta solução é então retornada.s
(inicialmente 1) ea
(inicialmente 0). Em cada iteração,a
é incrementado ea, s-a
é usado como o primeiro par. No entanto, quandoa
hitss
, ele está de volta reposto a 0 es
é incrementado. Isso significa que os pares são contados no seguinte padrão: Obviamente, isso contém alguns pares inválidos, porém estes são eliminados instantaneamente quando passados parag
(consulte o primeiro ponto).a
es
são encontrados de tal forma queg(n, a, s-a) == True
, esse valor é retornado. Como as possíveis soluções são contadas em ordem de 'tamanho' (classificadas por média e valor mínimo), a primeira solução encontrada será sempre a menor, conforme o desafio solicitar.fonte
R ,
183 bytes160 bytesExperimente online!
Agradecimentos a Giuseppe por jogar fora 23 bytes
Explicação do código
fonte
Mathematica, 117 bytes
Experimente online!
fonte
Geléia , 19 bytes
Experimente online!
-1 byte graças à prova de cartão_box . Caso seja reprovado, você pode acrescentar
UṂṚ
ao final da segunda linha um total de 22 bytes.fonte
Ḣ
x
parecer mais recente. Sex
fosse encontrado no terceiro índice para múltiplo, ele funcionaria0,x
e, portanto, também funcionaria em1,(x-1)/2
(x
ímpar) ou2,x/2-1
(x
par) no qualx
apareceria posteriormente no resultado, para que isso não aconteça. Para uma colisão posterior, a média só pode ser a mesma se os terceiros termos também forem os mesmos, mas é preciso haver uma diferença menor entre os termos iniciais (caso contrário, eles seriam os mesmos) e, portanto, seráx
encontrado em um índice posterior . Como tal, podemosṫ-Sṭµ¡i³¶ḶŒcÇÐṀ
salvar quatro bytes.ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
GolfScript -
88bytesNão verifiquei várias soluções, graças a cartão_box!
Explicação
fonte
Lote,
160158 bytesfonte
3 7
informações27
. A solução correta é0 9
.