Pages - Menu

▼

Pages

▼

Exercices d'algorithme : Piles et Files d'attente

Exercice 1 :

Réimplanter la fonction fibr ci-dessous en utilisant  une pile pour remplacer les appels récursifs. 

                 long fibr(int n) {
                   assert((n>0) && (n<47) // les données dans cet intervalle sinon erreur
                   if ( (n = = 1) || (n = =2) return 1;
                   else return fibr(n-1) + fibr(n-2);
                 } // fin de la fonction

Exercice 2 : 
 


Soient Q et P une file et une pile non vides, respectivement. En utilisant seulement une seule variable et les opérations de la classe PILE ET FILE, écrire un algorithme  qui renverse l’ordre des éléments de Q. 

 Exercice 3 : 



Un problème fréquent d’un compilateur et des traitements de textes est de déterminer  si les parenthèses d’une  chaîne de caractères sont balancées et proprement incluses l’une dans l’une.  Par exemple, la chaîne ((( ) ) ( ) ) ( ) est bien balancée et proprement écrite. Mais les chaînes  )( )(  ou ( ) ) ne le sont pas. 
 
  1. écrire un algorithme qui retourne TRUE si une chaîne de caractères est proprement écrite et bien balancée, et FALSE sinon. Utiliser pour cela une pile. 
  2. Écrire un algorithme qui retourne la position de la première parenthèse qui déroge à cette règle si la chaîne n’est pas bien écrite et bien balancée.  Utiliser une PILE pour résoudre ce problème.

3 commentaires:

  1. Unknown23 décembre 2019 à 05:03

    #include
    #include
    #include
    #include

    const max=3;
    typedef struct pile{
    int sommet;
    char t[];
    }pile;


    void creer_pvide( pile p){
    p.sommet=0;
    }

    bool est_vide ( pile p){
    if(p.sommet==0)
    return true;
    return false;
    }

    bool est_plein ( pile p){
    if(p.sommet==max)
    return true;
    return false;
    }

    void empiler(char x,struct pile *p){
    if (est_plein(*p))
    printf("la pile est plein");
    else{
    (*p).sommet++;
    (*p).t[(*p).sommet]=x;
    }
    }

    void depiler( pile *p){
    if(est_vide(*p))
    printf("error !! pile est vide");
    else
    (*p).sommet--;
    }

    int psommet( pile p){
    return p.t[p.sommet];
    }

    int taille( pile p){
    return p.sommet;
    }







    /*
    def bien_parenthese(txt):
    bp = True
    p = construit_pile()
    i = 0
    while bp and i < len(txt):
    if txt[i] == "(" or txt[i] == "[":
    empile(p, txt[i])
    elif txt[i] == ")":
    if sommet(p) != "(":
    bp = False
    else:
    depile(p)
    elif txt[i] == "]":
    if sommet(p) != "[":
    bp = False
    else:
    depile(p)
    i = i+1
    if not pile_vide(p):
    bp = False
    return bp

    */

    char caract_over(char x){
    if ((x=='(')||(x=='[')||(x=='{'))
    return x;
    }


    bool est_balance(char tab[]){
    pile *p;
    bool bo=true;
    creer_pvide(*p);
    int i=0;

    while(i<strlen(tab) && bo==true){

    if(caract(tab[i]))
    empiler(tab[i],&(*p));

    else {

    switch(tab[i]){
    case ')': if (psommet(*p)!='(')
    bo=false;
    else
    depiler(&(*p));
    case ']': if (psommet(*p)!='[')
    bo=false;
    else
    depiler(&(*p));

    case '}': if (psommet(*p)!='{')
    bo=false;
    else
    depiler(&(*p));
    }
    }
    i++;
    }
    return bo;

    }






    int main(int argc, char *argv[]) {
    char t[20];

    printf("donner l'expression :");
    scanf("%s",t);
    est_balance(t);
    scanf("%s",t);
    return 0;
    }

    RépondreSupprimer
  2. Unknown15 avril 2020 à 09:38

    c'est très compréhensif vos exercices...
    Merci bien les gars

    RépondreSupprimer
  3. sara6 février 2022 à 09:24

    #include
    #include
    #include
    #include
    ////////////////declaraton de type maillon ////////////////
    typedef struct tmaillon{
    char info ; struct tmaillon *suiv ;} maillon ;
    ///////////////////////////////////
    ///////////////////
    typedef maillon *pile ; //////pour dire de pile eest un struct tmaillon//////////////

    ///////////creation d'une pile vide///////////////
    void initpile(pile *p ){ *p = NULL ;}
    /////fonction qui verifier si la pile est vide ou nn //////////////
    bool pilevide(pile p){return (p == NULL);}
    void depile(pile *p , char *x){
    pile sauv ;
    if (p ==NULL) {printf("la pile est vide ");}
    else { *x =(*p)->info ;sauv = *p ; (*p)=(*p)->suiv ; free(sauv);}}
    ///////////////////////////////////////////////////////////////////////////
    void empile(pile *p , char x ) {
    pile nouv ;
    nouv = malloc(sizeof(maillon));
    nouv->info = x ;
    nouv->suiv = *p ;
    *p = nouv ;}
    ///////////////////////////////
    bool parenthes(char ch[]){
    pile p ; int i ; int n=strlen(ch) ; char x ; bool stop ;
    i =0 ;
    initpile(&p);
    stop = false;
    while(i<=n && !stop){
    if(ch[i]=='('){empile(&p,ch[i]);}
    else { if(ch[i]==')') {
    if(pilevide(p)){stop = true ;}
    else {depile(&p,&x);}}} i++ ; }
    if(!stop && pilevide(p)) {return true;}
    else { return false;}}
    ////////////////////////////////////
    main() {
    char ch[100] ;
    printf("donne la chaine : ");
    gets(ch);
    ////scanf("%s",ch); si je declare une chaine et j fait un espace danc vas sortir de la licture
    if(parenthes(ch)){printf("la chaine est bien balence");}
    else{printf("la chaine n'est pas bien balence ");}
    }

    RépondreSupprimer