Exercice : Partitions d’entiers

Exercice : Partitions d’entiers#

On appelle décomposition additive (ou partition) d’un nombre $n$ une liste de nombres dont la somme est égale à $n$. Par exemple, $(3, 2, 1, 1)$ est une décomposition additive de $7$. En utilisant uniquement les nombres de $1$ à $4$, il existe $11$ manières de décomposer le nombre $7$: $$(4,3) (4,2,1) (4,1,1,1) (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)$$

L’objectif de cet exercice est d’écrire une fonction qui compte le nombre de décompositions additives d’un nombre $n$ utilisant les nombres de $1$ à $t$ :

int partition(int n, int t);

Pour cela on partira de l’observation que le nombre de partitions additives de $n$ par les nombres de $1$ à $t$ est égal à la somme de:

le nombre de partitions additives de $n$ par les nombres de $1$ à $t-1$,
le nombre de partitions additives de $n-t$ par les nombres de $1$ à $t$ (si $n\ge t$).

Quels sont les cas d’arrêt pour cette fonction ?

BEGIN SOLUTION

Il va y avoir deux appels récursifs, l’un faisant décroitre $n$ et l’autre $t$, il va donc falloir trouver des cas limites pour les deux. Pour $n$, le cas $n=0$ indique que l’on a trouvé une décomposition et donc on peut renvoyer $1$. Pour $t$, deux solutions sont possibles, on peut s’arrêter pour $t=0$ en renvoyant $0$ pour indiquer que la décomposition à échouée, mais il est plus efficace de s’arrêter pour $t=1$ en renvoyant $1$ pour indiquer qu’une décomposition triviale à été trouvée.

END SOLUTION

Écrivez et testez la fonction partition.

BEGIN SOLUTION

Deux variantes possibles ici, la deuxième version évite la vérification entre $n$ et $t$ en ajoutant un cas d’arrêt supplémentaire.

int partition(int n, int t) {
    if (t == 1) return 1;
    if (n == 0) return 1;
    int r = partition(n, t - 1);
    if (n >= t)
        r += partition(n - t, t);
    return r;
}
int partition2(int n, int t) {
    if (t == 1) return 1;
    if (n == 0) return 1;
    if (n <  0) return 0;
    return partition2(n, t - 1) + partition2(n - t, t);
}

END SOLUTION