Différences

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

--- nsi:terminales:recursivite:exemples [2021/10/24 17:06] – créée 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 3: / Ligne 3: @@
 ===== Triangle de Sierpinski ======
+Il s'agit d'une figure construite récursivement. On peut définir ''S(n,c)'' ainsi :
+  * ''n'' est le niveau de détails souhaité,
+  * ''c'' est la taille du côté
+{{ :nsi:terminales:recursivite:sierpinski.png?direct |}}
+La construction nous indique que :
+  * pour ''n = 0'' on a un simple triangle plein
+  * pour ''n = 1'', ''S(1, c)'' est constitué de 3 triangles inférieurs : ''S(0, c/2)''
+  * pour ''n = 2'', ''S(2, c)'' est constitué de 3 triangles inférieurs : ''S(1, c/2)''
+  * on comprend que pour ''n > 1'', ''S(n,c)'' est constitué de 3 figures ''S(n-1, c/2)''.
+On peut faire le tracer en utilisant le module ''turtle'' :
+<code python linenums:1>
+from turtle import *
+speed(100)
+pensize(1)    # taille du tracé
+setheading(0) # orientation vers l'est
+# votre programme ici
+# fin du programme
+exitonclick()
+</code>
+Quelques commandes dans ce [[nsi:tds:tortue|TD]]. Vous pouvez aussi utiliser la [[https://docs.python.org/fr/3/library/turtle.html|documentation du module turtle]].
+<WRAP box>Écrivez la fonction ''S(n,c)'' faisant le tracé du triangle de Sierpinski. Faites l'essai par exemple avec ''S(5,200)''.</WRAP>
+<WRAP tip>Sur le même principe, [[https://fr.wikipedia.org/wiki/Flocon_de_Koch|flocon de Koch]]</WRAP>
+===== Tours de Hanoï =====
+Dans [[:nsi:tds:hanoi|ce TD]], on vous décrit le problème des tours de Hanoï.
+Un solution très simple de ce problème passe par une fonction récursive.
+On veut déplacer une pile de N cylindres de la position A à la position B. Pour cela, il faut :
+  * déplacer N-1 cylindres de A à C,
+  * déplacer le cylindre N de A à B,
+  * déplacer N-1 cylindres de C à B,
+<WRAP box>Implémentez cette solution.</WRAP>
+===== Mesures d'un arbre =====
+Dans cet [[nsi:sujets:21-nsij2me2:exercice_3|exercice]] nous avons vu des exemples de fonctions récursives permettant de calculer la hauteur ou la taille d'un arbre.
+<WRAP tip>Une liste chaînée peut être vue comme un arbre spécial -- un nœud n'a qu'un enfant -- et on pourrait donc appliquer la même méthode pour obtenir la longueur d'une liste.</WRAP>
+===== Sac à dos =====
+==== Rappel ====
+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.
+  * On cherche à placer des objets dans le sac en respectant la contrainte de capacité et en maximisant la valeur totale du contenu du sac.
+**Exemple :** On dispose d'un sac d'une capacité de C = 15 kg et de la liste d'objets suivants :
+^ nom   ^ Valeur ^ Poids ^
+| A     | 80     | 8     |
+| B     | 32     | 2     |
+| C     | 20     | 5     |
+| D     | 126    | 14    |
+| E     | 5      | 1     |
+| F     | 18     | 6     |
+Quel objet doit-on prendre pour maximiser la valeur contenue dans le sac ?
+==== Solution récursive ====
+Supposons que j'écrive une fonction ''meilleur_sac(C, objets)'' où ''objets'' est le tableau précédent. Pour résumer, on pourra noter ''[ABCDEF]'' le tableau complet et ''[CDEF]'' le même tableau duquel on
+aurait enlevé les lignes A et B.
+Supposons que je calcule ''meilleur_sac(15, [ABCDEF])''. Voici le raisonnement récursif que l'on va tenir :
+  * Soit on ne prend pas A. Dans ce cas le meilleur sac possible est obtenu avec ''meilleur_sac(15, [BCDEF])''.
+  * Soit on prend A. Dans ce cas, on occupe 8 kg de la capacité du sac. Il reste 7 kg de capacité. On peut se demander comment occuper au mieux ces 7 kg en demandant ''meilleur_sac(7, [BCDEF])''.
+  * Les deux options précédentes nous donne 2 choix de sac. Il faut sélectionner le meilleur des deux.
+<WRAP box>Implémentez la fonction ''meilleur_sac'' et donnez la solution du problème.</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>