Écrire une fonction Python triant une pile de crêpes suivant l'algorithme proposé dans la page précédente.
La pile de crêpes sera représentée par une liste Python, le sommet de la pile correspondant au début de la liste.
- un code possible
- version récursive
"""
On représente la pile de crêpes par une liste.
Le début de la liste est considéré comme
le sommet de la pile de crêpes.
Ainsi [ L[0], L[1], L[2] ] constitue les 3 crêpes du sommet
de la pile de crêpes représentée par la liste L.
"""
from random import randint
def retourner_haut_de_pile_crepes(pile_crepe, spatule):
"""
spatule = 4 signifiera qu'on retourne les 4 crêpes du haut.
"""
for i in range(0,spatule//2):
pile_crepe[i], pile_crepe[spatule-i-1] = pile_crepe[spatule-i-1], pile_crepe[i]
def plus_grande(pile_crepe, n):
"""
Renvoie l'indice de la plus grande crêpe
parmi les n du sommet.
"""
indice_maxi = 0
maxi = pile_crepe[0]
for i in range(n):
if pile_crepe[i] > maxi :
maxi = pile_crepe[i]
indice_maxi = i
return indice_maxi
def placer_plus_grande(pile_crepe, n):
"""
Repère la plus grande crêpe parmi les n du sommet.
Retourne la pile de crêpes en plaçant la spatule sous cette plus grande crêpe.
Puis retourne les n crêpes du sommet.
"""
pg = plus_grande(pile_crepe, n)
retourner_haut_de_pile_crepes(pile_crepe, pg+1)
retourner_haut_de_pile_crepes(pile_crepe, n)
def tri_crepes(pile_crepe):
nb_crepes = len(pile_crepe)
for k in range( nb_crepes, 1, -1) :
placer_plus_grande(pile_crepe, k)
L = [ randint(1,100) for _ in range(randint(5,15))]
print(L)
tri_crepes(L)
print(L)
"""
On représente la pile de crêpes par une liste.
Le début de la liste est considéré comme
le sommet de la pile de crêpes.
Ainsi [ L[0], L[1], L[2] ] constitue les 3 crêpes du sommet
de la pile de crêpes représentée par la liste L.
"""
from random import randint
def retourner_haut_de_pile_crepes(pile_crepe, spatule):
"""
spatule = 4 signifiera qu'on retourne les 4 crêpes du haut.
"""
for i in range(0,spatule//2):
pile_crepe[i], pile_crepe[spatule-i-1] = pile_crepe[spatule-i-1], pile_crepe[i]
def plus_grande(pile_crepe, n):
"""
Renvoie l'indice de la plus grande crêpe
parmi les n du sommet.
"""
indice_maxi = 0
maxi = pile_crepe[0]
for i in range(n):
if pile_crepe[i] > maxi :
maxi = pile_crepe[i]
indice_maxi = i
return indice_maxi
def placer_plus_grande(pile_crepe, n):
"""
Repère la plus grande crêpe parmi les n du sommet.
Retourne la pile de crêpes en plaçant la spatule sous cette plus grande crêpe.
Puis retourne les n crêpes du sommet.
"""
pg = plus_grande(pile_crepe, n)
retourner_haut_de_pile_crepes(pile_crepe, pg+1)
retourner_haut_de_pile_crepes(pile_crepe, n)
def tri_crepes_recursif(pile_crepe) :
""" version récursive """
nb_crepes = len(pile_crepe)
def tri(n) :
if n > 1 :
placer_plus_grande(pile_crepe, n)
tri( n-1 )
tri(nb_crepes)
L = [ randint(1,100) for _ in range(randint(5,15))]
print(L)
tri_crepes_recursif(L)
print(L)