Sujet : Contexte : Date : Auteur :

Le dragon, animal fractal TP d'informatique MP 1999 Cédric BRAY

Comment construire la bête?

	Prenez une feuile de papier. Pliez-la en deux. Renouvelez le pliage exactement de la même façon sur le morceau ainsi obtenu. Dépliez en considérant le profil de la feuille et de sorte que chaque pli fasse un angle droit. On observe, à une rotation près, le profil de la figure 1. Repliez la feuille comme précédemment, puis ajoutez un pli. Dépliez de la même façon qu'auparavant. On obtient le profil de la figure 2.
Fig 1
Fig 2

Et alors?

Pour voir le dragon apparaître sur le profil de votre feuille, il faudrait la plier un très grand nombre de fois, puis la déplier en formant des angles droits à chaque pli... Plutôt fastidieux.
Heureusement l'Informatique est là pour ce genre de procédure ; encore faut-il faire expliquer à l'ordinateur, avec ses mots à lui, notre séance de pliage.

Mise en oeuvre de la procédure

Considérons le profil de notre feuille de papier : comme chaque segment forme un angle droit avec ses adjacents, la seule information utile semble être la direction prise par le tracé d'un segment à l'autre, à savoir gauche ou droite.
On fera comme si on dirigeait à l'écran un curseur avançant pas à pas, comme en Logo.

La complexité du tracé augmente fortement avec le nombre de pliages. Considérons, à partir de la figure 2, le dernier pli effectué : à cause du dépliage, il se trouve au coin positionné exactement au milieu du tracé ( entendons : au milieu du parcours de notre curseur ). Ce pli fait que les 2 demi-feuilles qu'il délimite s'emboîtent parfaitement. Pour notre curseur, cela se traduit ainsi : la séquence des directions prises après ce pli est l'antisymétrique de la séquence des directions prises sur la première moitié du trajet.

La remarque précédente est valable pour tous les plis! On aboutit donc à une méthode récursive permettant la construction de la séquence des directions prises par le tracé.

Soit n le nombre de pliages, S(n) la séquence recherchée pour n pliages.
On notera D, G pour Droite et Gauche. Ainsi S(n) = { ..., D, ..., G,...}.
On notera AS(n) l'antisymétrique de S(n) : si S(n) = { D, G, G}, alors AS(n) = { D, D, G}.

• S(0) = { G } ( fixé arbitrairement ).
• S(n) = { S(n-1), G, AS(n-1) }

Une fois la séquence obtenue, il ne reste plus qu'à la faire lire par notre curseur.

Déplacement du curseur

Associons respectivement aux orientations possibles Gauche, Haut, Droite, Bas les valeurs 0, 1, 2, 3.
De même associons à D et G de la séquence les valeurs 1 et -1.
Initialisons un compteur C à 0. La lecture de la séquence consistera à ajouter à C les valeurs correspondant aux D et G successifs et à en déduire à modulo 4 l'orientation à suivre.