Найдите 4 числа, которые удовлетворяют любому уравнению суммы с данным числом

Question

У меня есть четыре целых числа a, b, c, d, и целое число x ϵ [1, 40].

Как найти значения {a, b, c, d}, для которых одно из следующих уравнений верно для любого 1 <= x <= 40? </p>

x = a or
x = b or
x = a + b or
x = a + b + c + d or
x + a = c + d or
x + a + b = c + d or
...
x + a + b + c = d or ... 

Пример:

Если x = 17, то {a = 1, b = 2, c = 5, d = 15} я могу написать x + a + b = c + d

Вопрос в том, чтобы представить любую x ϵ [1, 40] {a, b, c, d}.

Обновление:

Есть только одно решение, я уверен, и я думаю, что

{a = 1; a + b + c + d = 40}

Answer 1

На самом деле здесь ничего не связано с программированием. Это чистая математика. Алгоритм решения таких задач прост. Начиная с 1, мы берем следующее наибольшее возможное значение, чтобы мы могли получить все остальные числа до суммы (1..it), используя только + и -.

Итак, первое 1.

Вторым будет 3, так как 1 = 1, 2 = 3 - 1, 3 = 3, 4 = 3 + 1.

3-й - 9.

И вы видите совпадение каждого следующего числового идентификатора в 3 раза больше предыдущего. Вы ищете четыре числа: {1, 3, 9, 27}, и вы можете получить любое число от 1 до 1 + 3 + 9 + 27 = 40 с ними.

Answer 2

Это на самом деле случай сбалансированного троичного расположения. Для каждого из a, b, c и d вы можете либо добавить его к итогу, вычесть его (потому что x + a + b == c + d точно так же, как x == c + d - a - b, либо опустить его. Следовательно, нужные вам числа являются троичными цифры или 1, 3, 9 и 27.

Answer 3

Это называется проблемой заданного разбиения и некоторой суммы подмножеств, которые являются задачами NP Complete. Т.е. это сложная проблема, и вам лучше всего использовать подход грубой силы или подход динамического программирования. в любом случае не существует «эффективного» алгоритма для решения этого за линейное время. по крайней мере, пока никто не знает.

http://en.wikipedia.org/wiki/Partition_problem

http://en.wikipedia.org/wiki/Subset_sum_problem

Это может быть связано с теорией игр, но все же это проблема NP.