Цепочка сложения - это последовательность целых чисел, начинающаяся с 1, где каждое целое число, отличное от начального 1, является суммой двух предыдущих целых чисел.

Например, вот цепочка дополнений:

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

Вот суммы, которые составляют цепочку сложений:

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

В этом задании вам дадут положительное целое число n, и вы должны вывести одну из самых коротких цепочек сложений, которая заканчивается на n.

Примеры - обратите внимание, что есть много возможных выходных данных, все, что вам нужно найти, это цепочка дополнений, которая так же коротка:

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]

Стандартные правила ввода / вывода и т. Д. Стандартные лазейки запрещены. Код гольф: побеждает побольше байтов.

Haskell , 57 байт

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

Решение грубой силы. Попробуйте онлайн!

объяснение

Бесконечный список cсодержит все цепочки сложений, упорядоченные по длине. Он определяется индуктивно в терминах самого себя, беря список xиз cдвух элементов xи добавляя их сумму к x. Функция fнаходит первый список, cкоторый заканчивается нужным номером.

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.

Брахилог , 14 байт

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

Попробуйте онлайн!

Представление грубой силы, которое строит все возможные цепочки сложений, используя итеративное углубление, останавливаясь, когда цепочка, содержащая правильный аргумент, найдена. В отличие от большинства представлений Brachylog, это представление функции, которое вводится через свой правый аргумент (условно называемый «Выход») и выводит через его левый аргумент (условно называемый «Вход»); делает это несколько спорно, но самый высокий проголосовали мета ответ на эту тему говорит , что это законно (и делает это согласуется с нашими обычными по умолчанию I / O для функций). Если бы мы использовали ввод и вывод более обычным способом, это было бы 16 байтов (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), потому что правая часть программы не сможет использовать неявное ограничение (поэтому потребуется отключить его и дать новое явное ограничение стоимостью 2 байта).

объяснение

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

Здесь интересная тонкость заключается в том, что происходит на первой итерации, когда входные данные представляют собой число, а не список, как на других итерациях; мы начинаем с числа 1, делаем две копии каждой цифры (делая число 11), а затем находим ее двухзначную подпоследовательность (также число 11). Затем мы берем сумму цифр, равную 2, и, как таковая, последовательность начинается так, [1,2]как мы хотим. На итераций в будущем, мы начинаем со списком , как [1,2], удваивая его [1,2,1,2], а затем взять два-элемента подпоследовательности ( [1,1], [1,2], [2,1]или [2,2]); Очевидно, что суммы каждого из них будут действительными для следующих элементов цепочки сложения.

Немного огорчает, что здесь нужна подсказка о порядке оценки, особенно ≜компонент (кажется, что по умолчанию ᵃподсказка о порядке оценки принимается изнутри, а не снаружи, таким образом, довольно грубое использование для ≜того, чтобы вызвать проблему).

Желе , 17 байт

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

Выводит лексикографически первое решение в экспоненциальном времени.

Попробуйте онлайн!

Как это работает

’Œ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 байт

Редактировать: исправлено для вывода списка в обратном порядке

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

демонстрация

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 байт

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

Попробуйте онлайн!

Mathematica, 140 байт

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

,

каждый раз, когда вы запускаете его, создаете новую цепочку кратчайшего сложения

Попробуйте онлайн,
вставьте код с помощью ctrl + v, поместите ввод, т.е. [71] в конец кода, и нажмите shift + enter

Pyth, 13 байт

h-DsM^N2/#QyS

Тестирование

Дает лексикографически первую самую короткую цепочку. Это довольно медленно, но не так плохо - 19завершается примерно через 30 секунд, используя pypy.

Некоторые идеи из решения @ Dennis.

Мне действительно нравится этот - есть тонна изящных уловок, вовлеченных.

Объяснение:

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.

Это все еще немного трудно понять, но позвольте мне попытаться объяснить более подробно.

Начнем с того ySQ, что дает все возможные упорядоченные подмножества [1, 2, ... Q], в порядке возрастания размера. Самая короткая цепочка сложений, безусловно, одна из них, но нам нужно ее найти.

Первое, что мы сделаем, это отфильтруем список, чтобы сохранить только те списки, которые содержат Q. Мы делаем это с /#Q.

Далее мы упорядочиваем список по тому, что осталось после удаления результата определенной функции. -Dзаказы на остаток после удаления чего-либо.

То, что мы удаляем, это то sM^N2, где Nнаходится список, из которого мы удаляем вещи. ^N2дает себе декартово произведение Nвсех возможных пар из двух элементов N. sMзатем суммирует каждую из пар.

Какой наименьший возможный результат после этого удаления? Что ж, самый маленький элемент в списке ввода определенно останется, потому что все числа положительны, поэтому любая сумма двух чисел будет больше, чем наименьшее число. И будет по крайней мере один номер, потому что мы проверили, что вход присутствует в списке. Поэтому наименьший возможный результат будет, когда каждое число, кроме наименьшего, является суммой двух других чисел в списке, а наименьшее число в списке равно 1. В этом случае ключ сортировки будет [1]. Эти требования означают, что список должен быть цепочкой дополнений.

Итак, мы сортируем цепочки сложений вперед. Помните, что yего подмножества приводятся в порядке возрастания размера, поэтому список, который отсортирован вперед, должен быть одной из самых коротких цепочек сложений. hвыбирает этот список.