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.