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.
# 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()
# 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').
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 :
# Première implémentation pour les piles
>>> p = creer_pile()
>>> sommet(p)
IndexError: pile vide
>>> empiler(p, 4)
>>> empiler(p, 2)
>>> sommet(p)
2
# Deuxième implémentation pour les piles
>>> p = Pile()
>>> sommet(p)
IndexError: pile vide
>>> p.empiler(4)
>>> p.empiler(2)
>>> sommet(p)
2
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 :>> list(range(5,1,-1)) # la commande list n'est que pour l'affichage
[5, 4, 3, 2]
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 :
# Première implémentation pour les piles
>>> p = creer_pile()
>>> mettre_disques(p, 5)
>>> print(p)
[5, 4, 3, 2, 1]
# Deuxième implémentation pour les piles
>>> p = Pile()
>>> mettre_disques(p, 5)
>>> print(p)
[5, 4, 3, 2, 1]
Exercice 3 :¶
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 :
>>> 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.
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 :
>>> tours = creation_tours(5)
>>> print(tours)
[[5, 4, 3, 2, 1], [], []]
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.