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

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

Я делал бы попытку теперь, но я должен проделать работу :)

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

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

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

Единственная другая подсказка я думаю, что могу дать Вам, не портя Ваше прозрение, является словом 'раздел'.

После того как Вы поняли это, у Вас будет он в мгновение ока :)

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

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

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

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

удачи!

Уведомление: Моя математика немного ржава, но надо надеяться это поможет...

Вы подходите к своему повреждению вниз проблемы.

Думайте обычно:

• Номер 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.... разрушения каждого, как Вы продвигаетесь.

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

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

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

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

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