{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "__Remarque préliminaire__ : Jupyter est parfois capricieux pour le téléchargement des images. Si les images n'apparaissent pas dans le notebook, chargez les dans le même dossier que le notebook. Les adresses se trouvent en double cliquant dans les cellules de texte (là où il y a précisé \"image\", c'est qu'il y a une image normalement...). Puis changez le code comme ceci : `![Image : listes](http://www.maths-info-lycee.fr/images/arbre1.jpg)` devient `![Image : listes](imagearbre1.jpg)` ou même `![](imagearbre1.jpg)`\n", " \n", " \n", " \n", "# Retour sur les listes\n", "Dans ce notebook, on va reprendre les listes pour résoudre de deux nouvelles manières le problème de Josèphe. \n", " \n", "On va utiliser les listes, que l'on peut voir comme des arbres filiformes. \n", " \n", "On rappelle les primitives sur les listes : \n", "* test de vacuité d'une liste : `estVide(liste)`\n", "* Obtention de la longueur de la liste : `longueur(liste)`\n", "* Accéder au k-_ième_ élément de la liste : `lire(liste , k)`\n", "* Supprimer le k-_ième_ élément de la liste : `supprimer(liste , k)`\n", "* Insérer un élément en k-_ième_ position dans la liste : `inserer(liste , k)` \n", " \n", "## Une implémentation des listes chainées\n", "Ubne liste peut être considérée comme une suite de cellules (ou noeuds), éventuellement vide (`None`) pour la liste vide. Chaque cellule comporte une tête (la `donnée`) et une queue (le `suivant`), qui est soit une autre liste, soit la liste vide `(None, None)`. Pour faire le parallèle avec les arbres dégénérés, la tête correspond à la racine et la queue soit à vide(`None`), soit à l'unique sous-arbre, puisque qu'on se place dans le cas où l'arbre est filiforme. \n", "_Remarque_ : On utilise souvent `tête` au lieu de `donnee` et `queue` au lieu de `suivant`. Dans le cadre de ce TP, ces noms sont utilisés dans un autre sens pour les listes circulaires, ce qui pourrait porter à confusion.\n", "\n", "![Image : liste chainéee](http://www.maths-info-lycee.fr/images/liste_chainee.jpg)\n", "\n", "Les attributs de la classe `CelluleL` sont :\n", "* `donnee` : l'élément de tête de la liste (éventuellement `None`)\n", "* `suivant`: la liste composant la deuxième partie du noeud\n", "* `longueur`: on rajoute cet attribut pour plus de commodité\n", "les méthodes sont celles données par les primitives ci-dessus. \n", "_Quelques remarques_ sous forme de questions : \n", "* pourquoi est-il assez \"naturel\" d'utiliser des fonctions récursives, notamment pour insérer et supprimer ?\n", "* Comment se fait-il que les longueurs des listes après insertion et suppression soient justes, alors qu'on ne modifie pas l'attribut longueur ?\n", "\n", "### Utilisations des listes chaînées\n", "* piles\n", "* allocation mémoire sur un disque dur : les blocs libres sont stockés dans une liste chaînée\n", "* opérations arithmétiques sur des grands entiers\n", "* page suivante/précédente sur un navigateur : on utilise une liste doublement chaînée\n", "* idem pour un logiciel de visualisation d'images, ou d'écoute de musique" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class CelluleL:\n", " def __init__(self , donnee = None , suivant = None) :\n", " self.donnee = donnee\n", " if donnee is not None :\n", " self.suivant = suivant\n", " elif suivant is not None :\n", " self.suivant = None\n", " \n", " def __repr__(self):\n", " if self.donnee is None :\n", " return '()'\n", " else:\n", " # la 1ère possibilité met l'aspect récursif en avant\n", " # la 2ème possibilité mes l'aspect chaiîné en avant\n", " #return '(' + str(self.donnee) + repr(self.suivant).replace('None','()') + ')' \n", " return str(self.donnee) + '->' + repr(self.suivant)\n", " \n", " def estVide(self):\n", " return self.donnee is None\n", " \n", " def longueur(self):\n", " long = 0\n", " while not self.estVide():\n", " long = long + 1\n", " self = self.suivant\n", " return long \n", " \n", " def getMaillon(self, k):\n", " if k > self.longueur() :\n", " raise IndexError('Index trop grand')\n", " else :\n", " while k > 0:\n", " k = k - 1\n", " self = self.suivant\n", " return self\n", " \n", " def lire(self , k) :\n", " return self.getMaillon(k).donnee \n", " \n", " def inserer(self , k, element) :\n", " if k > self.longueur() :\n", " raise IndexError('Index trop grand')\n", " elif k == 0 and not self.estVide():\n", " return CelluleL(element,self)\n", " elif k == 0 and self.estVide():\n", " print(\"ici\")\n", " return CelluleL(element, CelluleL())\n", " else :\n", " maillon = self.getMaillon(k -1)\n", " prochain = CelluleL(element,maillon.suivant)\n", " maillon.suivant = prochain\n", " return self\n", " \n", " def supprimer(self , k) :\n", " longueur_liste = self.longueur()\n", " if k >= longueur_liste :\n", " raise IndexError('Index trop grand')\n", " elif k == 0 and longueur_liste == 1 :\n", " self = CelluleL()\n", " elif k == 0 :\n", " self = self.suivant\n", " else :\n", " maillon = self.getMaillon(k - 1)\n", " maillon.suivant = maillon.suivant.suivant\n", " return self\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Jeu de tests\n", "Dans la cellule précédente, créer un jeu de tests pour les différentes méthodes. On pourra en particulier :\n", "* créer la liste nil (vide), tester sa longueur et le fait qu'elle soit vide ;\n", "* y ajouter un élément, puis le supprimer, et vérifier que les longueurs sont bonnes ainsi que le test de vacuité ;\n", "* créer deux listes `1->2->3->4->5->()` et `5->4->3->2->1->()` ;\n", "* ajouter/supprimer des éléments en début, milieu et fin d'une de ces listes.\n", "\n", "### Application au problème de Josèphe\n", "On rappelle le terrible problème de Josèphe. Un nombre _n_ de soldats juifs sont positionnés en cercle. Les soldats romains tuent le 1er soldat, puis tuent un soldat sur _k_ jusqu'à ce qu'il n'y ait plus que _s_ survivants. On demande le(s) numéro(s) du(des) survivants. \n", "Résoudre ce problème en utilisant une liste chainée." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def josephe(n, k, s):\n", " \"\"\"\n", " Résoud le problème de Josèphe. Les soldats sont numérotés de 1 à n\n", " @param n : entier >= 1, nombre initial de soldats\n", " @param k : entier >= 2, saut entre deux meurtres de soldats\n", " @param s: entier >=0, nombre de soldats survivants\n", " @return survivor : liste d'entiers, numéros des sopldats survivants\n", " \"\"\"\n", " survivor = CelluleL()\n", "\n", " return survivor\n", "\n", "#tests à compléter (ça ne risque pas de fonctionner avec les \"?\")\n", "print(\"un soldat sur deux\")\n", "for i in range(1, 42):\n", " print(\"Survivant pour \", i, \"soldats :\",josephe(i,2,1).???)\n", "print()\n", "tset = josephe(41, 3, 2)\n", "print(\"2 survivants pour 41 soldats, avec 1 sur 3 :\", tset.????, tset.????)\n", "tset = josephe(1234,7, 10)\n", "print(\"10 survivants pour 1234 soldats, avec 1 sur 7 :\", tset)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Un deuxième type de liste : la liste chaînée circulaire\n", "Une liste chaînée circulaire est une liste chaînée dans laquelle le dernier élément n'est pas la liste vide, mais le premier élément de la liste. les listes chaînées circulaires sont notamment utilisées pour représenter des files. Cette structure de données est particulièrement adaptée à la résolution du problème de Josèphe. Mais elle est aussi utilisée par exemple pour gérer le partage du processeur (CPU) entre différents programmes (différents processus).\n", "\n", "![image : liste chaînée circulaire](http://www.maths-info-lycee.fr/images/liste_chainee_circ.jpg)\n", " \n", "On peut proposer différentes interfaces pour ce type de données. Dans le cadre de ce TP, les primitives proposées de `ListeCirc` sont :\n", "* Test de vacuité d'une liste : `estVide(liste)`\n", "* Obtention de la longueur de la liste : `longueur(liste)`\n", "* Ajout d'un élément en fin de liste : `ajoutfin(donnee)`\n", "* Supprimer la cellule courante connaissant la précédente: `supprimer(courant , precedent)` \n", "\n", "Une implantation de cette structure est proposée ci-dessous. Elle possède deux classes, `Noeud` et `ListeCirc`. La classe `Noeud` est celle de la liste chaînée non circulaire, l'attribut `longueur`en moins. \n", "Les attributs de `Noeud` sont: \n", "* `donnée` : le contenu du noeud\n", "* `suivant` : le noeud suivant \n", " \n", "La classe `ListeCirc` comporte deux noeuds : tête et queue. Plus précisément, les attributs à la création sont :\n", "* `tête` : `Noeud(None par défaut, ou données de la tête)`\n", "* `queue` : égale à `tête`lors de la création de la liste circulaire\n", "* `tête.suivant` : `queue`. Le noeud suivant la tête est la queue\n", "* `queue.suivant` : `tête`. Le noeud suivant la queue est la tête \n", " \n", "_Remarques / questions_ : \n", "* On aurait pu proposer une implémentation sans objet `ListeCirc`, et de même on aurait pu proposer un objet `ListeChainee`, qui aurait contenu les cellules de la liste chaînée non circulaire. On voit que les possibilités d'implémentations sont multiples.\n", "* Utiliser les mêmes noms de primitives permet d'écrire des programmes fonctionnant de manière identique avec les deux structures de données. Ce qui peut être très pratique.\n", "* La liste vide est composée d'une seule cellule, de donnée `None`, pointant sur elle-même. Lors du calcul de la longueur, de l'insertion ou de la suppression d'un élément, on est obligé de différencier ce cas. Le code est plus complexe que pour la liste chaînée non circulaire.\n", "* Pourquoi utilise-t-on ici deux classes, Noeud et ListeCirc ? \n", "* Pourquoi ne reprend-on pas directement le calcul de la longueur comme dans le cas de la liste chaînée ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Noeud: \n", " def __init__(self, donnee, suivant = None): \n", " self.donnee = donnee \n", " self.suivant = suivant\n", " \n", " def __repr__(self):\n", " if self.donnee == None:\n", " return \"\"\n", " else:\n", " return str(self.donnee)\n", "\n", "class ListeCirc: \n", " def __init__(self, donnee_tete = None): \n", " self.tete = Noeud(donnee_tete) \n", " self.queue = self.tete \n", " self.tete.suivant = self.queue \n", " self.queue.suivant = self.tete\n", " \n", " def estVide(self):\n", " return self.tete.donnee is None\n", " \n", " def longueur(self):\n", " lg = None \n", " return lg\n", " \n", " def supprimerCourant(self, precedent, courant):\n", " # Suppression du noeud courant connaissant le précédent\n", " if self.tete == self.queue : # cas particulier : un seul noeud\n", " self.tete.donnee = None\n", " elif courant == self.tete : # cas particulier : suppression de la tête\n", " self.tete = self.tete.suivant\n", " self.queue.suivant = self.tete\n", " elif courant == self.queue : # cas particulier : suppression de la queue\n", " self.queue = precedent\n", " self.queue.suivant = self.tete\n", " else: # cas général\n", " precedent.suivant = courant.suivant\n", " \n", " def ajoutfin(self, donnee): \n", " if self.tete.donnee is None: # on remplit d'abord la tête \n", " self.tete.donnee = donnee \n", " else: # sinon on crée un nouveau noeud\n", " nouveauNoeud = Noeud(donnee)\n", " self.queue.suivant = nouveauNoeud # On ajoute le noeud à la fin\n", " self.queue = nouveauNoeud # il devient la nouvelle queue\n", " self.queue.suivant = self.tete # et pointe sur la tête\n", " \n", " def __repr__(self):\n", " if self.tete.donnee is None :\n", " return 'Liste vide'\n", " else:\n", " chaine = str(self.tete.donnee) + \"->\"\n", " courant = self.tete\n", " while courant.suivant != self.tete and courant.suivant.donnee is not None : \n", " courant = courant.suivant \n", " chaine = chaine + str(courant.donnee) + \"->\"\n", " chaine = chaine + \"tête\"\n", " return chaine\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Jeu de tests\n", "Comme pour la liste chaînée, créer un jeu de tests pour les méthodes de la liste chaînée circulaire. \n", "Attention ici pas d'indices. Faire notamment un test pour supprimer la tête d'une liste, et pour supprimer le 2ème ou 3ème élément d'une liste.\n", "\n", "\n", "### Le retour de Flavius\n", "Résoudre le problème de Flavius Josèphe avec une liste chaînée circulaire. \n", "_Remarque_ : on utilisera la spécificité des listes circulaires, un petit schéma pour s'en sortir sur les courants/précédents est bien utile" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def josephe(n, k, s):\n", " \"\"\"\n", " Résoud le problème de Josèphe. Les soldats sont numérotés de 1 à n\n", " @param n : entier >= 1, nombre initial de soldats\n", " @param k : entier >= 2, saut entre deux meurtres de soldats\n", " @param s: entier >=0, nombre de soldats survivants\n", " @return survivor : liste d'entiers, numéros des sopldats survivants\n", " \"\"\"\n", " survivor = ListeCirc()\n", "\n", " return survivor\n", "\n", "\n", "print(\"un soldat sur deux\")\n", "for i in range(1,42):\n", " print(\"Survivant pour \", i, \"soldats :\",josephe(i,2,1).tete.donnee)\n", "print()\n", "\n", "tset = josephe(41,3,2)\n", "print(\"2 survivants pour 41 soldats, avec 1 sur 3 :\", tset.tete.donnee, tset.queue.donnee)\n", "tset = josephe(1234,7,10)\n", "print(\"10 survivants pour 1234 soldats, avec 1 sur 7 :\", tset)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### S'il vous reste du temps\n", "1. Construire un jeu de tests aussi complet que possible pour la classe `ListeCirc`.\n", "2. Coder la méthode `longueur` pour la classe `ListeCirc`.\n", "3. Coder des méthodes `lire(liste , k)`, `supprimer(liste , k)` et `inserer(liste , k)` pour la classe `ListeCirc`.\n", "4. Le fin du fin serait d'avoir la même interface pour les deux classes `listeCir` et `listeChainee` (mêmes méthodes avec les mêmes spécifications), afin de pouvoir les utiliser indifféremment. L'optique de ce TP était de montrer deux types d'implémentation différents. Mais si vous en avez le courage, vous pouvez écrire la classe `listeChainee`, y mettre toutes les méthodes auparavant dans `CelluleL`, et compléter les deux classes afin que leur interface soit identique.\n", " \n", " \n", "