Exercices algorithme : Piles et Files attente
Exercice 1 :
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.
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
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.
- é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.
- É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
