De combien de façons ? — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 3)

De combien de façons ?

Sacs avec répétitions, multi-ensembles et couples de sacs · niveau 2

Énoncé

On veut compter les façons de former la somme $S$ avec des pièces de valeurs $p_{0}, \dots, p_{n - 1}$ en nombre illimité, sans tenir compte de l'ordre ( $5 + 2 + 2 + 1$ et $2 + 5 + 1 + 2$ sont la même façon).

On note $f (k, s)$ le nombre de façons de former $s$ avec les $k$ premières sortes de pièces. Inspirez-vous de la seconde version du cours (« aucun exemplaire de la $k$ -ème pièce, ou au moins un ») pour écrire l'équation de récurrence.
Montrer qu'un seul tableau $F [0 : S + 1]$ suffit, parcouru par $s$ croissants. Écrire la fonction.
Combien de façons de former $10$ avec ${1, 2, 5}$ ? de former $100$ avec ${1, 2, 5, 10, 20, 50}$ ?

Corrigé

Les façons de former $s$ avec les $k$ premières sortes de pièces n'utilisent aucune pièce $p_{k - 1}$ (il y en a $f (k - 1, s)$ ) ou en utilisent au moins une : en retirant l'une d'elles, on obtient une façon de former $s - p_{k - 1}$ avec les mêmes $k$ sortes. Ces deux familles sont disjointes : on additionne. Base : $f (0, 0) = 1$ , $f (0, s) = 0$ pour $s \geq 1$ . Hérédité : $\forall k \geq 1$ ,

$f (k, s) = f (k - 1, s) + {f (k, s - p_{k - 1}) 0 si p_{k - 1} \leq s, sinon.$

Pour $k$ fixé, $f (k, s)$ demande $f (k - 1, s)$ (l'ancienne valeur de la case $s$ ) et $f (k, s - p_{k - 1})$ (une case de la même ligne, déjà mise à jour si l'on parcourt les $s$ par valeurs croissantes).


static long facons(int[] P, int S) {
    long[] F = new long[S + 1];
    F[0] = 1;                                  // base : la façon vide
    for (int p : P)                            // k croissants
        for (int s = p; s < S + 1; s++)        // s croissants
            F[s] += F[s - p];                  // F[s] devient f(k,s)
    return F[S];
}

La boucle externe sur les pièces garantit que l'ordre des pièces ne compte pas : chaque façon est construite en ajoutant les pièces sorte par sorte.


nom : F
valeurs : 1 1 2 2 3 4 5 6 7 8 10
colorier : 10
vert : 5..9
fleches : 5->10
legende : pièces 1, 2, 5, passage de la pièce 5 : F[10] = 6 + F[5] = 10

Le programme donne $10$ façons de former $10$ avec ${1, 2, 5}$ , et $4562$ façons de former $100$ avec ${1, 2, 5, 10, 20, 50}$ .