Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révision Les deux révisions suivantes | ||
les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/10 21:40] et |
les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/25 11:43] et [Ci-dessous un exemple d'utilisation de celui-ci :] |
||
---|---|---|---|
Ligne 2: | Ligne 2: | ||
---- | ---- | ||
+ | ==== C'est quoi un algorithme glouton ? ==== | ||
- | L' | + | L' |
+ | ==== L' | ||
+ | |||
+ | < | ||
+ | VARIABLE | ||
+ | |||
+ | x : un entier | ||
+ | f : une liste dans l' | ||
+ | r : une liste | ||
+ | |||
+ | DEBUT | ||
+ | |||
+ | ALGORITHME_GLOUTON(x, | ||
+ | compteur ← 1 | ||
+ | tant que x > 0 ou : | ||
+ | si f[compteur] > x: | ||
+ | compteur ← compteur + 1 | ||
+ | sinon: | ||
+ | x ← x - f[compteur] | ||
+ | r.append(f[compteur]) | ||
+ | compteur ← compteur + 1 | ||
+ | fin si | ||
+ | fin tant que | ||
+ | fin | ||
+ | </ | ||
+ | |||
+ | ====Ci-dessous un exemple d' | ||
+ | |||
+ | === Problème du voleur === | ||
+ | |||
+ | ^ Objet | ||
+ | ^ Masse | ||
+ | ^Valeur marchande| | ||
+ | |||
+ | 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 " | ||
+ | ^ Objet | | ||
+ | ^ 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' | ||
+ | * 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' | Voici un exemple de l' | ||
<code python> | <code python> | ||
Ligne 65: | Ligne 116: | ||
- | Le programme crée deux variables avec des input, et demande à l' | + | Le programme crée deux variables avec des input, et demande à l' |
<code python> | <code python> | ||
Ligne 116: | Ligne 167: | ||
- | Le programme vérifie le fait que la valeur de la pièce/ | + | Le programme vérifie le fait que la valeur de la pièce/ |
<code python> | <code python> | ||
if monnaie[x][0] > somme_a_rendre: | if monnaie[x][0] > somme_a_rendre: | ||
Ligne 125: | Ligne 176: | ||
monnaie[x][1] += 1 | monnaie[x][1] += 1 | ||
</ | </ | ||
+ | |||
+ | |||
+ | Le but de cette boucle '' | ||
+ | |||
+ | <code python> | ||
+ | for i in range(1, 13): | ||
+ | if monnaie[i][1] >= 1: | ||
+ | monnaie_used.append(monnaie[i]) | ||
+ | </ | ||
+ | |||
+ | |||
+ | Le '' | ||
+ | <code python> | ||
+ | print("" | ||
+ | return monnaie_used | ||
+ | </ | ||
+ | |||
+ | |||
+ | Ce '' | ||
+ | |||
+ | <code python> | ||
+ | else: | ||
+ | return "Le prix de l' | ||
+ | </ | ||
+ | |||
+ | |||
+ | Permet simplement d' | ||
+ | <code python> | ||
+ | print(rendu_monnaie(monnaie, | ||
+ | </ | ||
+ | |||
+ | Les explications sont terminées j' | ||
\\ | \\ |