Différences

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

--- nsi:terminales:recursivite:exemples [2022/12/01 15:51] – goupillwiki
+++ nsi:terminales:recursivite:exemples [2023/03/17 13:41] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. 193.51.53.161
@@ Ligne 60: / Ligne 60: @@
 ==== Rappel ====
-Ce problème a été vu en première dans le cadre de l'[[nsi:premiere:glouton|algorithme glouton]]. Rappelons-en le principe.
+Ce problème a été vu en première dans le cadre de l'[[nsi:premiere:glouton:glouton|algorithme glouton]]. Rappelons-en le principe.
   * On dispose d'un sac de capacité C,
   * d'un assortiment d'objets ayant tous un poids et une valeur.
@@ Ligne 89: / Ligne 89: @@
 <WRAP box>Implémentez la fonction ''meilleur_sac'' et donnez la solution du problème.</WRAP>
-<WRAP tip>Cette façon de faire est élégante. Le code est simple, facile à écrire et à comprendre. On a par contre un peu de mal à savoir si cela occasionnera beaucoup de calculs. Il se pourrait que l'on fasse plusieurs fois les mêmes calculs et que l'on perde du temps. Cet aspect est abordé avec la [[nsi:terminales:programmation_dynamique|programmation dynamique]].</WRAP>
+<code lang-none>
+FONCTION meilleur_sac
+ENTRÉES:
+   c : capacité restante
+   items: liste des items que l'on peut choisir
+SORTIE: le sac formé d'un choix dans la liste items,
+   qui forme le meilleur sac possible avec la capacité c
+DÉBUT
+   SI items vide ou c < = 0 ALORS
+       dans ce cas, on ne peut rien mettre dans le sac donc
+       RENVOYER sac vide
+   FIN SI
+   soit A le premier item parmi les items à choisir
+   (A existe forcément puisque si items vide, on aurait déjà fini)
+   soient items_sans_A la liste des items dont on a ôté A
+   on forme un premier essai de sac, appelé sac1. Dans ce sac on place A
+   il reste donc c - poids(A) de capacité que l'on peut remplir avec items_sans_A
+   en résumé, sac1 = A + meilleur_sac(c - poids(A), items_sans_A)
+   à noter : il se pourrait que ce sac ne soit pas valide. En effet, il se peut
+   que poids(A) > c.
+   on forme un autre sac, sac2, qui ne contient pas A. On dispose donc de la totalité
+   de la capacité pour former un sac au mieux avec les autres items.
+   donc sac2 = meilleur_sac(c, items_sans_A)
+   à noter : ce sac est forcément valide.
+   maintenant il faut choisir le meilleur sac entre sac1 et sac2 :
+   SI le sac1 est valide et qu'il a une valeur plus grande que sac2 ALORS
+       RENVOYER sac1
+   SINON
+       RENVOYER sac2
+   FIN
+FIN
+</code>
+<WRAP tip>Cette façon de faire est élégante. Le code est simple, facile à écrire et à comprendre. On a par contre un peu de mal à savoir si cela occasionnera beaucoup de calculs. Il se pourrait que l'on fasse plusieurs fois les mêmes calculs et que l'on perde du temps. Cet aspect est abordé avec la [[nsi:terminales:dynamique:programmation_dynamique|programmation dynamique]].</WRAP>