Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/10 21:40]
et
+++ les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/25 12:00]
et [L'algorithme Général]
@@ Ligne 2: / Ligne 2: @@
 ----
+==== C'est quoi un algorithme glouton ? ====
-L'algorithme ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape du programme ou autre.
+L'algorithme ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape. De ce fait, le résultat final n'est pas toujours le plus optimisé.
+==== L'algorithme Général ====
+<code>
+VARIABLE
+x : un entier
+f : une liste dans l'ordre croissant
+r : une liste
+DEBUT
+ALGORITHME_GLOUTON(x, l) :
+    compteur ← 1
+    tant que x > 0:
+        si f[compteur] > x:
+            compteur ← compteur + 1
+        sinon:
+            x ← x - f[compteur]
+            ajouter(f[compteur], r)
+            compteur ← compteur + 1
+        fin si
+    fin tant que
+fin
+</code>
+====Ci-dessous un exemple d'utilisation de celui-ci :====
+=== Problème du voleur ===
+^      Objet     |     A      |     B      |     C     |     D      |
+^      Masse     |    13Kg    |    12Kg    |    8Kg    |    10Kg    |
+^Valeur marchande|    700€    |    400€    |    300€   |    300€    |
+Le voleur à un sac avec une capacité de 30Kg.
+Sachant que l'on cherche à maximiser le gain, commençons par établir un tableau nous donnant la "valeur massique" de chaque objet (pour chaque objet on divise sa valeur par sa masse) :
+^ Objet          |   A    |    B    |    C    |    D    |
+^ Valeur Massique|54 €/Kg | 33 €/Kg | 38 €/Kg | 30 €/Kg |
+On classe ensuite les objets par ordre décroissant de valeur massique : A - C - B - D
+Enfin, on remplit le sac en prenant les objets dans l'ordre et en s'arrêtant dès que la masse limite est atteinte. C'est ici que ce fait "le choix glouton", à chaque étape, on prend l'objet ayant le rapport "valeur-masse" le plus intéressant au vu des objectifs :
+  * 1re étape : A (13 Kg)
+  * 2e étape : C (13+8=21 Kg)
+  * 3e étape : B (13+8+12=33 Kg) => impossible, on dépasse les 30 Kg.
+Le sac est donc composé de 2 objets : A et C pour un montant total de 1000 € et une masse totale de 21 Kg.
+On remarque que ce n'est pas la combinaison la plus optimisé, celle-ci serait A,B (1100€ pour 25Kg) et non A,C (1000€ pour 21Kg).
+======Implémentation en Python======
 Voici un exemple de l'algorithme Glouton avec le problème du rendu de monnaie, ce code renvoie quelle(s) billet(s)/pièce(s) a été utilisé et combien de fois il l'a utilisé :
 <code python>
@@ Ligne 65: / Ligne 116: @@
-Le programme crée deux variables avec des input, et demande à l'utilisateur le prix de l'objet et l'argent donnée. Puis le programme fait la différence et arrondie au centième :
+Le programme crée deux variables avec des input, et demande à l'utilisateur le prix de l'objet et l'argent donnée. Puis il fait la différence et arrondie au centième :
 <code python>
@@ Ligne 116: / Ligne 167: @@
-Le programme vérifie le fait que la valeur de la pièce/billet correspondent à la clef soit supérieur à ''somme_a_rendre'' pour éviter que ''somme_a_rendre'' devienne négatif. Sinon le programme soustrait la pièce/billet correspondent à la clef à ''somme_a_rendre'' puis ajoute à ''monnaie'' l'utilisation de la pièce/billet encore une fois avec la clef correspondent.
+Le programme vérifie le fait que la valeur de la pièce/billet qui correspondant à la clef soit supérieur à ''somme_a_rendre'' pour éviter que ''somme_a_rendre'' devienne négatif. Sinon le programme soustrait la pièce/billet correspondant à la clef à ''somme_a_rendre'', puis ajoute 1 à deuxième variable de ''monnaie'' encore une fois avec la clef correspondant.
 <code python>
 if monnaie[x][0] >  somme_a_rendre:
@@ Ligne 125: / Ligne 176: @@
         monnaie[x][1] += 1
 </code>
+Le but de cette boucle ''for'' est de savoir quelle pièce/billet à été utilisé avec le ''if monnaie[i][1] >= 1'' en vérifiant si la deuxième variable de la clef correspondante est supérieure ou égal à 1. Et si c'est le cas, alors le(s) billet(s)/pièce(s) utilisé(s) et le nombre de fois qu'ils ont été utilisé(s) sont ajoutés à ''monnaie_used''.
+<code python>
+for i in range(1, 13):
+            if monnaie[i][1] >= 1:
+                monnaie_used.append(monnaie[i])
+</code>
+Le ''print("")'' permet juste un saut de ligne pour de l'esthétique, et le programme renvoie les billet(s)/pièce(s) utilisé(s).
+<code python>
+print("")
+return monnaie_used
+</code>
+Ce ''else'' renvoie au ''if somme_a_rendre > 0'' utilisé précédemment, dans le cas ou ''somme_a_rendre'' est inférieur à 0.
+<code python>
+else:
+        return "Le prix de l'objet est plus grand que l'argent donnée"
+</code>
+Permet simplement d'utilisé la fonction ''rendu_monnaie''.
+<code python>
+print(rendu_monnaie(monnaie, somme_a_rendre))
+</code>
+Les explications sont terminées j'espère qu'elles vous auront été utiles !
  \\

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page