TP - Tri de crêpes☘

Téléchargez le fichier « à trous » TPG02.21.py (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans ce dossier.

Consignes communes à chaque partie

Le programme principal contient un appel au module doctest :

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.

Exposé du problème☘

Il s 'agit de trier une pile de crêpes afin qu'elles soient empilées de la plus large (en bas) à la plus étroite (au-dessus). Pour cela, la seule opération autorisée est de retourner la partie supérieure de la pile à l'aide d'une spatule, spatule que l’on peut placer sous l’une des crêpes.

Algorithme☘

On place la spatule sous la plus grande crêpe :
On retourne la partie supérieure :
On place la spatule sous la pile de crêpes :
On retourne la partie supérieure : la plus grande crêpe est dessous.
On considère la pile de crêpes restantes (c’est-à-dire toutes sauf celle qu’on vient de placer correctement). On place la spatule sous la plus grande crêpe de la pile restante.
On retourne la partie supérieure :
On place la spatule sous la pile de crêpes (hormis celles déjà triées) :
On retourne la partie supérieure : la plus grande crêpe est placée.
On recommence jusqu’à trier l’intégralité de la pile...

Partie 1 : Maximum jusqu'à☘

Complétez le corps de la fonction indice_du_maxi_jusqu_a() qui prend en paramètre un tableau tab et un indice i d'un élément de ce tableau.

Cette fonction renvoie l'indice de l'élément de plus grande valeur parmi les éléments tab[0], tab[1], ..., jusqu'à tab[i] inclus.

def indice_du_maxi_jusqu_a(tab, i):
    """
    tab – list, tableau de n éléments munis d'une relation d'ordre
    i – int, entier compris entre 0 et n-1
    Sortie: int – indice du maximum dans le sous-tableau tab[0..i]
    >>> A = [215, 681, 818, 609, 398, 635, 765, 882, 756, 418]
    >>> indice_du_maxi_jusqu_a(A, 2)
    2
    >>> indice_du_maxi_jusqu_a(A, 9)
    7
    """

Partie 2 : Renverser jusqu'à☘

L’algorithme de tri crêpe doit renverser l'ordre des valeurs contenues dans un tableau entre les indices 0 et i (inclus). Avant de pouvoir le programmer, il faut identifier comment renverser un tableau jusqu'à un indice donné.

On considère le tableau tab ci-dessous :

tab = 5 7 1 4 9 8 3 4 0 6
Déterminez sur votre cahier le contenu de tab après avoir renversé la « plage » tab[0..7].
Pour préciser comment programmer cet algorithme de renversement partiel, on approfondit l’exemple précédent. Pour cela, on repart du tableau :

tab = 5 7 1 4 9 8 3 4 0 6
On veut renverser la « plage » tab[0..7]. À chaque question, recopiez le tableau sur votre cahier et effectuez les opérations demandées.
1. Hachurez les éléments de tab qui ne doivent pas être pris en compte.
2. Échangez le premier et le dernier élément de la « plage » à renverser.
3. On passe à l’élément suivant, puis on échange.
4. On poursuit, puis on échange.
5. On poursuit, puis on termine.
On généralise l'exemple de la question précédente avec un indice i quelconque.
Pour renverser tab[0..i], il faut que :
1. l'élément d'indice 0 soit échangé avec l'élément d'indice ......
2. l'élément d'indice 1 soit échangé avec l'élément d'indice ......
3. etc...
4. l'élément d'indice k (avec 0 $\leqslant$ k $\leqslant$ i) soit échangé avec l'élément d'indice ......
Complétez le corps de la fonction renverser_jusqu_a() qui prend en paramètre un tableau tab et un indice i d'un élément de ce tableau.

Cette fonction à effet de bord renverse l'ordre des valeurs contenues dans le tableau tab entre les indices 0 et i (inclus) selon l’algorithme détaillé dans les questions précédentes.

def renverser_jusqu_a(tab, i):
    """
    tab – list, tableau de n éléments
    i – int, entier compris entre 0 et n-1
    Sortie: None – l'ordre des éléments de tab[0] jusqu'à tab[i] a été renversé
            (fonction à effet de bord)
    >>> A = [215, 681, 818, 609, 398, 635, 765, 882, 756, 418]
    >>> renverser_jusqu_a(A, 3)
    >>> A
    [609, 818, 681, 215, 398, 635, 765, 882, 756, 418]
    >>> renverser_jusqu_a(A, 6)
    >>> A
    [765, 635, 398, 215, 681, 818, 609, 882, 756, 418]
    """

Partie 3 : Tri crêpes☘

Complétez le corps de la fonction tri_crepes() qui prend en paramètre un tableau tab et qui implémente l'algorithme de « tri crêpes » résumé ci-dessous :

tab est un tableau ayant n éléments
Pour i allant de n-1 à 1
    j ← indice du maximum de tab[0..i]
    renverser tab[0..j]
    renverser tab[0..i]

Dans le « main », réalisez un plan de test des fonctions programmées dans ce TP avec le tableau tab donné en Partie 2, puis avec un tableau d’entiers générés aléatoirement et défini par compréhension.