ezano Admin
Messages : 59 Date d'inscription : 26/11/2009 Age : 34 Localisation : Lannion
| Sujet: exo concret sur la pile Dim 21 Fév - 21:48 | |
| Salut, Je passe pour vous demander ce que vous pensez des piles/files, au début j'étais réticent, mais en me renseignant sur le sujet, je me rend compte que sa sert souvent et que les programmes que l'on peut faire avec peuvent tenir la route contrairement à ce qu'on nous donne en TD/TP.
Par exemple, je vous propose de coder un programme d'intelligence artificielle qui doit faire sortir un rat (dédicace à guillaumeL) d'un labyrinthe. On pourrais utiliser un tableau, mais la pile est plus pratique dans ce genre de cas, pour mémoriser les déplacement du rat et ainsi si il arrive dans un cul de sac, dépiler etc Ca sert aussi beaucoup dans les algorithme de backtraking, ou d'nalyse syntaxique ou encore rien qu'un simple ctrl+z utilise la pile.
Idem la file est très utilisé.
En entrainement concret à la pile, je propose de coder ce rat qui sort de sont labyrinthe. Pas besoins de générer un labyrinthe aléatoirement, mais faites le dans un fichier texte et dans le code mettez le dans un tableau à 2 dimensions de manière dynamique au cas ou vous auriez envie de tester un autre labyrinthe un jour. Par exemple, les murs seront des X, le rat un R et la sortis un trou sur l'un des cotés du labyrinthe. les exo vu en TP/TD sont tellement bidon que s'entrainer un peu sur du concret fera de mal à personne ^^
Je vous quitte sur une citation de ce bon vieux Lietard: "Profitez de vos vacances pour travailler au moins 3h par jours" | |
|
Gautier
Messages : 65 Date d'inscription : 27/11/2009 Localisation : Lannion
| Sujet: Re: exo concret sur la pile Dim 21 Fév - 22:08 | |
| Si j'étais jeté je le ferai.. | |
|
ezano Admin
Messages : 59 Date d'inscription : 26/11/2009 Age : 34 Localisation : Lannion
| Sujet: Re: exo concret sur la pile Lun 22 Fév - 0:29 | |
| *Balance gautier par la fenêtre*
C'est bon tu peux le faire.
Mais tu parle de quoi au fait du laboRat ou des 3h par jours ^^ Parceque personne le fait les 3h par jours. | |
|
Gautier
Messages : 65 Date d'inscription : 27/11/2009 Localisation : Lannion
| Sujet: Re: exo concret sur la pile Lun 22 Fév - 1:57 | |
| | |
|
ezano Admin
Messages : 59 Date d'inscription : 26/11/2009 Age : 34 Localisation : Lannion
| Sujet: Re: exo concret sur la pile Lun 22 Fév - 2:30 | |
| | |
|
Flic-Flac
Messages : 20 Date d'inscription : 26/12/2009
| Sujet: Re: exo concret sur la pile Lun 22 Fév - 11:15 | |
| Une pile qui empile toutes les idées de Fabien et après qui dépile jusqu'à une bonne idée, ensuite on arrête.
Tiens, elle pointe sur NULL :] | |
|
Kage
Messages : 30 Date d'inscription : 26/11/2009 Age : 32 Localisation : Lesneven
| Sujet: Re: exo concret sur la pile Jeu 4 Mar - 10:47 | |
| Mais vous êtes méchants, c'est une super idée moi j'trouve. Je vais le faire ce rat, et même que je vais le faire en interface graphique pour faire honte à Fabien et ces pauvres X et R | |
|
ezano Admin
Messages : 59 Date d'inscription : 26/11/2009 Age : 34 Localisation : Lannion
| Sujet: Re: exo concret sur la pile Jeu 4 Mar - 16:23 | |
| Le but c'est d'utiliser la pile, interface graphique ou pas on s'en fout un peu à la base ^^ edit: Tu voulais voir mon algorithme, le voila. L'algo en lui même est dans la fonction main(). - Code:
-
#include <stdio.h> #include <stdlib.h> #include <time.h>
/* *Constante d'environnement du labyrinthe */ #define RAT 'R' #define MUR 'X' #define SORTIS 'S' #define VIDE ' ' #define MARQUE '.'
#define MAX 3
/* *Structure qui servira à stocker les coordonner du rat et de la prochaine case libre à enprunter */ typedef struct Coordonnee Coordonnee; struct Coordonnee { int x; int y; };
/* *Structure pile, qui servira à garder en mémoire les intersections à plusieurs croisement. */ typedef struct elem *Pile; struct elem { Coordonnee coord; Pile next; };
void afficheTab(int longueur, int largeur, char **tab); void calculeTaille(int *longueur, int *largeur, FILE *fp); void construiTableau(FILE *fp, char **tab, Coordonnee *coordonneeRat); int nbIntersection(char **tab, Coordonnee *coordonneeRat, Coordonnee *coordonneeLibre); int avancerCase(char **tab, Coordonnee *coordonneeRat, Coordonnee *coordonneeLibre); void reculer(char **tab, Coordonnee *coordonneeRat, Coordonnee *coordonneeRetour); void efface(int longueur); Pile empiler(Pile p, Coordonnee coordonneeRat); Pile depile(Pile p); int estVide(Pile p);
/* *Fonction principale */ int main(int argc, char **argv) { int i, longueur = 0, largeur = 0, nbCroisement, sortis = 0; char **tab; Coordonnee coordonneeRat, coordonneeLibre; Pile p = NULL; FILE *fp = NULL;
srand(time(NULL));
if (argc != 2) { fprintf(stderr, "usage: %s fichier\n", argv[0]); exit(EXIT_FAILURE); }
if((fp = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "Erreur dans l'ouverture du fichier\n"); exit(EXIT_FAILURE); }
calculeTaille(&longueur, &largeur, fp);
/*allocation dynamique d'un tableau à 2 dimensions en fonction de la longueur et la largeur définit au dessus*/
tab = (char**)malloc(longueur * sizeof(char*)); for(i = 0; i < longueur; i++) tab[i] = (char*)malloc(largeur * sizeof(char));
rewind(fp);//retour au début du fichier
construiTableau(fp, tab, &coordonneeRat); afficheTab(longueur, largeur, tab);
while(!sortis)//tant qu'on est pas sortis { if((nbCroisement = nbIntersection(tab, &coordonneeRat, &coordonneeLibre)) == 0)//Si le nombre d'intersection vaut 0... { if(estVide(p))//et que la pile est vide la labyrinthe est impossible { printf("Labyrinthe impossible\n"); break; } while((nbCroisement = nbIntersection(tab, &coordonneeRat, &coordonneeLibre)) == 0)//Sinon tant que le nombre d'intersection vaut 0, on recule jusqu'au précédent croisement { reculer(tab, &coordonneeRat, &(p->coord)); p = depile(p); efface(longueur); afficheTab(longueur, largeur, tab); } } else//Si le nombre d'intersection est > 0 { p = empiler(p, coordonneeRat);//On empile les coordonnee actuel du rat sortis = avancerCase(tab, &coordonneeRat, &coordonneeLibre);//on marque la case courante et on avance d'une case efface(longueur); afficheTab(longueur, largeur, tab); } }
if(sortis) printf("Le rat est sortis du labyrinthe\n");
//On libère la mémoire fclose(fp);
for (i = 0; i < longueur; i++) free(tab[i]); free(tab);
while (!estVide(p)) p = depile(p);
return EXIT_SUCCESS; }
/* *Fonction de test qui renvoi 1 si la pile est vide 0 sinon. */ int estVide(Pile p) { return !p; }
/* *Fonction qui empile les coordonnées d'un croisement ou est passé le rat */ Pile empiler(Pile p, Coordonnee coordonneeRat) { Pile croisement = malloc(sizeof(struct elem));
croisement->coord = coordonneeRat; croisement->next = p;
return croisement; }
Pile depile(Pile p) { if(p != NULL) { Pile croisement = p->next; free(p); return croisement; } else return NULL; }
/* *Fonction qui calcul le nombre de caractère du fichier en longueur et en largeur */ void calculeTaille(int *longueur, int *largeur, FILE *fp) { char car; int count = 0; *largeur = 0; while (fscanf(fp, "%c", &car) != EOF) { count++; if (car == '\n') { (*longueur)++; count = 0; } else if (count > *largeur) *largeur = count; } }
/* *Fonction qui place tous le fichier dans un tableau à 2 dimensions et détermine les coordonnées du rat */ void construiTableau(FILE *fp, char **tab, Coordonnee *coordonneeRat) { char car; int i = 0, j = 0;
while (fscanf(fp, "%c", &car) != EOF) { if(car == '\n') { i++; j = 0; continue; } tab[i][j] = car; if(car == RAT) { coordonneeRat->x = j; coordonneeRat->y = i; } j++; } }
/* *Fonction d'affichage du tableau */ void afficheTab(int longueur, int largeur, char **tab) { int i = 0, j = 0;
for(i = 0; i < longueur; i++) { for(j = 0; j < largeur; j++) printf("%c", tab[i][j]); printf("\n"); } }
/* *Fonction qui determine le nombre de chemin autour du rat */ int nbIntersection(char **tab, Coordonnee *coordonneeRat, Coordonnee *coordonneeLibre) { int i, j, compteur = 0, var; Coordonnee tabChoix[MAX];
j = coordonneeRat->x;//Je place les coordonnée dans i et j pour une question de visibilité après i = coordonneeRat->y;
if(tab[i-1][j] == VIDE || tab[i-1][j] == SORTIS) { coordonneeLibre->x = j; coordonneeLibre->y = i-1; tabChoix[compteur] = *coordonneeLibre;//On place les coordonnées dans un tableau compteur++; } if(tab[i][j-1] == VIDE || tab[i][j-1] == SORTIS) { coordonneeLibre->x = j-1; coordonneeLibre->y = i; tabChoix[compteur] = *coordonneeLibre; compteur++; } if(tab[i][j+1] == VIDE || tab[i][j+1] == SORTIS) { coordonneeLibre->x = j+1; coordonneeLibre->y = i; tabChoix[compteur] = *coordonneeLibre; compteur++; } if(tab[i+1][j] == VIDE || tab[i+1][j] == SORTIS) { coordonneeLibre->x = j; coordonneeLibre->y = i+1; tabChoix[compteur] = *coordonneeLibre; compteur++; } if(compteur != 0)//Si le compteur est différent de 0, no choisis au hasard quel sera le chemin que prendra le rat { var = rand() % compteur; coordonneeLibre->x = tabChoix[var].x; coordonneeLibre->y = tabChoix[var].y; }
return compteur; }
/* *Fonction qui marque la case courante d'un point et qui fait avancer le rat d'une case */ int avancerCase(char **tab, Coordonnee *coordonneeRat, Coordonnee *coordonneeLibre) { int sortis = 0; if(tab[coordonneeLibre->y][coordonneeLibre->x] == SORTIS) sortis++;
tab[coordonneeRat->y][coordonneeRat->x] = MARQUE; tab[coordonneeLibre->y][coordonneeLibre->x] = RAT; *coordonneeRat = *coordonneeLibre; return sortis; }
/* *Fonction qui fais reculer le rat d'une case quand il est dans un cul de sac */ void reculer(char **tab, Coordonnee *coordonneeRat, Coordonnee *coordonneeRetour) { tab[coordonneeRat->y][coordonneeRat->x] = MARQUE; tab[coordonneeRetour->y][coordonneeRetour->x] = RAT; *coordonneeRat = *coordonneeRetour; }
/* *Pour pas avoir voir défiler les labyrinthe et que sa reste portable. */ void efface(int longueur) { int i;
for(i = 0; i < longueur; i++) printf("\n"); } Pour le fichier texte, creer le toi même comme tu veux en respectant les variable que j'ai posé dans le code ou en les modifiants à ta guise. Edit 2: Le code est mal indenté, mais ça ne vient pas de moi mais du site qui modifie l'indentation tout seul. | |
|
Kage
Messages : 30 Date d'inscription : 26/11/2009 Age : 32 Localisation : Lesneven
| Sujet: Re: exo concret sur la pile Ven 5 Mar - 11:30 | |
| Ok ok, mais je comptais pas reprendre ton compte, je vais le faire à ma façon, j'aime pas la pile. Sinon, je comprends pas trop l'intérêt du char** ? | |
|
ezano Admin
Messages : 59 Date d'inscription : 26/11/2009 Age : 34 Localisation : Lannion
| Sujet: Re: exo concret sur la pile Ven 5 Mar - 23:12 | |
| Ben tu voulais mon algo alors je te donne le code, après t'en fais ce que tu veux. Le char ** est nécesssaire pour l'allocation dynamique d'un tableau à 2 dimensions.
Sinon je bosse sur un générateur de labyrinthe aléatoire, comme ça, plus besoin de se faire chier avec un fichier texte. Les algo sur la génération de labyrinthe sint assez interessant. | |
|
Kage
Messages : 30 Date d'inscription : 26/11/2009 Age : 32 Localisation : Lesneven
| Sujet: Re: exo concret sur la pile Ven 5 Mar - 23:22 | |
| Ouai carrément, faut juste faire gaffe à rendre le machin possible, sinon, pauvre petit rat . | |
|
Contenu sponsorisé
| Sujet: Re: exo concret sur la pile | |
| |
|