#!/usr/bin/env python # coding: utf-8 # # Devoir surveillé n°2 – Partie pratique A # # # ## Consignes # # Vous devez enregister ce fichier sous le nom `ds2A-nom-prenom.ipynb` # # De plus vous devez créer un fichier `ds2-nom-prenom.py` qui contient le code de toutes les fonctions définies ici y compris le code d'implémentation pour les piles que vous aurez utilisé afin de pouvoir l'importer pour la suite du développement de ce projet. # # À la fin de la séance, transmettez vos fichiers par mail à l'adresse `eric.madec@ecmorlaix.fr` # # Respectez bien le nom des fonctions pour faciliter la relecture du code. # # Vous pouvez rajouter des commentaires lorsque vous pensez que c’est nécessaire. # # De même, essayez de choisir des variables dont le nom est compréhensible, si c’est pertinent. # # # # Les tours de Hanoï # # Les tours seront modélisées par une liste de 3 piles. # # Pour les piles, vous avez le choix entre deux implémentations données : # - Dans la première, une pile est une liste Python. # - Dans la deuxième, on définit une classe Pile qui utilise également une liste Python. # # Vous devez manipuler une pile uniquement avec les fonctions ou méthodes fournies. # In[ ]: # Première implémentation pour les piles def creer_pile(): '''Renvoie une pile vide''' return [] def est_vide(pile): '''Renvoie un booléen, True si la pile est vide et False sinon''' return p == [] def empiler(pile, element): '''Empile element au sommet de pile''' pile.append(element) def depiler(pile): '''Renvoie et enlève la valeur du sommet de pile''' assert not est_vide(pile), "Pile vide" return pile.pop() # In[ ]: # Deuxième implémentation pour les piles class Pile: '''classe Pile création d’une instance Pile avec une liste''' def __init__(self): '''Initialise une pile vide''' self.liste = [] def est_vide(self): '''Renvoie un booléen, True si la pile est vide et False sinon''' return len(self.liste) == 0 def empiler(self, element): '''Empile element au sommet de pile''' self.liste.append(element) def depiler(self): '''Renvoie et enlève la valeur du sommet de pile''' return self.liste.pop() def __repr__(self): return repr(self.liste) # Pour faciliter l’analyse des programmes, on se permettra d’utiliser l’affichage des listes modélisant les piles afin de voir leur contenu. # # Les listes et les piles étant des objets mutables, lorsque vous les modifiez dans une fonction, les modifications perdurent après son exécution. # # ## Exercice 1 : # # Écrire une fonction `sommet(pile)` qui renvoie la valeur au sommet de la pile mais sans la supprimer de la pile au final. # # Vous pouvez dépiler, mais il faut bien rempiler la valeur avant la fin de l’exécution de la fonction. # # Si la pile est vide, il faut lever une exception avec raise IndexError('pile vide'). # In[ ]: def sommet(pile): ''' Renvoie la valeur au sommet de la pile mais sans la supprimer de la pile ''' # Tester votre fonction `sommet(pile)` ci-dessous de sorte que : # # ```python # # Première implémentation pour les piles # >>> p = creer_pile() # >>> sommet(p) # IndexError: pile vide # >>> empiler(p, 4) # >>> empiler(p, 2) # >>> sommet(p) # 2 # ``` # ```python # # Deuxième implémentation pour les piles # >>> p = Pile() # >>> sommet(p) # IndexError: pile vide # >>> p.empiler(4) # >>> p.empiler(2) # >>> sommet(p) # 2 # ``` # In[ ]: # In[ ]: # In[ ]: # # ## Exercice 2 : # # > Les piles de disques seront modélisées par des piles d’entiers. # # Écrire une fonction `mettre_disques(pile, n)` qui met des disques de taille n à 1 sur la pile. # # > Pour rappel, `range(a, b, -1)` avec a > b renvoie tous les entiers de a à b+1 inclus, dans l’ordre décroissant. # > Exemple : # > ```python # >>> list(range(5,1,-1)) # la commande list n'est que pour l'affichage # [5, 4, 3, 2] # ``` # In[ ]: def mettre_disques(pile, n): '''met des disques de taille n à 1 sur la pile''' # Tester votre fonction `mettre_disques(pile, n)` ci-dessous de sorte que : # # ```python # # Première implémentation pour les piles # >>> p = creer_pile() # >>> mettre_disques(p, 5) # >>> print(p) # [5, 4, 3, 2, 1] # ``` # ```python # # Deuxième implémentation pour les piles # >>> p = Pile() # >>> mettre_disques(p, 5) # >>> print(p) # [5, 4, 3, 2, 1] # ``` # In[ ]: # In[ ]: # In[ ]: # ## Exercice 3 : # # ds2_hanoi-01.png # # > Les tours sont formées par 3 piles et seront représentées par une liste de 3 piles. # > # > Ainsi, des tours dont l’affichage serait celui donné ci-dessous correspondrait à la situation ci-contre. # # Exemple : # # ```python # >>> print(tours) # [[5, 4], [2, 1], [3]] # ``` # # Écrire une fonction `creation_tours(n)` qui renvoie une liste de 3 piles, dont la première correspond à la pile des n disques, les autres étant vides. # # In[ ]: def creation_tours(n): ''' renvoie une liste de 3 piles, la première correspond à la pile des n disques, les autres étant vides.''' # Tester votre fonction `creation_tours(n)` ci-dessous de sorte que : # # ```python # >>> tours = creation_tours(5) # >>> print(tours) # [[5, 4, 3, 2, 1], [], []] # ``` # In[ ]: # In[ ]: # ## Consignes, rappels pour la suite : # # Vous devez enregister ce fichier sous le nom `ds2A-nom-prenom.ipynb` # # De plus vous devez créer un fichier `ds2-nom-prenom.py` qui contient le code de toutes les fonctions définies ici y compris le code d'implémentation pour les piles que vous avez utilisé afin de pouvoir l'importer pour la suite du développement de ce projet. # # À la fin de la séance, transmettez vos fichiers par mail à l'adresse `eric.madec@ecmorlaix.fr` # # Respectez bien le nom des fonctions pour faciliter la relecture du code. # # Vous pouvez rajouter des commentaires lorsque vous pensez que c’est nécessaire. # # De même, essayez de choisir des variables dont le nom est compréhensible, si c’est pertinent.