Le labyrinthe

Retour au menu principal
Aller directement au programme écrit en TURBO PASCAL 6.0

Le labyrinthe

Le problème est d'écrire un algorithme donnant le chemin menant à la sortie.

  1. Création de l'algorithme:Arbre et Feuilles


  2. Quand on va parcourir le labyrinthe, on va rencontrer plusieurs chemins possibles. Ce qui au fur et à mesure va constituer un arbre dont chaques feuilles constituera une voie d'exploration possible. Une voie d'exploration sera terminée lorsque:

    Dans ce cas le programme s'arrêtera et on visualisera à l'aide des informations contenues dans la feuille le chemin qui mène à la sortie.

  3. Modélisation d'un arbre de possibilités par une pile

  4. Les chiffres à l'intérieur du labyrinthe représentent le nombre d'itérations de l'algorithme. Jusqu'à l'itération 10, l'arbre n'a qu'une feuille.A partir de 10 on a deux possibilités C4 ou C6. A l'itération 12 on va donc créer deux feuilles reproduisant ces deux possibilités etc..










    Un arbre sera défini en programmation par une pile. Une pile est un type de tableau possédant une tête et une queue, dans lequel on peut stocker des objets. On ajoute un objet par la tête. Les autres objets dans la pile étant décalés d'un cran. Si on retire un objet celui-ci provient de la tête de la pile. Ici chaque objet de la pile sera une feuille. Chaque feuille possédera un chemin possible dans le labyrinthe, chemin qui aura pour origine l'entrée du labyrinthe.

  5. Algorithme


  6. Ajouter le point de départ (A2) à la pile source. A la n ème itérations on a N feuilles qui vont elle mêmes générer N+K feuilles à la n+1 ème itérations. D'un coté nous devons stocker les N feuilles dans une pile source, retirer la feuille du dessus de la pile, voire les feuilles générées par cette même feuille et enfin stocker les feuilles créer dans une nouvelle pile (pile objet) et reproduire le processus jusqu'à ce qu'il ne reste plus de feuille dans la pile source. Alors la pile objet devient la pile source.


  7. Programmes à télécharger

    Nom des fichiers
    Description des fichiers à télechargertypeType
    Programme en turbo pascal qui trouve la solution du labyrinthe laby.txt texte
    Fichier contenant le labyrinthe à interpréter lab.txt texte
    fichier exécutable pour PC
    qui trouve la solution du labyrinthe
    laby.exe exécutable pour PC

    Fichier contenant un fichier texte décrivant le labyrinthe à résoudre. Ce fichier doit se trouver impérativement sur votre disque dur lors de l'exécution du programme pascal.


    Pour plus d'information :écrivez-moi.