QCM☘

Rappel

Les questions ci-dessous sont là pour vous aider à contrôler ce que vous avez retenu.
Si vous ne répondez pas à toutes les questions sans hésitation, c'est sans doute qu'il faut retravailler les pages précédentes.

Pour chaque question, il faut trouver la (ou les) bonne(s) réponse(s).

QCM 1☘

On dispose en quantité illimité de pièces de 1 euro, 2 euros et 5 euros. On veut totaliser une somme de 18 euros.
Quelle est la solution donnée par l’algorithme glouton ?

[5, 5, 5, 2, 1].
[5, 5, 5, 2, 2, 1].
[5, 5, 2, 2, 2, 1, 1].
[5, 2, 2, 2, 2, 1, 1, 1, 1, 1].

Réponse

[5, 5, 5, 2, 1].
[5, 5, 5, 2, 2, 1].
[5, 5, 2, 2, 2, 1, 1].
[5, 2, 2, 2, 2, 1, 1, 1, 1, 1].

QCM 2☘

On dispose de sacs de jetons portant les nombres 10, 5, 3 et 1. On veut obtenir un total de 21 en utilisant ces jetons. Si on utilise le principe de l'algorithme glouton, quelle addition va-t-on réaliser pour obtenir ce total de 21 ?

5 + 5 + 5 + 5 + 1.
10 + 5 + 3 + 3.
10 + 5 + 5 + 1.
10 + 10 + 1.

Réponse

5 + 5 + 5 + 5 + 1.
10 + 5 + 3 + 3.
10 + 5 + 5 + 1.
10 + 10 + 1.

QCM 3☘

Pour payer une somme S (entier naturel) avec les pièces en cours, tout en utilisant le moins possible, on décide de suivre le principe glouton :
« donner la pièce de plus grande valeur possible, puis recommencer avec la somme restante... »

Avec quel système de pièces ce principe ne mène pas nécessairement à utiliser le plus petitnombre possible de pièces ?

pièces de montants 1, 2, 5, 10.
pièces de montants 1, 2, 4, 8, 16.
pièces de montants 1, 3, 9, 27.
pièces de montants 1, 4, 5, 8.

Réponse

pièces de montants 1, 2, 5, 10.
pièces de montants 1, 2, 4, 8, 16.
pièces de montants 1, 3, 9, 27.
pièces de montants 1, 4, 5, 8.

Le cas 1, 2, 5, 10 a été traité dans le cours. Les cas 1, 2, 4, 8, 16 et 1, 3, 9, 27 sont de la forme 1, p, p², p³, ... : voir cet exercice.

Pour le dernier cas, on voit par exemple que pour payer S = 15, l'algorithme utilisera une pièce de 8, une pièce de 5, deux pièces de 1, soit 4 pièces alors trois pièces de 5 suffisent.

QCM 4☘

Pour rendre la monnaie, il est possible d'utiliser un algorithme glouton.
Une seule des affirmations suivantes est vraie :

Avec un algorithme glouton, on rend la monnaie en commençant toujours par la pièce de plus petite valeur afin de maximiser le nombre de pièces rendues.
Avec un algorithme glouton, on rend la monnaie en commençant toujours par la pièce ayant la plus grande valeur possible et en procédant ensuite par valeurs décroissantes.
Quel que soit le type de pièces dans un pays donné, un algorithme glouton donne toujours la monnaie de manière optimale.
Un algorithme glouton procède en testant toutes les combinaisons possibles de pièces afin de trouver le rendu optimal.

Réponse

Avec un algorithme glouton, on rend la monnaie en commençant toujours par la pièce de plus petite valeur afin de maximiser le nombre de pièces rendues.
Avec un algorithme glouton, on rend la monnaie en commençant toujours par la pièce ayant la plus grande valeur possible et en procédant ensuite par valeurs décroissantes.
Quel que soit le type de pièces dans un pays donné, un algorithme glouton donne toujours la monnaie de manière optimale.
Un algorithme glouton procède en testant toutes les combinaisons possibles de pièces afin de trouver le rendu optimal.

QCM 5☘

On veut transporter une masse M de sable (en tonne, M étant un entier naturel).
On dispose pour cela, en très grand nombre, de camions pouvant transporter 10 tonnes, de camions pouvant transporter 5 tonnes, de camions pouvant transporter 2 tonnes et de camions pouvant transporter 1 tonne.

On décide de remplir le maximum de camions de 10 tonnes. Lorsqu'on n'a plus assez de sable pour remplir un camion de 10 T, on remplit des camions de 5 T. Lorsqu'on n'a plus assez de sable pour remplir un camion de 5T, on remplit des camions de 2T. Lorsqu'on n'a plus assez de sable pour remplir un camion de 2T, on remplit des camions de 1T.

En procédant ainsi, a-t-on utilisé le moins de camions possible ?

oui
non

Réponse

oui
non

Ce problème est exactement le même que payer une somme M avec des pièces de 10, 5, 2 et 1. Et on a vu qu'avec cette liste de valeurs possibles, l'algorithme glouton donne un résultat optimal.