Eine Additionskette ist eine Folge von Ganzzahlen, die mit 1 beginnen, wobei jede andere Ganzzahl als die anfängliche 1 eine Summe von zwei vorherigen Ganzzahlen ist.

Hier ist zum Beispiel eine Additionskette:

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

Hier sind die Summen, die es zu einer Additionskette machen:

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

In dieser Herausforderung erhalten Sie eine positive Ganzzahl nund müssen eine der kürzesten Additionsketten ausgeben, die auf endet n.

Beispiele - Beachten Sie, dass es viele mögliche Ausgaben gibt. Alles, was Sie finden müssen, ist eine ebenso kurze Additionskette:

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]

Standard-E / A-Regeln usw. Verbot von Standard-Regelungslücken. Codegolf: Wenige Bytes gewinnen.

Haskell , 57 Bytes

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

Eine Brute-Force-Lösung. Probieren Sie es online!

Erläuterung

Die unendliche Liste centhält alle Additionsketten, sortiert nach Länge. Es wird in sich selbst induktiv definiert, indem eine Liste xaus cund zwei Elemente aus genommen xund deren Summe angehängt werden x. Die Funktion ffindet die erste Liste c, die mit der gewünschten Nummer endet.

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 Bytes

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

Probieren Sie es online!

Eine Brute-Force-Übermittlung, die alle möglichen Additionsketten durch iteratives Vertiefen aufbaut und stoppt, wenn eine Kette mit dem richtigen Argument gefunden wird. Im Gegensatz zu den meisten Brachylog-Übermittlungen ist dies eine Funktionsübermittlung, die über ihr rechtes Argument (herkömmlicherweise als Ausgabe bezeichnet) und über ihr linkes Argument (herkömmlicherweise als Eingabe bezeichnet) eingibt. Dies zu tun ist etwas umstritten, aber das ), weil die rechte Seite des Programms die implizite Einschränkung nicht nutzen könnte (daher müsste diese deaktiviert und eine neue explizite Einschränkung angegeben werden, zu einem Preis von 2 Bytes ). höchsten bewertete Meta-Antwort zu diesem Thema besagt, dass es legal ist (und dies steht im Einklang mit unseren normalen E / A-Standardeinstellungen für Funktionen). Wenn wir die Ein- und Ausgabe konventioneller verwenden würden, wären dies 16 Bytes (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧

Erläuterung

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

Eine interessante Feinheit ist hier, was bei der ersten Iteration passiert, bei der die Eingabe eine Zahl und keine Liste wie bei den anderen Iterationen ist. wir beginnen mit der Nummer 1, machen zwei Kopien von jeder Ziffer (machen die Nummer 11), dann finden wir eine zweistellige Folge davon (auch die Nummer 11). Dann nehmen wir die Ziffernsumme, die 2 ist, und als solche beginnt die Sequenz so, [1,2]wie wir es wollen. Bei zukünftigen Iterationen, starten wir mit einer Liste wie [1,2], es zu verdoppeln [1,2,1,2], dann nahm eine Zwei-Element Teilfolge ( [1,1], [1,2], [2,1], oder [2,2]); Es ist klar, dass die Summen von jedem dieser Elemente als nächstes in der Additionskette gültig sind.

Es ist hier ein wenig frustrierend, dass der Hinweis auf die Bewertungsreihenfolge hier benötigt wird, insbesondere die ≜Komponente (anscheinend ᵃwird der Hinweis auf die Bewertungsreihenfolge standardmäßig eher von innen als von außen verwendet, daher der eher grobe Einsatz von ≜, um das Problem zu erzwingen).

Gelee , 17 Bytes

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

Gibt die lexikographisch erste Lösung in Exponentialzeit aus.

Probieren Sie es online!

Wie es funktioniert

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

Bearbeiten: Behoben, die Liste in nicht umgekehrter Reihenfolge auszugeben

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

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

.

erzeugt bei jedem Start eine andere kürzeste Additionskette

Probieren Sie es online aus,
fügen Sie den Code mit Strg + V ein, platzieren Sie die Eingabe, dh [71], am Ende des Codes und drücken Sie Umschalt + Eingabetaste

Pyth, 13 Bytes

h-DsM^N2/#QyS

Testsuite

Gibt die lexikographisch erste kürzeste Kette an. Es ist ziemlich langsam, aber nicht so schlimm - 19dauert mit pypy etwa 30 Sekunden.

Einige Ideen aus der @ Dennis-Lösung.

Ich mag dieses wirklich - es gibt eine Menge netter Tricks.

Erläuterung:

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.

Das ist immer noch etwas schwer zu verstehen, aber lassen Sie mich versuchen, es etwas genauer zu erklären.

Wir beginnen mit ySQ, die alle möglichen bestellten Teilmengen von gibt[1, 2, ... Q] in aufsteigender Reihenfolge der Größe gibt. Die kürzeste Additionskette ist definitiv eine davon, aber wir müssen sie finden.

Als Erstes filtern wir die Liste so, dass nur Listen mit a erhalten bleiben Q. Wir machen das mit /#Q.

Als nächstes ordnen wir die Liste nach dem, was übrig ist, nachdem wir das Ergebnis einer bestimmten Funktion entfernt haben. -DBestellungen durch den Rest nach dem Entfernen von etwas.

Das, was wir entfernen, ist sM^N2, wo Nist die Liste, aus der wir Dinge entfernen. ^N2gibt das kartesische Produkt Nmit sich, alle möglichen Paare von zwei Elementen in N. sMdann summiert jedes der Paare.

Was ist das kleinstmögliche Ergebnis nach dieser Entfernung? Nun, das kleinste Element in der Eingabeliste bleibt definitiv erhalten, da alle Zahlen positiv sind, sodass jede Summe von zwei Zahlen größer ist als die kleinste Zahl. Und es wird mindestens eine Nummer geben, da wir überprüft haben, ob die Eingabe in der Liste vorhanden ist. Daher ist das kleinstmögliche Ergebnis, wenn jede Zahl außer der kleinsten die Summe von zwei anderen Zahlen in der Liste ist und die kleinste Zahl in der Liste 1 ist. In diesem Fall lautet der Sortierschlüssel [1]. Diese Anforderungen bedeuten, dass die Liste eine Additionskette sein muss.

Also sortieren wir die Additionsketten nach vorne. Denken Sie daran, dass ydie Untermengen in aufsteigender Reihenfolge der Größe angegeben werden. Daher muss die nach vorne sortierte Liste eine der kürzesten Additionsketten sein. hwählt diese Liste aus.