(ProjectEuler) Комбинации сумм

Хороший способ подойти к ним - не зацикливаться на «100», а попытаться понять, какая разница между суммированием суммы п и п + 1, ища закономерности при увеличении n 1,2,3 ....

Я бы сейчас пошел, но у меня есть работа :)

Примечание: моя математика немного ржавая, но, надеюсь, это поможет ...

Вы хорошо справляетесь с решением проблемы.

Думайте в общем:

• Число п можно записать как (n-1) +1 или (n-2) +2.
• Вы обобщаете это на (n-m) + m
• Помните, что вышесказанное также относится ко всем числам (включая m).

Итак, идея состоит в том, чтобы найти первый набор (скажем, 5 = (5-1) +1), а затем обработать (5-1) как новый n ... 5 = 4 +1 ... 5 = ((4 -1) +1) +1. Один раз, который исчерпан, снова начинается с 5 = 3 + 2 .... что становится 5 = ((3-1) +1) +2 .... = 2 + 1 + 2 .... как вы идете.

Как и большинство проблем в Project Euler с большими числами, лучший способ думать о них - это не зацикливаться на этой огромной верхней границе, а думать о проблеме в меньших терминах и постепенно продвигаться вверх. Возможно, по пути вы узнаете закономерность или узнаете достаточно, чтобы легко найти ответ.

Единственный другой намек, который я могу дать вам, не испортив ваше прозрение, - это слово «раздел».

Как только вы это поймете, вы получите это в кратчайшие сроки :)

Номера разделов (или функции разделения) являются ключом к этому.

Подобные проблемы обычно легче решить, если вы начнете снизу и постепенно подниметесь вверх, чтобы увидеть, сможете ли вы обнаружить какие-либо закономерности.

• P (1) = 1 = {1}
• P (2) = 2 = {[2], [1 + 1]}
• P (3) = 3 = {[3], [2 + 1], [1 + 1 + 1]}
• P (4) = 5 = {[4], [3 + 1], [2 + 2], [2 + 1 + 1], [1 + 1 + 1 + 1]}
• P (5) = 7 ...
• P (6) = 11 ...
• P (7) = 15 ...
• P (8) = 22 ...
• Р (9) = 30 ...

Подсказка: посмотрите, сможете ли вы построить P (N) из некоторой комбинации результатов, предшествующих P (N).

один из подходов состоит в том, чтобы подумать рекурсивная функция: найти перестановки числового ряда, взятые из положительных целых чисел (дубликаты разрешены), которые в сумме дают 100

• ноль равен 1, т.е. для числа 1 есть нулевые решения
• единица равна 2, т.е. для числа 2 есть только одно решение

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

вы можете выполнять итерацию от 1 до 100; в любом случае вы получите один и тот же ответ. В каждой точке вы могли (для наивного решения) сгенерировать все перестановки серии положительных целых чисел, считая до целевого числа минус 1, и считать только те, которые в сумме составляют целевое число.

удачи!

Решение можно найти с помощью алгоритма измельчения.

Используйте, например, 6. Тогда у нас есть:

6
5+1
4+2
3+3

но мы еще не закончили.

Если мы возьмем 5 + 1 и будем считать, что +1 часть закончена, потому что все остальные конечные комбинации обрабатываются 4 + 2 и 3 + 3. Таким образом, нам нужно применить тот же трюк к 5.

4+1+1
3+2+1

И мы можем продолжить. Но не бездумно. Потому что, например, 4 + 2 дает 3 + 1 + 2 и 2 + 2 + 2. Но нам не нужно 3 + 1 + 2, потому что у нас будет 3 + 2 + 1. Таким образом, мы используем только все произведения 4, где наименьшее число больше или равно 2.

6
5+1
  4+1+1
    3+1+1+1
      2+1+1+1+1
        1+1+1+1+1+1
    2+2+1+1
  3+2+1
4+2
  2+2+2
3+3

Следующий шаг - добавить это в алгоритм.

Хорошо, нам нужна рекурсивная функция, которая принимает два параметра. Количество нарезки и минимальное значение:

func CountCombinations(Number, Minimal)
  temp = 1
  if Number<=1 then return 1
  for i = 1 to Floor(Number/2)
    if i>=Minimal then
      temp := temp + CountCombinations(Number-i, i)
  end for
  return temp
end func

Чтобы проверить алгоритм:

C(6,1) = 1 + C(5,1) + C(4,2) + C(3,3) = 11, which is correct.
C(5,1) = 1 + C(4,1) + C(3,2) = 7
C(4,1) = 1 + C(3,1) + C(2,2) = 5
C(3,1) = 1 + C(2,1) = 3
C(2,1) = 1 + C(1,1) = 2
C(1,1) = 1
C(2,2) = 1
C(3,2) = 1
C(4,2) = 1 + C(2,2) = 2
C(3,3) = 1

Кстати, количество комбинаций 100:

CC(100) = 190569292
CC(100) = 190569291 (if we don't take into account 100 + 0)

Многие математические задачи могут быть решены с помощью индукция. Вы знаете ответ для конкретного значения, и вы можете найти ответ для каждого значения, если найдете что-нибудь, связывающий n с n+1.

Например, в вашем случае вы знаете, что ответ для Сколько разных способов можно записать как сумму как минимум двух положительных целых чисел? - всего 1.

Что я имею в виду под связью между n и n+1? Я имею в виду именно то, что вы должны найти формулу, которая, если вы знаете ответ для n, вы найдете ответ для n+1. Затем, рекурсивно вызывая эту формулу, вы узнаете ответ, и все готово (примечание: это всего лишь математическая часть, в реальной жизни вы можете обнаружить, что этот подход дал бы вам что-то слишком медленное, чтобы быть практичным, поэтому вы еще не сделали - в этом случае я считать вам будет готов).

Теперь предположим, что вы знаете, что n можно записать в виде суммы как минимум двух натуральных чисел? в k разными способами, одним из которых может быть:

n = a1 + a2 + a3 + ... am (в этой сумме m членов)

Что можете сказать о n+1? Поскольку вам нужны просто подсказки, я пишу не решение здесь, а только то, что следует. Наверняка у вас один и тот же k разными способами, но в каждом из них будет термин +1, одним из которых будет:

n + 1 = a1 + a2 + a3 + ... am + 1 (в этой сумме m + 1 член)

Тогда, конечно, у вас будут другие возможности k, такие как те, в которых последний член каждой суммы не совпадает, но он будет увеличен на единицу, например:

n + 1 = a1 + a2 + a3 + ... (am + 1) (в этой сумме m членов)

Таким образом, существует как минимум 2к способов записи n+1как сумму не менее двух натуральных чисел. Ну, есть и другие. Узнай, если сможешь :-) И наслаждаться :-))