Fractale : triangle de Sierpinski
Une image qui a une apparence similaire quelle-que soit l'échelle à laquelle on l'observe est appelée une fractale (il y a d'autres types de fractales).
Un exemple simple de fractale est le triangle de Sierpinski, dont voici une représentation :
Une telle image peut être réalisée en quelques minutes avec n'importe-quel logiciel de dessin. On commence par former un triangle de trois pixels. On en fait ensuite trois copies que l'on utilise pour former un plus grand triangle, et on recommence l'opération avec ce nouveau triangle, et ainsi de suite, jusqu'à obtenir une figure de la taille souhaitée.
Voici une vue zoomée des trois premières étapes de l'opération :
Les dimensions de la figure étant multipliées par 2 à chaque nouvelle étape, le côté de la figure finale est une puissance de 2.
A vous d'afficher un triangle de Sierpinski de la taille demandée.
Votre programme doit impérativement être basé sur une fonction récursive, et non sur des boucles
Limites de temps et de mémoire (Python)
- Temps : 0,25 s sur une machine à 1 GHz.
- Mémoire : 1 000 ko.
Contraintes
- 1 <= N <= 64, où N est le côté de la figure.
Entrée
Un entier : la taille du côté de la figure. Ce sera toujours une puissance de 2.
Sortie
Le triangle de Sierpinski de la taille fournie en entrée.
Les pixels noirs doivent être affichés sous la forme de caractères '#', et les pixels blancs sous la forme d'espaces. N'affichez pas d'espaces à la fin des lignes, lorsqu'il n'y a plus de caractères '#' sur la ligne.
Exemple
entrée :
8
sortie :
######## # # # # ## ## # # #### # # ## #