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

Ответ 1

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

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

• 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...
• P (9) = 30...

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

Ответ 2

Решение может быть найдено с использованием алгоритма измельчения.

Используйте, например, 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)

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

Удачи!

Ответ 6

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

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

Подумайте:

• Число n может быть записано как (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.... разрушая каждый как вы идете.

Ответ 7

Многие математические проблемы могут быть решены с помощью induction. Вы знаете ответ для определенного значения, и вы можете найти ответ для каждого значения, если найдете что-то, что связывает 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 слагаемых)

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