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.

Article plus récent Article plus ancien

Leave a Reply