[AIDE] Inversion d'une File : Récursivité

Version imprimable

17/10/2007, 18h18
rirou

[AIDE] Inversion d'une File : Récursivité

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
17/10/2007, 18h37
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.
17/10/2007, 18h57
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
17/10/2007, 19h08
sidahmed
Bonsoir,

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

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.
17/10/2007, 19h29
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 :oops:

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

Code:

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

17/10/2007, 19h52
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:

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ï
17/10/2007, 19h57
sidahmed

Citation:

Envoyé par 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

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.

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:

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:

queue := défiler(f)

et moins propre !

Bon courage.

17/10/2007, 20h23
Jedai
Citation:
Envoyé par 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:

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ï
18/10/2007, 02h18
sidahmed

Citation:

Envoyé par Jedai

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
18/10/2007, 09h53
pseudocode

Citation:

Envoyé par sidahmed

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. :roll:
18/10/2007, 21h46
Jedai
Citation:

Envoyé par pseudocode

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. :roll:

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:

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
Citation:

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ï
19/10/2007, 14h50
rirou

Citation:

Envoyé par Jedai

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);
19/10/2007, 17h03
sidahmed
Bonsoir,

en se basant sur la définition suivante :

Citation:

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.
20/10/2007, 23h13
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.
21/10/2007, 16h12
Jedai

Citation:

Envoyé par Zavonen

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ï
21/10/2007, 18h36
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())

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:

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;
}

21/10/2007, 20h45
Jedai

Citation:

Envoyé par 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

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ï