Bloc-notes
Math Lycée
Info Lycée
Menu contextuel
Récursivité (Fiche élève)
[VHK371]
\hfill Pour comprendre la récursivité, il faut d'abord comprendre la récursivité.

Partie A — Les tours de Hanoï

Le jeu des tours de Hanoï comprend trois axes. L'axe de gauche contient un empilement de disques de diamètres décroissants. Le but du jeu est de déplacer l'empilement sur l'axe de droite en respectant les règles suivantes :
  • les disques sont déplacés un par un ;
  • un disque ne doit jamais être posé sur un disque plus petit.

Proposez une solution algorithmique au problème pour l'empilement de $n$ disques.

Partie B — Le tri fusion

Les méthodes de tri par sélection, par insertion ou à bulles trouvent leur limite lorsque la taille du tableau est grande. Le tri fusion est une méthode qui s'avère beaucoup plus efficace pour des grands tableaux. Elle repose sur un principe très général de l'algorithmique qui se nomme diviser pour régner. Le principe consiste à remplacer le problème par deux problèmes similaires mais plus petits. Il est alors fréquent que la résolution des deux problèmes plus petits prennent beaucoup moins de temps à résoudre que le seul gros problème de départ. Bien sûr il faudra aussi un peu de temps pour fabriquer la solution du gros problème à partir des solutions des deux petits problèmes.

1.
Nous allons illustrer la méthode en triant par fusion un jeu de 32 cartes :
  • L'élève n° 1 partage le jeu de cartes en deux tas égaux et donne l'un des tas à l'élève n° 2 et l'autre à l'élève n° 3.
  • Les élèves n° 2 et n° 3 font de même. Le premier donne ses tas aux élèves n° 4 et n° 5, le second aux élèves n° 6 et n° 7.
  • Les élèves qui viennent de recevoir les cartes font encore de même et donnent leurs tas (4 cartes) aux élèves restants (n° 8 à n°  15).
  • Les élèves qui viennent de recevoir 4 cartes trient maintenant ces cartes par ordre décroissant (as au dessus du roi, etc). En cas de hauteur identique appliquez la rèlge pique au-dessus de cœur, au-dessus de carreau, au-dessus de trèfle).

    Chacun rend ensuite son tas à l'élève qui le lui a donné.
  • Les élèves qui viennent de récupérer leur deux tas doivent maintenant rassembler ces deux tas en un seul bien ordonné. C'est l'étape de fusion des deux tas.

    Chacun rend ensuite son tas à l'élève qui le lui a donné.
  • Les élèves n° 2 et n° 3 fusionnent à leur tour leurs deux tas et rendent le tas ordonné à l'élève n°  1.
  • L'élève n° 1 termine le travail en fusionnant les deux tas.
Organisez-vous entre vous pour expérimenter la méthode décrite ci-dessus. Répétez plusieurs fois l'expérience afin de bien comprendre le principe.
2.
Pour mettre en œuvre le tri fusion dans un programme l'une des tâches à réaliser est de fusionner deux tableaux ordonnés en un seul tableau ordonné.
(a)
Proposez une fonction fusion (écrite en pseudo-code) qui à partir de deux tableaux ordonnés, l'un nommé gauche de taille $G$ et l'autre nommé droite de taille $D$ crée un nouveau tableau ordonné de taille $G+D$.
(b)
Proposez une fonction récursive tri-fusion (écrite en pseudo-code) qui trie un tableau table passé en argument. Cette fonction utilisera en particulier la fonction fusion ci-dessus.
(c)
Codez et mettez au point votre programme.
(d)
Comparez les temps d'exécution avec ceux des tris par sélection ou par insertion.

Partie C — Exploration du système de fichiers

Le système de fichiers d'un ordinateur est organisé sous la forme d'une arborescence de dossiers.

Un dossier est un fichier qui contient des noms de fichiers ainsi que les informations nécessaires pour localiser physiquement sur le disque dur le contenu de ces fichiers. Certains de ces dossiers peuvent eux-mêmes être des dossiers, autrement dit la structure est récursive. Les algorithmes récursifs sont donc tout à fait naturels pour explorer ou manipuler un système de fichiers.

Le programme ci-dessous illustre deux fonctions de la bibliothèque os que vous alez devoir utiliser. La première test si un fichier est un dossier. La seconde renvoie la liste des fichiers contenus dans un dossier.

import os
if os.path.isdir('/var/lib'):
    for name in os.listdir('/var/lib'):
        print name
(a)
Écrivez un programme récursif qui affiche le nom de tous les dossiers contenus dans un dossier. Exemple de sortie :
            /users/Denis/dicho/www/guppy/photo
            /users/Denis/dicho/www/guppy/skin
            /users/Denis/dicho/www/guppy/skin/skn_island
            /users/Denis/dicho/www/guppy/skin/skn_island/img
            /users/Denis/dicho/www/guppy/skin/skn_web20
            /users/Denis/dicho/www/guppy/skin/skn_web20/img
            /users/Denis/dicho/www/guppy/skin/no_skin
            /users/Denis/dicho/www/guppy/file
        
(b)
Améliorez votre programme en ajoutant des indentations à la sortie pour mettre en évidence la structure arborescente :
            /users/Denis/dicho/www/guppy/photo
            /users/Denis/dicho/www/guppy/skin
                /users/Denis/dicho/www/guppy/skin/skn_island
                    /users/Denis/dicho/www/guppy/skin/skn_island/img
                /users/Denis/dicho/www/guppy/skin/skn_web20
                    /users/Denis/dicho/www/guppy/skin/skn_web20/img
                /users/Denis/dicho/www/guppy/skin/no_skin
            /users/Denis/dicho/www/guppy/file
        
(c)
Écrivez un programme qui recherche les fichiers qui ont été modifiés récemment.

Partie D — Coloriage

Téléchargez l'image smiley.jpeg. Le but de l'exercice est d'écrire un programme Python qui colorie en bleu la tête du smiley.

(a)
Proposez un algorithme capable de résoudre ce problème.
(b)
Programmez l'algorithme en Python et testez-le.

Partie E — Tapis de Sierpinski

La figure ci-dessous est appelée tapis de Sierpinski. C'est un exemple de figure fractale. Un tapis de Sierpinski est constitué par l'assemblage de huit tapis de taille trois fois plus petite.

Dessiner un tapis de Sierpinski, c'est très simple :
  • Si le tapis est très petit (inférieur à 5 pixels) on dessine un carré rouge (personne de verra la triche).
  • Si le tapis est grand, on dessine 8 tapis trois fois plus petits.
(a)
Rédigez l'algorithme en pseudo-code.
(b)
Programmez l'algorithme en Python et testez-le.



Denis Pinsard -- Mis à jour le vendredi 08 mars 2013

Infos site
Visites

 0 visiteurs

 1 visiteur en ligne

Calendrier
^ Haut ^