Une chaîne d'addition est une séquence d'entiers commençant par 1, où chaque entier autre que le 1 initial est une somme de deux entiers précédents.

Par exemple, voici une chaîne d'addition:

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

Voici les sommes qui en font une chaîne d'addition:

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

Dans ce défi, vous recevrez un entier positif net vous devrez sortir l'une des chaînes d'addition les plus courtes qui se termine par n.

Exemples - notez qu'il existe de nombreuses sorties possibles, tout ce que vous devez trouver est une chaîne d'addition tout aussi courte:

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]

Règles d'E / S standard, etc. Interruptions standard interdites. Code golf: le moins d'octets gagne.

Haskell , 57 octets

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

Une solution de force brute. Essayez-le en ligne!

Explication

La liste infinie ccontient toutes les chaînes d'addition, classées par longueur. Il est défini de manière inductive en termes de lui-même, en prenant une liste xde cet deux éléments de x, et en ajoutant leur somme à x. La fonction ftrouve la première liste cqui se termine par le numéro souhaité.

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.

Brachylog , 14 octets

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

Essayez-le en ligne!

Une soumission par force brute qui construit toutes les chaînes d'addition possibles en utilisant l'approfondissement itératif, s'arrêtant lorsqu'une chaîne contenant son argument correct est trouvée. Contrairement à la plupart des soumissions Brachylog, il s'agit d'une soumission de fonction qui entre via son argument droit (appelé conventionnellement la sortie) et sort via son argument gauche (appelé conventionnellement l'entrée); cela est quelque peu controversé, mais la méta-réponse la plus votée sur le sujet dit que c'est légal (et cela est conforme à nos valeurs par défaut d'E / S pour les fonctions). Si nous utilisions l'entrée et la sortie d'une manière plus conventionnelle, ce serait 16 octets (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), car le côté droit du programme ne serait pas en mesure de faire usage de la contrainte implicite (aurait donc besoin de cette désactivation, et d'une nouvelle contrainte explicite donnée, au coût de 2 octets).

Explication

∧≜;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}

Une subtilité intéressante ici est ce qui se passe sur la première itération, où l'entrée est un nombre plutôt qu'une liste comme sur les autres itérations; nous commençons par le nombre 1, faisons deux copies de chaque chiffre (ce qui fait le nombre 11), puis trouvons une sous-séquence à 2 chiffres (également le nombre 11). Ensuite, nous prenons sa somme de chiffres, qui est 2, et en tant que telle, la séquence commence [1,2]comme nous le voulons. Sur les itérations futures, nous commençons avec une liste comme [1,2], doublant à [1,2,1,2], en prenant ensuite une sous deux éléments ( [1,1], [1,2], [2,1]ou [2,2]); il est clair que les sommes de chacun de ces éléments constitueront les prochains éléments valides de la chaîne d'addition.

Il est un peu frustrant ici que l'indicateur d'ordre d'évaluation soit nécessaire ici, en particulier le ≜composant (il semble que cela ᵃprenne son indice d'ordre d'évaluation de l' intérieur plutôt que de l'extérieur par défaut, d'où l'utilisation plutôt grossière de ≜afin de forcer le problème).

Gelée , 17 octets

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

Génère la première solution lexicographiquement en temps exponentiel.

Essayez-le en ligne!

Comment ça marche

’Œ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 octets

Modifier: corrigé pour sortir la liste dans un ordre non inverse

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

Démo

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 octets

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);

Essayez-le en ligne!

Mathematica, 140 octets

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@#&])&

.

produit une chaîne d'addition la plus courte différente à chaque fois que vous l'exécutez

Essayez-le en ligne
collez le code avec ctrl + v, placez l'entrée ie [71] à la fin du code et appuyez sur Maj + Entrée

Pyth, 13 octets

h-DsM^N2/#QyS

Suite de tests

Donne la première chaîne la plus courte lexicographiquement. C'est assez lent, mais pas si mal - se 19termine en environ 30 secondes en utilisant pypy.

Quelques idées de la solution de @ Dennis.

J'aime vraiment celui-ci - il y a une tonne de trucs sympas impliqués.

Explication:

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.

C'est encore un peu difficile à comprendre, mais permettez-moi d'essayer d'expliquer un peu plus en détail.

Nous commençons par ySQ, qui donne tous les sous-ensembles ordonnés possibles de [1, 2, ... Q], par ordre croissant de taille. La chaîne d'addition la plus courte en fait certainement partie, mais nous devons la trouver.

La première chose que nous ferons est de filtrer la liste pour ne conserver que les listes contenant un Q. Nous le faisons avec /#Q.

Ensuite, nous classons la liste en fonction de ce qui reste après avoir supprimé le résultat d'une certaine fonction. -Dcommandes par le reste après avoir retiré quelque chose.

La chose que nous supprimons est sM^N2, où Nest la liste dont nous supprimons les choses. ^N2donne au produit cartésien de Nlui-même, toutes les paires possibles de deux éléments N. sMpuis additionne chacune des paires.

Quel est le résultat le plus petit possible, après cette suppression? Eh bien, le plus petit élément de la liste d'entrée restera définitivement, car tous les nombres sont positifs, donc toute somme de deux nombres sera supérieure au plus petit nombre. Et il y aura au moins un nombre, car nous avons vérifié que l'entrée était présente dans la liste. Par conséquent, le résultat le plus petit possible sera lorsque chaque numéro, à l'exception du plus petit nombre, est la somme de deux autres nombres dans la liste, et le plus petit nombre dans la liste est 1. Dans ce cas, la clé de tri sera[1] . Ces exigences signifient que la liste doit être une chaîne d'addition.

Donc, nous trions les chaînes d'addition à l'avant. N'oubliez pas que cela ydonne ses sous-ensembles dans un ordre croissant de taille, donc la liste qui est triée à l'avant doit être l'une des chaînes d'addition les plus courtes. hsélectionne cette liste.