Discussion :

[rirou]

Ces 2 algorithmes sont mes solutions pour inverser une File F.
Il y a une seule différence :

Procedure Inverse(var F:File)
Debut
Si (Vide(F)=Faux) alors
Defiler(F)
Inverse(F)
Enfiler(Tete(F),F)
Fin Si
Fin

Procedure Inverse(var F:File)
Debut
Si (Vide(F)=Faux) alors
Defiler(F)
Inverse(F)
Fin Si
Enfiler(Tete(F),F)
Fin

Lequel des 2 me donne une File inversée, celui avec l'instruction "Enfiler" avant le "Fin Si" ou après.

Merci de m’aider

[PRomu@ld]

Le plus simple est de dérouler toi même l'algorithme sur un exemple simple, et voir ce que ça donne. Il n'y a que ça de vrai.

[sidahmed]

Bonsoir,

je pense que la deuxième procédure fait presque le calcul correctement !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
Procedure Inverse(var F:File)
Debut
 Si (Vide(F) = Faux) alors
  Defiler(F);
  Inverse(F);
 Fin Si
 Enfiler(Tete(F),F);
Fin

Mais enfiler la tête ou la queue de la file, reste à dérouler ? Une chose est sûre, c'est ta deuxième version qui est bonne !

À bientôt.

[rirou]

J’ai déjà déroulé le 2ème mais je n’ai pas su le faire pour le 1er.
Dans le 1er, lorsque la condition dans "Si" n’est plus satisfaite, l’algorithme est-il sensé sortir carrément de la Procédure ou va-t-il revenir, continuer et exécuter l’instruction "Enfiler" ?

Merci de m’aider

[rirou]

Votre Procédure est fausse Mr Sidahmed car supposons la file initial d’éléments de type entier suivante :
F : 5 2 3 4 1
On va avoir après chaque itération
2 3 4 1 1
3 4 1 1 1
4 1 1 1 1
1 1 1 1 1
1 1 1 1 1
…
Et ça ne vas jamais s’arrêter car queue ne sera jamais égal à tete que dans le cas où la valeur 5 se trouve elle-même dans la queue de la file et alors il n’y aura aucune itération

Merci de m’avoir aider

N’oublier pas cette question SVP
J’ai déjà déroulé le 2ème mais je n’ai pas su le faire pour le 1er.
Dans le 1er, lorsque la condition dans "Si" n’est plus satisfaite, l’algorithme est-il sensé sortir carrément de la Procédure ou va-t-il revenir, continuer et exécuter l’instruction "Enfiler" ?
Merci de m’aider

[pseudocode]

En imperatif, on revient toujours d'un appel de fonction (sauf exit ou crash ). Donc que la condition du IF soit vraie au fausse, lors du retour de la fonction on continue la où on en était.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
Appel initial                        1ere recursion
                                   
Procedure Inverse(var F:File)  ----> Procedure Inverse(var F:File)
Debut                         |      Debut
  Si (Vide(F)=Faux) alors     |        Si (Vide(F)=Faux) alors
    Defiler(F)                |          Defiler(F)
                              |
    Inverse(F) ---------------            Inverse(F) ------ - - ->
               <--------------                       <------ - - -
    Enfiler(Tete(F),F)        |          Enfiler(Tete(F),F)
  Fin Si                      |        Fin Si
Fin                            ----- Fin

[Jedai]

Inutile de mettre "aider" en couleur et en majuscule (l'équivalent d'un cri sur internet), c'est désagréable.
Ces deux versions sont fausses en cela qu'elles "perdent" des éléments, en effet elle défile()nt des éléments mais ne les stockent nulle part. Une version correcte serait plutôt :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
Procedure Inverse(var F:File)
Debut
   Si (Non Vide(F)) alors
      E:Element := Defiler(F);
      Inverse(F);
      Enfiler(E,F);
   Fin Si
Fin

--
Jedaï

[sidahmed]

Votre Procédure est fausse Mr Sidahmed car supposons la file initial d’éléments de type entier suivante :
F : 5 2 3 4 1
On va avoir après chaque itération
2 3 4 1 1
3 4 1 1 1
4 1 1 1 1
1 1 1 1 1
1 1 1 1 1
…
Et ça ne vas jamais s’arrêter car queue ne sera jamais égal à tete que dans le cas où la valeur 5 se trouve elle-même dans la queue de la file et alors il n’y aura aucune itération

C'est pas exactement ce que tu viens de dire, normalement l'algorithme s'arrête dès que la tête devient la queue de la file, donc inutile de l'enfiler puis la défiler, même pour une file vide, ça marche, cependant mon algorithme est archi-faux !

À bientôt.

[sidahmed]

D'ailleurs ce qui m'a trotté dans la tête, c'est que comment peut-on récupérer la queue de la file une fois cette dernière en est dépourvue ! À mon avis, il faut stocker la queue à chaque suppression, sans pour autant oublier que la signature du type abstrait file est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
Sorte File
Utilise Élément, Booléen
Opérations :
  file_vide : ----> File
  ajouter : File × Élément ----> File
  retirer (défiler) : File ----> File
  premier (tête) : File ----> File
  est_vide : File ----> Booléen

Donc l'instruction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

queue := défiler(f)

et moins propre !

Bon courage.

[Jedai]

D'ailleurs ce qui m'a trotté dans la tête, c'est que comment peut-on récupérer la queue de la file une fois cette dernière en est dépourvue ! À mon avis, il faut stocker la queue à chaque suppression, sans pour autant oublier que la signature du type abstrait file est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Sorte File
Utilise Element, Booléan
Opérations :
...
retirer (défiler) : File ----> File

Voilà une signature bien étrange dans un contexte impératif ! Généralement Défiler modifie son argument et renvoie l'élément retiré (c'est le cas dans toutes les implémentation impératives de files que je connais), même en fonctionnel, défiler() a la connotation de renvoyer l'élément retiré, en plus de la file modifiée...
S'agit-il d'une consigne de l'exercice ? Dans ce cas il faut utiliser Tete() avant pour récupérer l'élément.

--
Jedaï

[sidahmed]

Voilà une signature bien étrange dans un contexte impératif ! Généralement Défiler modifie son argument et renvoie l'élément retiré (c'est le cas dans toutes les implémentation impératives de files que je connais), même en fonctionnel, défiler() a la connotation de renvoyer l'élément retiré, en plus de la file modifiée...
S'agit-il d'une consigne de l'exercice ? Dans ce cas il faut utiliser Tete() avant pour récupérer l'élément.

--
Jedaï

Non non, je regrette, je connais cette signature ça fait des années.

J'ai confirme la véracité de la signature sus-citée en tapant sur google : signature du type abstrait file ==> Troisième résultat affiché par google (enfin troisième chez moi, ça peut changer d'une recherche à l'autre): Cours 4 : Le type File

[rirou]

Voilà une signature bien étrange dans un contexte impératif ! Généralement Défiler modifie son argument et renvoie l'élément retiré (c'est le cas dans toutes les implémentation impératives de files que je connais), même en fonctionnel, défiler() a la connotation de renvoyer l'élément retiré, en plus de la file modifiée...
S'agit-il d'une consigne de l'exercice ? Dans ce cas il faut utiliser Tete() avant pour récupérer l'élément.

--
Jedaï

On a besoin de Tete(F) parce que Defiler(F) est une procédure qui ne fait que modifier la file F en supprimant la tête sans renvoyer l'élément supprimé.
Il est donc faux d'ecrire F := Defiler(F);