¿Cómo puedo explicar esto entero particiones función de la recursividad?

Question

Cómo explicar cómo funciona el algoritmo? Tengo que escribir un artículo sobre esto, pero no puedo explicar por qué esta recursividad funciona bien.

Se define el número de particiones de un entero dado

function p(sum,largest):
    if largest==0: return 0
    if sum==0: return 1
    if sum<0: return 0
    return p(sum, largest-1) + p(sum-largest, largest)

(llame a: p(n,n))

Muchas gracias.

Answer 1

Esta función es la misma como $F(n, k)$ que es el número de particiones de $n$ tal que ningún elemento de la partición es mayor que $k$ (asumiendo $k <= n$).

El uso de esta función $F(n, n)$ indica el número de particiones de $n$ ya que ningún elemento de la partición de $n$ puede ser mayor que $n$.

Las condiciones de base $F(0, k) = 1$ $F(-m, k) = 0$ son por la definición de la función de partición $P(n)$, lo que representa el número total de particiones de $n$ ($m > 0$). $F(n, 0) = 0$ como $n$ no puede ser dividido de tal manera que ningún elemento de la partición es mayor que $0$.

Ahora, en cuanto a la última declaración de la función, creo que de $F(n, k)$ - el número de particiones de $n$ tal que ningún elemento en una partición es mayor que $k$ - como la unión de dos conjuntos mutuamente excluyentes, el primer conjunto que contiene todas las particiones tal que todos los elementos en una partición están a menos de $k$ y el segundo conjunto contiene todas las particiones tal que al menos un elemento en cada partición es igual a $k$.

Claramente la cardinalidad de la primera serie es $F(n, k-1)$ y la cardinalidad de la segunda $F(n-k, k)$ porque ya hemos escogido $k$ como un elemento en una partición, así que ahora tenemos a la partición de $n-k$.

Claramente la de los dos conjuntos son mutuamente excluyentes, por lo tanto,

$F(n, k) = F(n, k-1) + F(n-k, k) $

Answer 2

La terminología más grande es engañoso: la idea no es que el $p(n,m)$ es el número de particiones de $n$, cuya mayor parte es en la mayoría de las $m$, no el número, cuya mayor parte es $m$. Esta función normalmente se denota por a $q$, como en esta referencia.

Ahora mira a la condición de parada del algoritmo. La primera es que el $p(n,0)$ siempre $0$; que tiene sentido, ya que la partición se ha de tener una parte positiva. Saltar a la siguiente línea por un momento; si $n<0\ne m$, $p(n,m)=0$; que también tiene sentido, puesto que las particiones de enteros negativos no están definidos. El centro condición de parada dice que si $m\ne 0$,$p(0,m)=1$, lo que probablemente se ve un poco extraño. Resulta, sin embargo, para hacer la vida más sencilla si decimos, por convención, que el entero $0$ $1$ partición.

Lo que queda por explicar es la recurrencia:

$$p(n,m)=p(n,m-1)+p(n-m,m)\text{ if }m,n\ne 0\;.$$

Considerar las particiones de $n$ con ninguna parte más grande de $m$.

1. Algunos de ellos reales no tienen una parte igual a$m$; cuántos de esos hay?

2. El resto todos tienen al menos una parte igual a $m$. Esa parte, y lo que queda es una partición de lo entero? ¿Y cuál es el tamaño más grande posible de las partes restantes?

Answer 3

Sugerencias:

Se puede utilizar un número relativamente reducido y el trabajo a través del algoritmo para permitir que usted vea lo que está sucediendo?

A continuación, busque en la zona denominada 'el Intermedio de la Función" en este sitio web y vea si usted puede trabajar a través de este.

También puede buscar en la recurrencia de la relación aquí.

HTH ~