Piles, files

Vous n'utiliserez que les méthodes de la classe Pile pour répondre aux questions des exercices.

Notation objet	Description
Pile() -> Pile	Créer une pile vide
p.est_vide() -> bool	Détermine si la pile p est vide.
p.empiler(c:int) -> None	Ajoute l'entier c au sommet de la pile p
p.depiler() -> int	Renvoie l'entier au sommet de la pile p, lorsque cela est possible.
print(p) -> None	Affiche la pile p sans la modifier.

Pile : une structure mutable

1. Quelle affichage produit le code :

   p = Pile()
   p.empiler(1)
   p.empiler(2)
   p.empiler(3)
   p.empiler(4)
   print(p)    
   

2. On définit la fonction i ci-dessous.

   def i(p):
       """ Pile -> Pile """
       p_aux = Pile()
       while not p.est_vide():
           e = p.depiler()
           p_aux.empiler(e)
       p = p_aux
       return p
   

   Quel affichage produit le code :

   res = i(p)
   print(res)
   print(p)
   

   [Sommet] 1 2 3 4
   [Sommet]
   

Moyenne

1. Écrire une fonction moyenne qui prend en argument une pile p composée d'entiers et qui renvoie la moyenne des éléments qui la composent. On ne se souciera pas de restaurer l'état de la pile.

   On rappelle que si p est la pile constituée des éléments 7, 8, 12, alors la moyenne des éléments de p est donnée par la formule :

   $\dfrac{7 + 8 + 12}{3} $

   def moyenne(p):
       """ Pile -> int """
       s = 0
       n = 0
       while not p.est_vide():
           s += p.depiler()
           n += 1
       return s/n
   
   p = Pile()
   p.empiler(7)
   p.empiler(8)
   p.empiler(12)
   

      print(p)
      print(moyenne(p))
   

   [Sommet] 12 8 7
   9.0
   

2. Écrire une fonction moyenne_ponderee qui prend en argument une pile p composée de couples d'entiers (note, coefficient) et qui renvoie la moyenne pondérée associée. On ne se souciera pas de restaurer l'état de la pile.

   Par exemple, si la pile p est constituée des éléments (14, 1), (11, 3) et (18, 4), cela veut dire que la moyenne sera composée d'une note de 14 (coefficient 1), une note de 11 (coefficient 3) et d'une note de 18 (coefficient 4).

   La moyenne sera obtenue a l'aide de la formule :

   $\dfrac{14\times1 + 11\times 3 + 18\times 2}{1 + 3 + 2} $

      def moyenne_ponderee(p):
          """ Pile -> int """
          s = 0
          n = 0
          while not p.est_vide():
              note, coeff = p.depiler()
              s += note*coeff
              n += coeff
          return s/n
   
      p = Pile()
      p.empiler((14,1))
      p.empiler((11,3))
      p.empiler((18,4))
   

   print(p)
   print(moyenne_ponderee(p))
   

   [Sommet] (18, 4) (11, 3) (14, 1)
   14.875
   

Pile triée ?

1. Écrire une fonction sommet qui étant donné une pile d'entiers p supposée non vide renvoie la valeur présente au sommet de p sans modifier p.

   def sommet(p):
       a = p.depiler()
       p.empiler(a)
       return a       
   
   p = Pile()
   p.empiler(4)
   p.empiler(3)
   p.empiler(2)
   p.empiler(1)
   

   print(p)
   print(sommet(p))
   print(p) 
   

   [Sommet] 1 2 3 4
   1
   [Sommet] 1 2 3 4
   

2. Écrire une fonction est_triee qui étant donnée une pile p supposée non vide, détermine si les éléments qui la composent sont rangés par ordre croissant (le plus petit élément se trouve au sommet de la pile).

   La pile p devra être dans le même état qu'initialement après exécution de l'instruction est_triee(p).

   Indications. On initialisera une pile auxiliaire vide qui servira à restaurer l'état de la pile p. On dépilera un premier élément de p, que l'on stockera dans une variable a. Puis, tant que la pile p n'est pas vide et que a est inférieur au sommet de p, on dépile p en mettant à jour a et la pile auxiliaire.

   Si à l'issue de ces dépilements la pile est vide c'est qu'elle était initialement triée. Sinon, c'est qu'elle n'était pas triée. Puis, on restaure l'état initial à l'aide de la pile auxiliaire.

   def est_triee(p):
       """ Pile -> bool """
       p_aux = Pile()
       a = p.depiler()
       p_aux.empiler(a)
       while not p.est_vide() and a <= sommet(p):
           a = p.depiler()
           p_aux.empiler(a)
       res = True if p.est_vide() else False
       while not p_aux.est_vide():
           p.empiler(p_aux.depiler())
       return res
   
   p = Pile()
   p.empiler(4)
   p.empiler(3)
   p.empiler(3)
   p.empiler(2)
   p.empiler(1)
   

   print(p)       
   print(est_triee(p))
   print(p)
   

   [Sommet] 1 2 3 3 4
   True
   [Sommet] 1 2 3 3 4