(ProjectEuler) Суммарные комбинации

Question

С ProjectEuler.net :

Вероятность 76: Сколько различных способов можно записать сто как сумму, по крайней мере, двух натуральных чисел? Понятия не имею, с чего начать ... какие-нибудь точки в правильном направлении или помощь? Я не ищу, как это сделать, но некоторые подсказки о том, как это сделать.

Например, 5 можно записать так:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Итак, всего 6 возможностей.

Answer 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).

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

Answer 3

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

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

Answer 4

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

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

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

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

удачи!

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

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

• Число 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 ...., разбивая каждый как вы идете вместе.