Activité

Nous allons dans cette série d'activité étudier un problème classique en informatique, le problème du rendu de monnaie

activité 31.1

Nous sommes des commerçants, nous avons à notre disposition un nombre illimité de pièces de :

• 1 centime
• 2 centimes
• 5 centimes
• 10 centimes
• 20 centimes
• 50 centimes
• 1 €
• 2 €

Nous devons rendre la monnaie à un client à l'aide de ces pièces. La contrainte est d'utiliser le moins de pièces possible.

Trouvez une méthode gloutonne permettant d'effectuer un rendu de monnaie (en utilisant le moins possible de pièces).

Vous devez rendre la somme de 2,63 €, appliquez la méthode que vous venez de mettre au point.

Combien de pièces avez-vous utilisées ?

activité 31.2

À partir de la méthode gloutonne que vous avez élaborée dans l'activité 31.1, écrivez un algorithme glouton qui permettra de déterminer le nombre minimal de pièces à utiliser pour une somme donnée. Vous proposerez ensuite une implémentation en Python de votre algorithme. Vous testerez votre programme avec une somme à rendre de 2 euros et 63 centimes.

activité 31.3

Nous avons maintenant uniquement les pièces suivantes :

• 2 centimes
• 5 centimes
• 10 centimes
• 20 centimes
• 50 centimes
• 1 €
• 2 €

Utilisez le programme que vous avez développé dans l'activité 31.2 pour essayer de résoudre le problème pour une somme de 11 centimes à rendre. Que constatez-vous ?