Łańcuch dodawania jest sekwencją liczb całkowitych rozpoczynających się od 1, gdzie każda liczba całkowita inna niż początkowa 1 jest sumą dwóch poprzednich liczb całkowitych.

Oto na przykład łańcuch dodawania:

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

Oto sumy, które sprawiają, że jest to łańcuch dodawania:

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

W tym wyzwaniu otrzymasz dodatnią liczbę całkowitą ni musisz wygenerować jeden z najkrótszych łańcuchów dodawania, który kończy się na n.

Przykłady - zwróć uwagę, że istnieje wiele możliwych wyników, wszystko, co musisz znaleźć, to łańcuch dodatków, który jest tak samo krótki:

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]

Standardowe reguły we / wy itp. Standardowe luki zabronione. Code golf: Wygrywa najmniej bajtów.

Haskell , 57 bajtów

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

Rozwiązanie brutalnej siły. Wypróbuj online!

Wyjaśnienie

Lista nieskończona czawiera wszystkie łańcuchy dodawania uporządkowane według długości. Definiuje się go indukcyjnie, biorąc listę xz cdwóch elementów xi dołączając ich sumę do x. Funkcja fznajduje pierwszą listę, cktóra kończy się żądaną liczbą.

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 bajtów

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

Wypróbuj online!

Poddanie brutalnej siły, które buduje wszystkie możliwe łańcuchy dodatków przy użyciu iteracyjnego pogłębiania, zatrzymując się po znalezieniu łańcucha zawierającego właściwy argument. W przeciwieństwie do większości zgłoszeń Brachylog, jest to zgłoszenie funkcji, które wprowadza za pomocą swojego prawego argumentu (tradycyjnie nazywanego wyjściem) i wysyła za pomocą swojego lewego argumentu (konwencjonalnie nazywanego wejściem); robienie tego jest nieco kontrowersyjne, ale najwyżej głosowana meta odpowiedź na ten temat mówi, że jest legalna (i robi to zgodnie z naszymi normalnymi ustawieniami domyślnymi We / Wy dla funkcji). Gdybyśmy użyli wejścia i wyjścia w bardziej konwencjonalny sposób, byłoby to 16 bajtów (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), ponieważ prawa strona programu nie byłaby w stanie skorzystać z domniemanego ograniczenia (wymagałoby to wyłączenia i nowego jawnego ograniczenia, kosztem 2 bajtów).

Wyjaśnienie

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

Interesującą subtelnością jest to, co dzieje się podczas pierwszej iteracji, gdzie dane wejściowe to liczba, a nie lista, jak w innych iteracjach; zaczynamy od cyfry 1, wykonujemy dwie kopie każdej cyfry (tworząc cyfrę 11), a następnie znajdujemy 2-cyfrową podsekwencję (również cyfrę 11). Następnie bierzemy jego sumę cyfr, która wynosi 2, i dlatego sekwencja zaczyna się [1,2]tak, jak chcemy. Na kolejnych iteracjach, zaczynamy z listą podobnego [1,2], podwajając go [1,2,1,2], a następnie podjęcie dwóch elementów podciąg ( [1,1], [1,2], [2,1], lub [2,2]); wyraźnie, sumy każdego z nich będą obowiązywać kolejne elementy łańcucha dodawania.

Trochę frustrujące jest tutaj to, że potrzebna jest tutaj wskazówka kolejności oceny, szczególnie ≜komponent (wydaje się, że domyślnie ᵃbierze podpowiedź kolejności oceny od wewnątrz, a nie z zewnątrz, a więc raczej prymitywne użycie ≜w celu wymuszenia tego problemu).

Galaretka , 17 bajtów

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

Wysyła leksykograficznie pierwsze rozwiązanie w czasie wykładniczym.

Wypróbuj online!

Jak to działa

’Œ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 bajtów

Edycja: naprawiono, aby wyświetlać listę w odwrotnej kolejności

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

Próbny

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 bajtów

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

Wypróbuj online!

Mathematica, 140 bajtów

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

.

tworzy inny najkrótszy łańcuch dodawania za każdym razem, gdy go uruchomisz

Wypróbuj online,
wklej kod za pomocą ctrl + v, umieść dane wejściowe tj. [71] na końcu kodu i naciśnij shift + enter

Pyth, 13 bajtów

h-DsM^N2/#QyS

Zestaw testowy

Daje leksykograficznie pierwszy najkrótszy łańcuch. Jest dość wolny, ale nie taki zły - 19kończy się w około 30 sekund za pomocą pypy.

Kilka pomysłów z rozwiązania @ Dennis.

Naprawdę podoba mi się ten - jest w nim mnóstwo fajnych sztuczek.

Wyjaśnienie:

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.

Wciąż jest to trochę trudne do zrozumienia, ale pozwól mi wyjaśnić nieco bardziej szczegółowo.

Zaczynamy od ySQ, który daje wszystkie możliwe uporządkowane podzbiory [1, 2, ... Q], w rosnącym porządku wielkości. Najkrótszy łańcuch dodawania jest zdecydowanie jednym z nich, ale musimy go znaleźć.

Pierwszą rzeczą, którą zrobimy, jest filtrowanie listy, aby zachować tylko listy zawierające Q. Robimy to z /#Q.

Następnie porządkujemy listę według tego, co pozostało po usunięciu wyniku określonej funkcji. -Dzamówienia przez resztę po usunięciu czegoś.

Usuwamy to sM^N2, gdzie Nznajduje się lista, z której usuwamy rzeczy. ^N2daje produkt kartezjański Nze sobą, wszystkie możliwe pary dwóch elementów w N. sMnastępnie sumuje każdą z par.

Jaki jest najmniejszy możliwy wynik po tym usunięciu? Cóż, najmniejszy element na liście wejściowej na pewno pozostanie, ponieważ wszystkie liczby są dodatnie, więc każda suma dwóch liczb będzie większa niż najmniejsza liczba. I będzie co najmniej jedna liczba, ponieważ sprawdziliśmy, czy dane wejściowe były obecne na liście. Dlatego najmniejszym możliwym wynikiem będzie, gdy każda liczba oprócz najmniejszej liczby będzie sumą dwóch innych liczb na liście, a najmniejsza liczba na liście to 1. W tym przypadku kluczem sortującym będzie [1]. Wymagania te oznaczają, że lista musi być łańcuchem dodatkowym.

Tak więc sortujemy łańcuchy dodatków z przodu. Pamiętaj, że ypodaje podzbiory w kolejności rosnącej, więc lista posortowana na początku musi być jednym z najkrótszych łańcuchów dodawania. hwybiera tę listę.