Cours Algorithmes gloutons
QCM
  • 1
  • 2
  • 3
  • 4
  • 5

L'énoncé

Dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Suivant le système de pièces, l'algorithme glouton est optimal ou pas.

Cocher la (ou les) bonne(s) réponse(s).


Tu as obtenu le score de


Question 1

Dans le système monétaire français, les pièces et/ou les billets prennent les valeurs 1, 2, 5, 10, 20, 50, 100 euros. Pour simplifier, on ne considère pas les centimes.

Quelle somme donne l'algorithme glouton pour 49€ ?

49 x 1

10 + 10 + 10 + 10 + 5 + 2 + 2

20 + 20 + 5 + 2 + 2

L'algorithme glouton choisit d'abord la plus grande valeur parmi 1 , 2 , 5, 10, 20 (100 étant trop grand), contenue dans 49. Il choisit donc deux billets de 20 euros. Il reste alors 9 euros à rendre, l'algorithme choisit un billet de 5 euros puis deux pièces de 2 euros.

10 + 10 + 5 + 5 + 5 + 5 + 5 + 2 + 2

L'algorithme glouton choisit d'abord la plus grande valeur.

Question 2

On peut montrer que l'algorithme glouton donne toujours une solution optimale pour le système monétaire français. Comment est qualifié un tel système ?

Hyperbolique

Canonique

Un problème pour lequel l'algorithme glouton donne une valeur optimale est appelé canonique.

Minimal

Maximal

Un tel système semble être naturel et instinctif.

Question 3

Avec le système (1,3,6,12,24,30), quelle est la solution optimale pour le rendu 49 ?

30 + 12 + 6 + 1

49 x 1

4 x 12 + 1

2 x 24 + 1

Les autres des solutions ont plus de 3 pièces. Cette solution est optimale.

La solution optimale ne requiert que 3 pièces.

Question 4

Avec le même système (1,3,6,12,24,30), que répond l'algorithme glouton pour le rendu 49 ?

2 x 24 + 1

30 + 12 + 6 + 1

L'algorithme glouton choisit d'abord la plus grande valeur parmi 1 , 3 , 6, 12, 24, 30 contenue dans 49. Il choisit donc une pièce de 30. Il reste alors 19 à rendre, l'algorithme choisit une pièce de 12 puis une pièce de 6, puis une pièce de 1.

4 x 12 + 1

30 + 6 + 6 + 3 + 3 + 1

L'algorithme glouton choisit d'abord la plus grande valeur.

Question 5

Un voyageur souhaite minimiser son voyage de la ville A à la ville J.

 

route_length

 

Quelle sera la route prise par l'algorithme glouton (rouge) ? Quelle est la route optimale (vert) ?

A - B - F - I - J : 2 + 4 + 3 + 4 = 13

A - D - F - I - J : 2 + 4 + 3 + 4 = 11

A - B - F - I - J : 2 + 4 + 3 + 4 = 13

L'algorithme glouton choisit toujours le chemin le plus court localement. On voit bien qu'effectuer une série de choix localement optimaux, nous n'aboutissons pas toujours au choix globalement optimal.

A - D - F - I - J : 2 + 4 + 3 + 4 = 11

Dans cet exemple, l'algorithme glouton ne donne pas un résultat optimal.