Os números iniciais mais baixos em uma sequência semelhante a Fibonacci

22

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
Stewie Griffin
fonte
Se a>=0e a<bsempre existem várias soluções?
Jonathan Allan
Não posso garantir que haja ou não várias soluções. Ambos 1,4e 2,3daria 5, 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.
Stewie Griffin
2
totalmente inspirado em codegolf.stackexchange.com/q/147200/67961
J42161217
3
A sequência OEIS correspondente para a menor média possível, A249783 , possui um gráfico de aparência selvagem .
22416 Peter Kagey
1
@ ØrjanJohansen Adicionei uma prova à minha resposta de que não existem soluções duplicadas (já que minha resposta dependia disso).
cardboard_box

Respostas:

8

Husk , 19 18 16 14 13 15 bytes

Obrigado Zgarb por economizar 1 byte.

ḟö£⁰ƒẊ++ÖΣṖ2Θḣ⁰

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(+).).(++), onde mapad2é aplicada a função a todos os pares adjacentes em uma lista. (Embora, conhecendo Husk, no contexto deste programa possa significar outra coisa)

            Θḣ⁰    Create the list [0..input]
          Ṗ2       Generate all possible sublists of length 2
        ÖΣ         Sort them on their sums
ḟ                  Find the first element that satisfies the following predicate.
    ƒẊ++             Given [a,b], magically generate the infinite Fibonacci-like
                     sequence from [a,b] without [a,b] at the start.
 ö£⁰                 Is the input in that list (given that it is in sorted order)?
H.PWiz
fonte
Salvar um byte com ö
Zgarb 12/11
Eu tenho certeza que tentei isso ... #
2117 H.PWiz
8

JavaScript (Node.js) , 92 90 89 91 83 82 bytes

-3 bytes -1 byte graças a ThePirateBay

-8 -9 bytes graças a Neil.

f=(n,a=1,b=0,c=(a,b)=>b<n?c(a+b,a):b>n)=>c(a,b)?b+2<a?f(n,a-1,b+1):f(n,b-~a):[b,a]

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 com a,b:

FIB(a,b,0) = a
FIB(a,b,1) = b
FIB(a,b,k) = FIB(a,b,k-1) + FIB(a,b,k-2)

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,bexiste uma solução satisfatória a+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 < 5podem ser verificados exaustivamente.

Suponha que tenhamos duas soluções mínimas para n >= 5, a0,b0e a1,b1com a0 + b0 = a1 + b1e a0 != a1.

Então existe k0,k1tal que FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

  • Caso 1: k0 = k1

    O WLOG assume b0 < b1(e, portanto a0 > a1)

    Seja DIFF(k)a diferença entre as seqüências do tipo Fibonnaci começando com a1,b1e a0,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é quando k = 2, então a única opção k0 = 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 para k >= 0, também não é decrescente.

    Isso nos dá a2 >= b1 > a0e b2 >= 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, DIFFpossui 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 para k0é 1.

    FIB(a0,b0,1) = n

    b0 = n

    Isso contradiz o lema 2.

caixa de papelão
fonte
1
77 bytes
Neil
@ Neil Isso minimiza em bvez de minimizar a+be, 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.
cardboard_box
1
Eu acho que você pode salvar outro byte usando em b-~avez de a+b+1.
1111 Neil
1
Há um pequeno erro no seu segundo caso: a2 >= a1 + b1não está correto quando k1-k0=1. Em vez disso, você pode usar a2 >= b1 > a0e b2 >= a1+b1 = a0+b0, e depois o resto.
Ørjan Johansen
8

Haskell , 76 72 74 bytes

EDITAR:

  • -4 bytes: @ H.PWiz sugeriu o uso em /vez de div, embora isso exija o uso de um tipo de número fracionário.
  • +2 bytes: corrigido um erro com Enumintervalos adicionando -1.

fpega um valor Doubleou Rationaldigite e retorna uma tupla do mesmo. Doubledeve ser suficiente para todos os valores que não são grandes o suficiente para causar erros de arredondamento, enquanto Rationalé teoricamente ilimitado.

f n|let a?b=b==n||b<n&&b?(a+b)=[(a,s-a)|s<-[1..],a<-[0..s/2-1],a?(s-a)]!!0

Experimente online!(com os ajustes de cabeçalho de H.PWiz para entrada / saída Rationals no formato inteiro)

Como funciona

  • ?é um operador localmente aninhado no escopo de f. a?bpercorre recursivamente a sequência semelhante a Fibonacci, começando com a,baté b>=n, retornando Truese acertarn exatamente.
  • Na compreensão da lista:
    • sitera todos os números de 1cima para baixo, representando a soma de ae b.
    • a itera através dos números de 0 para s/2-1. (Se sfor ímpar, o final do intervalo será arredondado.)
    • a?(s-a)testa se a sequência que começa com a,s-ahitsn . Nesse caso, a compreensão da lista inclui a tupla (a,s-a). (Ou seja, b=s-aembora tenha sido muito curto para valer a pena nomear.)
    • !!0 seleciona o primeiro elemento (ocorrência) na compreensão.
Ørjan Johansen
fonte
8

APL (Dyalog) , 75 71 64 59 53 48 44 43 bytes

2 bytes salvos graças a @ Adám

12 bytes salvos graças a @ngn

o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨oa/⍨</¨a←,⍉|-21+k←⎕

Experimente online!

Usos ⎕IO←0.

Quão? Isso tinha enlouquecido de verdade.

k←⎕ - atribuir entrada para k

⍳2⍴1+k←⎕- Produto cartesiano da gama 0para ksi próprio

|-\¨ - subtrair cada elemento do par direito da esquerda e obter valores absolutos

a←,⍉ - transpor, achatar e atribuir a a

o←a/⍨</¨a - mantenha apenas pares onde o elemento esquerdo é menor que o direito e atribua a o

oagora contém uma lista de todos os pares com a < b, ordenados por sua média aritemática

+\∘⌽⍣{k≤⊃⍺}¨o- para cada par o, aplique fibonacci (inverta o par e o cumsum) até que o kprazo seja alcançado

k∊¨- decida se kesse último termo (ou seja, está contido na sequência)

o/⍨- e mantenha pares oonde a verificação anterior se aplica

- retorna o primeiro resultado.

Uriel
fonte
5

Python 2 , 127 109 107 bytes

-2 bytes graças a ovs (alterando andpara *)

g=lambda x,a,b:a<=b<x and g(x,b,a+b)or b==x
f=lambda n,s=1,a=0:g(n,a,s-a)*(a,s-a)or f(n,s+(a==s),a%s+(a<s))

Experimente online!

Quaisquer pontos de bônus para n,a,s-a ?

Explicação:

  • A primeira linha declara uma lambda recursiva g, que verifica se será a, bexpandida como uma sequência de Fibonacci x. Ele também verifica que a <= b, um dos critérios da questão. (Isso permitiria casos em que a == b, mas nesse caso0, a , já teriam sido descobertos e retornados).
    • A desigualdade encadeada a<=b<xexecuta duas tarefas úteis ao mesmo tempo: verificar a <= be queb < x .
    • Se b < xproduzir True, 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é ...
    • Se b < xceder False, chegamos ao ponto em que precisamos verificar se b==x. Nesse caso, isso retornará True, significando que o par inicial a, bchegará eventualmente x. Caso contrário, se b > xo par for inválido.
  • A segunda linha declara outra lambda recursiva f, que encontra a solução para um determinado valor n. Tenta recursivamente novos pares iniciais a, b, até g(n, a, b)obterTrue . Esta solução é então retornada.
    • A função recursivamente conta pares iniciais de Fibonacci usando duas variáveis s(inicialmente 1) e a(inicialmente 0). Em cada iteração, aé incrementado e a, s-aé usado como o primeiro par. No entanto, quando ahitss , ele está de volta reposto a 0 e sé incrementado. Isso significa que os pares são contados no seguinte padrão:
      s = 1 (0, 1) (1, 0)
      s = 2 (0, 2) (1, 1) (2, 0)
      s = 3 (0, 3) (1, 2), (2, 1), (3, 0)
      
      Obviamente, isso contém alguns pares inválidos, porém estes são eliminados instantaneamente quando passados ​​para g(consulte o primeiro ponto).
    • Quando valores ae ssão encontrados de tal forma que g(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.
FlipTack
fonte
3

R , 183 bytes 160 bytes

n=scan();e=expand.grid(n:0,n:0);e=e[e[,2]>e[,1],];r=e[mapply(h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),n,e[,1],e[,2]),];r[which.min(rowSums(r)),]

Experimente online!

Agradecimentos a Giuseppe por jogar fora 23 bytes

Explicação do código

n=scan()                        #STDIO input
e=expand.grid(n:0,n:0)          #full outer join of integer vector n to 0
e=e[e[,2]>e[,1],]               #filter so b > a
r=e[mapply(
  h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),
                                #create a named recursive function mid-call 
                                #(requires using <- vs = to denote local variable creation 
                                #rather than argument assignment
  n,e[,1],e[,2]),]              #map n, a and b to h() which returns a logical
                                #which is used to filter the possibilities
r[which.min(rowSums(r)),]       #calculate sum for each possibility, 
                                #get index of the minimum and return
                                #because each possibility has 2 values, the mean and 
                                #sum will sort identically.
Marca
fonte
1
160 bytes - em geral, você deve salvar os bytes sempre que puder, portanto, salvar 4 bytes removendo uma boa nomeação não é apenas aceitável ou incentivado, mas, em certo sentido, exigido pelo code-golf . Mesmo assim, boa resposta, +1.
Giuseppe
1

Mathematica, 117 bytes

If[#==1,{0,1},#&@@SortBy[(S=Select)[S[Range[0,s=#]~Tuples~2,Less@@#&],!FreeQ[LinearRecurrence[{1,1},#,s],s]&],Mean]]&


Experimente online!

J42161217
fonte
1

Geléia , 19 bytes

ṫ-Sṭµ¡³e
0rŒcÇÐfSÐṂ

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.

Erik, o Outgolfer
fonte
... um incremento inicial deve resolver a observação de @ StewieGriffin.
Jonathan Allan
Eu tenho um sentimento que você pode soltar a
Jonathan Allan
1
Só precisamos encontrar a semente que faz a entrada xparecer mais recente. Se x fosse encontrado no terceiro índice para múltiplo, ele funcionaria 0,xe, portanto, também funcionaria em 1,(x-1)/2( xímpar) ou 2,x/2-1( xpar) no qual xapareceria 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á xencontrado em um índice posterior . Como tal, podemos ṫ-Sṭµ¡i³¶ḶŒcÇÐṀsalvar quatro bytes.
Jonathan Allan
... opa, mais o incremento:ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
Jonathan Allan
@StewieGriffin Esse teste caso não existia quando eu respondi: p
Erik o Outgolfer
1

GolfScript - 88 bytes

~:N[,{1+:a,{[.;a]}/}/][{[.~{.N<}{.@+}while\;N=]}/]{)1=\;},{(\;~+}$(\;);~~' '\

Não verifiquei várias soluções, graças a cartão_box!

Explicação

~:N                           # Reads input
[,{1+:a,{[.;a]}/}/]           # Creates an array of pairs [a b]
[{[.~{.N<}{.@+}while\;N=]}/]  # Compute solutions
{)1=\;},         # Pairs that are not solutions are discarded
{(\;~+}$         # Sorts by mean
(\;);~~' '\      # Formats output
FedeWar
fonte
Experimente online!
Ørjan Johansen
0

Lote, 160 158 bytes

@set/aa=b=0
:g
@if %a% geq %b% set/ab-=~a,a=0
@set/ac=a,d=b
:l
@if %c% lss %1 set/ad+=c,c=d-c&goto l
@if %c% gtr %1 set/aa+=1,b-=1&goto g
@echo %a% %b%
Neil
fonte
Isso (também) fornece 3 7informações 27. A solução correta é 0 9.
22617
@cardboard_box ainda não vendo onde a questão exige que ...
Neil
Na primeira frase: "com o menor valor médio possível".
cardboard_box
@cardboard_box Ah, desculpe, isso foi muito fácil de ignorar.
911 Neil
1
@cardboard_box OK deve ser corrigido agora.
1111 Neil