Le sujet traite du problème de rendu de monnaie : comment rendre la monnaie en utilisant le plus petit nombre possible de pièces (ou d´unité atomique monaitaire)? Nous metterons en place le formalisme et les outils qui serviront pour la résolution de notre problème. On étudiera l’"algorithme glouton ». Nous réaliserons aussi un algorithme permettant de décider si le résultat de l’algorithme glouton est optimal pour un système de monnaie donné.

Modélisation du problème.

Un système de monnaie atomique est représenté mathématiquement par un vecteur de valeurs décroissantes (par exemple S=[200,100,50,20,10,1], nous représenterons en Java ce vecteurs par une liste.
Le rendu sera aussi représenté par un vecteur (donc une liste en Java) qui représente pour chaque position (indice) le nombre d'unité monétaire correspondant au même indice dans le système. (par exemple R=[1,0,2,0,0,5] représente R.S = 305. R.S état le produit cartésiens (euclidiens) E.S = SUM(ri*si) 0<=i<n

Commençons donc par quelques modélisation et calcul simple sur des vecteurs

Solution par force brute

1-Trouvez toutes les combinaisons (solutions)