Discussion :

[labt03]

Bonjour à tous, débutante en programmation ainsi qu'en algorithmique, j'ai pour devoir de répondre à un projet.
Celui de créer une grille dans laquelle se trouve un systeme proies/prédateur. Le début étant d'initialiser les structures des 3 éléments. On a pour consigne de créer une liste ( dynamique) à laquelle s'ajoute uniquement les proies et prédateurs saisies par l'utilisateur.
Je ne vois absolument pas comment.
J'avais pour idée de créer une liste statique, et de laisser des vides lorsque rien ne s'y trouve. Mais notre chargé de TD nous a dit que cest plus lourd et qu'il vaut mieux utilisé une liste dynamique plutôt que statique.

Merci pour votre aide.
Cordialement

[LittleWhite]

Bonjour,

J'imagine que la liste statique est une représentation de la grille, alors que la liste dynamique est une liste des éléments de la grille.
Du coup, les questions à répondre, avant de commencer sont (je ne parle que des éléments en ma connaissance) :

• comment on définit une liste en C++ ;
• que mettre dans notre liste ;
• comment mettre à jour la liste ;
• [BONUS] où trouver la documentation d'une telle liste en C++.

[labt03]

Pour créer une liste il faut créer un tableau, via une structure. Pour la liste dynamique il faut créer une structure dans laquelle on met la tête de liste ainsi que l'élément suivant.
Néanmoins la je ne vois pas comment coder de telle sorte que d'ajouter uniquement des proies ou prédateurs dans la liste dynamique.

[koala01]

Salut,

Je n'arrive vraiment pas à comprendre comment un prof peut vouloir donner un cours d'algorithmie sans expliquer les concepts fondamentaux!!!

Car l'algorithmie, par définition, c'est indépendant de tout langage, et donc, il y a des notions que l'on va retrouver dans tous les langages.
Parmi les notions tout à fait essentielles à la création d'un algorithme, autrement dit, à la mise en place d'une logique qui pourra être effectuée autant de fois que nécessaire en apportant les garanties nécessaires, on trouve:

• la notion de type de donnée: cela regroupe ce que l'on peut faire avec une donnée, car on ne va pas manipuler une valeur entière comme on manipulerait une chaine de caractères, par exemple
• la notion de variable Vs la notion de constante: car certaines données pourront être modifiées alors que d'autres ne pourront pas l'être
• la notion de test dont le résultat ne peut être que "vrai" ou "faux" car c'est la manière la plus simple de permettre la prise de décision sur base d'une comparaison
• la notion de boucle (il en existe plusieurs types, tous plus ou moins interchangeable) car c'est la manière la plus simple de faire en sorte qu'une partie de la logique soit répétée
• la notion de tests "à choix multiple", car il est souvent nécessaire de pouvoir décider d'une action sur base de la valeur particulière d'une donnée
• les notions de fonctions et de paramètres ou d'arguments, car elles permettent de simplifier la logique, en fournissant -- le cas échéant -- des données externes que la partie concernée serait incapable d'obtenir par elle même

Seulement, il ne faudra pas longtemps pour que l'on se rende compte que les types de données que les ordinateurs manipules sont trop "simples" par rapport à la complexité des notions que nous voulons leur faire manipuler.

On arrivera donc naturellement à présenter la notion de "type défini par l'utilisateur", qui se subdivise en trois notions principales:

• la notion de structure qui représente un "agrégat" de données, de type potentiellement différents. Les classes ne sont elles aussi que des agrégats de données, on les aborde simplement différemment, pour autant que le langage supporte cette notion
• la notion d'énumération: on regroupe plusieurs termes auxquels on donne une valeur numérique bien particulière, car le code est souvent plus facile à comprendre lorsque on utilise un terme qui a une signification bien précise que lorsque l'on utilise la valeur numérique assignée à ce terme (ex: EventKeyboard ou EventMouse au lieu de 1 et 2)
• la notion d'union qui correspond à un "espace mémoire" permettant de représenter des données de types différents en fonction du point de vue envisagé

Et, comme on se rendra certainement compte "tout juste après" que l'on manipule régulièrement les données "par lot", qu'il est difficile de gérer -- et surtout de faire évoluer -- un programme dans lequel toutes les données sont représentées de manière séparées, il faudra aborder la notion de "collections": le moyen de "regrouper" plusieurs données d'un type identique (ou à tout le moins "compatibles") qui seront utilisées dans un même but et de la même manière.

On commencera donc "simplement" par aborder la notion de "tableau (de taille fixe) de données": on demande au compilateur de nous donner un espace mémoire suffisant que pour représenter "un nombre bien particulier" d'éléments d'un même type (dont la taille de chaque élément est définie) et l'on fait confiance au compilateur pour qu'il nous donne l'accès à la donnée bien particulière qui nous intéresse lorsqu'on lui indique l'indice à laquelle celle-ci se trouve.

Seulement, il y aura forcément des situations dans lesquelles nous sommes totalement incapables, au moment d'écrire le code, de déterminer le nombre exact d'éléments que notre collection devra contenir, et qu'il n'est pas possible de définir une valeur "arbitraire" pour ce nombre. Nous devrons donc introduire la notion de "collection dynamique" (comprends: de collection dont le nombre d'éléments est susceptible d'évoluer selon les besoins, en cours d'utilisation).

Comme nous avons déjà abordé la notion de "tableau de taille fixe", il semble "logique" de parler en tout premier lieu des tableaux dynamiques (comprends: des tableaux dont le nombre d'éléments est susceptible d'évoluer selon les besoins en cours d'utilisation).

Ce type de collection a un énorme avantage, vu que toutes les données sont littéralement "les unes après les autres" en mémoire: vu que l'on connait la taille des données (identique pour chaque élément), il "suffit" d'une multiplication et d'une addition pour déterminer l'adresse à laquelle une donnée bien particulière (à laquelle on accède au travers de son indice) se trouve, et nous avons donc un "accès direct" à l'ensemble des éléments.

Je veux dire par là qu'il ne faudra pas plus de temps pour accéder au deuxième élément qu'au 110 eme, pour autant que le 110eme existe

Par contre, ce type de collection présente un inconvénient majeur: à chaque fois que la capacité du tableau doit être modifiée (que ce soit pour un ajout ou suite à un retrait), il faudra ... faire en sorte que le compilateur demande "un nouvel espace mémoire", suffisant pour représenter l'ensemble des éléments que le tableau devra contenir, au système d'exploitation. et ca, ca prend "un temps bête".

Pour être précis, il y a trois thèmes principaux relativement "antagonistes" qui peuvent influer sur les performances des collections, dans le sens où, si on si l'on gagne en vitesse sur l'un, c'est forcément au détriment de la vitesse d'un voir même des deux autres:

1. la vitesse laquelle on ajoute ou on retire un élément
2. la vitesse à laquelle on accède à un élément se trouvant à une position bien particulière
3. la vitesse à laquelle on obtient un résultat lorsque l'on recherche un élément dont on ignore la position exacte

Autant le dire tout de suite, la notion de tableau brille particulièrement sur le point (2), car l'accès à une position particulière se fait "en temps constant". Par contre, cette notion sera particulièrement lente pour le point (1) et ne pourra être réellement efficace pour le point (3) que si les données sont triées. Et le tri des donnée est un processus qui prend du temps.

Il sera donc temps d'introduire quatre autres types de collections "élémentaires", susceptibles de s'adapter à "tous les types de données".

Pour ce faire, il faut introduire deux notions particulières:

• la notion d'élément d'une collection, qui fournit, en plus des données qui nous intéressent, un "moyen quelconque", pour chaque élément, de se "rattacher" à un (ou à deux) autres éléments, à condition qu'ils existent bien sur (*)
• La notion de collection en elle même qui permettra, à tout le moins
  1. d'ajouter un élément
  2. de supprimer un élément
  3. (éventuellement, si c'est applicable) d'insérer un élément entre deux éléments existants
  4. d'accéder à "un élément de départ"
  5. (éventuellement, si c'est applicable) d'accéder à un élément particulier de la collection
  6. (éventuellement, si c'est applicable) de rechercher un élément sur base d'un critère bien particulier

Ces types de collections vont s'inspirer de ce que l'on fait "dans la vie de tous les jours", à savoir:
la notion de pile:
Quand on ajoute un élément, on le place "au dessus" du dernier élément qui se trouve déjà dans la pile, un peu à la manière d'une pile d'assiettes ou de caisses.

Ce système est particulièrement efficace vis à vis du point (1) car il se fait en temps constant : peu importe que ce soit le premier ou le dixième élément de la pile, l'ajout d'un élément ne prendra pas plus de temps, que ce soit pour ajouter ou pour retirer un élément

Par contre, il s'agit d'un système LIFO (Last In First Out, ou si vous préférez: dernier entré, premier sorti), car, le dernier élément ajouté sera le premier à devoir partir pour que l'on puisse accéder aux autres, sous peine de risquer de se ramasser toutes les caisses sur figure.

Si vous voulez spécifiquement atteindre le troisième élément qui a été ajouté (et "au dessus" duquel vous avez rajouté cinq autres éléments), vous devrez commencer par ... retirer tous les éléments qui ont été ajoutés après lui.

Quant à la recherche d'un élément particulier sur base d'un critère quelconque, elle est tout bonnement exclue, vu que cela implique de retirer tous les éléments qui ne correspondent pas au critère recherché. Dés lors, la question se pose de savoir ce que ces éléments retirés deviendraient

La notion de file:
C'est un système que l'on retrouve à la caisse des magasins: le premier client arrivé à la caisse sera le premier à payer ses achats et à sortir. Les clients suivant venant "naturellement" prendre place "derrière" le dernier élément qui se trouve dans la file.

Il s'agit là d'un système FIFO (First In, First Out, ou si vous préférez: premier entré premier sorti).

L'ajout d'un élément dans ce genre de collection se fait en temps constant vu que, peu importe qu'il y ait trois ou dix personnes à la caisse, les suivants arriveront toujours ... après le dernier qui soit entré dedans.

Par contre, si vous voulez accéder précisément au quatrième élément qui a été ajouté, vous devrez commencer par retirer... les trois éléments qui ont été ajoutés avant lui.

Quant à la recherche d'un élément particulier sur base d'un critère quelconque, elle est tout bonnement exclue, vu que cela implique de retirer tous les éléments qui ne correspondent pas au critère recherché. Dés lors, la question se pose de savoir ce que ces éléments retirés deviendraient

La notion de liste
Nous pourrions presque dire que la liste est un "hybride" entre la pile et la file, car elle permet tout aussi bien d'ajouter un élément "avant le premier" que "après le dernier" élément qui se trouve dans la liste; mais aussi "entre deux éléments déjà présents".

Et, comme ce "système hybride" n'est plus vraiment un FIFO ni un LIFO, on peut se permettre d'accéder à un élément bien particulier sans être "obligé" de retirer les autres.

Seulement cet accès se fera en temps proportionnel: si vous voulez accéder au troisième élément de la liste, vous devrez partir du premier (ou du dernier) et... "traverser" chacun des éléments qui sépare le premier élément de celui auquel vous voulez accéder. C'est donc un accès "plus lent" que pour le tableau, qui est la conséquence même que l'ajout et la suppression (ou même l'insertion) d'un élément se fera "plus rapidement" que pour le tableau.

La recherche d'un élément sur base d'un critère bien particulier est possible, mais, du fait même que l'accès est "séquentiel", le temps nécessaire pour trouver l'élément qui nous intéresse sera forcément ... proportionnel à la position à laquelle cet élément se trouve dans la liste.

La notion d'arbre binaire
Et si, au lieu de simplement représenter "un (ou deux) éléments" sans autre précision, auquel chaque élément peut se "rattacher", nous décidions de permettre à chaque élément de se "rattacher" à deux éléments dont un donnerait "forcément" accès à un élément considéré comme "plus petit" (selon un critère particulier) que l'élément courant, et dont l'autre donnerait forcément accès à un élément considéré comme "plus grand" (selon le même critère, bien sur)?

Cela demanderait sans doute "un peu plus de temps" d'ajouter (ou de supprimer) un élément, car l'idée est d'avoir "un maximum" d'éléments qui soient en relation aussi bien avec un élément "plus petit" qu'avec un élément "plus grand", ce qui implique qu'il faudrait réorganiser très régulièrement une grande partie de ces relations.

Par contre, cela permettrait, lorsque l'on voudrait accéder à un des élément (sur base du critère utilisé), d'ignorer purement et simplement "tout un pan" des éléments contenus dans cette collection, car, si on se rend compte que l'élément que l'on recherche est "plus petit" (ou "plus grand") que celui que l'on observe à un "instant T", il nous "suffirait" de choisir la "bonne relation" et ... d'ignorer l'autre.

L'idée étant que, si on cherche un élément "plus petit" que celui que l'on observe, il se trouvera ** forcément ** parmi ceux auxquels la relation "plus petit" nous donnera accès

La recherche d'un élément devient donc particulièrement rapide, car elle se fera "naturellement" sur une base "dichotomique", en nécessitant de tester qu'un nombre d'éléments correspondant au logarithme du nombre total d'éléments contenu dans la collection.

Ainsi, avec 255 éléments (correctement triés) dans la collections, nous pourrions obtenir une réponse ferme et définitive après n'en avoir testé que ... 8 dans le pire des cas.

(*) En C++, la possibilité de "créer un lien" entre deux éléments sera fournie par la notion de pointeurs, ce qui peut s'avérer intéressant pour ton projet.

J'ai rappelé, dans cette interventions, des concepts qui auraient du être abordés par tout cours de programmation, ou pire, d'algorithmie, aurait du aborder depuis longtemps lorsqu'il propose ce genre d'exercice.

Je n'ai bien sur fait que "gratter la surface", et mon intervention est pourtant déjà excessivement longue.

Tu devrais pourtant, grace à ces informations, arriver à t'en tirer plus facilement . Mais, si tu as besoin d'un complément d'information, n'hésite pas à demander

[LittleWhite]

Arf, moi je pensais en C++. Du coup, je voyais une liste -> std::list ou bien, soyons fous std::vector

[koala01]

Bien sur que l'on en viendra ** forcément ** à utiliser std::list ou std::vector... Ca fait partie des bases

Et comme le projet est visiblement destiné à faire joujou avec l'héritage et le polymorphisme d'inclusion, on en viendra forcément à jouer avec les notion de pointeurs, de pointeurs intelligents, d'utilisateur et de propriétaire des ressources

A ceci près que ces deux classes correspondent, justement, aux concepts que j'ai expliqués, et, pire encore, que les termes de "tableau" et de "liste" ont forcément un sens tout particulier pour un développeur. Surtout lorsqu'on parle d'algorithmie

Or, notre cher ami ne semble même pas être conscient du sens particulier donné à ces termes (et son prof non plus, d'ailleurs ).

Alors, je ne dis pas qu'il devrait coder lui-même les notions d'éléments et de listes, bien que je présume que c'est ce à quoi s'attend sincèrement son prof, loin de là,