Найти нет. способов получения суммы n со всеми натуральными числами меньше n

Question

Для данного числа n, скажем 2, сколько способов мы можем получить сумму 2, используя числа меньше 2.

1+1 = 2  
so, for 2 - just 1 way.

n = 3   
1+1+1=3  
1+2=3  
so,for 3 - it is 2 ways  
n = 4   
1+1+1+1=4  
1+1+2=4  
1+3=4  
2+2=4  

so, for 4 - it is 4 ways  

Может ли быть общий шаблон / решение этого вопроса?

Answer 1

Эта проблема известна как Проблема с разделами , подробности см. В ссылочной ссылке из вики:

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

smallest addend is k
smallest addend is strictly greater than k.

Количество разделов, удовлетворяющих первому условию, равно p (k, n - k). Чтобы увидеть это, представьте список всех разделов числа n - k на числа размером не менее k, затем представьте, что вы добавляете "+ k" к каждому раздел в списке. Теперь, что это за список? Как примечание стороны, один можно использовать это для определения своего рода рекурсивного отношения для раздела функция в терминах промежуточной функции, а именно

1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n),

Количество разделов, удовлетворяющих второму условию, равно p (k + 1, n) так как разбиение на части по крайней мере к, который не содержит частей ровно k должно иметь все части не менее k + 1.

Поскольку эти два условия являются взаимоисключающими, число разделение, удовлетворяющее какому-либо условию: p (k + 1, n) + p (k, n - k). рекурсивно определенная функция, таким образом:

p(k, n) = 0 if k > n

p(k, n) = 1 if k = n

p(k, n) = p(k+1, n) + p(k, n − k) otherwise.

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

Редактировать: Как упомянул unutbu в своем комментарии, в конце вычислений вы должны вычесть 1, чтобы вывести результат. То есть все значения P до последнего шага должны быть рассчитаны в соответствии с рекомендациями вики, однако в самом самом конце перед выводом результата его необходимо вычесть на 1.