Informatique T.D 2

RECURSIVITE

Marie-Pierre Béal et Laurent Moll

Exercice 1.— Le Jeu du baguenaudier On dispose d’une réglette contenant N cases numérotées de 1 à N. Sur chaque case est déposé un pion initialement. On désire enlever les N pions en respectant les règles suivantes :

• Il n’y a jamais qu’un pion au plus par case.

• On peut à tout moment poser (s’il n’y en a pas) ou enlever (s’il y en a un) un pion sur la case 1.

• On peut poser ou enlever un pion sur la case numérotée j avec 1 < j ≤ N s’il y a un pion sur la case j − 1 et aucun sur les cases précédentes.

On écrira deux procédures récursives Vider et Remplir, l’une permettant de vider les n premières cases lorsque celles-ci sont pleines, l’autre permettant de remplir les n premières cases lorsque celles-ci sont vides. L’entier n sera passé en paramètre. On peut faire une visualisation graphique des mouvements de pions.

Exercice 2.— Triangle de Sierpinski. On définit une suite d’images par récurrence de la façon suivante : une image élémentaire, d’ordre 1, est un carré noir de taille d. Une image d’ordre n est obtenue en découpant un carré de taille k, où k est une puissance de 2, en quatre carrés notés GaucheHaut, GaucheBas, DroiteHaut et DroiteBas; DroiteBas est un carré blanc et les trois autres sont des images d’ordre n − 1 et de taille k div 2. On calculera une image d’ordre 9 et de taille 256.

Exercice 3.— Flocon de Koch La transformation de Koch d’ordre 1 d’un segment consiste à transformer un segment P T en quatre segments P Q, QR, RS et ST, Q et S étant sur le segment P T et le partageant en trois morceaux d’égale longueur. Le triangle QRS est équilatéral et est situé du côté gauche par rapport au segment orienté P T. Les tranformations de Koch d’ordre supérieur sont obtenues en appliquant la transformation à nouveau sur les quatre segments obtenus. Ecrire une procédure permettant d’obtenir la transformation de Koch d’un segment d’ordre tel que les segments tracés soient de taille suffisamment petite. Enfin le flocon de Koch est obtenu en appliquant cette procédure aux trois côtés d’un triangle équilatéral.