:: Enseignements :: ESIPE :: E3INFO :: 2007-2008 :: Algorithmique - Slot 2 ::

Recursivité

Exercice 1 - Remplir une image

On représente une image par un tableau de pixels. Chaque valeur représente une couleur différente. Les pixels voisins à un pixel donné sont les les huit qui sont autour. Une zone de couleur est un ensemble connexe de pixels de la même couleur : on peut aller d'un pixel à un autre en passant de voisin en voisin.

On veut implémenter la fonction pot de peinture qui change la couleur d'une zone entière. Par exemple avec l'image

      int image[10][10] = { 
      {1, 1, 1, 1, 1, 1, 2, 1, 1, 1},
      {1, 1, 1, 2, 2, 3, 2, 1, 2, 1},
      {1, 1, 1, 2, 2, 3, 2, 1, 2, 1},
      {1, 1, 1, 5, 2, 3, 2, 1, 5, 1},
      {1, 1, 1, 2, 2, 2, 2, 1, 2, 1},
      {1, 1, 1, 1, 5, 3, 3, 1, 2, 1},
      {1, 1, 1, 2, 2, 3, 2, 1, 2, 1},
      {1, 1, 3, 2, 1, 2, 1, 3, 2, 1},
      {1, 1, 2, 1, 2, 1, 2, 2, 3, 3},
      {1, 1, 1, 2, 2, 3, 2, 1, 2, 1}
      };

si on applique la fonction en (1,3) avec 7 comme nouvelle couleur, on devrait obtenir

      { 
      {1, 1, 1, 1, 1, 1, 7, 1, 1, 1},
      {1, 1, 1, 7, 7, 3, 7, 1, 2, 1},
      {1, 1, 1, 7, 7, 3, 7, 1, 2, 1},
      {1, 1, 1, 5, 7, 3, 7, 1, 5, 1},
      {1, 1, 1, 7, 7, 7, 7, 1, 2, 1},
      {1, 1, 1, 1, 5, 3, 3, 1, 2, 1},
      {1, 1, 1, 2, 2, 3, 2, 1, 2, 1},
      {1, 1, 3, 2, 1, 2, 1, 3, 2, 1},
      {1, 1, 2, 1, 2, 1, 2, 2, 3, 3},
      {1, 1, 1, 2, 2, 3, 2, 1, 2, 1}
      };

Exercice 2 - Encore des listes

Ecrire une fonction récursive qui renverse une liste chaînée en O(n).
Ecrire des fonctions récursives qui renversent la sous-liste des emplacements d'indice pairs. Par exemple, 1 2 3 4 5 6 devient 1 6 3 4 5 2.

Exercice 3 - Calculette

On veut implémenter une calculette en notation polonaise (préfixe) : au lieu d'écrire 2*(9-4), on écrit *2-94.

On suppose qu'on a droit aux fonctions usuelles et aux nombres de 0 à 9. Ecrire une fonction qui lit dans un fichier une expression en notation polonaise et calcule le résultat.
Comment étendre le système pour des nombres quelconques?
Comment marche la notation postfixe, dans laquelle on écrirait 294-*?