informatique (MP2I/MPI) · Chapitre 17 · Application directe du cours

Problème — Compter au lieu d'optimiser : combinaisons ou compositions ?

Programmation dynamique · niveau 3 (difficile)

Énoncé

On ne cherche plus le nombre minimal de pièces, mais le nombre de façons de rendre une somme $S$ avec un système de pièces $P$ .

Écrire les deux programmes que l'on obtient selon l'ordre des deux boucles.
Que compte chacun ? Le vérifier à la main sur $S = 5$ avec $P = {1, 2}$ .
Donner les deux suites de valeurs pour $S = 0$ à $8$ , et reconnaître l'une d'elles.

Corrigé de la question 1

1. Les deux programmes ne diffèrent que par l'ordre des boucles :


/* (A) pieces a l'exterieur */
int a[S + 1]; a[0] = 1; for (int s = 1; s <= S; s++) { a[s] = 0; }
for (int i = 0; i < k; i = i + 1) {
    for (int s = p[i]; s <= S; s = s + 1) { a[s] = a[s] + a[s - p[i]]; }
}

/* (B) sommes a l'exterieur */
int b[S + 1]; b[0] = 1; for (int s = 1; s <= S; s++) { b[s] = 0; }
for (int s = 1; s <= S; s = s + 1) {
    for (int i = 0; i < k; i = i + 1) {
        if (p[i] <= s) { b[s] = b[s] + b[s - p[i]]; }
    }
}

Question 2 : comment l'IA t'aide

2. Que compte chacun ? Le vérifier à la main sur $S = 5$ avec $P = {1, 2}$ .

Élève

Les deux programmes additionnent les mêmes termes $a [s - p_{i}]$ , simplement dans un autre ordre. Comme l'addition est commutative, j'ai pensé qu'ils comptaient la même chose.

Les termes n'ont pas la même valeur au moment où ils sont lus. Dans (A), quand on traite la pièce $p_{i}$ , quelles pièces ont pu servir à construire $a [s - p_{i}]$ ? Et dans (B), pour $b [s - p_{i}]$ ?

Élève

Dans (A), $a [s - p_{i}]$ n'a été construit qu'avec les pièces déjà traitées, de $p_{0}$ à $p_{i}$ . Dans (B), toutes les pièces ont déjà pu servir.

Qu'est-ce que cela impose sur l'ordre des pièces dans une façon comptée par (A) ? Que deviennent $1 + 2$ et $2 + 1$ dans chacun des deux programmes, et que trouves-tu en énumérant à la main pour $S = 5$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →