rolex replica rolex replica fake rolex fake watches replica watches fake rolex replica rolex fake rolex fake watches replica watches

Files et Piles


  1. Les primitives d’une pile: LIFO
  2. Les primitives d’une file d’attente : FIFO
  3. Renverser une file d’attente
  4. Copier une pile
  5. Copier une file d’attente
  6. Permutation circulaire d’une pile
  7. Permutation circulaire d’une file d’attente
  8. Expression bien parenthésée
  9. Notation polonaise inversé ou post-fixée

Exercice 1: Les primitives d’une pile: LIFO

Les primitives d’une piles (LIFO Last In/First Out», c’est-à-dire «dernier arrivé, premier servi») ou les opérations caractéristiques d’une pile sont  :

  • creer_pile( ): qui permet de créer et retourner une pile
  • pilevide( P ) : Retourne True si la pile est vide et False sinon
  • empiler( P , e ) : Ajouter l’élément e au somme de la pile P
  • depiler ( P ) : supprimer l’élément du sommet
  • sommet( P ) : Retourne l’élément du sommet de la pile
  • taille( P ) : Retourne la taille de la pile P

Implémentation des ces primitives en langage Python seront réalisées en utilisant les listes et on choisit la fin de la liste comme sommet de la pile.


Exercice 2: Les primitives d’une file d’attente : FIFO

Les primitives d’une file d’attente (FIFO: First In/First Out, c’est-à-dire «premier arrivé, premier servi») ou les opérations caractéristiques d’une file d’attente sont  :

  • creer_file( ): qui permet de créer et retourner une file
  • filevide( F ) : Retourne True si la file est vide et False sinon
  • enfiler( F , e ) : “appelé aussi Enqueue” permet d’ajouter l’élément e à la fin de la file F
  • defiler ( F ) : “appelé aussi Dequeue permet de renvoie le premier élément de la file et le retire
  • tete( F ) : Retourne le premier élément de la file F.
  • taille( P ) : Retourne la taille de la file P

Implémentation des ces primitives en langage Python seront réalisées en utilisant les listes et on choisi le début de la liste comme tête de la file.



Exercice 3: Renverser une file d’attente

Fonction Python renverser( F ) qui retourne la file F renversée ( l’élément de la tête sera situé à la queue et ainsi de suite ) en utilisant seulement une pile P et les primitives des PILE et les primitives des FILE, F est une file d’attente passée en paramètre.

Exemple d’exécution:

>>>F=[ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
>>>renverser(F)
[ 7 , 6 , 5 , 4 , 3 , 2 , 1 ]


Exercice 4: Copier une pile

Fonction Python copier_pile( P ) qui retourne la copie de la pile P en utilisant les primitive d’une pile, P est une pile passée en paramétré.

Exemple d’exécution:

>>> P = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
>>>copier_file( P )
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]


Exercice 5: Copier une file d’attente

Fonction Python copier_file( F ) qui retourne la copie de la file F (Copier une file d’attente ) en utilisant les primitive d’une file, F est une file passée en paramétré.

Exemple d’exécution:

>>> F = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
>>>copier_file( F )
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]


Exercice 6: Permutation circulaire d’une pile

Fonction Python PermutationCirculairePile ( P , n ) qui utilise les primitives d’une pile et qui modifie la pile P de telle sorte que l’élément en position i se retrouve en position i +n  (c’est à dire que le premier se retrouve en position n +1, si n est plus petit que la longueur de q, le deuxième en position n +2, … et le dernier en position n).


Exercice 7: Permutation circulaire d’une file d’attente

Fonction Python PermutationCirculaireFile ( F , n ) qui utilise les primitives d’une file et qui modifie la file F de telle sorte que l’élément en position i se retrouve en position i +n  (c’est à dire que le premier se retrouve en position n +1, si n est plus petit que la longueur de q, le deuxième en position n +2, … et le dernier en position n).


Exercice 8:Expression bien parenthésée

Fonction Python parenthesage( expression ) qui retourne True si l’expression est bien parenthésée et False sinon en utilisant des piles, l’expression est sous forme une chaîne de caractère passée en argument est ou non bien parenthésée en utilisant les piles avec ses primitives.

Avec les parenthèses ( et ) une expression est bien parenthésée si :

  • Il ne contient aucune parenthèse ’(’ ou ’)’, ou
  • Il est de la forme ’(mot)’ avec expression est une expression bien parenthésée, ou
  • Il est la concaténation de 2 expressions bien parenthésées.

Par exemple :

  • Les expressions suivantes sont bien parenthésées : ( ) ; (( )( )) ; (( )( ))(( ))( )
  • Les expressions suivantes ne sont pas bien parenthésées : )( ; ((( )) ; ( )( )( ))

Pour le résoudre à l’aide d’une pile :

  1. On parcourt le mot de gauche à droite
  2. Dés que l’on rencontre un caractère ’(’ on l’empile sur la pile.
  3. Dés que l’on rencontre un caractère ’)’, deux cas se présentent :
    1. Soit la pile est vide, et dans ce cas l’expression n’est pas bien parenthésée.
    2. Soit la pile est non-vide, et dans ce cas on la dépile.
  4. A la fin si la pile est vide l’expression est bien parenthésée, sinon il ne l’est pas.

Exemple d’exécution

>>>parenthesage( ” (( )( ))(( ))( ) ” )
True
>>>parenthesage( ” ((( )) ” )
False


Exercice 9: Notation polonaise inversé ou post-fixée

Fonction Python PolonaiseInverse( expression ) qui permet d’évaluer des expressions écrites en polonaise inversée. La notation polonaise inversée ou post-fixée permet de noter les formules arithmétiques sans utiliser de parenthèses.

expression est une chaine de caractère sous forme notation polonaise inversé où les nombres ainsi les opérations sont séparés par des espaces.

Exemples:

  • la forme polonaise de m’expression (21 + 13)  * 40 est 21  13  +  40  *
  • la forme polonaise de m’expression 10 + (31   * 4 ) est 10  31  4  +  +
  • la forme polonaise de m’expression  ( 3 + ( 5 * ( 7 + 2 ))) + ( 4 + ( 8 * 9 )) est  3  5  7  2  +  *  +  4  8  9  *  +  +

Algorithme d’évaluation

Pour effectuer le calcul, chaque donnée numérique est empilée, et lorsqu’on lit un opérateur, les opérandes sont dépilés, l’opération est effectuée et le résultat est mis au sommet de la pile.

Par exemple, pour évaluer  2  3  +  4  * :

  1. lecture de 2 qui est reconnu comme donnée numérique et de ce fait est empilé
  2. lecture de 3 qui est également empilé
  3. lecture de + qui est un opérateur binaire : 2 et 3 sont dépilés, le calcul 2 + 3 est effectué, le résultat 5 est empilé
  4. lecture de 4 qui est empilé
  5. lecture de * , opérateur binaire : 4 et 5 sont dépilés, le calcul 4*5 est effectué et le résultat 20 est empilé
  6. l’expression est entièrement lue donc le résultat final est au sommet de la pile.

N.B :

  • Pour distinguer deux (ou plus) nombres consécutifs, ils ont séparé par des espaces.
  • Pour la résolution de cette fonction on utilise les primitives des piles.

Exemple d’exécution:

>>> polonaise( ‘ 30  15  7  12  +  *  +  11  8  10  *  +  + ‘ )
406



Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Résoudre : *
19 + 14 =