Целочисленное разделение (алгоритм и рекурсия)

Ответ 1

Рассмотрим все пути результирующего n путем добавления некоторых чисел, меньших или равных m. Как вы сказали, мы называем это p(n,m). Например, p (7,3) = 8, поскольку существует 8 способов сделать 7 из числа меньше 3, как указано ниже: (Для простоты можно предположить, что мы всегда добавляем числа в порядке от наибольшего к наименьшему)

• 3 + 3 + 1
• 3 + 2 + 2
• 3 + 2 + 1 + 1
• 3 + 1 + 1 + 1 + 1
• 2 + 2 + 2 + 1
• 2 + 2 + 1 + 1 + 1
• 2 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1

Теперь мы можем разбить эти комбинации на две группы:

• Комбинации, первый элемент которых равен m (= 3 в нашем примере:)

  • 3 + 3 + 1
  • 3 + 2 + 2
  • 3 + 2 + 1 + 1
  • 3 + 1 + 1 + 1 + 1

• Комбинации, первый элемент которых меньше m:

  • 2 + 2 + 2 + 1
  • 2 + 2 + 1 + 1 + 1
  • 2 + 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1 + 1 + 1

Поскольку каждый член комбинаций p(n,m) будет либо в Group1, либо в Group2, мы можем сказать p(n,m)=size(Group1) + size(Group2). Теперь, если мы докажем, что size(Group1)=p(n-m, m) и size(Group2)=p(n,m-1) подстановкой, получим p(n,m)=p(n-m,m)+p(n,m-1)

Докажите для size(Group1)=p(n-m, m):

Вышеупомянутое определение p(n-m, m) представляет собой число способов получения n-m путем добавления некоторых чисел, меньших или равных m.

• Если вы добавляете m к каждой комбинации p(n-m, m), это приведет к члену Group1. поэтому p(n-m, m) <= size(Group1)
• Если вы удалите первый m каждого члена Group1, это приведет к комбинации для p(n-m, m). поэтому size(Group1) <= p(n-m, m)

=> size(Group1) = p(n-m, m). В нашем примере:

Группа1 < === соответствие === > p (4, 3):

• 7 = 3 + 3+1 < =========== → 3+1= 4
• 7 = 3 + 2+2 < =========== → 2+2= 4
• 7 = 3 + 2+1+1 < ======= → 2+1+1= 4
• 7 = 3 + 1+1+1+1 < === > 1+1+1+1= 4

Таким образом, между любым членом p(n-m,m) и Group1 существует один к одному, и их размер равен.

Докажите для size(Group2)=p(n, m-1):

По определению p(n,m-1) - это количество способов результата n путем добавления некоторых чисел, меньших или равных m-1 (меньше m). Если вы перечитаете определение Group2, вы увидите, что эти два определения совпадают друг с другом. => size(Group2) = p(n, m-1)

Ответ 2

Прежде всего, вы можете узнать об этой функции, см. http://mathworld.wolfram.com/PartitionFunctionP.html.

Что касается этой формулы, помните, что p(n, m) определяется как количество разделов n, наибольший член которого не более m.

Следовательно, p(n, m) - это число разделов m, наибольший член которого не более m. Разделим их в соответствии с тем, является ли самый большой член на самом деле m.

Число разделов, наибольшим членом которых является m, является количество способов заполнения n = m + ..., которое представляет собой число разделов n-m, наибольший член которого не превышает m, который по определению равен p(n-m, m).

Число разделов n, наибольший член которого не превышает m-1, по определению p(n, m-1).

Поэтому p(n, m) = p(n-m, m) + p(n, m-1).

Ответ 3

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

p(n, m) - p(n, m - 1) = p(n-m, m)          (1)

Левая часть (1) - это разность p (n, m) и p (n, m - 1), которые являются числом всех комбинаций, которые содержат по крайней мере один m как добавочный, и оставшийся сумма равна n-m (такая, что общая величина n), кроме того, каждое добавление меньше или равно m. Но это точно означает p (n-m, m), что является правой частью (1).

Очевидно, что ответ на вопрос должен быть p (n, n).

Ответ 4

        / 0 (k>n)
p(k,n)={  1 (k=n)
        \ p(k+1,n)+p(k,n-k) (k<n)

Число разбиений n равно p (1, n).

p (k, n) - число разбиений n, разрешая только addends >= k.

Как и рекурсивная формула OP, она добавляет их (как выразился luiges90) один за другим (с добавленной неэффективностью многочисленных нулей). К счастью, он может быть рассчитан внутри массива с большой скоростью:

#include <stdio.h>

/* 406 is the largest n for which p(n) fits in 64 bits */
#define MAX 406
long long int pArray[MAX][MAX];

/* Emulate array starting at 1: */
#define p(k,n) pArray[k-1][n-1]

int main(int argc, char **argv) {

 int n, k;

 for (n = 1; n < MAX; n++) {
  for (k = n; k > 0; k--) {
   if (k > n) {
    p(k, n) = 0;
   }
   else if (k == n) {
    p(k, n) = 1;
   }
   else {
    p(k, n) = p(k, n-k)+p(k+1, n);
   }
  }
 }

 for (n = 1; n < MAX; n++) {
  printf("p(%d)=%lld\n", n, p(1,n));
 }

}