Discussion :

[xerondark25]

Bonjour tout le monde !

Nouveau dans ce forum j'espère que tout va bien ce passer

Je vous expose mon problème.

j'ai une file (donc FiFo) et je dois en trouver le nombre d'éléments qui la compose. Or les file pile liste ce sont mes hantises en programmation pourtant c'est la base

Pouvez vous m'aider svp

[yahiko]

Tout dépend de ton implémentation (et donc un peu du langage aussi).

Ta file est représentée sous quelle forme ? Via un tableau, via une liste chaînée ou autre ?

[xerondark25]

Merci de t'y pencher sur mon problème

C'est juste de l'algo pur et dur

j'ai ça en annexe et je comprends un peu mais je sais pas du tout manier la file.



ca serai avec un tableau ca serai très un simple une boucle POUR et c'est fini mais là ce n'est pas pareil..

[picodev]

Bonjour,

avec les primitives proposées, le seul moyen de connaître le nombre d'éléments est de tous les défiler. Ensuite il te faudra gérer le fait de devoir les réempiler pour éviter de détruire la file et de faire attention aux cas particuliers. C'est une solution en O(n) temps et espace, avec n le nombre d'éléments dans la file.
Si tu disposes d'un élément particulier qui n'est pas dans ta file ou si tu sais en plus que les éléments sont tous différents alors tu as une solution en O(n) temps et O(1) espace.

[yahiko]

Si on se base sur cette spécification abstraite d'une file, il faut raisonner en terme mathématique.
Pour obtenir le nombre d'éléments de la file, tu dois compter le nombre de retraits d'un élément de la file (Retirer_Elem) pour que la file soit vide.

Edit : il ne faut évidemment pas considérer une telle spécification abstraite comme une implémentation possible (qui serait bougrement inefficace) mais comme une liste des propriétés d'une file sous la forme d'invariants.

[xerondark25]

Salut Picodev et merci aussi de m'aider.

C'est une solution en O(n) temps et espace, avec n le nombre d'éléments dans la file.
Si tu disposes d'un élément particulier qui n'est pas dans ta file ou si tu sais en plus que les éléments sont tous différents alors tu as une solution en O(n) temps et O(1) espace.

C'est un algo de complexité si je me souviens de mon cours, je l'avais utilisé pour un tri par dichotomie si je me trompe pas. mais je n'arrive pas à voir le bout avec cette fille.

Yahiko, ton raisonnement n'est pas mauvais ça a l'air d'être une solution mais retirer tous les éléments ne serait ce pas bon je pense. Peut être compter les itérations en les enlevant et les "stocker dans une nouvelle fille ?

[yahiko]

Yahiko, ton raisonnement n'est pas mauvais ça a l'air d'être une solution mais retirer tous les éléments ne serait ce pas bon je pense. Peut être compter les itérations en les enlevant et les "stocker dans une nouvelle fille ?

Edit : il ne faut évidemment pas considérer une telle spécification abstraite comme une implémentation possible (qui serait bougrement inefficace) mais comme une liste des propriétés d'une file sous la forme d'invariants.

Comme dit dans mon édit, il ne faut surtout pas chercher à transposer littéralement ce raisonnement en programme.
Avec une telle spécification, nous sommes dans l'univers des mathématiques et non pas celui de la programmation.

En d'autres termes, tu peux considérer que retirer un élément de la file ne le retire pas réellement mais créé une copie de cette file avec un élément en moins.
f' = Retirer_Elem(f)
f" = Retirer_Elem(Retirer_Elem(f))
...
f⁽ⁿ⁾ = Retirer_Elem(Retirer_Elem(...(Retirer_Elem(f))))

de telle sorte que f⁽ⁿ⁾ correspond à la file de laquelle on a retiré tous ses éléments (file vide), et où n correspond au nombre d'éléments de la file.

[xerondark25]

C'est bien ce que je pensais par rapport à ton edit
Bah merci de m'avoir fait comprendre la file ^^ et je pense que pour la pile et liste c'est un peu comme ca aussi
Il va falloir que je m'y penche vraiment car je galère en algo et on a des applications dessus en C et en Java. (je suis plus dans les réseaux que dans le code moi )

Je pense avoir fait mon algo dans ma tête.

Code :

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

1
2
3
4
5
6
7
8
9
10
Procédure nbre_element_file(E Element, ES/File)
Variable  cpt entier 
DEBUT
cpt <- 0
TANTQUE (NON File_Vide(E/File))
Retirer_Elem(ES/File)
cpt <- cpt+1
FINTANTQUE
AFFICHER cpt
FIN

[yahiko]

L'idée est là.