Uma cadeia de adição é uma sequência de números inteiros começando com 1, em que cada número inteiro que não seja o 1 inicial é uma soma dos dois números anteriores.

Por exemplo, aqui está uma cadeia de adição:

[1, 2, 3, 4, 7, 8, 16, 32, 39, 71]

Aqui estão as somas que a tornam uma cadeia de adição:

1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
3 + 4 = 7
1 + 7 = 8
8 + 8 = 16
16 + 16 = 32
7 + 32 = 39
32 + 39 = 71

Neste desafio, você será dado um número inteiro positivo n, e você deve uma das cadeias de adição mais curtos que termina em saída n.

Exemplos - observe que existem muitas saídas possíveis, tudo o que você precisa encontrar é uma cadeia de adição tão curta quanto:

1: [1]
2: [1, 2]
3: [1, 2, 3]
4: [1, 2, 4]
5: [1, 2, 3, 5]
6: [1, 2, 3, 6]
7: [1, 2, 3, 4, 7]
11: [1, 2, 3, 4, 7, 11]
15: [1, 2, 3, 5, 10, 15]
19: [1, 2, 3, 4, 8, 11, 19]
29: [1, 2, 3, 4, 7, 11, 18, 29]
47: [1, 2, 3, 4, 7, 10, 20, 27, 47]
71: [1, 2, 3, 4, 7, 8, 16, 32, 39, 71]

Regras padrão de E / S, etc. Lacunas padrão banidas. Código de golfe: menos bytes ganha.

Haskell , 57 bytes

c=[1]:[x++[a+b]|x<-c,a<-x,b<-x]
f n=[x|x<-c,last x==n]!!0

Uma solução de força bruta. Experimente online!

Explicação

A lista infinita ccontém todas as cadeias de adição, ordenadas por comprimento. É definido indutivamente em termos de si mesmo, fazendo uma lista xdec e dois elementos de xe anexando sua soma a x. A função fencontra a primeira lista cque termina com o número desejado.

c=            -- c is the list of lists
 [1]:         -- containing [1] and
 [x           -- each list x
  ++[a+b]     -- extended with a+b
 |x<-c,       -- where x is drawn from c,
  a<-x,       -- a is drawn from x and
  b<-x]       -- b is drawn from x.
f n=          -- f on input n is:
 [x           -- take list of those lists x
 |x<-c,       -- where x is drawn from c and
  last x==n]  -- x ends with n,
 !!0          -- return its first element.

Braquilog , 14 bytes

∧≜;1{j⊇Ċ+}ᵃ⁽?∋

Experimente online!

Uma submissão de força bruta que constrói todas as cadeias de adição possíveis usando aprofundamento iterativo, parando quando uma cadeia contendo seu argumento correto é encontrada. Diferentemente da maioria das submissões do Brachylog, essa é uma submissão de funções que insere pelo argumento correto (convencionalmente chamado de Saída) e gera pelo argumento esquerdo (convencionalmente chamado de Entrada); fazer isso é um tanto controverso, mas a meta resposta mais votada sobre o assunto diz que é legal (e é consistente com nossos padrões normais de E / S para funções). Se usássemos a entrada e a saída de uma maneira mais convencional, seriam 16 bytes (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), porque o lado direito do programa não seria capaz de usar a restrição implícita (seria necessário desativá-la e fornecer uma nova restrição explícita, a um custo de 2 bytes).

Explicação

∧≜;1{j⊇Ċ+}ᵃ⁽?∋
∧               Disable implicit constraint to read the left argument
 ≜;        ⁽    Evaluation order hint: minimize number of iterations
    {    }ᵃ     Repeatedly run the following:
   1      ᵃ       From {1 on the first iteration, results seen so far otherwise}
     j            Make {two} copies of each list element
      ⊇           Find a subset of the elements
       Ċ          which has size 2
        +         and which sums to {the new result for the next iteration}
             ∋    If the list of results seen so far contains {the right argument}
            ?     Output it via the left argument {then terminate}

Uma sutileza interessante aqui é o que acontece na primeira iteração, em que a entrada é um número e não uma lista como nas outras iterações; começamos com o número 1, fazemos duas cópias de cada dígito (tornando o número 11) e, em seguida, encontramos uma subsequência de dois dígitos (também o número 11). Então pegamos sua soma de dígitos, que é 2, e, como tal, a sequência começa [1,2]como queremos. Em futuras iterações, estamos começando com uma lista como [1,2], dobrando-a [1,2,1,2], em seguida, tomar um de dois elementos subsequence ( [1,1], [1,2], [2,1]ou [2,2]); claramente, as somas de cada uma delas serão válidas nos próximos elementos da cadeia de adição.

É um pouco frustrante aqui que a dica de ordem de avaliação seja necessária aqui, especialmente o ≜componente (parece que ᵃleva a dica de ordem de avaliação de dentro para fora e não por padrão por padrão, portanto, o uso grosseiro de ≜para forçar o problema).

Geléia , 17 bytes

’ŒP;€µ+þ;1Fḟ@µÐḟḢ

Produz a primeira solução lexicograficamente em tempo exponencial.

Experimente online!

Como funciona

’ŒP;€µ+þ;1Fḟ@µÐḟḢ  Main link. Argument: n (integer)

’                  Decrement; n-1.
 ŒP                Powerset; generate all subarrays of [1, ..., n-1], sorted first
                   by length, then lexicographically.
   ;€              Append n to all generate subarrays.
     µ       µÐḟ   Filterfalse; keep only subarrays for which the chain between the
                   two chain separators (µ) returns a falsy value.
     µ             Monadic chain. Argument: A (array of integers)
      +þ               Add table; compute the sums of all pairs of elements in x,
                       grouping the results by the right addend.
        ;1             Append 1 to the resulting 2D array.
          F            Flatten the result.
           ḟ@          Filterfalse swapped; remove all elements of A that appear in
                       the result. This yields an empty list for addition chains.
                Ḣ  Head; select the first result.

JavaScript (ES6), 83 86 bytes

Editar: corrigido para exibir a lista em ordem não inversa

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

Demo

let f =

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

for(n = 1; n <= 15; n++) {
  console.log(n, '-->', JSON.stringify(f(n)));
}

PHP, 195 bytes

function p($a){global$argn,$r;if(!$r||$a<$r)if(end($a)==$argn)$r=$a;else foreach($a as$x)foreach($a as$y)in_array($w=$x+$y,$a)||$w>$argn||$w<=max($a)?:p(array_merge($a,[$w]));}p([1]);print_r($r);

Experimente online!

Mathematica, 140 bytes

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

.

produz uma cadeia de adição mais curta diferente sempre que você a executa

Experimente on-line,
cole o código com ctrl + v, insira a entrada [71] no final do código e pressione Shift + Enter

Pitão, 13 bytes

h-DsM^N2/#QyS

Suíte de teste

Dá a primeira cadeia lexicograficamente mais curta. É bastante lento, mas não tão ruim - é 19concluído em cerca de 30 segundos usando pypy.

Algumas idéias da solução de @ Dennis.

Eu realmente gosto deste - há uma tonelada de truques legais envolvidos.

Explicação:

h-DsM^N2/#QyS
h-DsM^N2/#QySQ    Implicit variable introduction
            SQ    Inclusive range, 1 to input.
           y      Subsets - all subsets of the input, sorted by length then lexicographically
                  Only sorted subsets will be generated.
                  Our addition chain will be one of these.
        /#Q       Filter for presence of the input.
  D               Order by
 -                What's left after we remove
     ^N2          All pairs of numbers in the input
   sM             Summed
h                 Output the list that got sorted to the front.

Ainda é um pouco difícil de entender, mas deixe-me tentar explicar um pouco mais detalhadamente.

Começamos com ySQ, que fornece todos os subconjuntos ordenados possíveis de [1, 2, ... Q], em ordem crescente de tamanho. A menor cadeia de adição é definitivamente uma delas, mas precisamos encontrá-la.

A primeira coisa que faremos é filtrar a lista para manter apenas as listas que contêm a Q. Fazemos isso com /#Q.

Em seguida, ordenamos a lista pelo que resta depois de removermos o resultado de uma determinada função. -Dordens pelo restante depois de remover algo.

O que removemos é sM^N2onde Nestá a lista da qual estamos removendo as coisas. ^N2fornece o produto cartesiano de Nsi mesmo, todos os pares possíveis de dois elementos N.sMentão soma cada um dos pares.

Qual é o menor resultado possível, após a remoção? Bem, o menor elemento da lista de entrada definitivamente permanecerá, porque todos os números são positivos, portanto, qualquer soma de dois números será maior que o menor número. E haverá pelo menos um número, porque verificamos que a entrada estava presente na lista. Portanto, o menor resultado possível será quando cada número, exceto o menor número, for a soma de dois outros números na lista e o menor número na lista for 1. Nesse caso, a chave de classificação será[1] . Esses requisitos significam que a lista deve ser uma cadeia de adição.

Então, classificamos as cadeias de adição à frente. Lembre-se de que yfornece seus subconjuntos em ordem crescente de tamanho; portanto, a lista que é classificada na frente deve ser uma das cadeias de adição mais curtas. hseleciona essa lista.