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.

[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

[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]

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

[pseudocode]

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

Il me semble également que c'est la signature utilisée par le Lisp, mais ca fait longtemps que je n'ai pas vérifié cette assertion.

[Jedai]

Il me semble également que c'est la signature utilisée par le Lisp, mais ca fait longtemps que je n'ai pas vérifié cet assertion.

Oui mais en Lisp, ça se justifie vu que c'est un langage fonctionnel, par contre en impératif ça me semble bizarre... En tout cas il suffit d'écrire plutôt :

Code :

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

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

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

Effectivement, ce cours répertorie cette signature... On constate d'ailleurs que retirer_file() renvoie la file modifiée ET modifie la file en argument ! En bref une API mal pensée...

--
Jedaï

[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);

[sidahmed]

Bonsoir,

en se basant sur la définition suivante :

Dans une file, on fait les adjonctions à une extrémité, les accès et les suppressions à l'autre extrémité.

Et en respectant la signature sus-citée du type abstrait file, franchement j'arrive pas à trouver une solution potable.

Cependant, je cherche encore une solution envisageable et voici donc une alternative, pas vraiment intéressante, mais je la cite quand même :

• Liste doublement chaînée.

À bientôt.

Cordialement,
Sidahmed.

[Zavonen]

Curieux toutes ces fonctions récursives qui ne commencent pas par traiter le cas terminal.
Tout Lispien écrirait:
(defun reverse (L)
(if (null L) L
(append (reverse (cdr l) (list (car l)))))
Mais de toute façon c'est pour la génération 'foo-bar' à la fois un cas d'école et
une horreur.
L'efficacité de cette méthode est déplorable.
Le mieux est de bricoler une petite pile, d'empiler les éléments de la liste et de les dépiler dans la liste résultat initialisée à NIL.
Cela dit, pour les listes doublement chaînées il n'y a stritement rien à faire, qu'à lire à l'envers.

[Jedai]

Le mieux est de bricoler une petite pile, d'empiler les éléments de la liste et de les dépiler dans la liste résultat initialisée à NIL.

Ce qui est exactement ce que fait mon programme, tu as remarqué ? Le seul truc c'est qu'il utilise directement la pile d'appel et que de ce fait il est peu efficace dans des langages non-adaptés à la récursion comme le C.

--
Jedaï

[Zavonen]

Oui c'est vrai, je n'ai pas regardé ton code à la loupe car (très sincèrement) je ne m'y retrouve pas dans ces termes 'enfiler' 'defiler' (je ne sais pas ce que cela veut dire, mais avec un peu d'imagination...).
Je suis plutôt habitué aux notations anglo-saxonnes.
Pour les FIFO qstore, qretrieve
pour les LIFO push, pop
Avec tout ça mon truc donnerait si la pile est vide au départ:

while L
stack.push (L.head)
while stack
L.append(stack.pop())

[Zavonen]

Voici une implémentation en C d'un algo de renversement d'une file circulaire en O(n/2) n étant la taille de la file

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <stdlib.h>
 
// la file circulaire
typedef struct
{
    int * base; // base de la File
    int * first; // adresse du premier entré
    int * last; // adresse du dernier
    int content; // nombre en attente
    int max; // capacité maximum
}FileCirc ;
 
 
// constructeur
void init (FileCirc * Q, int M)
{
    Q->base = (int *) malloc (M*sizeof(int));
    Q->first=Q->base;
    Q->last=Q->base;
    Q->content=0;
    Q->max=M;
}
 
// adresse du n-ième élément
int * pelement  (int n, FileCirc * Q)
{
    if ((Q->first + n)<(Q->base+Q->max))
        return Q->first+n;
    else
        return Q->first+n-Q->max;
 
}
 
// Ajouter un élément (enfiler)
void qstore (int u, FileCirc * Q)
{
    if (Q->content==Q->max)
        return; // file pleine
    else
    {
        Q->content++;
        *Q->last=u;
        Q->last=Q->last+1;
        if (Q->last >= (Q->base+Q->max))
            Q->last=Q->base;
    }
}
// Traiter le premier (défiler)
int qretrieve (FileCirc *Q)
{
    int x;
    if (!Q->content)
        return -100000000; // valeur hors norme pour file vide
    else
    {
        x=*Q->first;
        Q->content--;
        Q->first=(Q->first+1);
        if (Q->first >=(Q->base+Q->max))
            Q->first=Q->base;
        return x;
    }
}
 
// échange les valeurs de rang m et n
void exchange(int m, int n, FileCirc *Q)
{
    int x= *pelement(m,Q);
    int y=*pelement(n,Q);
    *pelement(m,Q)=y;
    * pelement(n,Q)=x;
}
 
// renverse la file
void reverse (FileCirc *Q)
{ int i;
  for (i=0; i<=Q->content/2;i++)
    exchange(i,Q->content-1-i,Q);
}
 
// voir la file
void show (FileCirc *Q)
{
    int i;
    for (i=0;i<Q->content;i++)
        printf("%d " , *pelement(i,Q));
    printf("\n");
}
 
int main()
{
    FileCirc F;
    init(&F,10);
    qstore (1,&F);
    qstore (2,&F);
    qstore (3,&F);
    show(&F);
    reverse(&F);
    show(&F);
    return 0;
}

[Jedai]

Voici une implémentation en C d'un algo de renversement d'une file circulaire en O(n/2) n étant la taille de la file

Oui enfin n/2 si tu comptes le nombre d'appel d'exchange(), si tu comptes le nombre d'assignements réels, c'est bien en n comme l'algorithme à base de pile (on pourrait également arguer qu'il y a plutôt 2n assignements avec la pile, enfin tout cela reste du O(n) de toute façon). De plus c'est spécifique à l'implémentation, contrairement à la solution utilisant une pile. Tant qu'à faire une implémentation pour optimiser reverse(), autant utiliser une liste doublement chainée, reverse() est alors en O(1).

--
Jedaï