Skip to content

2 4 7 exercice

Exercices

La fractale de Koch

Le flocon de Koch ([https://fr.wikipedia.org/wiki/Flocon_de_Koch] est une courbe fractale simple.

On peut la créer à partir d'un segment de droite, en modifiant récursivement chaque segment de droite de la façon suivante :

  1. On divise le segment de droite en trois segments de longueurs égales.
  2. On construit un triangle équilatéral ayant pour base le segment médian de la première étape.
  3. On supprime le segment de droite qui était la base du triangle de la deuxième étape.

Flocon de Koch pour un niveau de récursivité 0 à 5

Écrivez un code qui dessine un flocon de Koch grâce à une fonction récursive koch(niveau, taille)niveaudonne le niveau de récursivité restant (0 = segment de droite simple) et taille, la taille du segment.

Les tours de Hanoï

Sur wikipedia nous pouvons lire :

Les tours de Hanoï (originellement, la tour d'Hanoï) sont un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de départ à une tour d' arrivée en passant par une tour intermédiaire, et ceci en un minimum de coups, tout en respectant les règles suivantes : - on ne peut déplacer plus d'un disque à la fois ; - on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que la configuration de départ consiste en \(n\) (\(n \geq 0\)) disques empilés sur la tour de départ, de taille de plus en plus petite (voir figure).

Exemple de configuration initiale avec 8 anneaux sur la tour 0

Algorithme : pour déplacer une tour de \(n\) disques de A vers C,

  • soit la tour n'a aucun disque (\(n==0\)) et alors il ne faut faire aucun déplacement, la solution est la chaîne vide,
  • soit (\(n>0\)), on effectue ces trois étapes :
  • déplacer la tour des n-1 premiers disques de A vers B (étape qui nécessite une résolution des tours avec \(n-1\) anneaux) ;
  • déplacer le plus grand disque de A vers C (un seul déplacement) ;
  • déplacer la tour des n-1 premiers disques de B vers C (à nouveau étape qui nécessite une résolution des tours avec \(n-1\) anneaux).

Nous vous demandons d'écrire une fonction récursive hanoi(dico, n, init, final).

La fonction reçoit quatre paramètres :

  • dico : qui contient toutes les solutions des tours de Hanoï déjà calculées (initialement dico est vide).
  • n (supérieur ou égal à 0) : la hauteur de la tour de Hanoï qu'il faut résoudre
  • init : le numéro (0, 1 ou 2) de la pile où se trouve initialement les anneaux
  • final: le numéro (0, 1 ou 2) de la pile où doivent se trouver les anneaux après les avoir déplacés en respectant les règles.

On peut supposer que init et final sont différents.

Elle doit renvoyer une chaîne de caractères donnant la séquence des mouvements à réaliser pour déplacer la tour de n anneaux de la pile init vers la pile final en respectant les règles imposées. On suppose les tours numérotées de 0 à 2 et les anneaux de 1 à n.

**Conseil : ** Inspirez-vous de l'algorithme décrit plus haut.

Par exemple, hanoi(dico, 3, 0, 2) doit renvoyer la chaîne de caractères :

move 1 from 0 to 2
move 2 from 0 to 1
move 1 from 2 to 1
move 3 from 0 to 2
move 1 from 1 to 0
move 2 from 1 to 2
move 1 from 0 to 2

Chaque fois qu'une nouvelle configuration a été calculée, sous forme de chaîne de caractères donnant une séquence de lignes, délimitées par le caractère '\n', la fonction hanoi la rajoute dans dico (clé : (n,init,final) et valeur la chaîne de caractères).

Si hanoi est appelée pour une configuration déjà dans dico, elle renvoie le résultat sans refaire les calculs.

La fonction d'Ackermann

Écrivez de manière récursive une fonction ackermann(m,n) qui implémente la fonction d'Ackermann \(A(m, n)\) définie comme suit :

\[ \begin{array}{llllcl} A(m,n) = \\ & n+1 & si & m = 0 \\ & A(m-1, 1) & si & m > 0 & et & n = 0\\ & A(m-1, A(m, n-1)) & si & m > 0 & et & n > 0.\\ \end{array} \]

Vérifiez que ackermann(3,6) donne 509. Que se passe-t-il pour de plus grandes valeurs ? Pourquoi ?

Retour sur trace ou retour en arrière / Backtracking

Notons que de nombreux problèmes peuvent être formalisés sous forme de jeu à un ou plusieurs joueurs et peuvent être programmés grâce à la technique algorithmique du ("retour en arrière")[https://fr.wikipedia.org/wiki/Retour_sur_trace] ("backtracking") qui recherche une solution en revenant en arrière quand le chemin pris (ou la proposition de solution envisagée) n'est pas bon. La récursivité permet "facilement" de programmer ces méthodes.