---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: C++17
  language: C++17
  name: xcpp17
---

+++ {"tags": ["solution"]}

# 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$).

1.  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

2.  É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.

    ```cpp
    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