GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:recursivite:exemples

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:recursivite:exemples [2021/11/29 18:12] – goupillwikinsi:terminales:recursivite:exemples [2023/03/17 13:41] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. 193.51.53.161
Ligne 31: Ligne 31:
 </code> </code>
  
-[[https://docs.python.org/fr/3/library/turtle.html|Documentation du module turtle]].+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 box>Écrivez la fonction ''S(n,c)'' faisant le tracé du triangle de Sierpinski. Faites l'essai par exemple avec ''S(5,200)''.</WRAP>
Ligne 39: Ligne 39:
 ===== Tours de Hanoï ===== ===== Tours de Hanoï =====
  
-Dans [[nsi:tds:hanoi|ce TD]], on vous décrit le problème des 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. Un solution très simple de ce problème passe par une fonction récursive.
Ligne 60: Ligne 60:
 ==== Rappel ==== ==== 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,   * On dispose d'un sac de capacité C,
   * d'un assortiment d'objets ayant tous un poids et une valeur.   * d'un assortiment d'objets ayant tous un poids et une valeur.
Ligne 79: Ligne 79:
 ==== Solution récursive ==== ==== 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 +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. aurait enlevé les lignes A et B.
  
Ligne 89: Ligne 89:
 <WRAP box>Implémentez la fonction ''meilleur_sac'' et donnez la solution du problème.</WRAP> <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>
nsi/terminales/recursivite/exemples.1638205974.txt.gz · Dernière modification : de goupillwiki