Différences

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

--- les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/25 11:43]
et [Ci-dessous un exemple d'utilisation de celui-ci :]
+++ les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/30 08:28] (Version actuelle)
et
@@ Ligne 4: / Ligne 4: @@
 ==== C'est quoi un algorithme glouton ? ====
-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 ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape sans revenir sur ses décisions. De ce fait, le résultat final n'est pas toujours le plus optimisé.
-==== L'algorithme Général ====
+Pour sa complexité, si les objets sont déjà triés par ordre décroissant de valeur, alors la boucle bornée de 1 à n correspond à une complexité de l'ordre de O(n). Par contre si la liste des objets n'est pas triée on passe à une compléxité de l'ordre de O(n logn).
+==== L'algorithme dans le cas Général ====
 <code>
@@ Ligne 12: / Ligne 14: @@
 x : un entier
-f : une liste dans l'ordre croissant
+f : une liste ordonnée
 r : une liste
@@ Ligne 19: / Ligne 21: @@
 ALGORITHME_GLOUTON(x, l) :
     compteur ← 1
-    tant que x > 0 ou :
+    tant que x > 0:
         si f[compteur] > x:
             compteur ← compteur + 1
         sinon:
             x ← x - f[compteur]
-            r.append(f[compteur])
+            ajouter(f[compteur], r)
             compteur ← compteur + 1
         fin si
     fin tant que
-fin
+FIN
 </code>
-====Ci-dessous un exemple d'utilisation de celui-ci :====
+====Ci-dessous un exemple d'utilisation :====
 === Problème du voleur ===

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page