Exemples de récurrences

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é

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 :

from turtle import *
speed(100)
pensize(1)    # taille du tracé
setheading(0) # orientation vers l'est

# votre programme ici


# fin du programme
exitonclick()

Quelques commandes dans ce TD. Vous pouvez aussi utiliser la documentation du module turtle.

Dans 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,

Dans cet exercice nous avons vu des exemples de fonctions récursives permettant de calculer la hauteur ou la taille d'un arbre.

Ce problème a été vu en première dans le cadre de l'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 :

Quel objet doit-on prendre pour maximiser la valeur contenue dans le sac ?

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.

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