algorithm - recursivos - Partición entera(algoritmo y recursión)

recursividad programacion

Question

Encontrar cuántas combinaciones de un número de suma (la variable n en el código). Por ej .:

3 = 1 + 1 + 1 = 2 + 1 = 3 => ANS es 3

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 => ANS es 7

En el siguiente ejemplo, m es el número máximo y n es suma, el objetivo es encontrar cuántas combinaciones (suma) tiene.

Solo quiero saber por qué p(n, m) = p(n, m - 1) + p(n - m, m) ?

El código aquí:

int p (int n, int m)
{
    if (n == m)
        return 1 + p(n, m - 1);
    if (m == 0 || n < 0)
        return 0;
    if (n == 0 || m == 1)
        return 1;

    return p(n, m - 1) + p(n - m, m);

}

¡Apreciado!

Answer 1

Considere todas las formas de obtener n agregando algunos números menores o iguales a m . Como dijiste, llamamos a esto p(n,m) . Por ejemplo, p (7,3) = 8 porque hay 8 formas de hacer 7 de menos de 3 como se indica a continuación: (Para simplificar, podemos suponer que siempre agregamos números en orden de mayor a menor)

• 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

Ahora podemos dividir estas combinaciones en dos grupos:

1. Combinaciones cuyo primer elemento es igual a m (= 3 en nuestro ejemplo :)

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

2. Combinaciones cuyo primer elemento es menor que m :

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

Debido a que cada miembro de las combinaciones de p(n,m) estará en el Grupo 1 o en el Grupo 2, podemos decir p(n,m)=size(Group1) + size(Group2) . Ahora, si probamos que el size(Group1)=p(nm, m) y el size(Group2)=p(n,m-1) por sustitución, llegamos a p(n,m)=p(nm,m)+p(n,m-1)

Probar para el size(Group1)=p(nm, m) :

Por la definición mencionada anteriormente p(nm, m) es el número de formas de nm resultante al sumar algunos números menores o iguales a m .

• Si agrega m a cada combinación de p(nm, m) , resultará un miembro de Group1. entonces p(nm, m) <= size(Group1)
• Si elimina la primera m de cada miembro del Grupo 1, resultará una combinación para p(nm, m) . size(Group1) <= p(nm, m)

=> size(Group1) = p(nm, m) . En nuestro ejemplo:

Grupo 1 <=== correspondencia ===> 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

Así que hay una correspondencia uno a uno entre cualquier miembro de p(nm,m) y Group1 y su tamaño es igual.

Probar para size(Group2)=p(n, m-1) :

Por definición, p(n,m-1) es el número de formas de obtener n al sumar algunos números menores o iguales a m-1 (menos de m ). Si vuelve a leer la definición de Grupo 2, verá que estas dos definiciones son iguales entre sí. => size(Group2) = p(n, m-1)

Answer 2

Indica p(n, m) como el número de todas las combinaciones cuya suma es n y cada sumando es menor que o igual a m . El punto clave aquí es probar la siguiente ecuación recursiva:

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

El lado izquierdo de (1) es la diferencia de p (n, m) y p (n, m - 1), que es el número de todas las combinaciones que contienen al menos una m como sumando, y la suma de las sobras es nm (por ejemplo, que el total es n ), además de que cada sumando es menor o igual que m . Pero eso significa exactamente p (nm, m), que es el lado derecho de (1).

Obviamente, la respuesta de la pregunta debe ser p (n, n).

Answer 3

Primero por más de lo que podría querer saber acerca de esta función, consulte http://mathworld.wolfram.com/PartitionFunctionP.html .

En cuanto a esta fórmula, recuerde que p(n, m) se define como el número de particiones de n cuyo miembro más grande es a lo sumo m .

Por lo tanto, p(n, m) es el número de particiones de m cuyo miembro más grande es a lo sumo m . Vamos a dividirlos de acuerdo a si el miembro más grande es en realidad m .

El número de particiones cuyo miembro más grande es m es el número de formas de llenar n = m + ... que es el número de particiones de nm cuyo miembro más grande es a lo sumo m que por definición es p(nm, m) .

El número de particiones de n cuyo miembro más grande es como máximo m-1 es por definición p(n, m-1) .

Por lo tanto, p(n, m) = p(nm, m) + p(n, m-1) .

Answer 4

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

Número de particiones de n es p (1, n).

p (k, n) es el número de particiones de n, permitiendo solo sumandos> = k.

Al igual que la fórmula recursiva del OP, los agrega (como lo dice luiges90) uno por uno (con la ineficiencia agregada de numerosos ceros). Afortunadamente, sin embargo, se puede calcular dentro de una matriz con gran velocidad:

#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));
 }

}